从NLJ和HASH JOIN的选择说起

元旦在家歇了几天，彻底放松了一下，基本上没有打开电脑。三号晚上因为一个朋友遇到一个SQL性能问题，打开电脑帮助分析了一下。这是一个因为统计信息被锁定而导致的表连接方式选择错误。分析完问题后，想想明天一早要赶飞机，如果不发一篇文章，新年的就没有开个好头，于是顺手写了一篇。内容也是有感而发，根据朋友的案例想到的一些东西。

今天我们聊聊CBO优化器里的表连接。根据行源的情况选择正确的表连接方式是SQL执行计划优化中的十分关键的一点。不管是Oracle数据库还是Mysql，PG等开源数据库，都是一样的道理。常见的表连接方式包括Nested Loop，HASH JOIN，Sort Merge Join等。今天我们不是来讨论数据库表连接的方式的，因此我不从介绍这几种常见的表连接方式入手，想了解这方面技术的朋友可以参考我以前写过的文章。

今天我和大家一起分享一下HASH JOIN和Nested Loop Join这两种CBO优化器最容易选错的表连接方式，我说的那个朋友都问题就是因为错走了NESTED LOOP，导致一个原本几百毫秒的sql好几分钟都跑不出来。

Hash Join是数据库支持大表连接访问的利器，在Oracle数据库中，也是从CBO优化器出现以后才开始支持的。因为HASH JOIN需要对表和索引等获得十分准确的统计信息才能够生成适当的执行计划。而NESTED LOOP是最朴素的表连接方式，采用最为简单的循环调用的方式完成连接。

NESTED LOOP虽然很简单，但是如何循环的次数太多，则会效率不高。如果循环十几二十次，这个连接效率是很高的，如果这个循环要跑几百次甚至几千次上万次，那么NLJ的效率就极低了。这时候必须借助hash join这个利器了。

MYSQL数据库直到8.0.18才开始有限的支持Hash Join的，在支持Hash Join之前，Mysql只能够通过Nested Loop Join来实现两张表的连接操作。Nested Loop是采用一种嵌套循环的方式做表连接。首先选择一个行数较少的行源，以此做循环，每个循环去另外一张表中查找一组符合条件的记录。因此内表的表连接字段上一定要有适当的索引，否则每个循环都需要对内表进行一次全表扫描，如果内表很大，那就是灾难了。

为了解决这个问题，从Mysql 5.7开始，出现了一种改良版的Nested Loop Join算法，这就是Block Nested Loop Join。这个算法说起来也十分简单，首先还是要选择一张较小的外表O，扫描O的记录，批量取出连接关键字的值，放入一个内存缓冲区中去，当缓冲区写满后，将这一批键值交给扫描引擎，去扫描内表I,从而完成连接操作。
如果在I上没有合适的索引，那么如果O上的符合条件的记录有Bo个缓冲区，那么I表需要被扫描Bo次，如果每个BUFFER可以存储10个键值，那么扫描I表的次数可以减少为1/10，从而大大减少扫描的次数。

上图是在网上找到的一个关于Block Nested Loop Join的算法描述。实际上BNLJ要复杂的多。比如说内表I特别大，同时表的关联字段上有索引，那么Mysql可以通过索引来扫描，这时候要使用一个算法：Batched Key Access Algorithms（BKA）。通俗来说，就是批量键值访问。BKA会将需要扫描的一组键值组织成一个BUFFER，然后一次性交给Multi-Range Read (MRR)扫描引擎去做批量键值扫描，从而降低索引扫描的成本。不过在成本估算的时候，MYSQL仍然给这种MRR扫描较为悲观的估算，所以在缺省的配置下，MYSQL，并不能很好的估算出BNLJ的成本，从而选择使用BNLJ。

在实际的运行环境中，对于一些较大型的表某些关联操作，HASH JOIN就比NLJ的优势明显多了。下面我们通过一个Oracle的例子来看看这两种JOIN的差别。

drop table test_a;
create table test_a (t_date varchar2(8),t_name varchar2(100),t_id number);
create index idx_test_a_1 on test_a(t_date);
create index idx_test_a_2 on test_a(t_id);


drop table test_b;
create table test_b (t_id number,t_stat varchar(20));
create index idx_test_b on test_b(t_id);

首先我们创建两张表（test_a和test_b），二者通过t_id关联。这两张表都基于dba_object来生成一些测试数据。

TRUNCATE TABLE TEST_A；
TRUNCATE TABLE TEST_B;
insert into test_a  select to_char(sysdate,’yyyymmdd’),object_name,object_id from dba_objects;
insert into test_a  select to_char(sysdate,’yyyymmdd’),object_name,object_id from dba_objects;
insert into test_a  select to_char(sysdate,’yyyymmdd’),object_name,object_id from dba_objects;
commit;
insert into test_b select object_id,status from dba_objects;
commit;

