架构、Java、前端、AI技术汇

肖继潮的技术博客

【译】SQL 教程：如何编写更佳的查询

发表于 热度： ℃ 评论数：

原文：http://www.zcfy.cc/article/4011

结构化查询语言（SQL）是数据科学行业中一项不可或缺的技能，一般来说，学习这个技能是挺容易的。不过，很多人都忘记了写查询只是SQL的第一步。我们还得确保查询性能优异，或者符合正在工作的上下文环境。

正因为如此，本SQL教程将让你瞧瞧某些步骤，我们可以通过这些步骤来评估查询：

  • 首先，我们从简要介绍数据科学工作中学习SQL的重要性开始；

  • 接下来，我们将首先学习更多有关SQL查询处理和执行的信息，这样就可以正确理解编写高质量查询的重要性：更具体地说，就是我们将看到查询被解析、重写、优化和最终求值；

  • 考虑到这一点，我们不仅会重温初学者在编写查询时所做的一些查询反模式，而且还会学习更多针对那些可能的错误的替代方案和解决方案；还会学到更多有关基于集合的查询方法与过程式查询方法的知识。

  • 我们还会看到，这些反模式源于性能考虑，并且除了用“手动”方法来提升SQL查询之外，还可以通过使用能帮助我们查看查询计划的一些其他工具，以更结构化、更深入的方式分析查询；并且，

  • 我们会大致进一步深入时间复杂度和大O表示法，从而在执行查询之前，搞清楚执行计划的时间复杂度；最后，

  • 我们会大致获得一些关于如何进一步调整查询的指示。

数据科学为什么要学SQL？

SQL远没有死亡：它是我们从数据科学行业的职业描述中找到的最需要的技能之一，无论你是申请数据分析师、数据工程师、数据科学家，还是任何其他角色。2016年O’Reilly数据科学薪资调查报告时，70％的受访者证实了这一点，他们都表明在其专业背景中用到了SQL。此外，在本次调查中，SQL远胜于R（57％）和Python（54％）编程语言。

所以你明白了吧：如果要在数据科学行业谋求一份差事，那么SQL就是一项必备的技能。

这对一门在20世纪70年代初就被开发出来的语言来说还不赖，对吧？

那么到底SQL为什么被这样频繁地使用呢？为什么它即使已经存在了这么长时间还不死呢？

这里有几个原因：首要原因之一是公司大多将数据存储在关系型数据库管理系统（RDBMS）或关系型数据流管理系统（RDSMS）中，而我们需要SQL才能访问其中的数据。SQL是数据的通用语言：它能让我们与几乎任何数据库进行交互，甚至可以在本地建立自己的数据库！

如果这还不够，那么请记住，不少厂商之间的SQL实现并不兼容，而且不一定遵循标准。因此，了解标准SQL是我们在（数据科学）行业中找条活路的一个需求。

除此之外，可以肯定地说，较新的技术也已经拥抱了SQL，比如Hive（一种用于查询和管理大数据集的类SQL查询语言接口）和Spark SQL（可用于执行SQL查询）。当然，这些地方出现的SQL依然会与我们学过的标准有所不同，但学习曲线会容易得多。

如果想做个对比的话，可以把学SQL当成学线性代数：把所有精力都投入到线性代数这一个主题上，你知道你也能用它来掌握机器学习！

简而言之，如下就是为什么我们应该学习这种查询语言的原因：

  • 它相当易学，即使对完全的新手来说也是如此。学习曲线很容易并且是循序渐进，这样我们马上就可以写查询。

  • 它遵循“一次学习，到处可用”的原则，所以这是一项不错的时间投资！

  • 它是对编程语言的极好补充；在某些情况下，写查询甚至优于写代码，因为它性能更佳！

  • …

你还在等什么？:)

SQL处理和查询执行

为提高SQL查询的性能，我们首先必须知道当我们按快捷方式运行查询时，内部会发生什么。

