以小博大外小内大,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优化原则的以小博大，一脉相承，同出一辙，大道至简，殊途同归。