select返回记录的顺序

(转自：http://blog.chinaunix.net/u2/60332/showart_495257.html)

关键词： 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 上可找到。