文档章节

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

葡萄城控件技术团队
 葡萄城控件技术团队
发布于 2017/09/11 12:26
字数 1998
阅读 783
收藏 40
点赞 1
评论 0

本次我们学习《如何编写更好的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

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

© 著作权归作者所有

共有 人打赏支持
葡萄城控件技术团队

葡萄城控件技术团队

粉丝 321
博文 487
码字总数 694630
作品 13
西安
高级程序员
如何编写更好的SQL查询:终极指南-第一部分

结构化查询语言(SQL)是数据挖掘分析行业不可或缺的一项技能,总的来说,学习这个技能是比较容易的。对于SQL来说,编写查询语句只是第一步,确保查询语句高效并且适合于你的数据库操作工作,...

powertoolsteam ⋅ 2017/08/29 ⋅ 0

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

本次我们学习《如何编写更好的SQL查询》系列的最后一篇文章。 时间复杂度和大O符号 通过前两篇文章,我们已经对查询计划有了一定了解。接下来,我们还可以借助计算复杂度理论,来进一步深入地...

powertoolsteam ⋅ 2017/09/11 ⋅ 0

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

本次我们学习《如何编写更好的SQL查询》系列的最后一篇文章。 时间复杂度和大O符号 通过前两篇文章,我们已经对查询计划有了一定了解。接下来,我们还可以借助计算复杂度理论,来进一步深入地...

powertoolsteam ⋅ 2017/09/11 ⋅ 0

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

本次我们学习《如何编写更好的SQL查询》系列的最后一篇文章。 时间复杂度和大O符号 通过前两篇文章,我们已经对查询计划有了一定了解。接下来,我们还可以借助计算复杂度理论,来进一步深入地...

powertoolsteam ⋅ 2017/09/11 ⋅ 0

如何编写更好的SQL查询:终极指南-第二部分

上一篇文章中,我们学习了 SQL 查询是如何执行的以及在编写 SQL 查询语句时需要注意的地方。 下面,我进一步学习查询方法以及查询优化。 基于集合和程序的方法进行查询 反向模型中隐含的事实...

powertoolsteam ⋅ 2017/09/05 ⋅ 0

如何编写更好的SQL查询:终极指南-第二部分

上一篇文章中,我们学习了 SQL 查询是如何执行的以及在编写 SQL 查询语句时需要注意的地方。 下面,我进一步学习查询方法以及查询优化。 基于集合和程序的方法进行查询 反向模型中隐含的事实...

powertoolsteam ⋅ 2017/09/05 ⋅ 0

欢迎来撩 | 掘金翻译计划

介绍 掘金翻译计划 是一个翻译优质互联网技术文章的社区,文章来源为 掘金 上的英文分享文章。内容覆盖人工智能、Android、iOS、React、前端、后端、产品、设计 等领域,读者为热爱新技术的新...

LeviDing ⋅ 2017/10/16 ⋅ 0

调查报告:现在的开发人员对数据库的使用方式

根据Evans数据公司提供的数据,全世界大约有1900万开发人员。而2015年StackOverflow开发者调查显示,36%的开发人员最近使用过SQL。也就是说,现如今大约有700万开发人员使用SQL。在过去四年里...

oschina ⋅ 2016/01/01 ⋅ 4

如果你在找 CSS 学习资源,那就收藏这篇文章

本文由伯乐在线 -伯小乐 翻译。未经许可,禁止转载! 英文出处:Grace Smith。欢迎加入翻译组。 如果你在寻找一些 CSS 基础和高级的指南或资源,那这篇文章应该有你要的 CSS 初级和高级指南:...

伯乐在线 ⋅ 2014/11/07 ⋅ 0

10 件在 PHP 7 中不要做的事情

1. 不要使用函数 这一天终于来了,从此你不仅仅“不应该”使用函数。PHP 7 已经把它们从核心中全部移除了,也就是说你需要迁移到好得多的函数,或者更灵活的 PDO 实现。 2. 不要编写垃圾代码...

两味真火 ⋅ 2016/09/18 ⋅ 52

没有更多内容

加载失败,请刷新页面

加载更多

下一页

如何优雅的编程——C语言界面的一点小建议

我们鼓励在编程时应有清晰的哲学思维,而不是给予硬性规则。我并不希望你们能认可所有的东西,因为它们只是观点,观点会随着时间的变化而变化。可是,如果不是直到现在把它们写在纸上,长久以...

柳猫 ⋅ 22分钟前 ⋅ 0

从零手写 IOC容器

概述 IOC (Inversion of Control) 控制反转。熟悉Spring的应该都知道。那么具体是怎么实现的呢?下面我们通过一个例子说明。 1. Component注解定义 package cn.com.qunar.annotation;impo...

轨迹_ ⋅ 22分钟前 ⋅ 0

系统健康检查利器-Spring Boot-Actuator

前言 实例由于出现故障、部署或自动缩放的情况,会进行持续启动、重新启动或停止操作。它可能导致它们暂时或永久不可用。为避免问题,您的负载均衡器应该从路由中跳过不健康的实例,因为它们...

harries ⋅ 24分钟前 ⋅ 0

手把手教你搭建vue-cli脚手架-详细步骤图文解析[vue入门]

写在前面: 使用 vue-cli 可以快速创建 vue 项目,vue-cli很好用,但是在最初搭建环境安装vue-cli及相关内容的时候,对一些人来说是很头疼的一件事情,本人在搭建vue-cli的项目环境的时候也是...

韦姣敏 ⋅ 34分钟前 ⋅ 0

12c rman中输入sql命令

12c之前版本,要在rman中执行sql语句,必须使用sql "alter system switch logfile"; 而在12c版本中,可以支持大量的sql语句了: 比如: C:\Users\zhengquan>rman target / 恢复管理器: Release 1...

tututu_jiang ⋅ 48分钟前 ⋅ 0

Nginx的https配置记录以及http强制跳转到https的方法梳理

Nginx的https配置记录以及http强制跳转到https的方法梳理 一、Nginx安装(略) 安装的时候需要注意加上 --with-httpsslmodule,因为httpsslmodule不属于Nginx的基本模块。 Nginx安装方法: ...

Yomut ⋅ 今天 ⋅ 0

SpringCloud Feign 传递复杂参数对象需要注意的地方

1.传递复杂参数对象需要用Post,另外需要注意,Feign不支持使用GetMapping 和PostMapping @RequestMapping(value="user/save",method=RequestMethod.POST) 2.在传递的过程中,复杂对象使用...

@林文龙 ⋅ 今天 ⋅ 0

如何显示 word 左侧目录大纲

打开word说明文档,如下图,我们发现左侧根本就没有目录,给我们带来很大的阅读障碍 2 在word文档的头部菜单栏中,切换到”视图“选项卡 3 然后勾选“导航窗格”选项 4 我们会惊奇的发现左侧...

二营长意大利炮 ⋅ 今天 ⋅ 0

智能合约编程语言Solidity之线上开发工具

工具地址:https://ethereum.github.io/browser-solidity/ 实例实验: 1.创建hello.sol文件 2.调试输出结果

硅谷课堂 ⋅ 今天 ⋅ 0

ffmpeg 视频格式转换

转 Mp4 格式 #> ffmpeg -i input.avi -c:v libx264 output.mp4#> ffmpeg -i input.avi -c:v libx264 -strict -2 output.mp4#> ffmpeg -i input.avi -c:v libx264 -strict -2 -s 1......

Contac ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部