Microsoft SQL Server 2000 中的位图

　　摘要：Microsoft SQL Server 从版本 7.0 开始使用内置位图来提高执行查询的速度。通过在 SQL Server 2000 中引入新的运算符，可以将进一步的位图筛选技术应用于源自大型数据集的、更快速的查询结果。
　　
　　简介
　　本文首先介绍了在 Microsoft® SQL Server 7.0 的查询优化中位图的使用，然后介绍了它们在 SQL Server 2000™ 中增强的应用。
　　
　　SQL Server 7.0
　　Microsoft SQL Server 7.0 在所有的散列联接中无提示使用位图。散列联接包含创建和探测两个阶段。在创建阶段，其中一个已联接的表（也称为外部表）的所有联接键都被分布到一个散列表中。作为该散列操作的副产品，SQL Server 将生成一个独立的位图，其中“0”表示“外部表中没有键值分布到该位”，“1”表示“外部表中有一个或多个键值分布到该位”。
　　
　　位图的大小是在根据外部表中唯一值的数量而进行的优化查询过程中决定的。一旦外部表中所有的行都被散列后，位图就由 0 和 1 组成。然后将使用与处理外部键相同的散列算法对探测表（也称为内部表）中的每个键进行分布。
　　
　　在检查和搜索创建阶段的散列表之前，我们将先检查位图。如果对应的条目为“0”，则该行在外部表中不可能有匹配值，因此将被丢弃。
　　
　　由于搜索位图要比搜索散列表更经济，处理不生成联接记录的内部表中的行要比处理不带位图的行快。由于位图是散列联接不可分割的一部分，因此位图将自动创建并且不会显示在显示方案的输出中。
　　
　　SQL Server 2000
　　Microsoft SQL Server 2000 非常有效地使用了类似的位图，不仅在内部散列联接中使用，而且还用于外部联接运算符以删除包含不能生成任何联接记录的键值的行。在创建位图的显示方案输出中，有一个“Bitmap Create”运算符。在查询优化过程中，位图被自动引用到查询计划中。以下查询示例便使用了包含这些位图的计划：
　　
　　SELECT　S_NAME,　 S_ADDRESS ,S_PHONE ,S_COMMENT ,PS_PARTKEY
　　FROM　　SUPPLIER ,PARTSUPP
　　WHERE　 S_SUPPKEY = PS_SUPPKEY AND
　　PS_PARTKEY between 5000 AND 5999
　　
　　该查询从 SUPPLIER 表中选择所有供应商，这些供应商生产 5000 系列中的所有部件（部件键值在 5000 到 5999 之间）。除 SUPPLIER 表外，我们还使用 PARTSUPP（部件供应商）表，它包含了（针对每个部件）生产同一部件的不同供应商的所有记录。图 1 显示了由 SQL Server 2000 生成的显示方案图解。
　　　
　　图 1：示例查询的执行计划图解
　　
　　对于每个数据流，位图都在联接的外部输入端上的散列联接之前创建。从左至右和从上至下查看上面的显示计划图解，将发现 PARTSUPP 表的扫描是并行的。后面的交换运算符 (Parallelism/Repartition Streams) 使用键值分配行，这样它们将在并行的散列匹配（联接）之前被置于包含 SUPPLIER 表的再分配行的对应流中。先执行顶部分支，直至散列联接的散列表被填充，底部分支没有活动为止。
　　
　　在扫描 SUPPLIER 表时，我们已使用 PARTSUPP 键（在本查询中为 PS_SUPPKEY 列）在顶部分支上创建了位图。每一个进入散列联接的流都有一个位图。当 SUPPLIER 行在扫描后输入交换运算符时，我们首先要判断它们将进入哪一个流。如果在对应于键值（S_SUPPKEY 列）的项目中该行的位图包含“0”，则丢弃该行。因此，在被置于适当的交换输出流之前，不符合条件的行将被删除。
　　
　　SQL Server 2000 只在并行查询计划中使用这些位图。这是因为如果没有交换运算符，则在散列联接中的位图上没有额外的补偿。除了上述使用散列联接的方案外，SQL Server 2000 还在合并联接中使用这些位图，但仍然只限于并行计划，并且在外部分支上存在 SORT 运算符。SORT 运算符使 SQL Server 在处理内部表中的行之前先处理所有外部行，因此使我们可以创建位图。如果在外部分支上没有 SORT 运算符，将同时处理合并联接中来自内部表和外部表中的行，这样就不能使用位图了。
　　
　　测试结果显示速度的提高
　　通常，由于采用位图而产生的性能提高取决于被筛选出的行数。该数目是可以变化的，因此根据查询执行中其他运算符的开销的不同，速度提高的幅度可以从小到无法测量到非常显著。
　　
　　图 2 显示了在大型数据库（134 GB 的表，45 GB 的索引）中测试三种复杂查询时所观察到的速度提高。测试是在实验室中使用 RAM 为 4 GB 的 8 路 550 MHz 计算机完成的。
　　
　　查询 A 为包含结果汇总和排序的三个表（最大的表大约包含 100 GB 数据）的联接查询。
　　
　　
　　查询 B 为包含相关子查询的查询。
　　
　　
　　查询 C 为在联接顶部包含汇总的六个表的联接查询。
　　
　　图 2：位图筛选对三个大型数据库的复杂查询的优化
　　
　　结论
　　在查询优化过程中使用位图是 SQL Server 2000 采用的众多技术之一，旨在从大型数据集（如企业数据库中的数据集）中最快的获取查询结果。通过减少需要处理的行数，使内部联接和外部联接查询更有效，迅速返回数据的同时还减少了服务器处理的工作量。