IDC资讯中心
select返回记录的顺序
中兴通讯重庆研究所 游波 吴育红
关键词：select，顺序，优化，备份，扫描，索引
文章摘要：
当我们执行了select语句，select返回的记录的顺序对我们编程方式有较大影响，对数据库记录备份清除以及sql性能优化都有很大的关系。因此有必要明确select返回记录的顺序。本文按数据库分类讨论oracle/sybase/sql server返回记录的顺序，从原理探讨三种数据库各自的特点，并着重探讨了这些差异对数据查询及记录备份的影响。
缩略语：
iam：index allocation map
pfs：page free space
1.简介
当我们执行了select语句，select返回的记录的顺序对我们编程方式有较大影响，对数据库记录备份清除以及sql性能优化都有很大的关系。因此有必要明确select返回记录的顺序。
select返回记录的顺序与数据库类型有很大关系，因此以下按数据库类型分别讨论。本文主要讨论了oracle/sybase/sql server返回记录的顺序，从原理探讨三种数据库各自的特点，并着重探讨了这些差异对数据查询及记录备份的影响。
2. oracle
以下假设数据库查询优化方式均为基于rule的方式，oracle 采用两种访问表中记录的方式：
a. 全表扫描 (full table scan)
全表扫描就是顺序地访问表中每条记录. oracle采用一次读入多个数据块(database block)的方式优化全表扫描。
b. 通过rowid访问表
你可以采用基于rowid的访问方式情况，提高访问表的效率，rowid包含了表中记录的物理位置信息。oracle采用索引(index)实现了数据和存放数据的物理位置(rowid)之间的联系。通常索引提供了快速访问rowid的方法，因此那些基于索引列的查询就可以得到性能上的提高。通常表现为按索引扫描。(index scan)
2.1全表扫描
如果select语句不能使用索引，则oracle按全表扫描方式读取数据块，对于返回的结果集，oracle按rowid的大小顺序来返回记录。因此 select * from mytable 与 select * from mytable order by rowid效果是一样的
可以通过select rowid from table得到rowid伪列，数据类型为rowid类型。使用查询语句返回的是rowid的扩展格式（extended rowid）。扩展格式的rowid由18个字符组成。这18个字符可以按照oooooo.fff.bbbbbb.sss的格式分为4组。分别代表数据对象编号（data object number）,数据文件编号（datafile number），数据块编号（data block number）,记录或记录片断的块内行号。
必须说明的是，并不是后插入记录的rowid就越大，有可能后插入的记录rowid还要小。下面给出两个论点加以证明：
1．后插入的记录块内行号可能大，也可能小
根据我们的试验，假设现在表中有三条记录假设文件号相同，按块号，行号排列如下：
108 0
108 1
108 2
删除中间一条记录后，得到
108 0
108 2
再增加一条记录，可能会得到
108 0
108 1 <—新增加的记录
108 2
也可能是
108 0
108 2
108 3 <—新增加的记录
两种情况均有可能出现，取决于oracle块内的分配算法。关于该情况的更深入的分析可以参见文献2。
2．后插入的记录的块号有可能大，有可能小
插入记录的块号并不是线性增加的，而是受freelist控制。有关freelist的理论和算法可以参见文献1。
因此对于全表扫描可以得出以下结论：
1. 在oracle中 select * from mytable不能保证返回的记录顺序是按插入的先后顺序，而是按rowid顺序。
rowid的顺序与记录行存储的“物理序”一致。在没有索引情况下，select作全表扫描，是按“物理序”，此时select 返回记录按“物理序”最快。
2. 对于已经插入的记录其rowid不会发生变化。
如果全表扫描方式下，直接使用rownum作为选择条件，根据结论1，两次得到的记录可能是不一样的。如果sql有时间条件或其他条件作为sql语句辅助的筛选（排出当前插入的值），那么再用rownum作为选择条件，则返回的记录及记录的顺序均是一样的。
结论2的特性可用于某些日志表的清除-备份机制中。对于某些日志表为了提高insert性能，可能没有索引，并且在存储过程中对这些日志表进行清除和备份。利用insert into select 先将部分记录选入到备份表中，再用delete语句删除日志表中的记录。通过rownum来控制操作的行数，避免回滚段问题，通过时间条件来实施结论2，保证记录一致。
2.2按索引扫描
对于一段范围的按索引选择，在oracle内部表现为索引叶节点的扫描，索引叶节点通常已经排序并且叶节点之间存在指针，便于扫描。由于此时select按索引扫描表，因此返回的记录就按“索引序”排列。
利用上述特征，对于按索引扫描可以有以下的应用方式：
1．通过索引可以使返回记录事先排序。
在oracle中使用索引就可以使返回的记录得到排序，而无需再使用order by。对于不同的排序方式可以用不同的索引完成，通过hint/*+*/指示可以控制索引按不同的扫描方式工作，从而达到不同的效果。如/*+index(table index_name)*/或/*+index_desc(table index_name)*/指示按索引升序扫描或按索引降序扫描，从而实现返回的记录按字段的升序排列或按字段的降序排列。
例如对于表t(a int,b int)在a上有索引index_a，b上有索引b
则select * from t得到的记录
a
b
19
43
21
1
3
10
5
8
11
2
select /*+index(t index_a)*/* from t where a>0 或者
select * from t where a>0 order by a
a
b
3
10
5
8
11
2
19
43
21
1
从执行计划来看，按索引扫描和按索引rowid方式访问。
select /*+index_desc(t index_b)*/* from t where b>0 或者
select * from t where b>0 order by b
a
b
21
1
11
2
5
8
3
10
19
43
从执行计划来看，按索引扫描和按索引rowid方式访问。
2．通过以时间、流水号等字段为索引字段，可以使记录实现按插入的顺序返回
同样利用上述特性，来说明2.1中的备份问题。当日志表有索引时，选择限定扫描范围的索引字段，使之保证后插入的记录是在结果集后面的，如时间或流水号等，该顺序就保证了按rownum控制行数时insert和delete操作的记录是完全一致的，同时基于索引的扫描保证了sql的性能。
3.sybase
不管你的select 语句中是否在where后面使用了索引，sybase均可能基于代价对索引的使用进行调整。即使没有where语句也有可能使用索引，即使有where语句也有可能不用索引。当然，如果表本身就没有创建任何索引就肯定不会使用到索引。
3.1没有索引的表
没有索引的表在称为堆表。堆表在sysindexes表中有一条对应的记录，其indid=0。first字段表示堆表的首页，root表示堆表的尾页。堆表中所有的数据页形成从sysindex.first <-> sysindex.root的双向链表。
对于插入记录，插入到堆表中的所有数据会加到该表的尾部。sybase 利用sysindex表的indid（=0）和root值，找出该表的最后一个数据页。如果在该页上有空间，在数据的尾部插入新的记录行。如果最后一页上没有可获得的空间时，如果在该扩展单元的下一页有可获得的空间，这是用它；如果最后一页已经是扩展单元的最后一页，则开始使用一个新的扩展单元，对于新加入的页总是会链到链表的尾部，同时更新sysindex.root的值。
对于记录删除，当删除一条记录时，页内紧随被删除记录后的记录向该页前部移动，所有未使用的空间相邻地保留在页的底部。当一页中所有行均被删除，这一页就会脱离该堆表的数据链。
对于更新，堆表按下面的原则：
· 如果行的长度没有变化,就在原来的行上直接更新，并且没有页内数据的移动。
· 如果行的长度变化，并且页的空闲空间足够。行还是在页上的相同位置，但是其它行将上移或下移以保持页内行的连续。
· 如果该页不能容纳行。在allpages-locked堆表中，行会被删除，并且“新”行插入到最后页。data-only-lockedthe 堆表中，行插入到另外的页中，在原来的位置采用转向指针指到该页面，这样保证行的id位置不变。
对于扫描，按sysindex.first <-> sysindex.root链表方式读取数据页。
对于堆表，根据上述插入、删除、更新、扫描特性，可以得到下面的结论：
1．对于不带任何索引的堆表，如果确保不使用update，或确保update不产生插入操作，就可以放心的使用select 完成自然排序，此时记录按插入的先后顺序返回。
3.2有索引的表
对于sybase执行计划没有带索引的表,select返回记录的顺序和堆表扫描返回的顺序相同。
对于sybase执行计划带索引的表，select 按索引字段的顺序返回记录。sybase将索引组织为 b 树。索引内的每一页包含一个页首，页首后面跟着索引行。每个索引行都包含一个键值以及一个指向较低级页或数据行的指针。索引的每个页称为索引节点。b 树的顶端节点称为根节点。索引的底层节点称为叶节点。每级索引中的页链接在双向链接列表中。
对于有索引的表，得到以下结论：
1．以通过控制索引来控制查询方式，从而控制返回顺序。
如我们可以通过(index index_name)来指定对某个索引的使用，从而达到按索引index_name排序。也可以使用(index 0)指示强制不使用索引，从而使返回的记录顺序按堆表方式。
2．如何没有强制指定索引，不管你的select 语句中是否在where后面使用了索引，sybase均可能基于代价对索引的使用进行调整。由于sybase基于代价执行计划会对索引的使用进行调整，因此不能像oracle那样利用非聚簇索引完成返回记录的自然排序，这时最好加上order by以保证排序的准确。
3．如果需要排序的字段是聚簇索引，那么就可以放心使用该索引完成排序。这时，不论执行计划怎样，sybase均按聚簇索引字段顺序返回记录。对于聚簇索引表，在插入数据时，会引起页内部分记录（值大的记录）的移动，通过移动sybase保证了数据的物理顺序与聚簇索引顺序一致。
4.ms sql server
不管你的select 语句中是否在where后面使用了索引，sql server均可能基于代价对索引的使用进行调整。即使没有where语句也有可能使用索引，即使有where语句也有可能不用索引。当然，如果表本身就没有创建任何索引就肯定不会使用到索引。
4.1没有索引的表
没有索引的表在称为堆表或堆集。堆集使用 iam管理扩展盘区，多个iam形成iam链。堆集在 sysindexes 内有一行，其 indid = 0。sysindexes.firstiam 列指向 iam 页链的 iam 首页，iam 页链管理分配给堆集的空间。sql server 2000 使用 iam 页在堆集中浏览。堆集内的数据页和行没有任何特定的顺序，也不链接在一起。数据页之间唯一的逻辑连接是记录在 iam 页内的连接。
对于插入操作，当sql server 2000 需要插入新行而当前页没有可用空间时，它使用 iam 和 pfs 页查找具有足够空间容纳该行的页。sql server 使用 iam 页查找分配给对象的扩展盘区。对于每个扩展盘区，sql server 搜索 pfs 页以查看是否有一页具有足够的空间容纳这一行。
sql server 只有当无法在现有的扩展盘区内快速找到一页有足够空间容纳正插入的行时，才给对象分配新的扩展盘区。sql server 使用按比例分配算法，从文件组内的可用扩展盘区中分配扩展盘区。如果一个文件组有两个文件，其中一个的可用空间是另一个的两倍，那么每从后者分配一页，就从前者分配两页。这意味着文件组内的每个文件应该有近似的空间使用百分比。
对于删除操作，在堆表中，即使删除了记录，该记录所在页不会作页内移动。
对于数据更新，sql server可以采用多种方式来进行。更新可能是现场发生的，也可能是以先删除然后插入的方式进行的，还可以是通过查询处理器或存储引擎来管理更新。但是在堆表中，总是采用现场更新方式，对于更新的内容原来的页不能容纳的情况，sql server 2000采用转向指针处理，保证了更新后该记录位置的不变。
通过扫描 iam 页可以对堆集进行表扫描或串行读，以找到容纳这个堆集的页的扩展盘区。因为 iam 按扩展盘区在数据文件内存在的顺序表示它们，所以这意味着串行堆集扫描一律沿每个文件进行。
根据上述堆表的插入、更新、删除、扫描原则，可以得到以下的结论：
1．使用 iam 页设置扫描顺序意味着堆集中的行一般不按照插入的顺序返回。
2．对于已经存在的记录，记录的位置（数据库号，文件号，页号，行号）不会变化。
结论2可应用到备份-清除机制中。如果日志表是没有索引的堆表，就可以通过时间、流水号等字段排除当前插入的记录，使select和delete两次操作返回的结果集及顺序完全一致，再通过set rowcount来控制每次操作的记录条数，使得备份-清除操作能够安全进行。
4.2有索引的表
对于sql server 执行计划没有带索引的表,select返回记录的顺序和堆表扫描返回的顺序相同。
对于sql server 执行计划带索引的表，select 按索引字段的顺序返回记录。sql server将索引组织为 b 树。索引内的每一页包含一个页首，页首后面跟着索引行。每个索引行都包含一个键值以及一个指向较低级页或数据行的指针。索引的每个页称为索引节点。b 树的顶端节点称为根节点。索引的底层节点称为叶节点。每级索引中的页链接在双向链接列表中。
对于有索引的表，得到以下结论：
1．可以通过控制索引来控制查询方式，从而控制返回顺序。
如我们可以通过with(index(index_name))来指定对某个索引的使用，从而达到按索引index_name排序。
2．如何没有强制指定索引，不管你的select 语句中是否在where后面使用了索引，sql server均可能基于代价对索引的使用进行调整，即使没有where语句也有可能使用索引，即使有where语句也有可能不用索引。不管你的delete 语句中是否在where后面使用了索引，sql server均可能基于代价对索引的使用进行调整，即使没有where语句也有可能使用索引，即使有where语句也有可能不用索引。带相同where语句的select 和 delete 执行计划很可能不一样。
因此select 和 delete 得到的记录顺序很可能不一致，如果要选取前n条记录,那么得到的记录集尽管条数一致但内容不一致。尽管我们可以通过with(index(index_name))来强制select对索引的使用，但delete却不能够强制指定索引，因为delete涉及对索引本身的删除。
这种情况下，如果数据库的性能够好，要备份的数据不多，就不要使用set rowcount来控制条数。但如果确需要控制一次删除的条数，可以直接在where条件中控制更小的范围，如时间范围控制到小时，一天的数据通过24小时的循环来备份。
要么采用dts作备份。
3．如果需要排序的字段是聚簇索引，那么就可以放心使用该索引完成排序。这时，不论执行计划怎样，sql server均按聚簇索引字段顺序返回记录。
参考文献和资料：
1．《oracle freelist和hwm原理探讨及相关性能优化》，游波
2.《关于block中数据的存储和重组的探究》，http://www.itpub.net
3．《怎样按物理顺序提取记录?》，http://www.itpub.net
4．《如何找出一个表的最后一行？物理插入顺序》，http://www.itpub.net
5．《oracle 9i for windows nt/2000数据系统培训教程》,清华大学出版社
6.《microsoft sql server 2000技术内幕》,北京大学出版社
7．《heaps of data: tables without clustered indexes》
上述部分文章在我的blog网站http://blog.csdn.net/youbo2004上可找到。
