最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

环球即时看!以小博大外小内大,Db数据库SQL优化之小数据驱动大数据

来源:博客园

SQL优化中,有一条放之四海而皆准的既定方针,那就是:永远以小数据驱动大数据。其本质其实就是以小的数据样本作为驱动查询能够优化查询效率,在SQL中,涉及到不同表数据的连接、转移、或者合并,这些操作必须得有个数据集作为“带头”大哥,即驱动数据,而这个驱动数据最好是数据量最小的那一个。


(相关资料图)

内大外小

在讨论数据库之前,日常开发中,我们经常会遇到数据样本数量不一致,但是需要进行检索的情况,比如某人在地铁的某节车厢里捡到N台Iphone,而车厢里正好有T个人,他应该怎么去检索双样本数据,从而找到失主?

for (int i = 0; i < N; i++)       for (int j = 0; j < T; j++)   find();

一般的说法是把循环次数少的循环放在外面,其实,这个问题的主要原因是CPU内部的指令执行机制。现在,基本上CPU内部都有分支指令预测,就是当执行(现在大多将这一阶段提前到预取指令时执行)到转移指令时,都会直接从分支目标缓存(BTB)中取出目标指令的地址,然后将要执行的指令提前预取到CPU的指令预取指令队列中。这样,显然大大提高了效率。一个N次的一层循环在执行时,除了在第一次和最后一次会预测错误外,其他N-i次都会预取成功,避免了执行转移指令时重新取出新指令造成的时间浪费。 所以,当有两层循环,外层循环数为N,内层为T,N远大于T,那么最终造成的预测错误数为N*2+2,而如果外层数为T,内层数为N,预测错误数为T*2+2,显然后者要节省更多时间,而且这个时间是很可观的。N比T越大,这个时间差越明显。

连表查询

回到数据库场景,连表查询操作本质上其实就是扫描驱动表数据,根据条件,逐一去大表找数据,由小表作为驱动表,小表数据少,那么去大表找数据时,能减少数据的找寻量。体现在底层上也就减少了网络的IO,内存,自然效率就高。

不同的连表方式也会有不同的驱动表,左连接中左边为驱动表,右边为被驱动表;右连接中右边为驱动表,左边为被驱动表;内连接中Mysql会选择数据量比较小的表作为驱动表,大表作为被驱动表。我们也可以通过EXPLANIN关键字查看SQL语句的执行计划,从而搞清楚一次连表查询中的驱动表到底是那一张。

底层原理

连表查询操作时,数据库会从头到尾扫描驱动表,复杂度为O(n),也就是说有N条就要查N次,随后再逐一去其它关联表查询数据,众所周知,由于Mysql采用B+tree方式进行存放数据,关于B+tree,请移步:霜皮剥落紫龙鳞,下里巴人再谈数据库SQL优化,索引(一级/二级/聚簇/非聚簇)原理,因此查询时间复杂度为O(logn),总时间复杂度即为O(n)*O(logn),说白了就是驱动数据集有多少条数据,就得在B+tree中查询O(logn)次。

假设表n数据小于表m,则连表查询操作时,O(n)*O(logm) 小于 O(m)*O(logn),因此小数据集作为驱动数据相对就比较有效率。

子查询

外小内大原则也同样适用于子查询,当子表的数据集较小时,使用In操作,效率较高:

SELECT * FROM A WHERE ID IN (SELECT ID FROM B)

这里B表的数据量小于A表数据,很明显B表作为查询筛选的驱动表。

反之,当B表数据量大于外侧的数据表A:

SELECT * FROM A WHERE  EXISTS (SELECT 1 FROM B WHERE B.ID = A.ID)

此时使用EXISTS的效率更高,因为EXISTS是将主查询的数据放到子查询中做条件验证,根据验证结果(TRUE或者FALSE)来决定主查询的数据结果是否能够得以保留。

结语

循环嵌套优化原则的外小内大,数据库SQL优化原则的以小博大,一脉相承,同出一辙,大道至简,殊途同归。

关键词: 转移指令 时间复杂度 数据驱动