请教一个修改表的设计来提高查询效率的问题

数据库:Sql 2000   表:client    记录:2283761条.
ID      bigint    primary key identity,
Name varchar(20)    not null,
CorporationNO varchar(20)    not null,
phone varchar(50),
address varchar(100)
我在网页上用这样的查询语句:
select top 15 ID,Name,Phone,Address from client
where CorporationNO='301759' and ID not in(select top 0 ID from client
where CorporationNO='301759' order by ID desc)order by ID desc
然后我把它放到查询分析器上试了下挺块的，只有0:00:00秒
但是在网页上有些时候需要知道符合这个条件共有多少条记录，用上面那条语句是没办法实现的
于是我又加了条SQL语句:
select count(ID) from client where CorporationNO='301759'
这句是查出了符合条件的记录数，就是这条语句让我的页面打开很慢，我把它
放到查询分析器上试了下。用时0:00:12,花了12秒钟.
所以我想请教下大家，像我这样的表有没有办法优化下表的设计，来提高下查询效率呢？
因为12秒在网页上相对来说等待的时间是长了点。在这里请教下大家我该怎样来做。
同时我也顺便说下我还牵涉到的一个问题，我在网页上有个查询功能。是按Phone 和 Name
这两个字段来查询的，如果说要建索引的话，要怎样建比较合适。
但愿你们能够明白我所表达的意思，也希望我的问题能得到大家的帮助。谢谢

select count(ID) from client where CorporationNO='301759' 

CorporationNO这个字段上是不是没有索引，如果没有索引，那么数据库会进行表扫描，你表里这么多数据当然会慢，提高速度的方法是在这个字段上加上Index，当然在加Index之前你要看看这个字段是不是会频繁的在where条件中出现，如果你要经常使用CorporationNO这个字段来过滤记录，那么在这个字段上加上Index会得到速度的提高

是的，CorporationNO这个字段是经常出现的
那么我是不是这样写啊:
CREATE INDEX client_CorporationNO ON client(CorporationNO)
如果我要按电话和客户全称来实现查询，那是不是又要建索引了呢
另外我还有一个问题,我的数据库中有8个表，几乎每个表中都有CorporationNO 这个字段
那么是不是要为每张表的CorporationNO字段都创建一个索引呢

创建索引在绝大多数情况下会提高查询效率

create [unique] [clustered | nonclustered]
index index_name
on [[database.]owner.]table_name (column_name
[, column_name]...)

楼主是在分页算法中遇到的问题吧，要返回记录数。
这么大数量级的算法中，先看看是不是非得这么做，要是确定肯定要这么做，那真的想说需求控制不好。
呵呵 以上题外话了。

分析慢的原因，数据多，而且采用了字符串的格式，字符串的查询在数据库中真的没话说，一个字：慢。

楼上说要见索引，也不见你来回复个消息到底建索引行不行。我觉得可能效果不是很明显，当然了我没有进行实际数据测试。

我的建议是既然是分页算法，那么是不是不用这种Count(ID)的方法来或许记录数呢？自带的ROWCOUNT_BIG()不好用吗？楼主可以尝试一下。

我根据
"Ivan Li" 的方法去试了下，在执行count(id) 时确实快了点，但是在记录的最后几条和最前几条查询时就会慢一点，
但是"bumood" 所说的不用count(id) 来实现，
用ROWCOUNT_BIG()这个函数放在我的那种sqlg语句中怎么个实现呢？
我想请你把这个查询语法告诉我一下