一、名词解释NLJNested-Loop Join嵌套循环联接联接执行的一种方式外表一行一行取出每取一行就在内表上执行一次匹配查找。内表侧若有合适索引通常是反复索引探测内表若无索引往往演变成反复扫内表。BNLBlock Nested-Loop Join块嵌套循环联接在 NLJ 思路上的改进先把外表的多行放进join_buffer缓存成一批然后让内表扫描一轮与这一批外表行同时匹配再换下一批外表。目的是在内表无索引时减少「内表从头到尾」被完整扫描的次数。二、两种算法核心原理的实现0、TestDataFactorypackagecom.cj;importjava.util.ArrayList;importjava.util.List;/** * 测试数据工厂生成 NLJ/BNL 对比实验所需的驱动表和被驱动表 */publicclassTestDataFactory{/** * 行数据结构 */publicstaticclassRow{finalintid;finalStringdata;Row(intid,Stringdata){this.idid;this.datadata;}}/** * 生成驱动表外表 * * param rowCount 行数 * return 驱动表数据 */publicstaticListRowcreateDriverTable(introwCount){ListRowtablenewArrayList(rowCount);for(inti1;irowCount;i){table.add(newRow(i,D-i));}returntable;}/** * 生成被驱动表内表 * * param rowCount 行数 * return 被驱动表数据 */publicstaticListRowcreateDrivenTable(introwCount){ListRowtablenewArrayList(rowCount);for(inti1;irowCount;i){table.add(newRow(i,T-i));}returntable;}}1、NLJpackagecom.cj;importjava.util.ArrayList;importjava.util.List;/** * 朴素 NLJ外表每一行触发一次内表「从头到尾」完整扫描。 * 与 {link BNL} 使用相同数据规模便于对比 innerFullScans / 耗时。 */publicclassNLJ{/** 外表行数驱动表—与 BNL 保持一致 */privatestaticfinalintOUTER_ROWS8_000;/** 内表行数被驱动表假设无索引只能全表扫 */privatestaticfinalintINNER_ROWS40_000;/** * 每次「开始一整遍内表扫描」时调用模拟页读/寻道等非纯比较成本。 * BNL 因批处理会少调用很多次这里差异会被放大。 *//** 调大更明显体会「少扫几遍内表」带来的差距机器慢再改小 */privatestaticfinalintWORK_PER_INNER_SCAN_START400_000;SuppressWarnings(FieldCanBeLocal)privatestaticvolatilelongsink;staticvoidonInnerScanStart(){longx0;for(inti0;iWORK_PER_INNER_SCAN_START;i){x(long)i*i%997;}sinkx;}/** * 执行朴素嵌套循环连接NLJ * * param driverTable 驱动表外表 * param drivenTable 被驱动表内表 * return 连接结果集每个元素为 driverData|drivenData */staticListStringexecuteNLJ(ListTestDataFactory.RowdriverTable,ListTestDataFactory.RowdrivenTable){ListStringresultnewArrayList();intinnerFullScans0;for(TestDataFactory.RowdriverRow:driverTable){innerFullScans;onInnerScanStart();for(TestDataFactory.RowdrivenRow:drivenTable){if(driverRow.iddrivenRow.id){result.add(driverRow.data|drivenRow.data);}}}// 打印统计信息System.out.println(innerFullScans(内表整表扫描遍数) innerFullScans);System.out.println(matches result.size());returnresult;}publicstaticvoidmain(String[]args){// 准备测试数据ListTestDataFactory.RowdriverTableTestDataFactory.createDriverTable(OUTER_ROWS);ListTestDataFactory.RowdrivenTableTestDataFactory.createDrivenTable(INNER_ROWS);System.out.println( Naive NLJ );System.out.println(outerRowsOUTER_ROWS, innerRowsINNER_ROWS);// 执行 NLJ 算法并计时longt0System.nanoTime();ListStringresultexecuteNLJ(driverTable,drivenTable);longms(System.nanoTime()-t0)/1_000_000L;System.out.println(time ms ms);}}2、BNLpackagecom.cj;importjava.util.ArrayList;importjava.util.List;/** * BNL外表按批装入 buffer每批只触发一次内表「从头到尾」完整扫描。 * 与 {link NLJ} 使用相同数据规模innerFullScans ≈ ceil(OUTER_ROWS / BATCH_SIZE)。 */publicclassBNL{privatestaticfinalintOUTER_ROWS8_000;privatestaticfinalintINNER_ROWS40_000;/** 每批外表行数模拟 join_buffer 能容纳的外表行数 */privatestaticfinalintBATCH_SIZE100;/** 与 NLJ 保持一致保证可比 */privatestaticfinalintWORK_PER_INNER_SCAN_START400_000;SuppressWarnings(FieldCanBeLocal)privatestaticvolatilelongsink;staticvoidonInnerScanStart(){longx0;for(inti0;iWORK_PER_INNER_SCAN_START;i){x(long)i*i%997;}sinkx;}/** * 执行块嵌套循环连接BNL * * param driverTable 驱动表外表 * param drivenTable 被驱动表内表 * param batchSize 每批处理的外表行数模拟 join_buffer 大小 * return 连接结果集每个元素为 driverData|drivenData */staticListStringexecuteBNL(ListTestDataFactory.RowdriverTable,ListTestDataFactory.RowdrivenTable,intbatchSize){inttotalBlocks(int)Math.ceil(driverTable.size()/(double)batchSize);ListStringresultnewArrayList();intinnerFullScans0;for(intblockIndex0;blockIndextotalBlocks;blockIndex){intstartblockIndex*batchSize;intendMath.min(startbatchSize,driverTable.size());ListTestDataFactory.RowdriverBlockdriverTable.subList(start,end);innerFullScans;onInnerScanStart();for(TestDataFactory.RowdrivenRow:drivenTable){for(TestDataFactory.RowdriverRow:driverBlock){if(drivenRow.iddriverRow.id){result.add(driverRow.data|drivenRow.data);}}}}// 打印统计信息System.out.println(batches totalBlocks);System.out.println(innerFullScans(内表整表扫描遍数) innerFullScans);System.out.println(matches result.size());returnresult;}publicstaticvoidmain(String[]args){// 准备测试数据ListTestDataFactory.RowdriverTableTestDataFactory.createDriverTable(OUTER_ROWS);ListTestDataFactory.RowdrivenTableTestDataFactory.createDrivenTable(INNER_ROWS);System.out.println( Block Nested Loop (BNL) );System.out.println(outerRowsOUTER_ROWS, innerRowsINNER_ROWS, batchSizeBATCH_SIZE);// 执行 BNL 算法并计时longt0System.nanoTime();ListStringresultexecuteBNL(driverTable,drivenTable,BATCH_SIZE);longms(System.nanoTime()-t0)/1_000_000L;System.out.println(time ms ms);}}三、原理解释BNL 的目标并非把联接的比较量级从N×M理论上降为线性而是在内表缺少可用索引、往往只能整表扫描时通过join_buffer分批缓存外表行把内表「从头到尾完整遍历」的轮数从约N降到约⌈N/B⌉以降低重复全表扫描带来的开销。朴素 NLJ内表无可用索引外表每推进一行就对内表做一次「从头到尾」的完整遍历因此内表被完整扫描的轮数约等于外表行数N最后一行也会触发一整遍内表扫描。BNL外表按批处理时内表「从头到尾完整扫一遍」的次数约为「外表行数 ÷ 每批行数」向上取整每批能装多少行受join_buffer_size等限制最后一批可能不满。内表往往是大表时每多扫一遍页 I/O、Buffer Pool 压力都会叠加因此「少扫几遍」收益更明显。数据页通常经InnoDB Buffer Pool读。朴素 NLJ内表页可能被反复走过 N 轮易出现缓存抖动、物理读压力。BNL内表完整遍历约N/B 轮同一任务窗口内重复装载同一套内表页的次数通常少得多。join_buffer在Server 层与Buffer Pool不同前者缓冲一批外表参与联接的列后者缓存数据/索引页。四、在 EXPLAIN 里当Extra中出现Using join buffer (Block Nested Loop)具体文案随版本略有差异时多半与BNL及join_buffer相关需结合type、rows、Extra一并阅读。
NLJ 与 BNL 联接算法
一、名词解释NLJNested-Loop Join嵌套循环联接联接执行的一种方式外表一行一行取出每取一行就在内表上执行一次匹配查找。内表侧若有合适索引通常是反复索引探测内表若无索引往往演变成反复扫内表。BNLBlock Nested-Loop Join块嵌套循环联接在 NLJ 思路上的改进先把外表的多行放进join_buffer缓存成一批然后让内表扫描一轮与这一批外表行同时匹配再换下一批外表。目的是在内表无索引时减少「内表从头到尾」被完整扫描的次数。二、两种算法核心原理的实现0、TestDataFactorypackagecom.cj;importjava.util.ArrayList;importjava.util.List;/** * 测试数据工厂生成 NLJ/BNL 对比实验所需的驱动表和被驱动表 */publicclassTestDataFactory{/** * 行数据结构 */publicstaticclassRow{finalintid;finalStringdata;Row(intid,Stringdata){this.idid;this.datadata;}}/** * 生成驱动表外表 * * param rowCount 行数 * return 驱动表数据 */publicstaticListRowcreateDriverTable(introwCount){ListRowtablenewArrayList(rowCount);for(inti1;irowCount;i){table.add(newRow(i,D-i));}returntable;}/** * 生成被驱动表内表 * * param rowCount 行数 * return 被驱动表数据 */publicstaticListRowcreateDrivenTable(introwCount){ListRowtablenewArrayList(rowCount);for(inti1;irowCount;i){table.add(newRow(i,T-i));}returntable;}}1、NLJpackagecom.cj;importjava.util.ArrayList;importjava.util.List;/** * 朴素 NLJ外表每一行触发一次内表「从头到尾」完整扫描。 * 与 {link BNL} 使用相同数据规模便于对比 innerFullScans / 耗时。 */publicclassNLJ{/** 外表行数驱动表—与 BNL 保持一致 */privatestaticfinalintOUTER_ROWS8_000;/** 内表行数被驱动表假设无索引只能全表扫 */privatestaticfinalintINNER_ROWS40_000;/** * 每次「开始一整遍内表扫描」时调用模拟页读/寻道等非纯比较成本。 * BNL 因批处理会少调用很多次这里差异会被放大。 *//** 调大更明显体会「少扫几遍内表」带来的差距机器慢再改小 */privatestaticfinalintWORK_PER_INNER_SCAN_START400_000;SuppressWarnings(FieldCanBeLocal)privatestaticvolatilelongsink;staticvoidonInnerScanStart(){longx0;for(inti0;iWORK_PER_INNER_SCAN_START;i){x(long)i*i%997;}sinkx;}/** * 执行朴素嵌套循环连接NLJ * * param driverTable 驱动表外表 * param drivenTable 被驱动表内表 * return 连接结果集每个元素为 driverData|drivenData */staticListStringexecuteNLJ(ListTestDataFactory.RowdriverTable,ListTestDataFactory.RowdrivenTable){ListStringresultnewArrayList();intinnerFullScans0;for(TestDataFactory.RowdriverRow:driverTable){innerFullScans;onInnerScanStart();for(TestDataFactory.RowdrivenRow:drivenTable){if(driverRow.iddrivenRow.id){result.add(driverRow.data|drivenRow.data);}}}// 打印统计信息System.out.println(innerFullScans(内表整表扫描遍数) innerFullScans);System.out.println(matches result.size());returnresult;}publicstaticvoidmain(String[]args){// 准备测试数据ListTestDataFactory.RowdriverTableTestDataFactory.createDriverTable(OUTER_ROWS);ListTestDataFactory.RowdrivenTableTestDataFactory.createDrivenTable(INNER_ROWS);System.out.println( Naive NLJ );System.out.println(outerRowsOUTER_ROWS, innerRowsINNER_ROWS);// 执行 NLJ 算法并计时longt0System.nanoTime();ListStringresultexecuteNLJ(driverTable,drivenTable);longms(System.nanoTime()-t0)/1_000_000L;System.out.println(time ms ms);}}2、BNLpackagecom.cj;importjava.util.ArrayList;importjava.util.List;/** * BNL外表按批装入 buffer每批只触发一次内表「从头到尾」完整扫描。 * 与 {link NLJ} 使用相同数据规模innerFullScans ≈ ceil(OUTER_ROWS / BATCH_SIZE)。 */publicclassBNL{privatestaticfinalintOUTER_ROWS8_000;privatestaticfinalintINNER_ROWS40_000;/** 每批外表行数模拟 join_buffer 能容纳的外表行数 */privatestaticfinalintBATCH_SIZE100;/** 与 NLJ 保持一致保证可比 */privatestaticfinalintWORK_PER_INNER_SCAN_START400_000;SuppressWarnings(FieldCanBeLocal)privatestaticvolatilelongsink;staticvoidonInnerScanStart(){longx0;for(inti0;iWORK_PER_INNER_SCAN_START;i){x(long)i*i%997;}sinkx;}/** * 执行块嵌套循环连接BNL * * param driverTable 驱动表外表 * param drivenTable 被驱动表内表 * param batchSize 每批处理的外表行数模拟 join_buffer 大小 * return 连接结果集每个元素为 driverData|drivenData */staticListStringexecuteBNL(ListTestDataFactory.RowdriverTable,ListTestDataFactory.RowdrivenTable,intbatchSize){inttotalBlocks(int)Math.ceil(driverTable.size()/(double)batchSize);ListStringresultnewArrayList();intinnerFullScans0;for(intblockIndex0;blockIndextotalBlocks;blockIndex){intstartblockIndex*batchSize;intendMath.min(startbatchSize,driverTable.size());ListTestDataFactory.RowdriverBlockdriverTable.subList(start,end);innerFullScans;onInnerScanStart();for(TestDataFactory.RowdrivenRow:drivenTable){for(TestDataFactory.RowdriverRow:driverBlock){if(drivenRow.iddriverRow.id){result.add(driverRow.data|drivenRow.data);}}}}// 打印统计信息System.out.println(batches totalBlocks);System.out.println(innerFullScans(内表整表扫描遍数) innerFullScans);System.out.println(matches result.size());returnresult;}publicstaticvoidmain(String[]args){// 准备测试数据ListTestDataFactory.RowdriverTableTestDataFactory.createDriverTable(OUTER_ROWS);ListTestDataFactory.RowdrivenTableTestDataFactory.createDrivenTable(INNER_ROWS);System.out.println( Block Nested Loop (BNL) );System.out.println(outerRowsOUTER_ROWS, innerRowsINNER_ROWS, batchSizeBATCH_SIZE);// 执行 BNL 算法并计时longt0System.nanoTime();ListStringresultexecuteBNL(driverTable,drivenTable,BATCH_SIZE);longms(System.nanoTime()-t0)/1_000_000L;System.out.println(time ms ms);}}三、原理解释BNL 的目标并非把联接的比较量级从N×M理论上降为线性而是在内表缺少可用索引、往往只能整表扫描时通过join_buffer分批缓存外表行把内表「从头到尾完整遍历」的轮数从约N降到约⌈N/B⌉以降低重复全表扫描带来的开销。朴素 NLJ内表无可用索引外表每推进一行就对内表做一次「从头到尾」的完整遍历因此内表被完整扫描的轮数约等于外表行数N最后一行也会触发一整遍内表扫描。BNL外表按批处理时内表「从头到尾完整扫一遍」的次数约为「外表行数 ÷ 每批行数」向上取整每批能装多少行受join_buffer_size等限制最后一批可能不满。内表往往是大表时每多扫一遍页 I/O、Buffer Pool 压力都会叠加因此「少扫几遍」收益更明显。数据页通常经InnoDB Buffer Pool读。朴素 NLJ内表页可能被反复走过 N 轮易出现缓存抖动、物理读压力。BNL内表完整遍历约N/B 轮同一任务窗口内重复装载同一套内表页的次数通常少得多。join_buffer在Server 层与Buffer Pool不同前者缓冲一批外表参与联接的列后者缓存数据/索引页。四、在 EXPLAIN 里当Extra中出现Using join buffer (Block Nested Loop)具体文案随版本略有差异时多半与BNL及join_buffer相关需结合type、rows、Extra一并阅读。
