如何编写更好的SQL查询:终极指南(下)

SQL是数据挖掘分析行业不可或缺的一项技能,对于SQL来说,编写查询语句只是第一步,确保查询语句高效并且适合于你的数据库操作工作,才是最重要的。在上一篇文章中,我们分享了评估查询语句的步骤和方法(参考:如何编写更好的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 )。

嵌套连接

嵌套连接(nested loops)的复杂度通常为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查询:

  • 用索引扫描替换不必要的大数据表的全表扫描;
  • 确保表的连接顺序为最佳顺序;
  • 确保以最佳方式使用索引;
  • 将小数据表的全表扫描缓存起来。

原文发布于微信公众号 - 数据和云(OraNews)

原文发表时间:2017-10-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

搭建模型第一步:你需要预习的NumPy基础都在这了

NumPy 主要的运算对象为同质的多维数组,即由同一类型元素(一般是数字)组成的表格,且所有元素通过正整数元组进行索引。在 NumPy 中,维度 (dimens...

692
来自专栏C语言及其他语言

【优秀题解】问题 1442:打印十字图

我的思路就是一步一步的分析,首先我想到的就是分配一块内存来储存图案,通过观察知道图案是一个方正,于是想到用字符矩阵。然后分布完成,首先就是把方块字符中...

291
来自专栏挖掘大数据

处理海量数据的10种常见方法

本文将介绍10种处理海量数据问题的常见方法,也可以说是对海量数据的处理方法进行一个简单的总结,希望对你有帮助。

20210
来自专栏杂七杂八

numpy科学计算包的使用2

利用数组进行数据处理 NumPy数组使你可以将许多种数据处理任务表述为简洁的数组表达式(否则需要编写循环)。用数组表达式代替循环的做法,通常被称为矢量化。 矢...

34412
来自专栏前端架构

深入理解Java闭包概念

简单理解:闭包能够将一个方法作为一个变量去存储,这个方法有能力去访问所在类的自由变量。

461
来自专栏Python爬虫与算法进阶

学点算法之字符串的乱序检查

问题 字符串的乱序检查。 一个字符串是另一个字符串的乱序。如果第二个字符串只是第一个的重新排列,例如,’heart’ 和 ‘earth’ 就是乱序字符串。’py...

3588
来自专栏云端架构

【云端架构】教你口算MD5算法

对MD5算法简要的叙述可以为:MD5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成...

45214
来自专栏take time, save time

你所能用到的BMP格式介绍(二)

一、可能你忽视的基础         在正式开始之前,我不得不从最基本的地方开始,因为这些地方大多数人会忽视的一干二净,如果不在开始进行说明,那么在后面一定会有...

2637
来自专栏闻道于事

算法笔记(二)数据结构

1030
来自专栏竹清助手

【机器学习】 搭建模型第一步:你需要预习的NumPy基础都在这了

NumPy 主要的运算对象为同质的多维数组,即由同一类型元素(一般是数字)组成的表格,且所有元素通过正整数元组进行索引。在 NumPy 中,维度 (dimens...

974

扫描关注云+社区