🙍 📻 👆🏽 SQL指南：如何更好地编写查询（第2部分） 🎩 🤮 🛶

从请求到执行计划

知道反模式不是一成不变的，并且随着您作为SQL开发人员的成长而发展，并且在考虑替代方案时要记住很多事情，这也意味着避免反模式和重写查询可能非常困难。任务。任何帮助都可以派上用场，这就是为什么使用某些工具来结构化查询优化的方法可能最有效。

还应该注意的是，上一节中提到的某些反模式源自性能问题，例如AND ， OR和NOT运算符，以及它们在使用索引时的缺失。关于性能的思考不仅需要更结构化的方法，而且还需要更深层次的方法。

但是，这种结构化且深入的方法将主要基于查询计划，您记得，查询计划是将查询首先解析为“解析树”或“解析树”并确定哪种算法的结果。用于每个操作以及如何协调它们的执行。

查询优化

在阅读简介时，您可能需要检查并设置由优化程序手动编译的计划。在这种情况下，您将需要通过查看请求计划来再次分析您的请求。

要访问此计划，必须使用数据库管理系统提供的工具。您可以使用以下工具：

一些软件包包含生成查询计划的图形表示的工具。考虑以下示例：
其他工具将提供查询计划的文字描述。一个示例是Oracle中的EXPLAIN PLAN语句，但是指令的名称取决于您使用的DBMS。在其他地方，您可以找到EXPLAIN （MySQL，PostgreSQL）或EXPLAIN QUERY PLAN （SQLite）。

请注意 ，在使用PostgreSQL时，您可以在EXPLAIN之间进行区分，在EXPLAIN ，您仅获得描述，告诉您计划者打算如何执行查询而不执行查询，而EXPLAIN ANALYZE实际上执行查询并返回分析预期和实际的请求计划。一般而言，实际执行计划是实际执行请求的计划，而评估执行计划确定在不满足请求的情况下将执行的操作。尽管从逻辑上讲这是等效的，但是实际执行计划更为有用，因为它包含有关执行请求时实际发生情况的其他信息和统计信息。

在本节的其余部分，您将了解有关EXPLAIN和ANALYZE更多信息，以及如何使用它们来获取有关查询计划及其可能的性能的更多信息。为此，请从几个示例开始，在其中将使用两个表： one_million和half_million 。

您可以使用EXPLAIN从one_million表中获取当前信息；确保将其直接放置在请求上方，执行之后，它将向您返回查询计划：

 EXPLAIN SELECT * FROM one_million; QUERY PLAN ____________________________________________________ Seq Scan on one_million (cost=0.00..18584.82 rows=1025082 width=36) (1 row)

在这种情况下，您看到请求的成本为0.00..18584.82 ，并且行数为1025082 。列数的宽度是36 。

另外，您可以使用ANALYZE更新统计信息。

 ANALYZE one_million; EXPLAIN SELECT * FROM one_million; QUERY PLAN ____________________________________________________ Seq Scan on one_million (cost=0.00..18334.00 rows=1000000 width=37) (1 row)

除了EXPLAIN和ANALYZE ，您还可以使用EXPLAIN ANALYZE获得实际的运行时：

 EXPLAIN ANALYZE SELECT * FROM one_million; QUERY PLAN ___________________________________________________________ Seq Scan on one_million (cost=0.00..18334.00 rows=1000000 width=37) (actual time=0.015..1207.019 rows=1000000 loops=1) Total runtime: 2320.146 ms (2 rows)

使用EXPLAIN ANALYZE的缺点是查询实际上是在执行的，因此要小心！

到目前为止，您所看到的所有算法都是Seq Scan （顺序扫描）或全表扫描：这是在数据库中执行的扫描，其中扫描表的每一行都是按顺序读取的，并检查找到的列是否存在是否符合条件。在性能方面，顺序扫描绝对不是最佳的执行计划，因为您仍在进行全表扫描。但是，当表不能容纳在内存中时，这并不是很糟糕：即使在慢速磁盘上，顺序读取也相当快。

稍后当我们讨论索引扫描时，您将学到更多有关此的知识。

但是，还有其他算法。例如，以下关于连接的查询计划：

 EXPLAIN ANALYZE SELECT * FROM one_million JOIN half_million ON (one_million.counter=half_million.counter); QUERY PLAN _________________________________________________________________ Hash Join (cost=15417.00..68831.00 rows=500000 width=42) (actual time=1241.471..5912.553 rows=500000 loops=1) Hash Cond: (one_million.counter = half_million.counter) -> Seq Scan on one_million (cost=0.00..18334.00 rows=1000000 width=37) (actual time=0.007..1254.027 rows=1000000 loops=1) -> Hash (cost=7213.00..7213.00 rows=500000 width=5) (actual time=1241.251..1241.251 rows=500000 loops=1) Buckets: 4096 Batches: 16 Memory Usage: 770kB -> Seq Scan on half_million (cost=0.00..7213.00 rows=500000 width=5) (actual time=0.008..601.128 rows=500000 loops=1) Total runtime: 6468.337 ms