首先，查询被解析成一个“解析树”；查询被分析，看看它是否满足语法和语义要求。解析器为输入的查询创建一个内部表示，然后将此内部表示作为输出，传给重写引擎。

然后，优化器的任务是找到给定查询的最优执行或查询计划。执行计划准确地定义了每个操作使用什么算法，以及如何协调操作的执行。

为了找到最优执行计划，优化器会列举所有可能的执行计划，确定每个计划的质量或成本，获取有关当前数据库状态的信息，然后选择最好的一个作为最终的执行计划。由于查询优化器可能不完善，因此数据库用户和管理员有时需要手动检查并调整优化器生成的计划，以获得更好的性能。

现在你可能想知道什么才算一个“好的查询计划”。

正如我们所读过所见，计划的成本质量起着重要的作用。更具体地说，就是评估计划所需的磁盘I/O数量、计划的CPU成本以及数据库客户端可以观察到的整体响应时间和总执行时间等因素至关重要。而那就是时间复杂度的概念会出现的地方。稍后我们会阅读更多。

接下来，执行所选择的查询计划，由系统的执行引擎进行求值，并返回查询结果。

写SQL查询

这时候，从上一节到现在可能还没有变得清晰的一件事，即进来的是垃圾，出去的也是垃圾（GIGO）原则，在查询处理和执行过程中就自然而然地浮出水面：制定查询的人也握有SQL查询性能的钥匙。如果优化器得到一个制定得糟糕的查询，那么它也只能优化得糟糕…

这意味着我们在写查询时可以做一些事情。正如在简介中已经看到的那样，责任是双重的：它不仅与写出符合某一标准的查询有关，而且还与收集查询中性能问题可能潜伏在何处的想法有关。

一个理想的起点是在查询中考虑问题可能潜入的“点”。而且，一般来说，新手可能会出现性能问题的地方有四个子句和关键字：

  • **WHERE**子句；

  • 任何INNER JOIN或LEFT JOIN关键字；以及，

  • HAVING子句；

我承认，这种做法简单而粗暴，但是作为初学者，这些子句和语句是很好的指示器。而且，可以肯定地说，我们刚开始学习写查询时，这些地方就是错误发生的地方，并且，具有讽刺意味的是，这些地方在哪里也很难发现。

不过，我们还要明白，性能是需要一个上下文背景才变得有意义：简单地说，在考虑SQL性能时，这些子句和关键字并不一定会导致性能糟糕。查询中有WHERE或HAVING子句不一定意味着这是一个糟糕的查询…

看看一下小节，了解有关构建查询的反模式以及替代方法的更多信息。这些提示和技巧仅作指导。实际怎样重写查询取决于数据量、数据库和执行查询所需的次数等等。它完全取决于查询的目标，并且对要查询的数据库有一些先验知识也是至关重要的！

1.仅取回需要的数据

在写SQL查询时，不应该有“数据越多越好”的心态。如果这样有这样的心态的话，不仅会有由于获得了比实际需要更多的数据从而蒙蔽了观察力的风险，而且还会因为查询提取太多数据而影响性能。

这就是为什么一般来说，留心SELECT语句、DISTINCT子句和LIKE运算符是一个好主意的原因。

  • SELECT 语句

查询编写完后，首先应该检查的是SELECT语句是否尽可能紧凑。目标应该是从SELECT中删除不必要的列。这样就可以强制自己只提取用于查询目标的数据。

如果有含有EXISTS的相关子查询，就应试试在该子查询的SELECT语句中使用常量，而不是选择一个实际列的值。这在只检查值是否存在时特别方便。

请记住，相关子查询是使用来自外部查询中的值的子查询。并且注意，甚至NULL也可以在此上下文背景中作为一个“常量”，这是非常令人困惑的！

为理解使用常量的含义，请考虑以下示例：

