跳到主要内容

外连接转化为内连接

Copyright © 2023 PawSQL

表连接的类型​

表连接的类型主要分为内连接、外连接（左外、右外、全外）、交叉连接，关于他们的语义可以参考下图。

此图来自文章(Visual Representation of SQL Joins)，描述的非常清楚，本文不做太多赘述。

连接类型对执行计划的影响​

我们知道数据库优化器采用动态规划算法对可能的执行路径进行代价估算，以选择出代价尽量小的执行计划进行执行。数据库优化器对执行路径进行规划时，主要进行三类规划：数据表的访问方式；表连接的顺序；表连接的方法。

当优化器进行表连接的规划时，对于Nested Loop Join连接方法，它只考虑以下计划：对于每个连接操作，外部表都会先于内部表被访问。因此当使用外连接时，内外表在SQL中就被明确了（外表为左连接的左表/右连接的右表），优化器的选择是有限的,因而可能导致性能较低的执行计划。

以MySQL官方文档上的例子来说明：

考虑下面这种形式的查询，其中 R(T2) 极大地过滤了来自 T2 表的匹配行数:
SELECT * T1 FROM T1 LEFT JOIN T2 ON P1(T1,T2) WHERE P(T1,T2) AND R(T2) 
如果按照上面所述的执行查询，优化器没有选择余地，只能先访问限制较少的 T1 表，然后再访问限制较多的 T2 表，这可能会导致非常低效的执行计划。

对于全外连接，优化器一般是将其转化为一个左外联机和右外连接的UNION或是采用FULL OUTER HASH JOIN进行执行，会产生类似的性能问题。

外连接简化重写​

如果R(T2) 是一个空拒绝条件条件(NFC)，那么以上的外连接可以转化为内连接，即

SELECT * T1 FROM T1 JOIN T2 ON P1(T1,T2) WHERE P(T1,T2) AND R(T2)

这样，优化器可以先应用R(T2) ，获取非常小的结果集，然后再和T1进行关联。

NFC条件（NULL Filtered Condition）​

空拒绝条件指的是，如果输入为NULL，则其判断结果为false或是unknown，导致该行被过滤掉的条件。判断某个条件是否为外连接操作的空拒绝条件（NFC）的规则很简单:

  • 它是 A IS NOT NULL 的形式，其中 A 是内表的任何属性
  • 它是包含内表引用的谓词，当其中一个参数为 NULL 时评估为 UNKNOWN
  • 它是包含空拒绝条件的“与关联”（AND）组合
  • 它是空拒绝条件的“或关联”（OR）组合

因此，对于这个外连接:

T1 LEFT JOIN T2 ON T1.A=T2.A

以下的条件被视为空拒绝条件：

  • T2.B IS NOT NULL
  • T2.B > 3
  • T2.C <= T1.C
  • T1.B < 3 AND T2.B IS NOT NULL
  • T2.B < 2 OR T2.C > 1

以下的条件不被视为空拒绝条件:

  • T2.B IS NULL
  • T1.B < 3 OR T2.B IS NOT NULL
  • T1.B < 3 OR T2.B > 3
  • T2.B in (1,2, NULL)

数据库中的外连接简化​

绝大多数的关系型数据库优化器都能够提供上述的外连接简化重写。下面以一个案例来示例在MySQL和PostgreSQL中的外连接简化重写。

  • 示例SQL语句
select c_custkey from orders left join customer on c_custkey=o_custkey where C_NATIONKEY  < 20
  • MySQL执行计划
-> Inner hash join (orders.O_CUSTKEY = customer.C_CUSTKEY)  (cost=20541.08 rows=20013)
    -> Table scan on orders  (cost=2529.21 rows=200128)
    -> Hash
        -> Filter: (customer.C_NATIONKEY < 20)  (cost=0.35 rows=1)
            -> Table scan on customer  (cost=0.35 rows=1)
  • PostgreSQL
