松散索引扫描

性能片段

松散索引扫描

适用于 PostgreSQL

8.4

用

SQL

依赖于

无

"松散索引扫描"在 MySQL 和 Cockroach 中，以及 "混合扫描" 在 YugabyteDB 中，是用于高效查找 B 树索引前导列的唯一值的运算符名称；与扫描所有等于某个键值的记录不同，一旦找到新的值，就会重新开始搜索，查找更大的值。当索引有许多相等的键值时，这要快得多。

松散索引扫描与索引跳跃扫描

虽然它们应用了类似的技术，但松散索引扫描和索引跳跃扫描描述了两种不同的优化。下面是一个比较表格。

松散索引扫描与索引跳跃扫描的比较

	松散索引扫描	索引跳跃扫描
返回值	用于分组集的结果，通常是唯一值	满足谓词的所有匹配行，可以轻松返回多个具有相同值的记录
限制	要求使用索引中列的前缀作为分组键	适用于索引中任何列的选择，并对索引中任何子集的列进行过滤
必须提供跳过值的必要信息	在扫描执行期间，或（在某些限制下）在查询执行之前	在扫描执行之前
示例	SELECT DISTINCT user_id FROM orders; -- common SELECT user_id FROM orders GROUP BY user_id HAVING count(*) > 10; -- Uncommon / nonexistent	CREATE INDEX ON orderlines (order_id, product_id); SELECT order_id, product_option FROM orderlines WHERE product_id IN (2, 11, 23);

索引扫描类型的供应商支持

数据库引擎	松散索引扫描	索引跳跃扫描
PostgreSQL	否	否
MySQL	是，但有限制	是
Oracle		是
DB2		是
SQLite		是
CockroachDB	是，但有限制	否
YugabyteDB	是，但有限制	是

选择唯一值

Postgres 本身不支持松散索引扫描（尽管 有计划），但可以使用递归 CTE 如下模拟它们

WITH RECURSIVE t AS (
   SELECT min(col) AS col FROM tbl
   UNION ALL
   SELECT (SELECT min(col) FROM tbl WHERE col > t.col)
   FROM t WHERE t.col IS NOT NULL
   )
SELECT col FROM t WHERE col IS NOT NULL
UNION ALL
SELECT null WHERE EXISTS(SELECT 1 FROM tbl WHERE col IS NULL);

查询的递归部分在每次传递中处理一个新的行，查找大于前一次传递中列值的最小值；主查询在需要时添加一个单独的空值结果。上面的查询等价于

SELECT DISTINCT col FROM tbl;

但当 "col" 只有按比例少量的唯一值时，其运行速度快几个数量级。

如果 col IS NOT NULL

如果 col 被定义为 NOT NULL，查询可以简化。
还可以使用 ORDER BY / LIMIT 1 的替代语法，这通常会导致更简单（也更快）的查询计划

WITH RECURSIVE t AS (
   (SELECT col FROM tbl ORDER BY col LIMIT 1)  -- parentheses required
   UNION ALL
   SELECT (SELECT col FROM tbl WHERE col > t.col ORDER BY col LIMIT 1)
   FROM t
   WHERE t.col IS NOT NULL
   )
SELECT col FROM t WHERE col IS NOT NULL;

SQL 小提琴（Postgres 9.3）演示了这两种方法。

利用索引的非前导列

相同的技术可用于允许查询从具有少量唯一值的前导列（并且不会自然地指定在查询中）和一个非常具体的第二列（查询使用该列）的索引中获益。前导列可以以不改变含义的方式引入查询。

要设置示例

CREATE TABLE tbl (col integer NOT NULL, col2 integer NOT NULL);
INSERT INTO tbl
SELECT trunc(random()*5) AS col, (random()*1000000)::int AS col2 FROM generate_series(1,10000000);
CREATE INDEX ON tbl (col, col2);

查询的自然规范，它通常不使用索引，需要 1758 毫秒

SELECT count(*) FROM tbl WHERE col2 = 9854;

修改后的版本可以从索引中获益，并在 2 毫秒内运行

SELECT count(*) FROM tbl WHERE col2 = 9854 AND col IN 
(
  WITH RECURSIVE
     t AS (SELECT min(col) AS col FROM tbl
           UNION ALL
           SELECT (SELECT min(col) FROM tbl WHERE col > t.col) FROM t WHERE t.col IS NOT NULL)
  SELECT col FROM t
);

如果 col 可以为 NULL，则此查询的正确版本将更加复杂。