您会看到查询优化器在这里选择了Hash Join ！请记住此操作，因为您需要它来评估请求的时间复杂度。现在，请注意， half_million.counter没有索引，我们在以下示例中添加该索引：

 CREATE INDEX ON half_million(counter); EXPLAIN ANALYZE SELECT * FROM one_million JOIN half_million ON (one_million.counter=half_million.counter); QUERY PLAN ________________________________________________________________ Merge Join (cost=4.12..37650.65 rows=500000 width=42) (actual time=0.033..3272.940 rows=500000 loops=1) Merge Cond: (one_million.counter = half_million.counter) -> Index Scan using one_million_counter_idx on one_million (cost=0.00..32129.34 rows=1000000 width=37) (actual time=0.011..694.466 rows=500001 loops=1) -> Index Scan using half_million_counter_idx on half_million (cost=0.00..14120.29 rows=500000 width=5) (actual time=0.010..683.674 rows=500000 loops=1) Total runtime: 3833.310 ms (5 rows)

您会看到，通过创建索引，查询优化器现在决定在扫描“ Index Scan索引时使用Merge join 。

请注意索引扫描与全表扫描或顺序扫描之间的区别：第一个（也称为“表扫描”）扫描数据或索引页以找到相应的记录，而第二个扫描表的每一行。

您会看到总体运行时间有所减少，性能应该会更好，但是有两次索引扫描，这使得内存在这里尤为重要，尤其是在表不适合其中的情况下。在这种情况下，您必须首先执行全索引扫描，这是使用快速顺序读取执行的，这不是问题，但是随后您将执行许多随机读取操作，以按索引值选择行。这些是随机读取操作，通常比顺序读取要慢几个数量级。在这些情况下，全表扫描确实比全索引扫描更快。

提示：如果您想了解更多有关EXPLAIN的信息或更详细地考虑示例，请考虑阅读Guillaume Lelarge的《理解说明》。

时间复杂度和大O

现在，您已经简要回顾了查询计划，可以开始使用计算复杂性理论更深入地研究并以更正式的术语考虑性能。这是理论计算机科学领域，除其他事项外，它着重于根据计算问题的复杂性进行分类。这些计算问题可能是算法，也可能是查询。

但是，对于查询，不一定根据其复杂性对它们进行分类，而是取决于完成查询和获得结果所需的时间。这称为时间复杂度，您可以使用大号O表示法来表示或测量这种类型的复杂度。

使用大O表示，您可以根据输入随心所欲地相对于输入的增长速度来表示运行时间。大号O表示法排除系数和低阶成员，因此您可以专注于查询执行时间的重要部分：其增长率。当以这种方式表示时，丢弃低阶的系数和项，他们说时间复杂度是渐近描述的。这意味着输入大小将变为无穷大。

在数据库语言中，复杂度决定了随着数据表的大小以及数据库的增长，完成查询所花费的时间。

请注意 ，数据库的大小不仅因表中数据量的增加而增加，而且存在索引的事实也对大小起作用。

估算查询计划的时间复杂度

如您先前所见，执行计划除其他事项外，确定用于每个操作的算法，这使您可以根据查询计划中包含的表的大小来逻辑表示每个查询的执行时间，这称为复杂度函数。换句话说，您可以使用大O表示法和执行计划来评估查询的复杂性和性能。

在以下各节中，您将概述四种类型的时间复杂度，并看到一些示例，这些示例说明了查询的时间复杂度如何根据执行上下文的不同而变化。

提示：索引是这个故事的一部分！

但是，应该注意的是，对于不同的数据库，索引的类型不同，执行计划不同，实现方式也不同，因此下面列出的临时困难非常普遍，可能会因具体设置而异。

O（1）：恒定时间

他们说，如果算法需要相同的时间量，则无论输入数据的大小如何，算法都将在恒定时间内工作。对于查询，无论表的大小如何，如果需要相同的时间量，它将在固定时间内执行。

这种查询并不是很常见，但是下面是一个这样的示例：

 SELECT TOP 1 t.* FROM t

由于从表中选择了任意一行，因此时间复杂度是恒定的。因此，时间长度不应取决于表的大小。

线性时间：O（n）

他们说，如果算法的执行时间与输入数据的大小成正比，则该算法以线性时间工作，也就是说，时间随输入数据的大小线性增加。对于数据库，这意味着执行时间将与表的大小成正比：随着表中行数的增加，查询的执行时间会增加。

