网站开发工程师英文简历,wordpress站关注别人,wordpress修改主题模板,凡客网站网址返回#xff1a;SQLite—系列文章目录
上一篇#xff1a;SQLite中的隔离(八#xff09;
下一篇#xff1a;SQLite下一代查询规划器(十#xff09; 1. 引言
本文档概述了查询规划器和优化器如何 用于 SQLite 工作。
给定一个 SQL 语句#xff0c;可能有几十个、几百…返回SQLite—系列文章目录
上一篇SQLite中的隔离(八
下一篇SQLite下一代查询规划器(十 1. 引言
本文档概述了查询规划器和优化器如何 用于 SQLite 工作。
给定一个 SQL 语句可能有几十个、几百个甚至 实现该语句的数千种方法具体取决于复杂性 语句本身和基础数据库架构。这 查询规划器的任务是选择最小化的算法 磁盘 I/O 和 CPU 开销。
索引教程文档中提供了其他背景信息。
从 3.8.0 版 2013-08-26 开始 SQLite查询规划器被重新实现为下一代查询规划器或“NGQP”。所有功能、技术、 本文档中描述的算法适用于 3.8.0 之前的旧版查询规划器和 NGQP。欲了解更多信息 NGQP 与旧版查询规划器有何不同请参阅 NGQP 的详细说明。 2. WHERE子句分析
查询的 WHERE 子句被分解为“terms”其中每个术语 通过 AND 运算符与其他运算符分开。 如果 WHERE 子句由由 OR 分隔的约束组成 运算符则整个子句被视为单个“术语” 应用 OR 子句优化。
分析 WHERE 子句的所有术语看看它们是否可以 使用索引感到满意。 要使索引可用术语通常必须是以下项之一 形式 column expressioncolumn IS expressioncolumn expressioncolumn expressioncolumn expressioncolumn expressionexpression columnexpression columnexpression columnexpression columnexpression columncolumn IN (expression-list)column IN (subquery)column IS NULLcolumn LIKE patterncolumn GLOB pattern
如果使用如下语句创建索引
CREATE INDEX idx_ex1 ON ex1(a,b,c,d,e,...,y,z);
然后如果索引的初始列 列 a、b 等出现在 WHERE 子句术语中。 索引的初始列必须与 或 IN 或 IS 运算符。 使用的最右边的列可以使用不等式。 对于最右边 列最多可以有两个不等式 这必须将列的允许值夹在两个极端之间。
索引的每一列都不必出现在 WHERE 子句术语以便使用该索引。 但是所使用的索引列中不能有间隙。 因此对于上面的示例索引如果没有 WHERE 子句术语 约束 C 列则约束 A 列和 B 列的项可以 与索引一起使用但不能与限制 d 到 z 列的术语一起使用。 同样通常不会使用索引列用于索引目的 如果它们在右边 仅受不等式约束的列。 有关例外情况请参阅下面的跳过扫描优化。
对于表达式的索引只要单词“column”是 在上述文本中可以用“索引表达式”代替 表示 CREATE INDEX 语句中出现的表达式的副本一切都将正常工作。
2.1. 索引术语用法示例
对于上面的索引和 WHERE 子句如下所示
... WHERE a5 AND b IN (1,2,3) AND c IS NULL AND dhello
索引的前四列 a、b、c 和 d 将可用因为 这四列构成了索引的前缀并且都由 相等约束。
对于上面的索引和 WHERE 子句如下所示
... WHERE a5 AND b IN (1,2,3) AND c12 AND dhello
只有索引的 a、b 和 c 列可用。d 列 将不可用因为它发生在 C 和 C 的右侧 仅受不平等的制约。
对于上面的索引和 WHERE 子句如下所示
... WHERE a5 AND b IN (1,2,3) AND dhello
只有索引的 a 列和 b 可用。d 列 将不可用因为 C 列不受约束并且可以 索引可用的列集中没有间隙。
对于上面的索引和 WHERE 子句如下所示
... WHERE b IN (1,2,3) AND c NOT NULL AND dhello
索引根本无法使用因为 索引列“a”不受约束。假设没有其他 索引上面的查询将导致全表扫描。
对于上面的索引和 WHERE 子句如下所示
... WHERE a5 OR b IN (1,2,3) OR c NOT NULL OR dhello
索引不可用因为 WHERE 子句术语已连接 由 OR 而不是 AND。此查询将导致全表扫描。 但是如果添加了三个包含列的附加索引 b、c 和 d 作为其最左边的列则 OR 子句优化可能适用。
3. BETWEEN 优化
如果 WHERE 子句的术语采用以下形式 expr1 BETWEEN expr2 AND expr3
然后添加两个“虚拟”术语如下所示 expr1 expr2 AND expr1 expr3
虚拟术语仅用于分析不会导致任何字节码 要生成。 如果两个虚拟项最终都用作索引的约束 则省略原来的 BETWEEN 项和相应的测试 不对输入行执行。 因此如果 BETWEEN 项最终被用作索引约束 从未对该术语进行过任何测试。 另一方面 虚拟术语本身从来不会导致对 输入行。 因此如果 BETWEEN 项不用作索引约束并且 相反必须用于测试输入行expr1 表达式为 只评估一次。
4. 手术室优化
通过 OR 而不是 AND 连接的 WHERE 子句约束可以 以两种不同的方式处理。 如果一个术语由多个包含公共列的子术语组成 name 并用 OR 分隔如下所示 column expr1 OR column expr2 OR column expr3 OR ...
然后该术语被重写如下 column IN (expr1,expr2,expr3,...)
然后重写的术语可能会继续使用 IN 运算符的正常规则。请注意列必须是 每个 OR 连接子项中的同一列 尽管该列可以出现在 的 运算符。
当且仅当前面描述的将 OR 转换为 IN 运算符 不起作用则尝试第二次 OR 子句优化。 假设 OR 子句由多个子项组成如下所示
expr1 OR expr2 OR expr3
单个子项可以是单个比较表达式例如 a5 或 xy也可以是 LIKE 或 BETWEEN 表达式或子术语 可以是带括号的 AND 连接子子术语的列表。 每个子项都像分析整个 WHERE 子句一样 以查看子项本身是否可索引。 如果 OR 子句的每个子项都是可单独索引的 然后可以对 OR 子句进行编码以便使用单独的索引 来评估 OR 子句的每个项。一种思考方式 SQLite对每个OR子句使用单独的索引可以想象 将 WHERE 子句改写如下
rowid IN (SELECT rowid FROM table WHERE expr1UNION SELECT rowid FROM table WHERE expr2UNION SELECT rowid FROM table WHERE expr3)
上面重写的表达式是概念性的;包含 WHERE 子句 或者不是真的以这种方式重写。 OR 子句的实际实现使用一种机制即 效率更高即使不适用于没有 ROWID 表或 无法访问“rowid”的表。不过 语句捕获了实现的本质 上图使用单独的索引来查找候选结果行 从每个 OR 子句项最终结果是 那些行。
请注意在大多数情况下SQLite 只会对每个索引使用一个索引 表。第二个 OR 子句优化 这里描述的是该规则的例外情况。使用 OR 子句 对于 OR 子句中的每个子项可以使用不同的索引。
对于任何给定的查询OR 子句优化描述的事实 这里可以使用并不保证它会被使用。 SQLite 使用基于成本的查询计划器来估计 CPU 和 磁盘 I/O 成本各种竞争查询计划并选择计划 它认为这将是最快的。如果 OR 术语 WHERE 子句或者如果单个 OR 子句上的某些索引 子项不是很有选择性那么SQLite可能会决定它是 更快地使用不同的查询算法甚至是全表扫描。 应用程序开发人员可以在语句上使用 EXPLAIN QUERY PLAN 前缀来获取 所选查询策略的高级概述。 5. LIKE优化
使用 LIKE 或 GLOB 运算符的 WHERE 子句术语 有时可以与索引一起使用以进行范围搜索 几乎就像 LIKE 或 GLOB 是 BETWEEN 运算符的替代品一样。 此优化有许多条件
LIKE 或 GLOB 的右侧必须是字符串文本 或绑定到字符串文本的参数 这不是以通配符开头的。不能通过以下方式使 LIKE 或 GLOB 运算符为 true 在 左侧。这意味着 LIKE 或 GLOB 运算符的左侧是名称 具有 TEXT 相关性的索引列或者右侧模式参数不以 减号 “-” 或数字。 这种限制源于数字不排序的事实 词典顺序。例如910 但“9”“10”。用于实现 LIKE 和 GLOB 的内置函数不得 已使用 sqlite3_create_function API 重载。对于 GLOB 运算符必须使用 内置 BINARY 排序序列。对于 LIKE 运算符如果启用了 case_sensitive_like 模式则 必须使用 BINARY 排序序列对列进行索引或者如果禁用case_sensitive_like模式则必须对列进行索引 使用内置的 NOCASE 排序序列。如果使用 ESCAPE 选项则 ESCAPE 字符必须为 ASCII 或 UTF-8 中的单字节字符。
LIKE 运算符有两种模式可以通过编译指示进行设置。这 默认模式是 LIKE 比较对差异不敏感 latin1 字符的大小写。因此默认情况下以下内容 表达式为 true
a LIKE A
如果启用了case_sensitive_like编译指示如下所示
PRAGMA case_sensitive_likeON;
然后 LIKE 运算符注意大小写上面的例子会 计算结果为 false。请注意不区分大小写仅适用于 latin1 字符 - 基本上是英语的大写和小写字母 在 ASCII 的下部 127 字节代码中。国际字符集 在 SQLite 中区分大小写除非提供了应用程序定义的排序规则序列和 like SQL 函数 考虑非 ASCII 字符。 如果应用程序定义的排序序列和/或类似 SQL 提供的功能这里描述的 LIKE 优化永远不会 被带走。
默认情况下LIKE 运算符不区分大小写因为这是 SQL标准要求。您可以在以下位置更改默认行为 使用 SQLITE_CASE_SENSITIVE_LIKE 命令行选项编译时 到编译器。
如果 运算符使用内置的 BINARY 排序规则序列进行索引并且 case_sensitive_like已打开。或者如果出现以下情况则可能会进行优化 使用内置的 NOCASE 排序序列对列进行索引并且 case_sensitive_like模式已关闭。这是仅有的两种组合 在此下LIKE运算符将得到优化。
GLOB 运算符始终区分大小写。左侧的列 的 GLOB 运算符必须始终使用内置的 BINARY 排序规则序列 或者不会尝试使用索引优化该运算符。
只有在以下情况下才会尝试 LIKE 优化 GLOB 或 LIKE 运算符的右侧是 文本字符串或已绑定到字符串文本的参数。字符串文本不得 以通配符开头;如果右侧以通配符开头 字符则不尝试此优化。如果右侧 是一个绑定到字符串的参数那么这个优化是 仅当预准备语句包含表达式时才尝试 是用 sqlite3_prepare_v2 或 sqlite3_prepare16_v2 编译的。 如果 右侧是一个参数语句是使用 sqlite3_prepare 或 sqlite3_prepare16 准备的。
假设右侧是非通配符的初始序列 LIKE 或 GLOB 运算符的一侧是 x。我们正在使用一个 字符来表示此非通配符前缀但读者应 了解前缀可以包含多个字符。 设 y 是最小字符串其长度与 /x/ 相同但 比较大于 x。例如如果 x 是“hello”那么 y 将是“hellp”。 LIKE 和 GLOB 优化包括添加两个虚拟项 喜欢这个 column x AND column y
在大多数情况下原始的 LIKE 或 GLOB 运算符仍然是 针对每个输入行进行了测试即使使用虚拟术语 约束索引。这是因为我们不知道还有什么额外的 右边的字符可能会施加约束 x 前缀。但是如果只有一个 x 右侧的全局通配符然后是原始的 LIKE 或 GLOB 测试已禁用。 换句话说如果模式是这样的
column LIKE x%
column GLOB x*
然后当虚拟 术语约束索引因为在这种情况下我们知道所有 索引选择的行将通过 LIKE 或 GLOB 测试。
请注意当 LIKE 或 GLOB 运算符的右侧是 一个参数并使用 sqlite3_prepare_v2 或 sqlite3_prepare16_v2 准备语句然后自动重新解析语句 并在每次运行的第一个 sqlite3_step 调用时重新编译如果绑定 自上次运行以来右侧参数已更改。 这种重新分析和重新编译本质上是相同的操作 在架构更改之后。重新编译是必要的以便查询 Planner 可以检查绑定到 LIKE 或 GLOB 运算符并确定是否使用 优化如上所述。 6. 跳跃扫描优化
一般规则是索引仅在以下情况下才有用 索引最左侧列的 WHERE 子句约束。 但是在某些情况下 SQLite 能够使用索引即使 WHERE 子句中省略了索引但后面的列省略了索引 都包括在内。
请考虑如下表
CREATE TABLE people(name TEXT PRIMARY KEY,role TEXT NOT NULL,height INT NOT NULL, -- in cmCHECK( role IN (student,teacher) )
);
CREATE INDEX people_idx1 ON people(role, height);
people 表对每个人有一个条目在一个大 组织。每个人都是“学生”或“老师” 由“角色”字段确定。该表还记录了 每个人的厘米。角色和高度已编制索引。 请注意索引的最左边的列不是很 选择性 - 它只包含两个可能的值。
现在考虑一个查询以查找 身高 180 厘米或以上的组织
SELECT name FROM people WHERE height180;
因为索引的最左边的列不会出现在 查询的 WHERE 子句人们很容易得出结论 索引在这里不可用。但是SQLite能够使用索引。 从概念上讲SQLite使用索引就好像查询更多 如下所示
SELECT name FROM peopleWHERE role IN (SELECT DISTINCT role FROM people)AND height180;
或者这个
SELECT name FROM people WHERE roleteacher AND height180
UNION ALL
SELECT name FROM people WHERE rolestudent AND height180;
上面显示的替代查询公式只是概念性的。 SQLite 并没有真正转换查询。 实际查询方案如下 SQLite 找到“role”的第一个可能值它 可以通过将“people_idx1”索引倒回开头并读取来完成 第一条记录。SQLite 将第一个“角色”值存储在 内部变量我们在这里称之为“$role”。然后是 SQLite 运行类似“SELECT name FROM people WHERE role$role AND height180”的查询。 此查询对 索引因此索引可用于解析该查询。一次 该查询完成后SQLite 然后使用“people_idx1”索引来 找到“role”列的下一个值使用逻辑上的代码 类似于“从角色中选择角色$role限制 1”。 这个新的“角色”值将覆盖 $role 变量和进程 重复直到检查完“role”的所有可能值。
我们将这种索引用法称为“跳过扫描”因为数据库 引擎基本上是对索引进行全面扫描但它优化了 扫描使其小于“满”偶尔跳到 下一个候选值。
如果 SQLite 知道第一个索引它可能会对索引使用跳过扫描 一列或多列包含许多重复值。 如果重复项太少 在索引的最左边的列中那么它将 更快地简单地迈向下一个值从而这样做 全表扫描而不是对索引进行二进制搜索来定位 下一个左列值。
SQLite知道有很多重复项的唯一方法 在索引的最左边的列中 是否已运行 ANALYZE 命令 在数据库上。 如果没有 ANALYZE 的结果SQLite 必须猜测 表中的数据默认猜测是存在平均值 索引最左边列中的每个值有 10 个重复项。 跳过扫描只会变得有利可图它只会比 全表扫描当重复项数约为 18 个或更多时。 因此绝不会对未分析的数据库使用跳过扫描。 7. 加入
内部联接的 ON 和 USING 子句将转换为附加 在上述第 2.0 段所述的 WHERE 子句分析之前WHERE 子句的条款。 因此对于SQLite没有计算 使用较新的 SQL92 联接语法的优势 在较旧的 SQL89 逗号联接语法上。他们俩最终都完成了 在内部连接上完全相同。
对于 OUTER JOIN情况更为复杂。以下 两个查询不等效
SELECT * FROM tab1 LEFT JOIN tab2 ON tab1.xtab2.y;
SELECT * FROM tab1 LEFT JOIN tab2 WHERE tab1.xtab2.y;
对于内部联接上述两个查询是相同的。然而 特殊处理适用于 OUTER 联接的 ON 和 USING 子句 具体而言在以下情况下ON 或 USING 子句中的约束不适用 联接的右侧表位于 null 行上但约束条件适用 在 WHERE 子句中。净效果是将 ON 或 USING WHERE 子句中 LEFT JOIN 的子句表达式有效地转换了 对 普通的 INNER JOIN - 尽管是运行速度较慢的内部连接。
7.1. 联接中表的顺序
目前实施的 SQLite 仅使用循环连接。也就是说联接的实现方式为 嵌套循环。
联接中嵌套循环的默认顺序是最左边的 表在 FROM 子句中形成外循环和最右边的循环 表形成内循环。 但是如果这样做SQLite 将以不同的顺序嵌套循环 将帮助它选择更好的索引。
内部连接可以自由重新排序。但是左外连接是 既不是交换也不是关联因此不会重新排序。 外部连接左侧和右侧的内部连接可能会重新排序 如果优化器认为这是有利的但外部连接是有利的 始终按它们发生的顺序进行评估。
SQLite 专门处理 CROSS JOIN 运算符。 从理论上讲CROSS JOIN 运算符是可交换的。但是SQLite选择 切勿对 CROSS JOIN 中的表重新排序。这提供了一种机制 程序员可以强制SQLite选择特定的循环嵌套 次序。
在选择联接中表的顺序时SQLite 使用高效的 多项式时间算法。正因为如此 SQLite 能够在 50 或 60 路联接中规划查询 微秒
联接重新排序是自动的通常运行良好可以 程序员不必考虑它特别是如果 ANALYZE 已被用于收集有关可用索引的统计信息 尽管偶尔需要程序员的一些提示。 例如请考虑以下架构
CREATE TABLE node(id INTEGER PRIMARY KEY,name TEXT
);
CREATE INDEX node_idx ON node(name);
CREATE TABLE edge(orig INTEGER REFERENCES node,dest INTEGER REFERENCES node,PRIMARY KEY(orig, dest)
);
CREATE INDEX edge_idx ON edge(dest,orig);
上面的架构定义了一个有向图能够存储一个 每个节点的名称。现在考虑针对此架构的查询
SELECT *FROM edge AS e,node AS n1,node AS n2WHERE n1.name aliceAND n2.name bobAND e.orig n1.idAND e.dest n2.id;
此查询要求的是关于从 标记为“Alice”的节点到标记为“Bob”的节点。 SQLite中的查询优化器基本上有两种选择 实现此查询。实际上有六种不同的选择但是 我们在这里只考虑其中的两个。 下面的伪代码演示了这两种选择。
选项 1
foreach n1 where n1.namealice do:foreach n2 where n2.namebob do:foreach e where e.orign1.id and e.destn2.idreturn n1.*, n2.*, e.*endend
end 选项 2
foreach n1 where n1.namealice do:foreach e where e.orign1.id do:foreach n2 where n2.ide.dest and n2.namebob do:return n1.*, n2.*, e.*endend
end
在两个实现中使用相同的索引来加速每个循环 选项。 这两个查询计划的唯一区别是 循环是嵌套的。
那么哪个查询方案更好呢事实证明答案取决于 在节点表和边缘表中找到哪些类型的数据。
设 alice 节点数为 Mbob 节点数为 N。 请考虑两种情况。在第一种情况下M 和 N 都是 2但 每个节点上有数千条边。在这种情况下选项 1 是 首选。使用选项 1内部循环检查是否存在 一对节点之间的边如果找到结果则输出结果。 因为每个只有 2 个 alice 和 bob 节点所以内部循环 只需要运行四次查询速度非常快。备选方案2将 在这里需要更长的时间。选项 2 的外循环只执行两次 但是因为有大量的边离开每个 Alice 节点 中间循环必须迭代数千次。这将是 慢得多。因此在第一种情况下我们更愿意使用选项 1。
现在考虑 M 和 N 都是 3500 的情况。Alice 节点是 丰富。这一次假设这些节点中的每一个都只由一个节点连接 或两条边。现在首选选项 2。使用选项 2 外环仍然要运行3500次但中间循环只有 每个外循环运行一次或两次内循环只会 对每个中间循环运行一次如果有的话。所以总数 内部循环的迭代次数约为 7000 次。选项 1另一方面 手必须同时运行其外环和中环 3500 次 每个导致中间循环的 1200 万次迭代。 因此在第二种情况下选项 2 的速度快了近 2000 倍 比选项 1。
因此您可以看到根据数据在表中的结构 查询计划 1 或查询计划 2 可能更好。哪个计划可以 SQLite默认选择从版本 3.6.18 开始在不运行 ANALYZE 的情况下 SQLite 将选择选项 2。 如果运行 ANALYZE 命令以收集统计信息 如果统计数据表明 替代方案可能会运行得更快。 7.2. 使用SQLITE_STAT表手动控制查询计划
SQLite为高级程序员提供了行使控制权的能力 在优化器选择的查询计划之上。一种方法 用于伪造 sqlite_stat1、sqlite_stat3 和/或sqlite_stat4表中的 ANALYZE 结果。这不是 建议用于大多数情况。
7.3. 使用 CROSS JOIN 手动控制查询计划
程序员可以强制SQLite使用特定的循环嵌套顺序 对于使用 CROSS JOIN 运算符而不仅仅是 JOIN 进行联接 INNER JOIN、NATURAL JOIN 或 “” 联接。虽然 CROSS JOIN 是 从理论上讲SQLite选择从不对表进行重新排序 交叉连接。因此CROSS JOIN 的左表将始终为 在相对于右表的外循环中。
在以下查询中优化器可以自由地对 FROM 子句的表以任何它认为合适的方式
SELECT *FROM node AS n1,edge AS e,node AS n2WHERE n1.name aliceAND n2.name bobAND e.orig n1.idAND e.dest n2.id;
在以下同一查询的逻辑等价公式中 用“CROSS JOIN”代替“”意味着顺序 表的数必须为 N1、E、N2。
SELECT *FROM node AS n1 CROSS JOINedge AS e CROSS JOINnode AS n2WHERE n1.name aliceAND n2.name bobAND e.orig n1.idAND e.dest n2.id;
在后一个查询中查询计划必须是选项 2。请注意 您必须使用关键字“CROSS”才能禁用表重新排序 优化;INNER JOIN、NATURAL JOIN、JOIN 和其他类似内容 组合就像逗号连接一样工作因为优化器是 可以自由地对表格进行重新排序。表重新排序也是 在外部联接上禁用但那是因为外部联接不是 关联或交换。在 OUTER JOIN 更改中对表重新排序 结果。
请参阅“Fossil NGQP 升级案例研究”了解另一个真实示例 使用 CROSS JOIN 手动控制联接的嵌套顺序。 同一文档后面的查询计划器清单提供了 有关手动控制查询规划器的进一步指导。
8. 在多个索引之间进行选择
查询的 FROM 子句中的每个表最多只能使用一个索引 除非 OR 子句优化进入 播放 SQLite努力在每个表上至少使用一个索引。有时 两个或多个索引可能是在单个表上使用的候选索引。 例如
CREATE TABLE ex2(x,y,z);
CREATE INDEX ex2i1 ON ex2(x);
CREATE INDEX ex2i2 ON ex2(y);
SELECT z FROM ex2 WHERE x5 AND y6;
对于上面的 SELECT 语句优化器可以使用 ex2i1 索引 查找包含 x5 的 ex2 行然后针对每一行进行测试 y6 项。或者它可以使用 ex2i2 索引来查找行 包含 y6 的 ex2 中的每一行都根据 x5 项。
当面临两个或多个索引的选择时SQLite 尝试估计 使用每个选项执行查询所需的总工作量。 然后它选择提供最少估计工时的选项。
帮助优化人员更准确地估计所涉及的工作 在使用各种索引时用户可以选择运行 ANALYZE 命令。 ANALYZE 命令扫描数据库的所有索引其中可能存在 在两个或多个索引之间进行选择并收集有关 这些索引的选择性。收集的统计数据 此扫描存储在特殊数据库中 表 名称 显示名称 全部 以“sqlite_stat”开头。 这些表的内容不会作为数据库进行更新 更改因此在进行重大更改后可能谨慎地 重新运行 ANALYZE。 ANALYZE 命令的结果仅适用于数据库连接 在 ANALYZE 命令完成后打开。
各种 sqlite_statN 表包含有关如何 选择各种索引是。例如sqlite_stat1表可能指示对列 x 的相等约束会减少 搜索空间平均为 10 行而相等约束 Y 列将搜索空间平均减少到 3 行。在这种情况下 SQLite 更愿意使用索引 ex2i2因为该索引更具选择性。 8.1. 使用 Unary-“” 取消 WHERE 子句条款的资格
可以手动取消 WHERE 条款的条款使其无法与 通过在列名前面加上一元 运算符来索引。这 一元 是无操作的不会在准备好的 陈述。 但是一元 运算符将阻止该项 约束索引。 因此在上面的示例中如果查询被重写为
SELECT z FROM ex2 WHERE x5 AND y6;
x 列上的 运算符将阻止该术语 约束索引。这将强制使用 ex2i2 索引。
请注意一元 运算符还会从 一个表达式在某些情况下这可能会导致 表达式的含义。 在上面的例子中 如果列 x 具有 TEXT 亲和力则比较“x5”将作为文本完成。 运算符 删除亲和力。所以比较“x5”将比较文本 在 X 列中数值为 5 且将始终为 false。
8.2. 范围查询
考虑一个略有不同的场景
CREATE TABLE ex2(x,y,z);
CREATE INDEX ex2i1 ON ex2(x);
CREATE INDEX ex2i2 ON ex2(y);
SELECT z FROM ex2 WHERE x BETWEEN 1 AND 100 AND y BETWEEN 1 AND 100;
进一步假设列 x 包含分布的值 介于 0 和 1,000,000 之间Y 列包含值 跨度介于 0 和 1,000 之间。在这种情况下 对 X 列的范围约束应将搜索空间减少 系数为 10,000而 y 列的范围约束应 仅将搜索空间减少 10 倍。所以 ex2i1 索引 应该是首选。
SQLite将做出此决定但前提是它已被编译 与SQLITE_ENABLE_STAT3或SQLITE_ENABLE_STAT4。 SQLITE_ENABLE_STAT3和SQLITE_ENABLE_STAT4选项导致 ANALYZE 命令收集 sqlite_stat3 或 sqlite_stat4 表中列内容的直方图并使用此直方图执行 更好地猜测用于范围约束的最佳查询 如上所述。STAT3 和 STAT4 之间的主要区别在于 STAT3 仅记录最左边列的直方图数据 索引而 STAT4 记录 指数。对于单列索引STAT3 和 STAT4 的工作方式相同。
直方图数据仅在约束的右侧有用 是一个简单的编译时常量或参数而不是表达式。
直方图数据的另一个局限性是它仅适用于 索引上最左边的列。请考虑以下方案
CREATE TABLE ex3(w,x,y,z);
CREATE INDEX ex3i1 ON ex2(w, x);
CREATE INDEX ex3i2 ON ex2(w, y);
SELECT z FROM ex3 WHERE w5 AND x BETWEEN 1 AND 100 AND y BETWEEN 1 AND 100;
这里的不等式位于列 x 和 y 上它们不是 最左边的索引列。因此收集的直方图数据没有 最左边的索引列在帮助在 对列 x 和 y 的范围约束。
9. 覆盖指数
对行进行索引查找时通常的过程是 对索引进行二叉搜索以查找索引条目然后提取 索引中的 rowid并使用该 rowid 执行二进制搜索 原始表。因此典型的索引查找涉及两个 二进制搜索。 但是如果要从表中获取的所有列 索引本身已经可用SQLite将使用这些值 包含在索引中并且永远不会查找原始表 排。这样可以节省每行的一个二进制搜索并且可以进行许多 查询的运行速度是原来的两倍。
当索引包含查询所需的所有数据时以及当 原始表永远不需要查阅我们称该索引为 A “覆盖指数”。
10. 排序依据优化
SQLite 尝试使用索引来满足 尽可能查询。 当面临使用索引来满足 WHERE 子句的选择时 约束或满足 ORDER BY 子句SQLite 也会做同样的事情 上述成本分析 并选择它认为会得到最快答案的索引。
SQLite 还将尝试使用索引来帮助满足 GROUP BY 子句 和 DISTINCT 关键字。如果可以排列连接的嵌套循环 使得与 GROUP BY 或 DISTINCT 等效的行是 连续则 GROUP BY 或 DISTINCT 逻辑可以确定 当前行是同一组的一部分或者当前行是不同的 只需将当前行与上一行进行比较即可。 这可能比将每一行进行比较的替代方案要快得多 所有前行。 10.1. 部分 ORDER BY 通过索引
如果查询包含包含多个术语的 ORDER BY 子句则它可能 SQLite可以使用索引来使行按顺序出现 ORDER BY 中术语的某些前缀但后来的术语 ORDER BY 不满足。在这种情况下SQLite 会进行块排序。 假设 ORDER BY 子句有四个项并且 查询导致行按前两个术语的顺序显示。如 每一行都由查询引擎输出并进入排序器 当前行中对应的前两项的输出 将 ORDER BY 与上一行进行比较。如果他们有 已更改则当前排序已完成并输出新排序为 开始。这会导致排序速度稍快。甚至更大 优点是需要在内存中保存的行要少得多 降低内存要求输出可以开始出现 核心查询已运行完成。
11. 子查询扁平化
当子查询出现在 SELECT 的 FROM 子句中时最简单的 行为是将子查询评估到瞬态表中然后运行 针对瞬态表的外部 SELECT。这样的计划 可能是次优的因为瞬态表将没有任何索引 并且外部查询可能是联接将强制执行 瞬态表上的全表扫描。
为了克服这个问题SQLite 尝试将 SELECT 的 FROM 子句。 这涉及将子查询的 FROM 子句插入到 外部查询的 FROM 子句并重写 引用子查询的结果集的外部查询。 例如
SELECT t1.a, t2.b FROM t2, (SELECT xy AS a FROM t1 WHERE z100) WHERE a5
将使用查询扁平化重写为
SELECT t1.xt1.y AS a, t2.b FROM t2, t1 WHERE z100 AND a5
为了 要进行查询平展。某些约束被标记为 被斜体文本淘汰。这些额外的约束保留在 文档以保留其他约束的编号。
普通读者不应理解所有这些规则。 本节的一个关键要点是确定 如果查询扁平化是安全的或不安全的则微妙且 复杂。多年来由于以下原因导致了多个错误 过于激进的查询扁平化。另一方面性能 的复杂查询和/或涉及视图的查询往往会受到影响 如果查询扁平化更保守。 已过时。查询扁平化不再 尝试聚合子查询。已过时。查询扁平化不再 尝试聚合子查询。如果子查询是 LEFT JOIN 的右操作数则 子查询可能不是联接并且子查询的 FROM 子句可以 不包含虚拟表并且外部查询可能不是聚合。子查询不是 DISTINCT。归入约束条件 4已过时。查询扁平化不再 尝试聚合子查询。子查询具有 FROM 子句。子查询不使用 LIMIT或者外部查询不是联接。子查询不使用 LIMIT外部查询不使用 集 料。2005年放宽限制子查询和外部查询不都具有 ORDER BY 子句。归入约束条件 3子查询和外部查询不都使用 LIMIT。子查询不使用 OFFSET。如果外部查询是复合选择的一部分则 subquery 可能没有 LIMIT 子句。如果外部查询是聚合则子查询可以 不包含 ORDER BY。如果子查询是复合 SELECT则 所有复合运算符都必须是 UNION ALL并且子查询复合的任何术语都不能聚合 或 DISTINCT以及子查询中的每个术语都必须具有 FROM 子句并且外部查询可能不是聚合、DISTINCT 查询或联接。 父查询和子查询可能包含 WHERE 子句。受制于 规则11、12和13它们还可以包含ORDER BY LIMIT 和 OFFSET 子句。如果子查询是复合选择则 ORDER by 子句的父项必须是 子查询的列。如果子查询使用 LIMIT则外部查询可能不会 有一个 WHERE 子句。如果子查询是复合选择则不得使用 ORDER BY 子句。如果子查询使用 LIMIT则外部查询可能不是 不同。子查询可能不是递归 CTE。归入约束条件 17d。已过时。查询扁平化不再 尝试聚合子查询。
查询扁平化是一项重要的优化当视图用作 视图的每次使用都会转换为子查询。
12. 子查询协程 在 SQLite 3.7.15 2012-12-12 之前 FROM 子句中的子查询为 要么扁平化到外部查询中要么运行子查询 完成 在外部查询开始之前子查询的结果集 将存储在瞬态表中 然后瞬态表将在外部查询中使用。新 SQLite的版本还有第三个选项即实现子查询 使用协程。
协程类似于子例程因为它在同一线程中运行 作为调用方并最终将控制权归还给调用方。这 不同的是协程也具有返回的能力 在它完成之前然后从下一个中断的地方继续 时间它被称为。
当子查询实现为协程时将生成字节码 将子查询实现为独立查询除非 不是将结果行返回给应用程序而是 协程在计算每一行后将控制权交还给调用方。 然后调用方可以使用该计算行作为其计算的一部分 然后在协程准备好进入下一行时再次调用协程。
协程比存储子查询的完整结果集要好 在瞬态表中因为协程使用较少的内存。使用共同例程 只需要记住结果的一行而 必须为瞬态表存储结果。另外因为 co-routine 不需要在外部查询之前运行到完成 开始工作输出的第一行可以更快地出现如果 整个查询在完成之前就被放弃了完成的工作更少 整体。
另一方面如果子查询的结果必须扫描多个 倍因为例如它只是联接中的一个表然后它 最好使用瞬态表来记住 子查询以避免多次计算子查询。 12.1. 使用协程将工作推迟到排序之后
从 SQLite 版本 3.21.0 2017-10-24 开始查询规划器将 总是喜欢使用协程来实现 FROM 子句子查询 包含 ORDER BY 子句并且在以下情况下不属于联接 外部查询的结果集为“复杂”。此功能允许 应用程序将昂贵的计算从之前转移 分拣机直到分拣机之后这可以导致更快的操作。 例如请考虑以下查询
SELECT expensive_function(a) FROM tab ORDER BY date DESC LIMIT 5;
此查询的目标是为五个最 表中的最近条目。在上面的查询中 “expensive_function”在排序之前被调用因此是 在表的每一行上调用甚至 由于 LIMIT 子句而最终省略的行。 可以使用协程来解决此问题
SELECT expensive_function(a) FROM (SELECT a FROM tab ORDER BY date DESC LIMIT 5
);
在修改后的查询中由协程实现的子查询计算 “a”的五个最新值。这五个值是从 协程到外部查询中其中“expensive_function”是 仅在应用程序关心的特定行上调用。
未来版本的SQLite中的查询规划器可能会变得足够智能 在两个方向上自动进行上述转换。 也就是说未来版本的 SQLite 可能会转换 第一种形式写入第二种形式或将第二种方式编写的查询放入 第一。从 SQLite 版本 3.22.0 2018-01-22 开始查询规划器 如果外部查询不使用任何 其结果集中的用户定义函数或子查询。对于示例 但是如上所示SQLite 将每个查询实现为 写。 13. MIN/MAX 优化
包含单个 MIN 或 MAX 聚合函数的查询其 参数是索引的最左边的列可能得到满足 通过执行单个索引查找而不是扫描整个表。 例子
SELECT MIN(x) FROM table;
SELECT MAX(x)1 FROM table; 14. 自动索引
当没有索引可用于帮助评估查询时SQLite 可能会创建一个仅在持续时间内持续的自动索引 单个 SQL 语句。 由于构建自动索引的成本是 ONlogN其中 N 是表中的条目数和 做全表扫描只有ON自动索引会 仅当 SQLite 期望查找的运行时间超过 logN 次。请看一个例子
CREATE TABLE t1(a,b);
CREATE TABLE t2(c,d);
-- Insert many rows into both t1 and t2
SELECT * FROM t1, t2 WHERE ac;
在上面的查询中如果 t1 和 t2 都有大约 N 行那么 如果没有任何索引则查询将需要 ON*N 时间。另一方面 手在表 t2 上创建索引需要 ONlogN 时间并使用 用于评估查询的索引需要额外的 ONlogN 时间。 在没有 ANALYZE 信息的情况下SQLite 猜测 N 为 1 万因此它认为构建自动索引将 成为更便宜的方法。
自动索引也可用于子查询
CREATE TABLE t1(a,b);
CREATE TABLE t2(c,d);
-- Insert many rows into both t1 and t2
SELECT a, (SELECT d FROM t2 WHERE cb) FROM t1;
在此示例中t2 表在子查询中用于转换值 t1.b 列。如果每个表包含 N 行则 SQLite 期望 子查询将运行 N 次因此它会认为它更快 首先在 T2 上构造一个自动的瞬态索引然后使用 该索引满足子查询的 N 个实例。
可以在运行时使用 automatic_index Pragma。自动索引由以下人员打开 默认值但可以更改此值以便关闭自动索引 默认情况下使用 SQLITE_DEFAULT_AUTOMATIC_INDEX 编译时选项。 创建自动索引的功能可以通过以下方式完全禁用 使用 SQLITE_OMIT_AUTOMATIC_INDEX 编译时选项进行编译。
在 SQLite 版本 3.8.0 2013-08-26 及更高版本中 发送SQLITE_WARNING_AUTOINDEX消息 到错误日志每次准备使用 自动索引。应用程序开发人员可以而且应该使用这些警告 确定架构中是否需要新的持久性索引。
不要将自动索引与内部索引混淆具有名称 像“sqlite_autoindex_table_N”一样有时是 创建以实现 PRIMARY KEY 约束或 UNIQUE 约束。 此处描述的自动索引仅在 单个查询从不持久化到磁盘并且仅对 单一数据库连接。内部索引是实现的一部分 的 PRIMARY KEY 和 UNIQUE 约束是持久且持久的 到磁盘并且对所有数据库连接都可见。术语“自动索引” 由于遗留原因出现在内部索引的名称中并且确实如此 不表示内部索引和自动索引相关。
14.1. 哈希连接
自动索引与哈希联接大致相同。唯一的区别 是使用 B 树而不是哈希表。如果你愿意 假设为自动索引构造的瞬态 B 树是 实际上只是一个花哨的哈希表然后是一个使用自动 index 只是一个哈希连接。
SQLite在此构造一个瞬态索引而不是哈希表 实例因为它已经具有强大且高性能的 B 树 实现在手而需要添加哈希表。 添加一个单独的哈希表实现来处理这种情况 将增加库的大小设计用于 低内存嵌入式设备以实现最小的性能提升。SQLite可能 有朝一日会通过哈希表实现来增强但就目前而言似乎 在客户端/服务器的情况下最好继续使用自动索引 数据库引擎可能使用哈希联接。
15. 下推优化
如果子查询无法展合到外部查询中则可能 仍然可以通过“下推”WHERE 子句来增强性能 从外部查询到子查询的术语。请看一个例子
CREATE TABLE t1(a INT, b INT);
CREATE TABLE t2(x INT, y INT);
CREATE VIEW v1(a,b) AS SELECT DISTINCT a, b FROM t1;SELECT x, y, bFROM t2 JOIN v1 ON (xa)WHERE b BETWEEN 10 AND 20;
视图 v1 无法拼合因为它是 DISTINCT。它必须 而是作为子查询运行结果存储在 瞬态表则在 t2 和 瞬态表。下推优化下推 “b BETWEEN 10 AND 20”项进入视图。这使得瞬态 表更小如果有则帮助子查询运行得更快 是 t1.b 上的索引。生成的评估如下
SELECT x, y, bFROM t2JOIN (SELECT DISTINCT a, b FROM t1 WHERE b BETWEEN 10 AND 20)WHERE b BETWEEN 10 AND 20;
不能总是使用下推优化。例如 如果子查询包含 LIMIT则向下推 外部查询中的 WHERE 子句可能会更改 内部查询。还有其他限制在 在 pushDownWhereTerms 例程的源代码中进行注释 实现此优化。
16. OUTER JOIN 强度降低优化
外部联接左联接、右联接或完全联接 有时可以简化。可以转换 LEFT 或 RIGHT JOIN 转换为普通内部联接或者 FULL JOIN 可以转换为 LEFT 或 RIGHT JOIN。如果有条款则可能会发生这种情况 在 WHERE 子句中保证简化后的结果相同。 例如如果有 LEFT JOIN 的右侧表中的列必须为非 NULL 为了使 WHERE 子句为 true则 LEFT JOIN 为 降级为普通 JOIN。
确定连接是否可以简化的定理证明器是 缺。它有时会返回假阴性。换言之 它有时无法证明降低 OUTER JOIN 的强度 是安全的而实际上它是安全的。 例如证明者不知道 datetime SQL 函数将始终返回 NULL如果它的第一个 参数为 NULL因此它不会识别 LEFT JOIN 在以下查询中可以降低强度
SELECT urls.urlFROM urlsLEFT JOIN(SELECT *FROM (SELECT url_id AS uid, max(retrieval_time) AS rtimeFROM lookups GROUP BY 1 ORDER BY 1)WHERE uid IN (358341,358341,358341)) recentON u.source_seed_id recent.xyz OR u.url_id recent.xyzWHEREDATETIME(recent.rtime) DATETIME(now, -5 days);
未来对证明器的增强可能会启用它 识别某些内置函数的 NULL 输入 始终导致 NULL 答案。但是并非所有内置 函数具有该属性例如 coalesce 和 当然证明者将永远无法推理应用程序定义的 SQL 函数。
17. 省略 OUTER JOIN 优化
有时LEFT 或 RIGHT JOIN 可以从查询中完全省略而无需 更改结果。如果满足以下所有情况则可能会发生这种情况 真 查询不是聚合查询要么是 DISTINCT要么是 ON 或 USING 子句 on the OUTER JOIN 约束联接使其匹配 只有一行LEFT JOIN 的右侧表或 RIGHT JOIN 不会在任何地方使用 在其自己的 USING 或 ON 子句之外的查询中。
当使用 OUTER JOIN 时通常会出现 OUTER JOIN 消除 在视图中然后以以下方式使用视图 LEFT JOIN 的右侧表上的无列或 在 RIGHT JOIN 的左侧表格中被引用。
下面是一个省略 LEFT JOIN 的简单示例
CREATE TABLE t1(ipk INTEGER PRIMARY KEY, v1);
CREATE TABLE t2(ipk INTEGER PRIMARY KEY, v2);
CREATE TABLE t3(ipk INTEGER PRIMARY KEY, v3);SELECT v1, v3 FROM t1 LEFT JOIN t2 ON (t1.ipkt2.ipk)LEFT JOIN t3 ON (t1.ipkt3.ipk)
t2 表在上面的查询中完全未使用因此 查询规划器能够实现查询就好像它是编写的一样
SELECT v1, v3 FROM t1 LEFT JOIN t3 ON (t1.ipkt3.ipk)
在撰写本文时只有 LEFT JOIN 被消除。这优化了 尚未推广到将 RIGHT JOIN 用作 RIGHT JOIN 是 SQLite 的一个相对较新的补充。这种不对称可能会 在将来的版本中更正。
18. 常量传播优化
当 WHERE 子句包含两个或多个连接的相等约束时 通过 AND 运算符使得各种 约束是相同的那么 SQLite 可能会使用传递属性 的相等性来构造新的“虚拟”约束这些约束可用于 简化表达式和/或提高性能。这称为 “常量传播优化”。
例如请考虑以下架构和查询
CREATE TABLE t1(a INTEGER PRIMARY KEY, b INT, c INT);
SELECT * FROM t1 WHERE ab AND b5;
SQLite 查看“ab”和“b5”约束并推断出 如果这两个约束条件为真那么也必须如此 “a5”是真的。这意味着可以查找所需的行 快速将值 5 用于 INTEGER PRIMARY KEY。
