倒序目录在业务系统中分页查询时候的应用

倒序索引在业务系统中分页查询时候的应用
本帖最后由 x_wy46 于 2013-08-22 17:34:10 编辑

--本文所说的情况只是符合特定的应用场景，所假设的条件也都不绝对
--仅仅是有感而发，根据自己的感受体会写出来的，可能有不对的地方，欢迎指正
 
 
--倒序索引在业务系统中分页的应用
 
 
 
--系统中的查询中，经常会遇到分页查询
--因为是业务系统，所以基本上是按照时间的倒序来排序的，
--注意，这里说的情况不绝对，相当一部分数据，多数情况下是按照时间倒序来排序的
--其实这种情况也可以理解，
--比如业务系统，
--今天是不是来了新的需要报关的单子.......
--今天是不是有哪些新的加班单需要批准.......
--今天还有哪些送货信息还没有确认.......
--随着“老”数据被一步一步地处理
--系统用户总是关注最新的数据，我翻了一下代码，绝大多数业务数据查询分页是是按照时间的倒序排的
--但是多数情况下是按照CreateDate来order by的，
--但是在创建时间字段上建立聚集索引的时候默认是ASC
--按照B树索引的结构，我们每次查询的最新的数据，
--默认的正序索引的，最新的数据存储在B树的最右边
--每次要遍历整个B树才能查询到这部分最新的数据
 
 
--所以就想到了，何不来个倒序索引，这样最新的数据永远存储在B树的最左边，
--查询时，可能是一开始遍历B树就找到了这部分数据
--下面开始测试
 
 
 
--建立测试表，比较简单，有一个ID，模拟业务表中的主键，
--这里为了简单起见，就用整型的自增列吧
create table Test_ASCIndex
(
    id int identity(1,1),
    Cloumn1 varchar(100),
    Cloumn2 varchar(100),
    CreateDate datetime2
)
 
 
--创建测试数据，用GUID和时间来填充列，
--其中时间字段在当前时间的基础上，HH递加
--目的就是为了减少同一个时刻存在大量的数据的情况，
--模拟日常生产系统中的业务数据增长情况
--当然实际生产系统下也有统一时刻插入的情况，这个不绝对
--若有特殊情况，再根据具体情况处理
declare @i int
set @i=1
while @i<=100000
begin
    insert into Test_ASCIndex values (NEWID(),NEWID(),DateAdd(HH,@i,GETDATE()))
    set @i=@i+1
end
 
 
--将数据插入到另外一个测试表中
select * into Test_DESCIndex from Test_ASCIndex 
 
 
--在Test_ASCIndex建立正序索引
create clustered index ASCIndex on Test_ASCIndex(CreateDate)
--在Test_ASCIndex建立倒序索引
create clustered index DESCIndex on Test_DESCIndex(CreateDate desc)
 
 
set statistics io on
 
--比如这里我要查询按时间倒序排，第三页数据（其实随便第一页，第二页，第三页都一样）
 
--在正序索引的表中是这样的
SELECT TOP 10 *
  FROM Test_ASCIndex
 WHERE (createdate >
           (SELECT max(createdate)
               FROM (SELECT TOP 99970 createdate
                       FROM Test_ASCIndex
                      ORDER BY createdate ) AS T)) 
 
 ORDER BY createdate 
  
id          Cloumn1                                          Cloumn2                                                                                              CreateDate
----------- ---------------------------------------
99971       722137E4-DDB5-4F7D-8608-5219B52AE991             063948ED-BC6F-4018-B7CF-F5262A73CB53                                                                 2025-01-17 03:49:56.47
99972       D75A08D2-6C18-4918-8BD7-D3B59D8BB510             7C7B05FF-F4ED-48E7-A5BB-C6FF8A89056E                                                                 2025-01-17 04:49:56.47
99973       431F03A7-A8D5-4A4B-BECD-766F3394E366             4A4C7D34-C239-471F-AC62-9E13242445D5                                                                 2025-01-17 05:49:56.47
99974       36C9E59D-236F-480B-88D8-FCC8E996B039             03932B2E-ED79-4D68-91D0-9C58911B05DD                                                                 2025-01-17 06:49:56.47 
 
99975       B79884FC-D036-4CE1-90F6-D18996F4630B             5995A891-24C5-4B32-BB37-7FC8CA0EC0A2                                                                 2025-01-17 07:49:56.47
99976       45F6632E-E4AB-4A93-9506-1FC8543ED102             1CB6A3D0-0D96-4DD5-AD43-16AD8863F103                                                                 2025-01-17 08:49:56.47
99977       E8B65483-B2F1-4691-A256-96B3830AC98C             5E81E193-9D33-4CAB-B14A-C0C3446517D8                                                                 2025-01-17 09:49:56.47
99978       7809874A-B984-4E98-B944-BDF16B06DD68             FB3B16F3-0714-43F2-8733-651F8A408C29                                                                 2025-01-17 10:49:56.47
99979       67712C88-3B12-403E-9697-C424BD469FE1             1945A672-882B-47EA-ACA7-04B33354D7FF                                                                 2025-01-17 11:49:56.47 
 