SELECT driverslicensenr, name 
FROM Drivers 
WHERE EXISTS (SELECT '1' FROM Fines 
              WHERE fines.driverslicensenr = drivers.driverslicensenr);

提示：要知道有相关子查询并不总是一个好主意。你可以随时考虑去掉相关子查询，比如，用 INNER JOIN 重写：

SELECT driverslicensenr, name 
FROM drivers 
INNER JOIN fines ON fines.driverslicensenr = drivers.driverslicensenr;

  • DISTINCT 子句

SELECT DISTINCT语句用于仅返回有区别的（不同的）值。应该尽可能避免使用DISTINCT子句；就像在其他示例中读过的那样，如果将此子句添加到查询中，执行时间只会增加。因此，考虑是否真的需要执行DISTINCT操作来获取要完成的结果，总是一个好主意。

  • LIKE 运算符

在查询中使用LIKE运算符时，如果模式以％或_开头，就不会用到索引。它会阻止数据库使用索引（如果有索引的话）。当然，从另一个角度来看，你也可以认为这类的查询可能会导致获取太多不一定满足查询目标的记录。

再一次，对存储在数据库中的数据的了解可以帮助我们制定一个模式，该模式会对所有数据正确过滤，这样就只查找对查询至关重要的行。

2.限制查询结果

当无法避免要在SELECT语句中过滤一些数据时，可以考虑以其他方式限制结果。如下是LIMIT子句和数据类型转换等方法出现的地方：

  • TOP、LIMIT 和 ROWNUM 子句

可以将LIMIT或TOP子句添加到查询中，来设置结果集的最大行数。例如：

`SELECT TOP 3 * FROM Drivers;`

请注意，可以进一步指定PERCENT，例如，通过SELECT TOP 50 PERCENT *更改查询的第一行。

`SELECT driverslicensenr, name FROM Drivers LIMIT 2;`

此外，还可以添加ROWNUM子句，相当于在查询中使用LIMIT：

SELECT * 
FROM Drivers 
WHERE driverslicensenr = 123456 AND ROWNUM <= 3;

  • 数据类型转换

应该始终尽可能使用最有效率（即最小）的数据类型。当一个较小的数据类型就足够时，用大的数据类型总是一个风险。

不过，当给查询添加数据类型转换时，只会增加执行时间。

一个替代方案是尽可能避免数据类型转换。还要注意，并不总是可以从查询中删除或省略数据类型转换，但是包含它们的时候一定要小心，并且在包含它们时，在运行查询之前应该测试添加了它们后的效果。

3. 不要让查询变得比所需要的更复杂

数据类型转换又带来下一点：不要过度设计查询。尽量保持简单高效。这作为一个诀窍可能看起来太简单或愚蠢，特别是因为查询本来就可能变复杂。

不过，在下一小节中提到的示例中我们会看到，我们很容易会从一开始就让简单查询变得比需要的更复杂。

  • OR 运算符

当在查询中使用OR运算符时，我们很可能没有用索引。

请记住，索引是一种数据结构，可以提高数据库表中数据获取的速度，但会带来成本：会需要额外的写入和额外的存储空间来维护索引数据结构。索引用于快速定位或查找数据，而不用在每次访问数据库表时必须搜索数据库中的每一行。索引可以用在数据库表中的一个或多个列来创建。

如果不使用数据库包含的索引，那么查询就会不可避免地需要更长时间运行。这就是为什么最好在使用OR运算符的查询中寻找替代方法的原因；

考虑以下查询：

SELECT driverslicensenr, name 
FROM Drivers 
WHERE driverslicensenr = 123456 OR driverslicensenr = 678910 OR driverslicensenr = 345678;

可以通过用以下方式替换 OR 运算符：

  • 带有 IN的条件；或者
1
2
3
SELECT driverslicensenr, name 
FROM Drivers 
WHERE driverslicensenr IN (123456, 678910, 345678);
  • 带有UNION的两个SELECT语句。

