企业局域网做网站屏蔽,用illustrator做网站,沈阳网站建设公司哪家好,php 禁止电脑访问网站文章目录 1. 引言2. WHERE子句分析2.1. 索引项使用示例 3. BETWEEN优化4. OR优化4.1. 将OR连接的约束转换为IN运算符4.2. 分别评估OR约束并取结果的并集 5. LIKE优化6. 跳跃扫描优化7. 连接7.1. 手动控制连接顺序7.1.1. 使用 SQLITE_STAT 表手动控制查询计划7.1.2. 使用 CROSS … 文章目录 1. 引言2. WHERE子句分析2.1. 索引项使用示例 3. BETWEEN优化4. OR优化4.1. 将OR连接的约束转换为IN运算符4.2. 分别评估OR约束并取结果的并集 5. LIKE优化6. 跳跃扫描优化7. 连接7.1. 手动控制连接顺序7.1.1. 使用 SQLITE_STAT 表手动控制查询计划7.1.2. 使用 CROSS JOIN 手动控制查询计划 8. 在多个索引之间进行选择8.1. 使用一元 取消 WHERE 子句条件8.2. 范围查询 9. 覆盖索引10. ORDER BY 优化10.1. 通过索引部分 ORDER BY 11. 子查询展平12. 子查询协同程序12.1. 在排序后使用协同程序延迟工作 13. MIN/MAX 优化14. 自动查询时索引14.1. 哈希连接 15. WHERE 子句下推优化16. OUTER JOIN 强度减小优化17. 省略 OUTER JOIN 优化18. 常量传播优化 1. 引言
给定一个SQL语句可能有数十种、数百种甚至数千种方法来实现该语句这取决于语句本身的复杂性和底层数据库模式的复杂性。查询计划的任务是选择最小化磁盘I/O和CPU开销的算法。
2. WHERE子句分析
在分析之前进行以下转换将所有的连接约束转移到WHERE子句中
所有的NATURAL连接被转换为带有USING子句的连接。所有的USING子句包括上一步创建的被转换为等效的ON子句。所有的ON子句包括上一步创建的作为新的连接词AND连接的项添加到WHERE子句中。
SQLite不区分出现在WHERE子句中的连接约束和内连接的ON子句中的约束因为这种区别不会影响结果。然而外连接的ON子句约束和WHERE子句约束是有区别的。因此当SQLite将一个外连接的ON子句约束移动到WHERE子句时它会在抽象语法树AST中添加特殊的标签以指示约束来自外连接并且来自哪个外连接。在纯SQL文本中无法添加这些标签。因此SQL输入必须在外连接上使用ON子句。但在内部AST中所有的约束都是WHERE子句的一部分因为将所有的内容放在一个地方可以简化处理。
在所有的约束都转移到WHERE子句之后WHERE子句被分解为连接词以下称为项。换句话说WHERE子句被分解为由AND运算符分隔的片段。如果WHERE子句由OR运算符析取式分隔的约束组成则整个子句被视为一个项对其应用OR子句优化。
分析WHERE子句的所有项看看它们是否可以使用索引来满足。要被索引使用项通常必须是以下形式之一 column expressioncolumn IS expressioncolumn expressioncolumn expressioncolumn expressioncolumn expressionexpression columnexpression IS 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的项。同样索引列通常不会被使用用于索引目的如果它们在仅受不等式约束的列的右边。请参阅下面的跳过扫描优化以获取例外。
在表达式上的索引的情况下无论上述文本中何时使用“列”这个词都可以替换为“索引表达式”意思是出现在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优化
由OR而不是AND连接的WHERE子句约束可以用两种不同的方式处理。
4.1. 将OR连接的约束转换为IN运算符
如果一个项由多个包含公共列名的子项组成并由OR分隔如下所示 column expr1 OR column expr2 OR column expr3 OR ...那么该项将被重写为以下形式 column IN (expr1,expr2,expr3,...)然后重写的项可能会按照IN运算符的正常规则约束索引。请注意列必须在每个OR连接的子项中都是相同的列尽管列可以出现在运算符的左边或右边。
4.2. 分别评估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)上面的重写表达式是概念性的包含OR的WHERE子句实际上并没有以这种方式重写。实际上OR子句的实现使用了一种更高效的机制即使对于WITHOUT ROWID表或rowid不可访问的表也可以工作。然而通过上述语句可以捕捉到实现的本质对于每个OR子句项使用单独的索引查找候选结果行最终结果是这些行的并集。
请注意在大多数情况下SQLite只会为查询的FROM子句中的每个表使用一个索引。这里描述的第二个OR子句优化是该规则的例外。对于OR子句每个子项可能使用不同的索引。
对于任何给定的查询这里描述的OR子句优化可以使用的事实并不保证它会被使用。SQLite使用基于成本的查询计划器估计各种竞争查询计划的CPU和磁盘I/O成本并选择它认为最快的计划。如果WHERE子句中有许多OR项或者如果某些OR子句子项上的索引不是很有选择性那么SQLite可能会决定使用不同的查询算法甚至全表扫描。应用程序开发人员可以在语句前面使用EXPLAIN QUERY PLAN前缀以获取所选查询策略的高级概述。
5. LIKE优化
使用LIKE或GLOB运算符的WHERE子句项有时可以与索引一起使用以进行范围搜索就像LIKE或GLOB是BETWEEN运算符的替代品一样。这种优化有许多条件
LIKE或GLOB的右侧必须是一个字符串字面量或者一个绑定到不以通配符字符开头的字符串字面量的参数。不能通过在LIKE或GLOB运算符的左侧有一个数值而不是字符串或blob使LIKE或GLOB运算符为真。这意味着 LIKE或GLOB运算符的左侧是具有TEXT亲和性的索引列的名称或者右侧的模式参数不以负号“-”或数字开头。 这个约束源于数字不按字典顺序排序的事实。例如910但’9’‘10’。 不能使用sqlite3_create_function() API来重载实现LIKE和GLOB的内置函数。对于GLOB运算符列必须使用内置的BINARY排序序列进行索引。对于LIKE运算符如果启用了case_sensitive_like模式则列必须使用BINARY排序序列进行索引如果禁用了case_sensitive_like模式则列必须使用内置的NOCASE排序序列进行索引。如果使用了ESCAPE选项则ESCAPE字符必须是ASCII或者在UTF-8中是单字节字符。
LIKE运算符有两种模式可以通过pragma设置。默认模式是让LIKE比较对于拉丁1字符的大小写不敏感。因此默认情况下以下表达式为真
a LIKE A如果启用了case_sensitive_like pragma如下所示
PRAGMA case_sensitive_likeON;那么LIKE运算符将注意大小写上面的示例将被评估为假。注意大小写不敏感只适用于拉丁1字符 - 基本上是ASCII的低127字节代码中的英文大写和小写字母。SQLite中的国际字符集是大小写敏感的除非提供了考虑非ASCII字符的应用程序定义的排序序列和like() SQL函数。如果提供了应用程序定义的排序序列和/或like() SQL函数那么这里描述的LIKE优化将永远不会被采用。
LIKE运算符默认是大小写不敏感的因为这是SQL标准要求的。你可以在编译时使用SQLITE_CASE_SENSITIVE_LIKE命令行选项更改默认行为。
LIKE优化可能会发生如果运算符左边的列名使用内置的BINARY排序序列进行索引并且case_sensitive_like已经打开。或者优化可能会发生如果列使用内置的NOCASE排序序列进行索引并且case_sensitive_like模式关闭。这些是LIKE运算符将被优化的唯一两种组合。
GLOB运算符总是区分大小写。GLOB运算符左边的列必须始终使用内置的BINARY排序序列否则不会尝试使用索引优化该运算符。
只有当GLOB或LIKE运算符的右侧是字面字符串或绑定到字面字符串的参数时才会尝试LIKE优化。字符串字面量不能以通配符开头如果右侧以通配符字符开头则不会尝试此优化。如果右侧是绑定到字符串的参数那么只有在包含表达式的预编译语句使用sqlite3_prepare_v2()或sqlite3_prepare16_v2()编译时才会尝试此优化。如果右侧是参数并且语句使用sqlite3_prepare()或sqlite3_prepare16()准备则不会尝试LIKE优化。
假设LIKE或GLOB运算符的右侧的非通配符字符的初始序列是x。我们使用单个字符来表示这个非通配符前缀但读者应该理解前缀可以由多于1个字符组成。让y是与/x/长度相同但比x大的最小字符串。例如如果x是’hello’那么y将是’hellp’。然后LIKE或GLOB优化将运算符重写为以下形式 column x AND column y然后优化器将尝试使用索引来满足这两个新的虚拟约束。如果成功那么将使用索引来满足LIKE或GLOB运算符。如果失败那么将回退到全表扫描。在任何情况下都将使用LIKE或GLOB运算符对所有候选行进行测试以确保它们符合LIKE或GLOB模式。这是因为索引只能用于确定前缀匹配。索引不能用于处理LIKE或GLOB模式中可能出现的通配符。
6. 跳跃扫描优化
一般规则是索引只有在 WHERE 子句约束了索引的最左侧列时才有用。然而在某些情况下即使索引的前几列被 WHERE 子句省略但后面的列被包含SQLite 也能够使用索引。
考虑如下表
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 表包含了一个大型组织中的每个人的条目。每个人要么是 “student”要么是 “teacher”由 “role” 字段确定。该表还记录了每个人的身高以厘米为单位。角色和身高都被索引。注意索引的最左侧列的选择性不高 - 它只包含两个可能的值。
现在考虑一个查询找出组织中身高为180cm或更高的每个人的名字
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” 值存储在一个我们在这里称为 “ r o l e 的内部变量中。然后 S Q L i t e 运行一个类似于 S E L E C T n a m e F R O M p e o p l e W H E R E r o l e role 的内部变量中。然后 SQLite 运行一个类似于 SELECT name FROM people WHERE role role的内部变量中。然后SQLite运行一个类似于SELECTnameFROMpeopleWHERErolerole AND height180” 的查询。这个查询在索引的最左侧列上有一个相等约束所以索引可以用来解决这个查询。一旦这个查询完成SQLite 然后使用 “people_idx1” 索引来定位 “role” 列的下一个值使用的代码在逻辑上类似于 “SELECT role FROM people WHERE role$role LIMIT 1”。这个新的 “role” 值覆盖了 $role 变量这个过程重复直到检查了所有可能的 “role” 值。
我们称这种索引使用方式为 “跳跃扫描”因为数据库引擎基本上是在对索引进行全扫描但是通过偶尔跳跃到下一个候选值来优化扫描使其少于 “全”。
SQLite 可能会在索引上使用跳跃扫描如果它知道第一列或更多列包含许多重复值。如果在索引的最左侧列中有太少的重复项那么简单地向前走到下一个值从而进行全表扫描会比在索引上进行二分搜索来定位下一个左列值更快。
SQLite 只有在对数据库运行 ANALYZE 命令后才能知道索引的最左侧列中有许多重复项。没有 ANALYZE 的结果SQLite 不得不猜测表中数据的 “形状”默认猜测是在索引的最左侧列中每个值有平均10个重复项。当重复项的数量大约为18个或更多时跳跃扫描才变得有利可图它只是比全表扫描更快。因此在没有分析过的数据库上永远不会使用跳跃扫描。
7. 连接
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这两个实现选项中每个循环都使用相同的索引来加速。这两个查询计划的唯一区别是循环的嵌套顺序。
那么哪个查询计划更好呢结果取决于节点表和边表中的数据类型。
假设有 M 个 alice 节点N 个 bob 节点。考虑两种情况。在第一种情况中M 和 N 都为2但每个节点有数千条边。在这种情况下选项1更优。对于选项1内循环检查一对节点之间是否存在边并在找到时输出结果。因为只有2个 alice 和 bob 节点所以内循环只需要运行四次查询就非常快了。选项2在这里会花费更长的时间。选项2的外循环只执行两次但因为每个 alice 节点都有大量的边所以中间循环必须迭代数千次。它会慢得多。所以在第一种情况下我们更倾向于使用选项1。
现在考虑 M 和 N 都为3500的情况。Alice 节点非常多。这次假设这些节点中的每一个只通过一两条边连接。现在选项2更优。对于选项2外循环仍然需要运行3500次但是每个外循环中中间循环只运行一次或两次内循环只有在每个中间循环中才会运行一次如果有的话。所以内循环的总迭代次数大约是7000次。另一方面选项1必须分别运行其外循环和中间循环3500次导致中间循环的迭代次数达到1200万次。因此在第二种情况下选项2比选项1快近2000倍。
所以你可以看到根据表中数据的结构查询计划1或查询计划2可能更好。SQLite 默认选择哪个计划呢在3.6.18版本中如果没有运行 ANALYZESQLite 将选择选项2。如果运行了 ANALYZE 命令以收集统计信息如果统计信息表明另一种选择可能运行得更快可能会做出不同的选择。
7.1. 手动控制连接顺序
SQLite 几乎总是自动选择最佳的连接顺序。很少有开发者需要干预来给查询规划器提供关于最佳连接顺序的提示。最好的策略是使用 PRAGMA optimize 确保查询规划器可以访问数据库中数据形状的最新统计信息。
本节描述了开发者如何控制 SQLite 中的连接顺序以解决可能出现的任何性能问题。然而除非作为最后的手段否则不推荐使用这些技术。
如果你遇到一个情况即使在运行 PRAGMA optimize 后SQLite 仍然选择了次优的连接顺序请在 SQLite 社区论坛上报告你的情况以便 SQLite 的维护者可以对查询规划器进行新的改进使得不需要手动干预。
7.1.1. 使用 SQLITE_STAT 表手动控制查询计划
SQLite 提供了一种能力让高级程序员可以控制优化器选择的查询计划。一种方法是在 sqlite_stat1 表中篡改 ANALYZE 的结果。
7.1.2. 使用 CROSS JOIN 手动控制查询计划
程序员可以通过使用 CROSS JOIN 运算符而不是 JOIN、INNER JOIN、NATURAL JOIN 或 “,” 连接强制 SQLite 使用特定的循环嵌套顺序。尽管理论上 CROSS JOIN 是可交换的但 SQLite 选择永远不重新排序 CROSS JOIN 中的表。因此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 中的表会改变结果。
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 索引查找 ex2 中包含 x5 的行然后针对 y6 项测试每一行。或者它可以使用 ex2i2 索引查找 ex2 中包含 y6 的行然后针对 x5 项测试每个行。
在面临两个或多个索引的选择时SQLite 尝试估计使用每个选项执行查询所需的总工作量。然后选择估计工作量最少的选项。
为了帮助优化器更准确地估计使用各种索引涉及的工作量用户可以选择运行 ANALYZE 命令。ANALYZE 命令扫描数据库中可能在两个或多个索引之间进行选择的所有索引并收集有关这些索引的选择性的统计信息。此扫描收集的统计信息存储在以 “sqlite_stat” 开头的特殊数据库表中。这些表的内容不会随着数据库的更改而更新因此在进行重大更改后重新运行 ANALYZE 可能是明智的。ANALYZE命令的结果仅对在 ANALYZE 命令完成后打开的数据库连接可用。
各种 sqlite_statN 表包含有关各种索引选择性的信息。例如sqlite_stat1 表可能指示列 x 上的等式约束平均将搜索空间减少到10行而列 y 上的等式约束平均将搜索空间减少到3行。在这种情况下SQLite 会更喜欢使用 ex2i2 索引因为该索引更具选择性。
8.1. 使用一元 “” 取消 WHERE 子句条件
请注意以这种方式取消 WHERE 子句条件不是推荐的做法。这是一种变通方法。只有在作为最后手段来获得所需性能时才这样做。
可以通过在列名前加上一元 运算符来手动取消 WHERE 子句中的条件以用于索引。一元 是一个空操作不会在预处理语句中生成任何字节码。然而一元 运算符将阻止该项约束索引。因此在上面的示例中如果查询被重写为
SELECT z FROM ex2 WHERE x5 AND y6;x 列上的 运算符将阻止该项约束索引。这将强制使用 ex2i2 索引。
注意一元 运算符还会从表达式中删除类型关联而在某些情况下这可能导致表达式含义的微妙变化。在上面的示例中如果列 x 具有 TEXT 关联则比较 “x5” 将作为文本进行。 运算符删除了关联。因此比较 “x5” 将把列 x 中的文本与数字值 5 进行比较结果总是为假。
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 将使用索引中的值而永远不会查找原始表行。这节省了每行的一次二分查找可以使许多查询运行速度加倍。
当一个索引包含查询所需的所有数据并且原始表永远不需要被查询时我们称该索引为 “覆盖索引”。
10. ORDER BY 优化
SQLite 尝试使用索引来满足查询的 ORDER BY 子句。当面临使用索引满足 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必须满足一长串条件才能进行查询展平。其中一些约束由斜体文本标记为过时。这些额外的约束保留在文档中以保留其他约束的编号。
这里的重点是展平规则是微妙而复杂的。多年来由于过于激进的查询展平导致了多个错误。另一方面如果查询展平更保守那么复杂查询和/或涉及视图的查询的性能可能会受到影响。
查询展平是使用视图时的重要优化。视图是嵌套查询因此查询展平通常可以将视图查询的部分或全部并入调用查询从而提高性能。
在某些情况下查询展平可能会导致查询性能下降。这主要是因为展平的查询可能会导致更大的联接而更大的联接可能会导致查询计划的搜索空间变得更大从而导致查询优化器无法找到最佳的查询计划。SQLite 允许在视图和子查询名之前加上 “NOT INDEXED” 来禁止查询展平。例如
SELECT * FROM my_view NOT INDEXED WHERE ...;在上面的查询中“my_view” 视图将被评估为一个单独的临时表然后临时表将被插入到外部查询中。这可能会导致查询性能下降但如果查询展平导致查询优化器无法找到最佳的查询计划那么这可能会提高性能。在这种情况下“NOT INDEXED” 是一种有用的工具。
12. 子查询协同程序
SQLite 以三种方式之一实现 FROM 子句子查询
将子查询展平到其外部查询将子查询评估为一个临时表该表在执行的一个 SQL 语句的持续时间内存在然后针对该临时表运行外部查询。在与外部查询并行运行的协同程序中评估子查询根据需要向外部查询提供行。
本节描述了第三种技术将子查询实现为协同程序。
协同程序类似于子程序它在与调用者相同的线程中运行并最终将控制权返回给调用者。不同之处在于协同程序还具有在完成之前返回的能力然后在下次调用时从中断的地方继续。
当子查询作为协同程序实现时生成字节码以实现子查询就像它是一个独立的查询一样只是在计算每一行后协同程序将控制权返回给调用者而不是将结果行返回给应用程序。调用者可以使用计算出的一行作为其计算的一部分然后在准备好下一行时再次调用协同程序。
与在临时表中存储子查询的完整结果集相比协同程序更好因为协同程序使用的内存更少。对于协同程序只需要记住结果的一行而对于临时表需要存储所有结果行。此外由于协同程序在外部查询开始工作之前不需要运行到完成因此输出的第一行可以更快地出现并且如果整个查询在完成之前被放弃总体工作量会减少。
另一方面如果子查询的结果必须多次扫描例如因为它是连接中的一个表那么最好使用临时表来记住子查询的整个结果以避免多次计算子查询。
12.1. 在排序后使用协同程序延迟工作
从 SQLite 版本 3.21.02017-10-24开始查询规划器将始终优先使用协同程序实现包含 ORDER BY 子句且不是连接的 FROM 子句子查询当外部查询的结果集是“复杂”的时候。此功能允许应用程序在排序后将昂贵的计算从排序前移出从而实现更快的操作。例如考虑以下查询
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.02018-01-22如果外部查询在其结果集中不使用任何用户定义的函数或子查询查询规划器将展平子查询。然而对于上面显示的示例SQLite 按照编写的查询实现每个查询。
13. MIN/MAX 优化
包含单个 MIN() 或 MAX() 聚合函数的查询其参数是索引的最左列可以通过执行单个索引查找而不是扫描整个表来满足。例如
SELECT MIN(x) FROM table;
SELECT MAX(x)1 FROM table;14. 自动查询时索引
当没有索引可用于辅助查询评估时SQLite 可能会创建一个仅在单个 SQL 语句的持续时间内存在的自动索引。自动索引有时也称为“查询时索引”。由于构造自动或查询时索引的成本是 O(NlogN)其中 N 是表中的条目数而执行完整表扫描的成本仅为 O(N)因此仅当 SQLite 预计在 SQL 语句执行过程中查找将运行超过 logN 次时才会创建自动索引。考虑一个例子
CREATE TABLE t1(a,b);
CREATE TABLE t2(c,d);
-- 向 t1 和 t2 插入许多行
SELECT * FROM t1, t2 WHERE ac;在上面的查询中如果 t1 和 t2 都有大约 N 行那么在没有任何索引的情况下查询将需要 O(N*N) 时间。另一方面创建表 t2 上的索引需要 O(NlogN) 时间使用该索引评估查询需要额外的 O(NlogN) 时间。在没有 ANALYZE 信息的情况下SQLite 猜测 N 是一百万因此它相信构造自动索引将是更便宜的方法。
自动查询时索引还可以用于子查询
CREATE TABLE t1(a,b);
CREATE TABLE t2(c,d);
-- 向 t1 和 t2 插入许多行
SELECT a, (SELECT d FROM t2 WHERE cb) FROM t1;在这个例子中t2 表用于子查询来转换 t1.b 列的值。如果每个表包含 N 行SQLite 预计子查询将运行 N 次因此它会认为首先在 t2 上构建一个自动的临时索引然后使用该索引满足子查询的 N 个实例是更快的方法。
使用自动索引功能可以在运行时使用 automatic_index 条目禁用。自动索引默认是开启的但可以使用 SQLITE_DEFAULT_AUTOMATIC_INDEX 编译时选项将其更改为默认关闭。通过使用 SQLITE_OMIT_AUTOMATIC_INDEX 编译时选项完全禁用创建自动索引的功能。
在 SQLite 版本 3.8.02013-08-26及更高版本中每次准备使用自动索引的语句时都会将 SQLITE_WARNING_AUTOINDEX 消息发送到错误日志。应用程序开发人员可以并且应该使用这些警告来识别模式中需要新的持久性索引的需求。
请勿将自动索引与有时用于实现 PRIMARY KEY 约束或 UNIQUE 约束的内部索引名称类似于 “sqlite_autoindex_table_N”混淆。这里描述的自动索引仅在单个查询的持续时间内存在永远不会持久化到磁盘并且仅对单个数据库连接可见。内部索引是实现 PRIMARY KEY 和 UNIQUE 约束的一部分是长期持久化到磁盘的并且对所有数据库连接可见。内部索引的名称中出现了 “autoindex” 一词是由于历史原因并不表明内部索引和自动索引有关。
14.1. 哈希连接
自动索引几乎与哈希连接相同。唯一的区别是使用 B-Tree 而不是哈希表。如果你愿意说为自动索引构造的临时 B-Tree 实际上只是一个花哨的哈希表那么使用自动索引的查询就是一个哈希连接。
SQLite 在这种情况下构造临时索引而不是哈希表因为它已经有了一个健壮且高性能的 B-Tree 实现而哈希表需要添加。为了处理这一情况而添加一个单独的哈希表实现会增加库的大小该库设计用于低内存嵌入式设备并带来最小的性能增益。SQLite 可能会在某一天增强哈希表实现但是现在在客户端/服务器数据库引擎可能使用哈希连接的情况下继续使用自动索引似乎更好。
15. WHERE 子句下推优化
如果子查询不能展平到外部查询可能仍然可以通过将 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;WHERE 子句下推优化不能总是使用。例如如果子查询包含 LIMIT那么从外部查询下推 WHERE 子句的任何部分都可能改变内部查询的结果。还有其他限制这在源代码中实现此优化的 pushDownWhereTerms() 函数的注释中有解释。
不要将此优化与 MySQL 中名称相似的优化混淆。MySQL 的下推优化改变了 WHERE 子句约束的评估顺序使得可以仅使用索引而不需要找到对应的表行的约束先被评估从而避免在约束失败时不必要的表行查找。为了消除歧义SQLite 称其为 “MySQL 下推优化”。SQLite 也做了 MySQL 下推优化除了 WHERE 子句下推优化。但是本节的重点是 WHERE 子句下推优化。
16. OUTER JOIN 强度减小优化
OUTER JOINLEFT JOINRIGHT JOIN 或 FULL JOIN有时可以简化。LEFT 或 RIGHT JOIN 可以转换为普通INNERJOIN或者 FULL JOIN 可能被转换为 LEFT 或 RIGHT JOIN。如果 WHERE 子句中的条件可以保证简化后的结果相同那么就可以发生这种情况。例如如果 LEFT JOIN 的右表中的任何列必须为非 NULL 以使 WHERE 子句为真那么 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或者 OUTER JOIN 的 ON 或 USING 子句约束连接使其只匹配一行LEFT JOIN 的右表或 RIGHT JOIN 的左表在查询中的任何地方都不会在其自己的 USING 或 ON 子句之外使用。
当 OUTER JOIN 用于视图内部然后以不引用 LEFT JOIN 的右表或 RIGHT JOIN 的左表的任何列的方式使用视图时通常会出现 OUTER 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 快速查找所需的行。