99980       7FF7A083-F1CF-4EF4-AFF0-B309D7AB1151             4DD14603-0A79-4326-BDF7-0C3F709A0B51                                                                 2025-01-17 12:49:56.47
 
--(10 行受影响)
 
--表 'Test_ASCIndex'。扫描计数 2，逻辑读取 1261 次，物理读取 0 次，预读 0 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。
 
 
 
 
 
 --在倒序索引的表中是这样的
 SELECT TOP 10 *
  FROM Test_DESCIndex
 WHERE (createdate <
       (SELECT min(createdate)
           FROM (SELECT TOP 20 createdate
                   FROM Test_DESCIndex
                  ORDER BY createdate desc) AS T))
 ORDER BY createdate desc
  
 id          Cloumn1                                     Cloumn2                                                                                              CreateDate
----------- ---------------------------------------- ---------------------------------------------------------------- ----------------------
99980       7FF7A083-F1CF-4EF4-AFF0-B309D7AB1151       4DD14603-0A79-4326-BDF7-0C3F709A0B51                                                                 2025-01-17 12:49:56.47 
 
99979       67712C88-3B12-403E-9697-C424BD469FE1       1945A672-882B-47EA-ACA7-04B33354D7FF                                                                 2025-01-17 11:49:56.47
99978       7809874A-B984-4E98-B944-BDF16B06DD68       FB3B16F3-0714-43F2-8733-651F8A408C29                                                                 2025-01-17 10:49:56.47
99977       E8B65483-B2F1-4691-A256-96B3830AC98C       5E81E193-9D33-4CAB-B14A-C0C3446517D8                                                                 2025-01-17 09:49:56.47
99976       45F6632E-E4AB-4A93-9506-1FC8543ED102       1CB6A3D0-0D96-4DD5-AD43-16AD8863F103                                                                 2025-01-17 08:49:56.47
99975       B79884FC-D036-4CE1-90F6-D18996F4630B       5995A891-24C5-4B32-BB37-7FC8CA0EC0A2                                                                 2025-01-17 07:49:56.47
99974       36C9E59D-236F-480B-88D8-FCC8E996B039       03932B2E-ED79-4D68-91D0-9C58911B05DD                                                                 2025-01-17 06:49:56.47 
 
99973       431F03A7-A8D5-4A4B-BECD-766F3394E366       4A4C7D34-C239-471F-AC62-9E13242445D5                                                                 2025-01-17 05:49:56.47
99972       D75A08D2-6C18-4918-8BD7-D3B59D8BB510       7C7B05FF-F4ED-48E7-A5BB-C6FF8A89056E                                                                 2025-01-17 04:49:56.47
99971       722137E4-DDB5-4F7D-8608-5219B52AE991       063948ED-BC6F-4018-B7CF-F5262A73CB53                                                                 2025-01-17 03:49:56.47
 
--(10 行受影响)
 
--表 'Test_DESCIndex'。扫描计数 2，逻辑读取 6 次，物理读取 0 次，预读 0 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。
 
 
 
--这里是完全相同的表结构，完全相同的数据，查询数据也完全一致，
--就是因为索引的排序不同，造成了很明显的IO差异
--其实这里继续增大测试数据的量的话，这个差别将更加明显
 
 
 
 
 
 
 
 
 
--有兴趣的话可以继续做做测试

倒序索引 分页
[解决办法]

--说2点问题:
--#1.下面这句话,中的最后一句是不对的。
--默认的正序索引的，最新的数据存储在B树的最右边
--每次要遍历整个B树才能查询到这部分最新的数据

--原因：索引是一颗平衡树,虽然说正序排序的话,最新的数据(叶子节点)会存储在B树的右边,但由于索引的SEEK是类似于2分查找法的层级查找。 
 
--所以不管是正序还是倒序创建索引,查询某一段数据所用的资源几乎是相同的。请看下面的例子（查询结果一样,但一个用正序索引,一个用倒序,且IO都是5个逻辑读）

--正序
SELECT * FROM
(SELECT rowid = ROW_NUMBER() OVER(ORDER BY createdate DESC), * FROM Test_ASCIndex) t
WHERE rowid BETWEEN 1 AND 10
/*
(10 行受影响)
表 'Test_ASCIndex'。扫描计数 1，逻辑读取 5 次，物理读取 0 次，预读 0 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。
*/

--倒序
SELECT * FROM
(SELECT rowid = ROW_NUMBER() OVER(ORDER BY createdate DESC), * FROM Test_DESCIndex) t
WHERE rowid BETWEEN 1 AND 10
/*
(10 行受影响)
表 'Test_DESCIndex'。扫描计数 1，逻辑读取 5 次，物理读取 0 次，预读 7 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。
*/