提示：在这里，需要注意不要不必要地使用UNION操作，因为这样做会多次遍历同一个表。同时，必须意识到，当在查询中使用UNION时，执行时间将会增加。UNION操作的替代方法是：重新规划查询，把所有条件都放在一个SELECT指令中，或者使用OUTER JOIN来代替UNION。

提示：在这里也要记住，尽管OR以及下面几节中提到的其他运算符可能不使用索引，索引查找并非总是首选！

  • NOT 运算符

当查询包含NOT运算符时，很可能不使用索引，就像使用OR运算符一样。这会不可避免地减慢查询。如果不知道这是什么意思，请考虑以下查询：

`SELECT driverslicensenr, name FROM Drivers WHERE NOT (year > 1980);`

这个查询肯定会比你预期的更慢，主要是因为它规划的比想像的复杂得多：像这种情况，最好是找一个替代方案。考虑用比较运算符替换NOT，如>，或!>；上面的例子可能会被重写，变成这样：

`SELECT driverslicensenr, name FROM Drivers WHERE year <= 1980;`

这样看起来更整洁，对吧？

  • AND 运算符

AND运算符是另一个不使用索引的运算符，如果以过于复杂和低效的方式使用，可能会降低查询速度，如下例所示：

SELECT driverslicensenr, name 
FROM Drivers 
WHERE year >= 1960 AND year <= 1980;

最好用BETWEEN运算符重写：

SELECT driverslicensenr, name 
FROM Drivers 
WHERE year BETWEEN 1960 AND 1980;

  • ANY 和 ALL 运算符

此外，ALL和ANY运算符应该小心使用，因为如果将它们包含在查询中，索引也不会被使用。这里可以使用的替代方法是聚合函数，如MIN或MAX。

提示：在用上面推荐的替代方案时，必须注意：所有聚合函数（如SUM、AVG、MIN、MAX）在作用于很多行时，都会导致查询长时间运行。在这种情况下，可以试试要么最小化要处理的行数，要么预先计算这些值。我们可以再次看到，当决定使用哪个查询时，重要的是要注意环境和查询目标…

  • 隔离条件中的列

另外，如果列被用在计算或标量函数中，也不会使用索引。一个可能的解决方案是仅隔离指定列，使其不再是计算或函数的一部分。请考虑以下示例：

SELECT driverslicensenr, name 
FROM Drivers 
WHERE year + 10 = 1980;

这看起来很恶心，对吧？那就试试重新考虑计算，并将查询重写为如下所示：

SELECT driverslicensenr, name 
FROM Drivers 
WHERE year = 1970;

4. 不要用蛮力

最后一个提示实际上就是不应该试图过份限制查询，因为会影响查询性能。对于连接和HAVING子句尤其如此。

  • 连接

  • 表的顺序
    当连接两个表时，考虑连接中表的顺序可能很重要。如果注意到一个表比另一个表大得多，可能就需要重写查询，把最大的表放在连接的最后。

  • 连接中的冗余条件

当给连接添加太多条件时，本质上是强迫SQL来选择某个路径。不过，这条路径并非总是性能较好的。

  • HAVING 子句

HAVING子句添加到SQL中，原本是因为WHERE关键字不能与聚合函数一起使用。HAVING通常与GROUP BY子句一起使用，将返回行的组限制为仅满足某些条件的行。不过，如果在查询中使用此子句，就会不使用索引，而我们已经知道这可能会导致查询不能很好地执行。

如果正在寻找替代方案，那就考虑使用WHERE子句。考虑如下查询：

1
2
3
SELECT state, COUNT(*) FROM Drivers WHERE state IN ('GA', 'TX') GROUP BY state ORDER BY state

SELECT state, COUNT(*) FROM Drivers GROUP BY state HAVING state IN ('GA', 'TX') ORDER BY state

