本文参考文章：https://www.datacamp.com/community/tutorials/sql-tutorial-query#importance
转载请注明出自：葡萄城官网，葡萄城为开发者提供专业的开发工具、解决方案和服务，赋能开发者。
本次我们学习《如何编写更好的SQL查询》系列的最后一篇文章。
时间复杂度和大O符号
通过前两篇文章，我们已经对查询计划有了一定了解。接下来，我们还可以借助计算复杂度理论，来进一步深入地挖掘和思考性能的提升。理论计算机科学这一领域聚焦于：根据难度来对计算问题进行分类。这些计算问题可以是算法问题，也可以是查询问题。
对于查询，我们可以不按照难度进行分类，而是按照运行查询并得到结果所需的时间来进行分类。这种方式也被称为按照时间复杂度进行分类。
使用大O符号，可以根据输入的增长速度来表示运行时间，因为输入可以任意大。大O符号不包括系数和低阶项，以便可以专注于查询运行时间的重要部分：增长率。使用这种方式时，会丢弃系数和低阶项，时间复杂度是逐渐描述出的，这意味着输入会变为无穷大。
在数据库语言中，复杂性衡量了查询运行时间的长短。
请注意，数据库的大小不仅随着表中存储数据的增加而增加，数据库中的索引也会影响数据库大小。
估算查询计划的时间复杂性
执行计划定义了每个操作所使用的算法，这也使得每个查询的执行时间可以在逻辑上表示为查询计划中数据表大小的函数。换句话说，可以使用大O符号和执行计划来估算查询的复杂性和性能。
在下面的小结中，我们将会了解四种类型的时间复杂度概念。
通过这些示例，可以看到查询的时间复杂度会根据运行的查询内容不同而有所不同。
对于不同的数据库，需要考虑不同的索引方式、不同的执行计划和不同的实现方式。
因此以下所列出的时间复杂度概念非常普遍。
O（1）：恒定时间
有一种查询算法，不论输入的大小如何，都需要相同的时间来执行，这种方式就是恒定时间查询。这些类型的查询并不常见，下面是一个例子：
SELECT TOP 1 t.*
FROM t
这种算法的时间复杂度是一个常数，因为只是从表中选择任意一行。因此，时间长度与表的大小无关。
线性时间：O（n）
如果一个算法的时间执行与输入大小成正比，那么算法的执行时间会随着输入大小的增加而增加。对于数据库，这意味着查询执行时间与表大小成正比：随着表中数据行数的增加，查询时间也会相应增加。
一个示例就是在非索引列上使用WHERE子句进行查询：这就需要使用全表扫描或顺序扫描，这将导致O（n）的时间复杂度。这意味着需要读取表中的每一行，以便找到正确ID的数据。即使第一行就查找到了正确的数据，查询还是会对每一行数据进行读取。
如果没有索引，那么这个查询的复杂度为O（n）i_id：
SELECT i_id
FROM item;
- 这也意味像COUNT(*) FROM TABLE这样的计数查询，具有O（n）的时间复杂度，除非存储了数据表的总行数，否则就会进行全表扫描。此时，复杂度将更像是O（1）。
与线性执行时间密切相关的是，所有线性执行计划的时间总和。下面是一些例子：
- 哈希连接（hash join）的复杂度为O（M + N）。两个内部数据表连接的经典哈希连接算法是，首先为较小的数据表准备一个哈希表。哈希表的入口由连接属性和行组成。通过将hash函数应用于join属性，来实现哈希表的访问。一旦构建了哈希表，就会扫描较大的表，并通过查看哈希表来查找较小表中的相关行。
- 合并连接（merge join）的复杂度为O（M + N），但是这种连接严重依赖于连接列上的索引，并且在没有索引的情况下，会根据连接中使用的key对行先进行排序：
- 如果根据连接中使用的key，对两个表进行了排序，那么查询的复杂度为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）或聚集索引扫描的查询计划时间复杂度，就是对数时间。聚集索引是索引的叶级别包含表的实际数据行的索引。聚集与其他索引非常相似：它是在一个或多个列上定义的。这也形成了索引主键。聚集主键是是聚集索引的主键列。聚集索引扫描是聚集索引中RDBMS从头到尾一行一行读取的基本操作。
以下的示例中存在一个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查询。
相关阅读：