--#2.楼主做的例子非常好，数据也完全正确。但它的原理是基于：SQL语句的写法+索引产生的。分析如下：
--正序(一共扫描了10+99970行记录)
SELECT TOP 10 *--这儿再从表中扫描10条记录(效率同倒序中的那行相同)
  FROM Test_ASCIndex
 WHERE (createdate >
           (SELECT max(createdate)
               FROM (SELECT TOP 99970 createdate--T-SQL中TOP的语法,会强制返回一个结果集后再进行下一步运算.也就是说TOP 99970这个子查询,不得不扫描99970行记录,优化器无法优化.
                       FROM Test_ASCIndex--这个SQL的效率几乎全部消耗在了这儿
                      ORDER BY createdate ) AS T))
 ORDER BY createdate 

 --倒序(一共扫描了10+20行记录)
 SELECT TOP 10 *--这儿再从表中扫描10条记录(效率同正序中的那行相同)
 FROM Test_DESCIndex
 WHERE (createdate <
       (SELECT min(createdate)
           FROM (SELECT TOP 20 createdate--同上分析,这儿只是扫了20行, 不管这20行在数据表的哪个位置,都很快(因为有索引且数据少)
                   FROM Test_DESCIndex
                  ORDER BY createdate desc) AS T))
 ORDER BY createdate desc

[解决办法]
以前我问过大神，建立索引ASC/DESC的区别和影响

1、索引是双链结构，搜索效率上不存在ASC/和DESC的差别。

2、如果采用DESC，物理层面会引起磁头的来回移动；所以采用ASC比较好。

（尤其是在搜索结构大范围分散在整个记录集时）

B树机构下，假设每2条记录存在一个子节点中，搜索的读取过程：
ASC：1,2——3,4——5,6——7,8
DESC：2,1——4,3——6,5——8,7
[解决办法]

引用:

以前我问过大神，建立索引ASC/DESC的区别和影响

1、索引是双链结构，搜索效率上不存在ASC/和DESC的差别。

2、如果采用DESC，物理层面会引起磁头的来回移动；所以采用ASC比较好。
（尤其是在搜索结构大范围分散在整个记录集时）

B树机构下，假设每2条记录存在一个子节点中，搜索的读取过程：
ASC：1,2——3,4——5,6——7,8
DESC：2,1——4,3——6,5——8,7

大神应该不是我，不过有点眼熟，特意查了一下我的回复的帖子，有回答过你相关的问题。

也许我表达得不太清楚，所以你的理解可能有些偏差。

OLTP系统中，索引的排序应该和INSERT数据的顺序一致，反序的话很快就会有很多碎片：链表结构是逆序的，也就是下一页指向的页面号小于当前页面号，顺序扫描会引起磁头的反复移动，OK，这是初级层面的理解。

第二层面当时我没说，不过也应该想到，物理读取特别是预读的时候会进行优化，例如对即将要扫描的页面号排序，执行向前的物理读取，尽量将碎片的影响降到最低，所以，碎片的影响并没有想象中那么大。前段时间有个哥们发了个帖子，谈索引必然强调磁头/磁臂移动如何耗资源，我在想这哪跟哪，还没到关注物理硬件的时候呢。

逻辑读阶段是内存数据，链表结构，顺序再乱也不会有很大影响，ASC/DESC更是无关紧要，哪个方向的顺序读都一样，所以对索引数据ORDER BY ASC/DESC是不需要额外排序的。

PS：楼主你的测试是不公平的，拿ASC的最后1页和DESC的第1页比较，要比应该这样比：

SELECT TOP 10 *
FROM Test_ASCIndex
 WHERE (createdate <
       (SELECT min(createdate)
           FROM (SELECT TOP 20 createdate
                   FROM Test_ASCIndex
                  ORDER BY createdate desc) AS T))
 ORDER BY createdate desc

应该是和DESC索引差不多的。
[解决办法]
我也不信ASC索引就不能DESC查找了，测试一下吧：

set statistics io on
go
dbcc dropcleanbuffers
dbcc freeproccache
go
SELECT TOP 10 * FROM Test_ASCIndex WHERE (createdate < (SELECT min(createdate)FROM (SELECT TOP 20 createdate FROM Test_ASCIndex ORDER BY createdate desc) AS T)) ORDER BY createdate desc
go
SELECT TOP 10 * FROM Test_DESCIndex WHERE (createdate < (SELECT min(createdate) FROM (SELECT TOP 20 createdate FROM Test_DESCIndex ORDER BY createdate desc) AS T)) ORDER BY createdate desc
go

/*
表 'Test_ASCIndex'。扫描计数 2，逻辑读取 7 次，物理读取 1 次，预读 0 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。
表 'Test_DESCIndex'。扫描计数 2，逻辑读取 6 次，物理读取 1 次，预读 0 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。 
 
*/

结果基本符合预期，大不了Test_ASCIndex的逻辑读多1次，因为最后1页未满，最后30条数据跨页了。

两害相权取其轻，OLTP系统没必要建和INSERT顺序反序的聚集索引，碎片问题自己琢磨吧，还有每插入1行时偏移矩阵的维护等等，微软不是神仙，物理架构决定的。

查看更多 下一篇