第一个查询使用WHERE子句来限制需要统计的行数；而第二个查询对表中的所有行计数，然后使用HAVING过滤计算出来的计数。在这些类型的情况下，使用WHERE子句的替代方案显然是更好的，因为不会浪费任何资源。

我们可以看到，这不是限制结果集，而是限制查询中记录的中间数。

请注意，这两个子句之间的区别在于WHERE子句是在每一行上引入一个条件，而HAVING子句是在一个选择（selection）的聚合或者结果上（这里单个结果，比如MIN、MAX、SUM，已经从多行中生成了）引入一个条件。

所以说，在要尽可能考虑性能时，评估质量、写以及重写查询并非易事；当编写要在专业环境中的数据库上运行的查询时，避免反模式以及考虑替代方案也会成为职责的一部分。

这个列表只是一些有望帮助初学者的反模式和技巧的简单概述；如果想了解更多高级开发人员认为最常见的反模式的话，请查看此讨论。

基于集合的查询方法与过程式查询方法

上述反模式中隐含的事实是，它们实际上归结为基于集合的方法创建查询与过程式方法创建查询之间的区别。

过程式方法创建查询是一种非常类似于编程的方法：我们可以告诉系统该做什么以及如何做。

一个例子是连接中的冗余条件，或者像上例中一样滥用HAVING子句的情况下，通过执行一个函数然后调用另一个函数来查询数据库，或者使用包含循环、条件、用户定义函数（UDF）、光标等等逻辑来得到最终结果。在这种方法中，会经常发现自己要请求数据的一个子集，然后从该数据中请求另一个子集等等。

所以，毫不奇怪，这种方法通常被称为“逐步”或“逐行”查询。

另一种方法是基于集合的方法，这里我们只需指定要执行的操作。我们的任务包括为想从查询中得到的结果集指定条件或需求。将如何获取数据留给确定查询实现的内部机制：让数据库引擎确定执行查询的最佳算法或处理逻辑。

由于SQL是基于集合的，所以不出意料，这种方法比过程式方法更有效，这也解释了为什么在某些情况下，SQL能比代码工作的更快。

提示：基于集合的查询方法也是数据科学行业最顶尖的雇主将要求你掌握的方法！你会经常需要在这两类方法之间切换。

请注意，如果你发现自己有过程式查询，就应考虑重写或重构它。

从查询到执行计划

反模式并非一成不变的，会随着我们作为SQL开发人员的发展而发展，并且在考虑替代方案时需要考虑良多，知道这个事实，也就意味着避免查询反模式以及重写查询可能会是一件相当棘手的任务。这时候任何辅助手段都可以派上用场，这就是为什么用一些工具以更加结构化的方式来优化查询也是条可取的路径。

还要注意，上一节中提到的一些反模式源于性能问题，如AND、OR和NOT运算符以及它们缺少索引使用。对性能的思考不仅需要更结构化的方法，而且还需要更深入的方法。

不过，这种结构化和深入的方法将主要是基于查询计划，而查询计划是首先被解析为“解析树”的查询结果，并且定义每个操作用什么算法以及操作的执行如何协调。

查询优化

正如在介绍中所看到的那样，我们可能需要手动检查和调整优化器生成的计划。在这种情况下，我们将需要通过查看查询计划来再次分析查询。

要控制此计划，我们得用数据库管理系统提供的工具。可以使用的一些工具如下：

  • 某些软件包有工具可以生成查询计划的图形表示。看看这个例子：

  • 其他工具能提供查询计划的文本描述。一个例子是Oracle中的EXPLAIN PLAN语句，不过指令的名称根据正在用的RDBMS而有所不同。比如，MySQL、PostgreSQL中是EXPLAIN，SQLite中是EXPLAIN QUERY PLAN。

