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

相关文章

来自专栏数据和云

常与无常:SQL语句中常量的处理及性能差异解析

杨廷琨,网名 yangtingkun 云和恩墨技术总监,Oracle ACE Director,ACOUG 核心专家 在ITPUB论坛上看到一个有意思的问题:两...

3269
来自专栏JetpropelledSnake

Django学习笔记之ORM多表操作

作者详细模型:把作者的详情放到详情表,包含生日,手机号,家庭住址等信息。作者详情模型和作者模型之间是一对一的关系(one-to-one)

964
来自专栏mukekeheart的iOS之旅

数据库操作要点知识整理

第一课:客户端         1. Sql Plus(客户端),命令行直接输入:sqlplus,然后按提示输入用户名,密码。         2. 从开始...

2289
来自专栏程序猿

SQL优化法则小记

SQL优化技巧 1.选择最有效率的表名顺序(只在基于规则的优化器中有效): oracle的解析器按照从右到左的顺序处理 from 子句中的表名,...

3559
来自专栏YG小书屋

ES中文分词器之精确短语匹配(解决了match_phrase匹配不全的问题)

2594
来自专栏xingoo, 一个梦想做发明家的程序员

Elasticsearch Span Query跨度查询

ES基于Lucene开发,因此也继承了Lucene的一些多样化的查询,比如本篇说的Span Query跨度查询,就是基于Lucene中的SpanTermQue...

3037
来自专栏腾讯云流计算

Apache Calcite 功能简析及在 Flink 的应用

• Apache Calcite 是一个动态数据的管理框架,可以用来构建数据库系统的语法解析模块

5687
来自专栏Jackson0714

基础很重要~~04.表表达式-下篇

35616
来自专栏GreenLeaves

使用group by rollup和group by cube后的辅助函数

本文主要介绍,报表在使用group by rollup和group by cube后的辅助函数。 CREATE TABLE TEST8 ( "ID...

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

IP地址定位区间的问题分析

以前写过一篇Oracle中关于IP地址定位的问题分析,最后引申出了一系列的问题。当时问题紧急严峻,抓取了10053事件定位源头,想出了一个解决妙法,还自鸣...

2858

扫码关注云+社区