一个示例是使用WHERE查询未索引的列：将需要全表扫描或Seq Scan ，这将导致O（n）时间复杂度。这意味着必须阅读每一行才能找到具有所需标识符（ID）的行。您根本没有任何限制，因此即使第一行符合条件，您也需要对每一行进行计数。

还考虑以下查询示例，如果i_id字段上没有索引，则查询示例的复杂度为O（n）：

 SELECT i_id FROM item;

前面的内容还意味着其他查询，例如计算COUNT (*) FROM TABLE;的行数的查询COUNT (*) FROM TABLE; 将具有O（n）的时间复杂度，因为由于尚未保存表的总行数，因此需要进行全表扫描。否则，时间复杂度将类似于O（1） 。

线性运行时间与具有表联接的计划的运行时间密切相关。以下是一些示例：

哈希联接的预期复杂度为O（M + N），用于内部联接两个表的经典哈希联接算法首先准备较小表的哈希表。哈希表条目由连接属性及其字符串组成。通过将哈希函数应用于连接属性来访问哈希表。构建哈希表后，将扫描大型表，并通过搜索哈希表找到较小表中的相应行。
合并联接通常具有O（M + N）复杂度，但是它在很大程度上取决于联接列索引，如果没有索引，则是否根据联接中使用的键对行进行排序：
- 如果两个表均根据联接中使用的键进行排序，则查询的时间复杂度为O（M + N）。
- 如果两个表都具有连接列的索引，则索引已经按顺序支持了这些列，并且不需要排序。难度为O（M + N）。
- 如果没有一个表在连接的列上有索引，则必须首先对两个表进行排序，以使复杂度看起来像O（M log M + N log N）。
- 如果只有一个表在连接的列上具有索引，则在连接步骤发生之前仅必须对没有索引的表进行排序，以使复杂度看起来像O（M + N log N）。
对于嵌套联接，复杂度通常为O（MN）。当一个或两个表都非常小（例如，少于10条记录）时，此联接有效。在评估查询时，这是很常见的情况，因为某些子查询被编写为仅返回一行。

请记住：嵌套联接是将一个表中的每个记录与另一个表中的每个记录进行比较的联接。

对数时间：O（log（n））

据说，如果算法的执行时间与输入大小的对数成正比，则该算法以对数时间工作；对于查询，这意味着如果执行时间与数据库大小的对数成正比，则将执行查询。

此对数时间复杂度对于Index Scan或聚集索引的查询计划有效。聚集索引是一个索引，其中最终索引级别包含表的实际行。聚集索引与任何其他索引相似：它在一个或多个列中定义。它们形成索引键。聚簇键是聚簇索引的键列。扫描聚簇索引基本上是从DBMS中读取聚簇索引中从上到下的一行或多行的操作。

考虑以下查询示例，其中有一个i_id索引，通常会导致O（log（n））复杂度：

 SELECT i_stock FROM item WHERE i_id = N;

注意，没有索引，时间复杂度将为O（n）。

二次时间：O（n ^ 2）

如果算法的执行时间与输入大小的平方成正比，则可以认为算法以二次时间执行。同样，对于数据库，这意味着查询执行时间与数据库大小的平方成正比。

二次时间复杂度查询的一个可能示例如下：

 SELECT * FROM item, author WHERE item.i_a_id=author.a_id

基于连接属性的索引信息，最小复杂度可以是O（n log（n）），但是最大复杂度可以是O（n ^ 2）。

总而言之，您还可以查看以下备忘单，根据其时间复杂度和有效性来评估查询性能：

SQL调优

给定查询执行计划和时间复杂度，您可以进一步自定义SQL查询。您可以从以下几点开始：

用索引扫描代替不必要的全表扫描；
确保应用了最佳加入顺序。
确保最佳使用索引。和
使用小表的全文本扫描的缓存（缓存小表的全表扫描。）。

进一步使用SQL

恭喜你！您已经到了本文的结尾，这里只是简要介绍了SQL查询的性能。希望您了解有关反模式，查询优化器以及可用于分析，评估和解释查询计划的复杂性的工具的更多信息。但是，您仍有很多发现！如果您想了解更多信息，请阅读R. Ramakrishnan和J. Gehrke撰写的“数据库管理系统”一书。

最后，我不想在这句话中拒绝您的StackOverflow：

我最喜欢的反模式不会检查您的请求。

但是，它适用于以下情况：

您的查询提供多个表。
您认为您已经为请求设计了最佳的产品，但是不要尝试验证您的假设。
您接受第一个工作请求，却不知道它与最佳请求有多接近。

SQL指南：如何更好地编写查询（第2部分）