请注意，如果是在用PostgreSQL，那么EXPLAIN和 EXPLAIN ANALYZE 之间是有区别的。前者只得到一个说明计划器要如何执行查询的描述，但是不会执行查询；而后者会实际执行查询，并返回一个预期与实际查询计划的分析。一般来说，实际的执行计划是实际执行查询时用的那个计划，而估算的执行计划是在不执行查询的情况下算出执行计划会做什么。虽然二者在逻辑上差不多，但是实际执行计划更为有用，因为它包含执行查询时实际发生的其他细节和统计信息。

在本节的剩余部分中，我们将了解有关EXPLAIN和ANALYZE的更多信息，以及如何使用这两个语句来了解有关查询计划的更多信息以及查询的可能性能。为此，我们会从几个示例开始。示例中要用到两个表：one_million 和 half_million。

我们可以借助 EXPLAIN 获取表 one_million的当前信息；确保把 EXPLAIN放在查询的最上面，运行后，就会返回查询计划：

1
2
3
4
5
6
7
8
9
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更新统计信息。

1
2
3
4
5
6
7
8
9
10
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 获取实际执行时间：

1
2
3
4
5
6
7
8
9
10
11
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（顺序扫描）或者全表扫描：这是在数据库上进行的扫描，其中被扫描的表的每一行以按（串行）顺序读取，并且检查找到的列是否满足条件。在性能方面，顺序扫描显然不是最佳的执行计划，因为我们依然是在进行全表扫描。 然而，当表没法刚好放入内存时，这并不太糟糕：即使使用慢磁盘，顺序读取也会很快。

当讨论索引扫描时，我们会看到更多信息。

不过，还有一些其他的算法。比如，为连接采用的这个查询计划：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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上没有索引，可以在下一个例子中添加：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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)

可以看到，通过创建索引，查询优化器现在决定选择 Merge join（合并连接），而合并连接的时候是用 索引扫描。

注意索引扫描与全表扫描或顺序扫描之间的区别：前者，也称“表扫描”，是扫描数据或索引页以找到适当的记录，而后者扫描表的每一行。

可以看到总运行时已经减少了，性能应该更好，但是有两个索引扫描，这使得内存在这里变得更加重要，特别是如果表没法刚好放入内存中时。 在这种情况下，我们首先必须执行全索引扫描，这是快速的顺序读取，不会引起任何问题，但是随后有很多随机读来通过索引值获取行。 而这些随机读取通常比顺序读取慢一个数量级。 在这种情况下，全表扫描实际上比全索引扫描更快。

提示：如果想了解更多关于EXPLAIN的信息或者更详细地查看示例，请考虑阅读Guillaume Lelarge写的《Understanding Explain》一书。

时间复杂度和大O表示法

现在我们已经大致复习了查询计划，可以在计算复杂度理论的帮助下开始深入挖掘，并以更正式的方式思考性能。理论计算机科学的这个领域，重点是根据难度对计算问题进行分类；这些计算问题可以是算法，也可以是查询。

但是，对于查询，我们不一定根据其难度对其分类，而是根据运行它并返回一些结果所花的时间来分类。具体来说，这被称为时间复杂度，而且表达或测量这种类型的复杂度，我们可以使用大O表示法。

用大O表示法，我们可以依据运行时间随着输入变得无穷大，相对于输入的增长速度，来表达运行时间。大O表示法排除掉系数和低阶项，这样我们就可以专注于查询运行时间的重要部分：其增长率。当以这种方式表示时，丢弃系数和低阶项，时间复杂度被认为是渐近地描述的。也就是说，输入大小达到无穷大。

在数据库语言中，复杂度衡量了随着数据表的大小增长以及随之带来的数据库增长，查询运行时间的长短。

请注意，数据库的大小不仅会随着更多的数据存储在表中而增长，而且存在于数据库中的索引也会对大小增长起作用。

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

如前所述，除了做其他事情外，执行计划还定义了每个操作用什么算法，让每个查询执行时间可以被逻辑地表示为一个查询计划中表大小的函数，这个函数被称为复杂度函数。换句话说，可以用大O表示法和执行计划来估算查询的复杂度和性能。

