过滤条件包含 OR 谓词，如何进行查询优化——OceanBase SQL 优化实践

这篇博客涉及两个点，一个是 “OR Expansion 改写”，另一个是 “基于代价的改写”。

背景

在写SQL查询时，难以避免在过滤条件中使用 OR 谓词，但其往往会导致索引利用效率下降的问题 。本文将分享如何通过查询改写的2种方式进行优化。

使用 Or 谓词的示例如下：

CREATE TABLE `t1` (
  `c1` varchar(255) NOT NULL,
  `c2` varchar(255) NOT NULL,
  PRIMARY KEY (`c1`),
  UNIQUE KEY (`c2`));

explain select  * from t1 where c1 = '1' or c2 = '3';
+------------------------------------------------------------------------------------+
| Query Plan                                                                         |
+------------------------------------------------------------------------------------+
| ===============================================                                    |
| |ID|OPERATOR       |NAME|EST.ROWS|EST.TIME(us)|                                    |
| -----------------------------------------------                                    |
| |0 |TABLE FULL SCAN|t1  |1       |3           |                                    |
| ===============================================                                    |
| Outputs & filters:                                                                 |
| -------------------------------------                                              |
|   0 - output([t1.c1], [t1.c2]), filter([t1.c1 = '1' OR t1.c2 = '3']), rowset=16    |
|       access([t1.c1], [t1.c2]), partitions(p0)                                     |
|       is_index_back=false, is_global_index=false, filter_before_indexback[false],  |
|       range_key([t1.c1]), range(MIN ; MAX)always true                              |
+------------------------------------------------------------------------------------+
11 rows in set (0.087 sec)

从上述计划中不难发现，当过滤条件为 where c1 = '1' or c2 = '3' 时，尽管 c1 列和 c2 列都分别建立了索引（或主键），但由于 OR 谓词的工作原理与 AND 谓词不同，导致在实际操作中无法通过索引来避免全表扫描的开销。

如果大家一时反应不过来为何无法利用索引，那这里就再多解释几句：因为在一个 table scan 最多只能选取一个索引进行使用，假如咱们选择使用建在 c1 上的主键索引，并完成了对 where c1 = '1' 的过滤，那么后面依然要在计算 where c2 = '3' 的时候进行一次全表扫描，如果选择使用建在 c2 上的索引也会出现类似的情况。所以无论怎么建索引，怎么用索引，这次全表扫总归是逃不掉的。

基础知识

OR 语句可以被改写成一条等价的带有 UNION ALL 的 SQL，例如上面的这条 SQL，就可以改写成：

explain 

SELECT *
FROM t1
WHERE t1.c1 = 1

UNION ALL

SELECT *
FROM t1
WHERE t1.c2 = 3 and lnnvl(t1.c1 = 1);

其中的 lnnvl 函数，大家可以简单的理解成是一个类似于逻辑非的操作。这个改写一般被称为 OR Expansion（OR 展开），改写的好处就是，把不能利用索引的 OR 操作，改成了等价的且可以在 union all 两侧分别利用两个索引的操作。

优化思路

遇到这种希望利用 OR 两边的索引避免全表扫的场景时，OceanBase 支持通过 Hint /*+ use_concat */ 来强制优化器对原始 SQL 进行 OR Expansion 的改写。这样查询就会被拆分为两个部分，分别利用两个索引，在某些场景下可能可以提升查询性能。

