数据库查询优化中的索引跳跃扫描（Index Skip Scan）优化技术

描述：索引跳跃扫描是一种数据库查询优化技术，用于在复合索引（多列索引）中，当查询条件只包含了索引的后缀列（非前导列），而缺失了索引的前导列时，依然能够高效地利用该复合索引进行数据访问。在没有此项优化的情况下，缺失前导列的查询通常无法有效使用该复合索引，可能导致全表扫描。索引跳跃扫描通过“逻辑上”跳过不同的前导列值，分别对每个不同的前导列值执行一次针对后缀列的索引范围扫描，然后将结果合并，从而实现对复合索引的部分使用。

解题过程/技术原理：

1. 问题场景与背景：

   • 假设在员工表(employee)上有一个复合索引idx_dept_salary (department_id, salary)。索引首先按department_id排序，在相同的department_id内再按salary排序。
   • 一个常见的查询是：SELECT * FROM employee WHERE salary > 10000;。此查询条件只涉及索引的第二列salary，而没有指定第一列department_id。
   • 在传统索引扫描中，由于索引是按(department_id, salary)组织的，数据库无法直接定位salary > 10000的记录在索引中的连续位置，因为不同部门的相同salary值是分散在索引的不同位置的。因此，优化器可能会选择忽略这个复合索引，转而进行全表扫描，效率低下。

2. 索引跳跃扫描的核心思想：

   • 索引跳跃扫描将上述查询“逻辑转换”为对每个不同的department_id值执行一次查询。即，将SELECT * FROM employee WHERE salary > 10000; 在逻辑上视为执行了多次子查询的并集：

     SELECT * FROM employee WHERE department_id = 'A' AND salary > 10000
     UNION ALL
     SELECT * FROM employee WHERE department_id = 'B' AND salary > 10000
     UNION ALL
     ...
     SELECT * FROM employee WHERE department_id = 'Z' AND salary > 10000;
     

   • 对于每一个已知的department_id值（这些值可以通过快速扫描索引的department_id部分或从表的统计信息中获得），数据库引擎在索引中定位到该department_id对应的索引叶块范围的起始点，然后在这个“局部”范围内，由于salary是排好序的，它可以快速地进行范围扫描（salary > 10000）。这个过程对每个不同的department_id值重复执行。

3. 技术实现步骤：

   • 步骤1：识别可用的复合索引与前导列不同值。优化器分析查询条件，发现WHERE子句中包含复合索引idx_dept_salary的后缀列salary，但缺少前导列department_id。它会决定尝试索引跳跃扫描。
   • 步骤2：收集前导列的不同值列表。数据库需要获取department_id列在表中存在的所有不同值。这可以通过扫描索引键的前导列部分（通常比扫描全表快）或利用已有的统计信息（如直方图或不同值数量NDV）来获得一个列表，例如[‘A‘, ‘B‘, ‘C‘, ...]。
   • 步骤3：为每个前导列值执行一次“子扫描”。对于步骤2中得到的每一个不同的department_id值（如‘A‘），数据库在索引idx_dept_salary中进行查找：
     1. 利用索引的B树结构，快速定位到第一个department_id = ‘A‘的索引条目。
     2. 从这个位置开始，在department_id = ‘A‘的这个连续索引段内，因为salary是有序的，所以可以高效地执行salary > 10000的范围扫描，直到遇到下一个不同的department_id（如‘B‘）为止。
     3. 记录下所有满足department_id = ‘A‘ AND salary > 10000的记录的ROWID（或直接获取数据，如果索引包含所有查询列）。
   • 步骤4：合并所有“子扫描”的结果。将步骤3中为每个department_id值扫描得到的结果集合并起来，形成最终的查询结果。
   • 步骤5：访问表数据（如需要）。如果索引不包含查询所需的所有列（即不是覆盖索引），数据库会使用步骤4中收集到的ROWID列表回表（访问主表）获取完整的行数据。

4. 适用条件与代价考量：

   • 适用条件：
     1. 查询条件包含复合索引的后缀列，但不包含或不完全包含前导列。
     2. 复合索引的前导列的不同值数量相对较少。如果前导列有大量不同值（高基数），那么“跳跃”的次数会非常多，每次“子扫描”可能只覆盖很少的数据，导致开销（主要是索引树遍历定位的开销）大于收益，优化器可能就不会选择此计划。
     3. 数据库优化器支持此技术（如Oracle的“Index Skip Scan”， MySQL 8.0的“Skip Scan”范围访问方法，某些版本的SQL Server和PostgreSQL也有类似优化或变体）。
   • 代价估算：优化器会估算索引跳跃扫描的代价，主要包括：收集前导列不同值的代价 + (不同值数量 * 每次定位并扫描一个局部范围的代价) + 合并结果的代价。它会与全表扫描、全索引扫描或其他可能索引的代价进行比较，选择代价最低的计划。

5. 优点与局限性：

   • 优点：避免了在缺失复合索引前导列时必须进行全表扫描的窘境，提高了查询性能。尤其是在前导列基数低、数据分布均匀、后缀列选择性高的场景下，性能提升显著。
   • 局限性：
     1. 效率高度依赖于前导列的不同值数量。前导列基数越低，跳跃次数越少，效率越高。反之，则可能不如全表扫描。
     2. 通常不如在查询条件中包含前导列的等值条件后直接利用该复合索引进行范围扫描高效。
     3. 不是所有数据库或所有版本都支持。
     4. 对于WHERE salary > 10000 OR department_id = ‘X‘这类包含OR的复杂条件，可能无法应用。

总结：索引跳跃扫描是一种巧妙的优化，它通过将针对复合索引后缀列的查询，分解为针对每个不同前导列值的多次“局部”索引扫描，从而绕过了缺失前导列时无法有效使用索引的限制。其有效性关键取决于前导列的基数。理解这项技术有助于DBA和开发者更好地设计索引和编写查询，尤其是在无法为所有查询组合都创建完美索引的现实约束下。