如何编写更好的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 条评论
登录 后参与评论

相关文章

来自专栏人人都是极客

三维图形渲染显示的全过程

图像中物体所处位置及外形由其几何数据和摄像机的位置共同决定,物体外表是受到其材质属性、光源、纹理及着色模型所影响。

1222
来自专栏Kirito的技术分享

Java随机数探秘

一提到 Java 中的随机数,很多人就会想到 Random,当出现生成随机数这样需求时,大多数人都会选择使用 Random 来生成随机数。Random 类是线程...

1265
来自专栏瓜大三哥

IO约束(上)

IO约束的语法 XDC中可以用于IO约束的命令包括: set_input_delay set_output_delay set_max_delay set_mi...

1918
来自专栏吉浦迅科技

DAY29:阅读最大化存储器的吞吐率

863
来自专栏挖掘大数据

PipeLineDB数据库介绍和总结

PipelineDB 是开源的关系型数据库,可以在 streams 中持续运行 SQL 查询,逐渐将结果存储在表中。本文将对PipelineDB做相应的总结。

3130
来自专栏无题

多机的Sequence问题与处理

数据库拆分之后,会引入诸多新的问题,其中之一就是,以MySQL为例,原先单表的时候, 可以通过MySQL自带的aut_increment实现自增不重复id,现在...

38210
来自专栏PingCAP的专栏

TiDB 源码阅读系列文章(八)基于代价的优化

本文会先简单介绍制定查询计划以及优化的过程,然后用较大篇幅详述在得到逻辑计划后,如何基于统计信息和不同的属性选择等生成各种不同代价的物理计划。

3.7K10
来自专栏灯塔大数据

每周学点大数据 | No.30前序计数

No.30期 前序计数 Mr. 王:我们再来说说父子关系判定的应用。前序计数是一种非常常用的对树进行处理的方法。前序计数实现的就是对各个节点按照其前序遍...

3347
来自专栏用户2442861的专栏

腾讯2014校园招聘技术类笔试题详解

http://blog.csdn.net/silangquan/article/details/19977839

1051
来自专栏杨建荣的学习笔记

关于consistent gets(r5笔记第12天)

在sql调优的时候,一个关键指标就是consistent gets,如果这个指标很低,一般认为sql语句执行还是很高效的,反之效率会很低。但是这个指标我们知之甚...

3215

扫码关注云+社区