SQL性能优化 – JOIN实现原理及优化思路

JOIN实现原理与优化

实现原理

假设A表 \scriptsize N_a 行，B表 \scriptsize N_b 行

SELECT * FROM A
LEFT JOIN B
ON A.id = B.refId

Simple Nested-Loop Join

连接算法的基本思想是先做笛卡尔积再进行筛选，最简单的实现是双重循环：外层循环固定左表行，内存循环遍历和匹配右表行，每匹配成功形成一个结果行，时间复杂度 \scriptsize O(N_aN_b)

Block Nested-Loop Join

Simple Nested-Loop Join是此算法的逻辑原理，连接匹配方式均相同，时间复杂度 \scriptsize O(N_aN_b)。但在系统实现时数据以内存块的形式从磁盘加载到内存，这样就减少了IO次数，从而提升连接速度

Index Nested-Loop Join

连接的左表必须完整扫描，但在右表中匹配左表关联键时，无需遍历整张右表，可用查找算法优化关联键值的查询性能

当右表使用B+树索引时，时间复杂度 \scriptsize O(N_alogN_b)
当右表使用Hash索引时，时间复杂度 \scriptsize O(N_a)

优化思路

减少连表：从业务和表设计上简化

一般情况下不超过3张表连接，否则使用冗余列，用空间换时间

查询效率：减少扫描行数

强制修改驱动表

左表被称为驱动表。依据Index Nested-Loop Join中的分析，使用索引时，时间复杂度主要取决于 \scriptsize N_a，因此选择行数比较小的表作为左表可提升性能

为了防止优化器更改驱动表，使用straight join可强制使得左表成为驱动表

使用B+索引

左表的索引主要用于WHERE语句筛选出驱动表
右表的索引用于关联键值查询降低连接成本

右表使用B+树索引连接时，连接复杂度降为 \scriptsize O(N_a + N_alogN_b)

使用Hash索引

右表使用Hash索引连接时，连接复杂度降为 \scriptsize O(N_a)

数据库层面实现：MySQL在8.0.20之后支持Hash索引
业务层面实现：可以先将左右表数据手动查出，构造关联键set，逐一连接拼装结果集

提升IO效率

调大连接缓存

内存可装下的数据量越多，IO次数越少，性能也更高。因此增加连接操作中分配的临时内存可优化连接性能，连接结束后临时内存被回收。可通过 join buffer 来调节单个session的join缓存大小

转换顺序IO

按照左表数据行顺序，根据关联键索引回表定位到右表数据行进行连接，此时对右表数据的读取是随机IO。如果积攒一定数量的回表后的右表主键，将主键排序后再进行读取连接，将进一步减少IO次数，这个顺序读机制被称为 Multi-Range Read，用在JOIN场景中称为 Batched Key Access

通过以下参数开启

set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on'