explain select /*+ use_concat */  * from t1 where c1 = '1' or c2 = '3';
+-----------------------------------------------------------------------------------------------+
| Query Plan                                                                                    |
+-----------------------------------------------------------------------------------------------+
| ====================================================                                          |
| |ID|OPERATOR          |NAME  |EST.ROWS|EST.TIME(us)|                                          |
| ----------------------------------------------------                                          |
| |0 |UNION ALL         |      |1       |7           |                                          |
| |1 |├─TABLE GET       |t1    |1       |5           |                                          |
| |2 |└─TABLE RANGE SCAN|t1(c2)|0       |3           |                                          |
| ====================================================                                          |
| Outputs & filters:                                                                            |
| -------------------------------------                                                         |
|   0 - output([UNION([1])], [UNION([2])]), filter(nil), rowset=16                              |
|   1 - output([t1.c1], [t1.c2]), filter(nil), rowset=16                                        |
|       access([t1.c1], [t1.c2]), partitions(p0)                                                |
|       is_index_back=false, is_global_index=false,                                             |
|       range_key([t1.c1]), range[1 ; 1],                                                       |
|       range_cond([t1.c1 = '1'])                                                               |
|   2 - output([t1.c1], [t1.c2]), filter([lnnvl(cast(t1.c1 = '1', TINYINT(-1, 0)))]), rowset=16 |
|       access([t1.c1], [t1.c2]), partitions(p0)                                                |
|       is_index_back=false, is_global_index=false, filter_before_indexback[false],             |
|       range_key([t1.c2], [t1.shadow_pk_0]), range(3,MIN ; 3,MAX),                             |
|       range_cond([t1.c2 = '3'])                                                               |
+-----------------------------------------------------------------------------------------------+
20 rows in set (0.008 sec)

在上面的计划中，可以看到，使用 hint 进行改写后，union all 左边是 table get，说明走了主键，右边是 table range scan，走了 c2 列上的索引。

What's more ?

上面在介绍优化思路时，提到了一句 “在某些场景下可能可以提升查询性能”，原因是优化器的改写算法分为两类：

• 第一类叫基于规则的改写，这类改写总会有正面的效果，例如消除恒真、恒假条件。
• 第二类叫基于代价的改写，特点是某些场景下改写后能生成更好的执行计划，另一些场景下则不能。是否可以触发这类改写，优化器会根据实际的数据分布、是否有合适的索引等因素来进行判断。基于代价的算法在完成改写后需要 “询问” 优化器：“改写后的 SQL 是否能够生成执行代价更小的计划？”，如果代价的确降低了，这次改写才会被触发。

咱们上面提到的 OR Expansion，就属于第二类 “基于代价的改写”，因为 SQL 被一分为二了，所以只有当 union all 两边都有索引，并且索引的过滤性不错的情况下，才能够达到优化的目的。

Q1: 
SELECT * FROM T1 WHERE C1 < 20000 OR C2 < 30 ;

=>

Q2: 
SELECT /*SEL_1*/ * FROM T1 WHERE C1 < 20000 UNION ALL
SELECT /*SEL_2*/ * FROM T1 WHERE C2 < 30 AND LNNVL (C1 < 20000);

针对上面这个 OR Expansion 的例子，简单解释下为什么有些改写需要基于代价才能触发：

• 当 T1 表上在 C1 列和 C2 列上都有索引时：Q1 无法利用这两个索引，它只能走主表扫描。
• Q2 中的 SEL_1 可以利用 C1 上的索引， SEL_2 可以利用 C2 上的索引。如果这两个过滤条件有强的过滤性，那么索引扫描可以大大减少读取数据的开销。此时，触发 OR Expansion 改写有利于生成更好的执行计划。
• 当 T1 表上没有任何索引时：Q1 和 Q2 都需要进行全表扫描。但是 Q2 被分拆为两个 SELECT 子句，它需要进行两次全表扫描。因此，改写后的执行代价会上升。在这种情况下，不应该触发 OR Expansion。

综上所述：在没有及时收集统计信息时（即优化器不能准备计算代价时），可以根据实际情况（两边是否都有索引，以及索引过滤性），通过 Hint /*+ use_concat */ 进行 OR Expansion 改写，达到充分利用索引的目的。当然，也可以根据实际情况，通过 Hint /* +no_expand */ 来禁用 OR Expansion 改写。