可以看出我们生成了两张表的测试数据，其中test_a的数据条数比test_b多，并且行长度也比test_b长。为了获得最准确的执行计划，我们先把表分析一下。

exec dbms_stats.gather_table_stats(ownname=>’xuji’,tabname=>’test_a’,cascade=>true,estimate_percent=>100);
exec dbms_stats.gather_table_stats(ownname=>’xuji’,tabname=>’test_b’,cascade=>true,estimate_percent=>100);


下面我们来做第一个测试，执行一条查询语句。
SET AUTOTRACE TRACEONLY;
SET TIMING ON;
select b.t_stat,a.t_name from test_a a,test_b b where a.t_date >=to_char(sysdate-1,’yyyymmdd’)
and a.t_date<=to_char(sysdate,’yyyymmdd’) and a.t_id<200000
and a.t_id=b.t_id;
直接看结果：

可以看出Oracle CBO根据行数和表的大小，选择了test_b作为驱动表，因为HASH JOIN需要在内存中生成HASH表，选择较小的表作为驱动表比较适合。虽然我们在WHERE条件中的过滤条件都是在test_a上的，不过因为存在a.t_id=b.t_id的连接条件，因此test_a上的t_id的过滤条件会自动传递到test_b上，通过predicate information的第三行可以看到这种传递。可以看出这条SQL一共产生了19532个get，执行时间为0.38秒。如果我们强制使用NLJ来执行这条SQL，看看效果。

可以看出，执行的时间也变长了，GET也增加了将近1倍，效率明显降低了。下面我们继续看一个实验。

我们首先把这两张表的统计数据锁定起来，然后再A表中插入一些t_date是sysdate+2的记录。再执行类似的SQL，不过我们把SQL中关于t_date的条件修改了一下。

上面的执行计划居然使用了NLJ,这是因为统计数据不准确，CBO优化器认为符合条件的数据只有1条。我们锁定了统计数据，因此表和字段上的统计数据并未更新。

通过上面的SQL查看表字段的统计信息，T_DATE的HIGH_VAL还是20221003。接下来我们解除表统计信息的锁定，再分析一下相关的表，看看会出现什么样的情况。

执行计划变为HASH JOIN了，逻辑读也降低到了1/4左右，开销明显降低了。

从上面的例子可以看出，统计数据的正确性对于CBO优化器选择适当的执行计划是如何的重要。如果某些表上的索引很多，而且相似性的索引也很多，那么如果统计信息不准确将会导致索引选择错误。而更可怕的是选择错了连接的方式，使用错误的NESTED LOOP替代了HASH JOIN。在以前我们给用户做Oracle数据库运维服务的时候，经常就会遇到类似的问题导致的系统性能问题。甚至严重时，可以消耗光所有的CPU和IO资源，从而引起应用故障。这种时候我们大部分情况下，可以通过重新采集统计数据来解决。

目前我们的国产数据库在CBO优化器上和Oracle还是有一定的差距，在选择NLJ和HASH JOIN的时候也经常会出现错误。因此为了解决这些问题，我们可以考虑从获得更准确的统计信息数据和优化评估算法的角度去提高执行计划生成的准确性。另外我们也可以充分利用当代硬件的优势，优化执行计划产生和动态调整的算法。比如我们计划使用NLJ来处理某个JOIN，但是在第一步算子执行结束的时候，发现返回的记录数和执行计划产生时不同，那么我们可以进行动态的调整，用新的评估数据重新计算执行计划。甚至我们可以在解析SQL的时候，针对HASH JOIN和NLJ直接生成2套并行的执行计划，同时设定一个阈值，当第一步算子返回外表的行数超过某个阈值时，放弃当前正在执行的执行计划，转而使用另外一套执行计划。

实际上Oracle已经有类似的技术了，我们在研发国产数据库的时候，也可以考虑在这方面多投入一些。

2021年11月20日举办的平安银行数据库技术交流活动中，南科大计算机系的唐博教授就分享了一个通过动态执行计划优化SPARK SQL性能的案例，当时让我们也大开眼界。我们的国产数据库想要实现尽快追赶最新的技术，在优化器领域弯道超车是一个必然要走的路径。除了刚才所说的动态执行计划，把Mysql的BLOCK NESTED LOOP JOIN引入到你的数据库中，当选择错了NLJ的时候，使用BNLJ来让SQL执行的快一些，也是有些价值的。

最近遇到一些数据库运维、优化方面的事情，总是会想到国产数据库，实际上我只是个DBA，不过总是在操数据库厂商的心，真的可能是有点老了，喜欢操闲心了。不过和最近总是在和数据库国产化较劲也有一点关系，真心希望我们的国产数据库能把啥好东西都用上了，早点能支撑我们的核心业务。