Hash Join  (cost=100.19..410.47 rows=33 width=4)
  Hash Cond: (orders.o_custkey = customer.c_custkey)
  ->  Seq Scan on orders  (cost=0.00..284.01 rows=10001 width=4)
  ->  Hash  (cost=99.78..99.78 rows=33 width=4)
        ->  Bitmap Heap Scan on customer  (cost=4.54..99.78 rows=33 width=4)
              Recheck Cond: (c_nationkey < 20)
              ->  Bitmap Index Scan on c_nationkey_idx  (cost=0.00..4.53 rows=33 width=0)
                    Index Cond: (c_nationkey < 20)

从执行计划来看，MySQL和PostgreSQL都支持外连接到内连接的重写优化。

PawSQL中的外连接重写优化​

PawSQL实现通过Outer2InnerConversionRewrite规则实现了类似的重写优化，它支持左外连接、右外连接到内连接的重写优化，以及全外连接到左外联机、右外连接或内连接的重写优化。

重要提示: PawSQL实现外连接重写优化的目的不是为了重现数据库优化器的重写优化逻辑，而是因为它可以触发数据库优化器不能实现的索引推荐功能。

  1. 输入SQL语句
select c_custkey from orders left join customer on c_custkey=o_custkey where C_NATIONKEY  < 20
  1. 应用Outer2InnerConversionRewrite后重写的SQL为：
select c_custkey from orders inner join customer on c_custkey=o_custkey where C_NATIONKEY  < 20

  1. 推荐索引

    重写后的SQL通过PawSQL索引推荐引擎推荐出如下两个索引。

CREATE INDEX CONCURRENTLY PAW_IDX1028958902 ON PUBLIC.ORDERS(O_CUSTKEY);
CREATE INDEX CONCURRENTLY PAW_IDX1196677611 ON PUBLIC.CUSTOMER(C_NATIONKEY,C_CUSTKEY);

  1. 执行计划

    把推荐出的索引纳入优化器规划范围后的执行计划为：

  • PostgreSQL上的执行计划
Nested Loop  (cost=0.57..85.53 rows=33 width=4)
->  Index Only Scan using paw_idx1196677611 on customer  (cost=0.29..8.86 rows=33 width=4)
      Index Cond: (c_nationkey < 20)
->  Index Only Scan using paw_idx1028958902 on orders  (cost=0.29..2.24 rows=8 width=4)
      Index Cond: (o_custkey = customer.c_custkey)
  • MySQL上的执行计划
-> Nested loop inner join  (cost=1.91 rows=6)
  -> Filter: (customer.C_NATIONKEY < 20)  (cost=0.35 rows=1)
      -> Index scan on customer using PAW_IDX1360881332  (cost=0.35 rows=1)
  -> Covering index lookup on orders using PAW_IDX1028958902 (O_CUSTKEY=customer.C_CUSTKEY)  (cost=1.56 rows=6)

可以看到，通过PawSQL的整个优化流程，通过索引推荐引擎推荐的两个索引，在数据量较小的PostgreSQL数据库上，查询的代价从410.47减低到85.53，性能提升了379.91%。而在数据量较大的MySQL数据库服务器上，查询代价从20541.08降低到1.91，性能提升了553161.15%。

题外话：测试这个功能是，发现一个知识点，在MySQL中，如果某个字段被定义为外键，默认会有对应的索引建立在上面；而在PostgreSQL系列的数据库中，将某些字段设置外键并不会自动在这些字段上建上索引。

关于PawSQL​

PawSQL专注数据库性能优化的自动化和智能化，支持MySQL，PostgreSQL，Opengauss等，提供的SQL优化产品包括

  • PawSQL Cloud，在线自动化SQL优化工具，支持SQL审查，智能查询重写、基于代价的索引推荐，适用于数据库管理员及数据应用开发人员，
  • PawSQL Advisor，IntelliJ 插件, 适用于数据应用开发人员，可以IDEA/DataGrip应用市场通过名称搜索“PawSQL Advisor”安装。
  • PawSQL Engine, 是PawSQL系列产品的后端优化引擎，可以独立安装部署，并通过http/json的接口提供SQL优化服务。PawSQL Engine以docker镜像的方式提供部署安装。

联系我们​