在以下小节中，您将得到有关四种类型的时间复杂性的一般概念，您将看到一些示例，说明查询的时间复杂度如何根据您运行它的上下文而有所不同。

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

但是请注意，考虑到有不同类型的索引、不同的执行计划以及不同数据库的不同实现，所以下面列出的时间复杂度是一个非常总体的概括，可能会根据具体设置而有所不同。

常数时间: O(1)

如果一个算法不管输入有多大，总是需要相同的时间量，那么就说该算法以常数时间运行。对于查询，如果不管表有多大，总是需要相同的时间量，那么该查询就会以常数时间运行。

这类查询并不常见，不过这里有这么一个例子：

1
2
SELECT TOP 1 t.* 
FROM t

这里时间复杂度是常数，因为只从表中选择一个任意行。 因此，时间长度应该与表的大小无关。

线性时间: O(n)

如果一个算法的时间执行与输入大小成正比，即随着输入大小的增加，时间线性增长，那么该算法就是以线性时间运行。对于数据库，这意味着时间执行与表大小成正比：随着表中行数的增加，查询的时间增长。

一个示例是在未索引的列上使用WHERE子句的查询：将需要全表扫描或Seq Scan，这会导致时间复杂度为O(n)。 这意味着需要读取每一行以找到具有正确ID的数据。 你根本没有限制，所以每行都需要读取，即使第一行就匹配条件也是如此。

还可以考虑以下示例，如果i_id上没有索引，那么这个查询的复杂度就为O(n)：

1
2
SELECT i_id 
FROM item;
  • 这也意味着其他查询，例如COUNT（*）FROM TABLE;这样的计数查询的时间复杂度为O(n)，因为将需要全表扫描，除非存储表的总行数，那么复杂度会更像O(1)。

与线性执行时间密切相关的是其中有连接的执行计划的执行时间。 这里有些例子：

  • 哈希连接（hash join）具有预期的复杂度O(M + N)。 用于两个表内连接的经典哈希连接算法首先准备较小表的哈希表。哈希表项由连接属性及其行组成。 通过将一个哈希函数应用于连接属性来访问哈希表。 一旦构建了哈希表，就会扫描较大的表，并通过查看哈希表来查找较小表中的相关行。

  • 合并连接（merge join）通常具有复杂度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))

如果一个算法的时间执行与输入大小的对数成比例，则该算法被称为以对数时间运行; 对于查询，这意味着如果执行时间与数据库大小的对数成正比，它们将以对数时间运行。

这种对数时间复杂度对于执行“索引扫描”或聚簇索引扫描的查询计划是真实的。聚簇索引是索引的叶级别包含表的实际数据行的索引。聚簇索引与其他索引非常相似：它在一个或多个列上定义。这些列形成索引键。 聚簇键是聚簇索引的关键列。聚簇索引扫描基本上是RDBMS从上到下读取聚簇索引中的行的操作。

考虑如下的查询示例，这里在 i_id 上有一个索引，通常会得到复杂度O(log(n))：

1
2
3
SELECT i_stock 
FROM item 
WHERE i_id = N;

注意：如果没有索引，那么时间复杂度就变成了 O(n)。

平方时间: O(n^2)

如果一个算法的时间执行与输入大小的平方成正比，那么该算法就被称为以平方时间运行。再次，对于数据库，这意味着查询的执行时间与数据库大小的平方成正比。

具有平方时间复杂度的查询的一个示例如下：

1
2
3
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用户的这条引文：

“我最喜欢的反模式是不要测试查询。

这适用于：

  • 你的查询涉及多个表。
  • 你认为你有一个优化的查询设计，不想费心测试你的假设。
  • 你接受第一个查询是有效的，没有关于它是否接近优化的线索。“

英文原文：https://medium.com/towards-data-science/sql-tutorial-how-to-write-better-queries-108ae91d5f4e

欢迎关注我的其它发布渠道