digoal
2022-09-10
PostgreSQL , duckdb , sqlite3
作为最先进的数据库PostgreSQL, 目前优化器还未支持Skip scan的优化, 需要通过递归语句来实现这个能力.
《DB吐槽大会,第62期 - PG 不支持index skip scan》
《递归+排序字段加权 skip scan 解决 窗口查询多列分组去重的性能问题》
《PostgreSQL Oracle 兼容性之 - INDEX SKIP SCAN (递归查询变态优化) 非驱动列索引扫描优化》
《distinct xx和count(distinct xx)的变态递归优化方法 - 索引收敛(skip scan)扫描》
《用PostgreSQL找回618秒逝去的青春 - 递归收敛优化》
SQLite3 优化器已经支持skip scan, 它是怎么做的呢? 理论上和递归类似:
https://www.sqlite.org/optoverview.html#the_skip_scan_optimization
使用索引扫描时, 一般规则是，只有当索引最左侧的列有 WHERE 子句约束时，索引才有用。但是，在某些情况下，即使索引的前几列从 WHERE 子句中省略，但后面的列被包含，SQLite 也能够使用索引。
例如 index (c1,c2) , search 条件 where c2>100 某些情况也能使用以上 index.
例子：
CREATE TABLE people(
name TEXT PRIMARY KEY,
role TEXT NOT NULL,
height INT NOT NULL, -- in cm
CHECK( role IN ('student','teacher') )
);
CREATE INDEX people_idx1 ON people(role, height);
people 表为大型组织中的每个人提供一条记录。每个人要么是“ student ”，要么是“ teacher ”，由“ role ”字段决定。该表还记录每个人的身高（以厘米为单位）。role, height 都已编入索引。请注意，索引最左边的列role(有些时候也被称为驱动列)选择性很差 - 它只包含两个可能的值。
现在考虑一个查询，查找组织中身高 180 厘米或以上的每个人的姓名：
SELECT name FROM people WHERE height>=180;
由于索引最左边的列role未出现在查询的 WHERE 子句中，因此人们很容易得出索引在这里不可用的结论。但是，SQLite 能够使用索引。从概念上讲，SQLite 使用索引的方式就好像查询更像以下内容：
SELECT name FROM people
WHERE role IN (SELECT DISTINCT role FROM people)
AND height>=180;
或这个：
SELECT name FROM people WHERE role='teacher' AND height>=180
UNION ALL
SELECT name FROM people WHERE role='student' AND height>=180;
上面显示的替代查询公式仅是概念性的。SQLite 不会真正转换查询。实际的查询计划如下：SQLite 定位“role”的第一个可能值，它可以通过将“people_idx1”索引倒回到开头并读取第一个记录来实现。SQLite 将这个第一个“role”值存储在一个内部变量中，我们在此将其称为“$role”。然后 SQLite 运行如下查询：SELECT name FROM people WHERE role=$role AND height>=180。此查询在索引的最左侧列上具有相等约束，因此可以使用索引来解析该查询。该查询完成后，SQLite 使用“people_idx1”索引来定位“role”列的下一个值，使用的代码在逻辑上类似于SELECT role FROM people WHERE role>$role LIMIT 1。这个新的“role”值将覆盖 $role 变量，并重复该过程，直到检查完“role”的所有可能值。
我们将这种索引使用称为“索引跳跃扫描”，因为数据库引擎通常需要对索引进行完整扫描，但“索引跳跃扫描”通过偶尔跳到下一个候选值来优化扫描（使其低于“完整”扫描）。
如果 SQLite 知道前一个或多个列包含许多重复值，它可能会使用“索引跳跃扫描”来扫描索引。如果索引最左侧列中的重复值太少，那么直接前进到下一个值并进行全表扫描会比在索引上进行二分搜索来查找下一个左列值更快。
SQLite 知道索引最左列中存在许多重复项的唯一方法是，在数据库上运行ANALYZE命令。如果没有 ANALYZE 的结果，SQLite 必须猜测表中数据的“形状”，默认猜测是索引最左列中每个值的平均重复项数为 10。只有当重复项数约为 18 或更多时，“索引跳跃扫描”才有用（它只会比全表扫描更快）。因此，“索引跳跃扫描”永远不会用于未经分析的数据库。
