MyException - 我的异常网
当前位置:我的异常网» SQL » 怎么编写更好的SQL查询:终极指南-第三部分

怎么编写更好的SQL查询:终极指南-第三部分

www.MyException.Cn  网友分享于:2013-09-28  浏览:0次
如何编写更好的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 )。
  • 对于嵌套连接,复杂度通常为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查询。

原文链接:https://www.datacamp.com/community/tutorials/sql-tutorial-query#importance

转载请注明出自:葡萄城控件

文章评论

程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员和编码员之间的区别
程序员和编码员之间的区别
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
编程语言是女人
编程语言是女人
漫画:程序员的工作
漫画:程序员的工作
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
程序员的鄙视链
程序员的鄙视链
程序员都该阅读的书
程序员都该阅读的书
代码女神横空出世
代码女神横空出世
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
鲜为人知的编程真相
鲜为人知的编程真相
 程序员的样子
程序员的样子
中美印日四国程序员比较
中美印日四国程序员比较
每天工作4小时的程序员
每天工作4小时的程序员
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
旅行,写作,编程
旅行,写作,编程
我是如何打败拖延症的
我是如何打败拖延症的
为什么程序员都是夜猫子
为什么程序员都是夜猫子
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
总结2014中国互联网十大段子
总结2014中国互联网十大段子
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
那些争议最大的编程观点
那些争议最大的编程观点
程序员应该关注的一些事儿
程序员应该关注的一些事儿
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有