前置知识

过滤条件下推

在我们的常规认知中，过滤条件肯定是推的越靠近底层越好，将尽可能多的过滤条件更贴近数据源，以使查询时能跳过无关的数据，在AnalyticDB MySQL中，由于存储计算分离架构，那么谓词下推就是把所有能推的谓词都推到存储节点上去做。比如下图，所有的过滤条件都推到存储节点上去做，这样减少了后续算子的计算量，也减少了中间网络传输的数据量。谓词下推带来了很多的好处，基本上所有数据库，都会把谓词下推作为他们重要的优化功能。

全下推到存储弊端

但是过滤条件下推到存储层一定会快吗？
为了弄清这个问题，我们先来看一下AnalyticDB MySQL的存储节点的索引结构。ADB目前默认是全索引，即会为所有列创建索引，并且支持多个条件同时走索引，快速多路合并，能够在毫秒级别找出满足条件的结果集。下图展示了一个表上多个过滤条件的索引查找过程。可以看到是每一列都会查找索引，最后将RowIds做交并差集运算。

不下推 VS 下推

了解完索引结构后，我们构造一个简单的例子，来说明过滤条件下推到存储之后却变慢的情况。我们简单假设一个代价模型，每一行扫索引的代价是A，每一行取明细以及数据传输的代价是B，计算层每一行过滤的代价是C。并考虑如下sql。

create table user (age int, id int);
select count(*) from user; -- 结果10,000;
select count(*) from user where age > 18; -- 结果9,000
select count(*) from user where id < 10; -- 结果 20
-- 考虑如下sql
select * from user where age > 18 and id < 10 -- 结果 10

● 常规计划代价 10,000A + 10,000A + 10B （两列分别查索引的代价 + 取明细以及数据传输的代价)

● Id列不下推计划代价 10,000A + 20B + 20C (一列查索引代价 + 取明细以及数据传输的代价 +计算层代价）
可以看出如果 10B + 20C < 10,000A 的话，Id列不下推计划是更优的计划。

可优化场景

默认情况下，优化器会将所有带索引的列下推存储，从而减少读取至计算引擎的数据。但是仍存在几种场景不建议使用索引过滤数据：
● 谓词选择率高，且谓词条件多，数据经过过滤后返回的数据仍然很多，那么使用索引进行数据过滤然后取交集的效果不一定好。

● 磁盘IO压力大。如果用户业务的查询特征是占用较多的IO资源，或者数据写入较多导致占用了较多IO资源，那么使用索引进行数据过滤时，存在磁盘IO资源的争抢，过滤效果也可能较差。

● 过滤谓词中带有复杂操作，比如字符串比较，LIKE操作等，会对存储节点产生较大的资源消耗，如果其他条件过滤后数据不多，不下推会对整体性能更加友好。

智能下推

所以为了优化ADB上述场景的性能，同时也为了避免ADB研发人员和用户耗费精力使用不下推hint来进行sql调优，在ADB新版本推出了智能优化功能，优化器基于准确的统计信息，在ADB中智能控制过滤条件是否下推到存储节点，让用户不用再纠结于是否下推的sql调优，加速用户查询，把简单交给用户。

术语定义
▶︎ conjunction
我们把过滤条件按照最外层的AND拆分之后的单元叫做conjunction，比如 ((A & B) | C) & D & E 就是由 ((A & B) | C)， D，E 三个conjunction组成的。只所以这么定义是，conjunction是是否下推到存储的最小单元。
一个conjunction里面的条件要么都下推，要么都不下推。
▶︎ selectivity
谓词的过滤度，如果有100行数据，满足A>10的数据是10行，那么A>10的selectivity是10%
▶︎ connector
ADB 优化器支持多个connector，既可以支持ADB本身存储引擎，也可以支持OSS外表。不同的connector需要不同的处理。
实现
▶︎ A series of rules
这里是ADB优化器原有的一系列过滤条件下推的规则，会尽量把filter一路推到 table 上方，推到距离存储节点最近的地方，然后下面的工作便交给了智能下推模块。智能下推模块来决定什么谓词可以继续推给存储节点。
▶︎ Pretreatment
短路优化：在模块的开始会粗略判断整个表扫描的开销，比如是个很小的表，那就快速跳过，以减少后续流程处理的额外开销
表达式转化：应用布尔代数定律，尽量将过滤条件转换为AND连接。拿一个简单的例子来说，( A & B ) | ( C & D ) 是无法做到部分下推，部分不下推的，但是将其转换为( A | C ) & ( A | D ) & ( B | C ) & ( B | D)之后。便可以做到部分下推。这一步进行了限制，不会盲目转化，因为转换之后的表达式变长，可能会导致codegen超限等影响。
▶︎ CalcSelectivity
在这里会根据直方图等精准的statistics，调用ADB优化器中的Cardinality Estimation模块去为每个conjunction计算selectivity和相应的reliability。这个模块依托ADB优化器中精准的统计信息以及完善的基数估计，提供高质量的选择率，为后续的代价的计算以及下推方案的选择，提供准确的输入。
▶︎ Connector Cost Model
存储层自定义的代价模型，定义了根据selectivity计算出来的cost满足一定条件的过滤条件不会下推。这种分离的模式使得接入ADB的别的存储层，有智能下推的需求，也可以简单实现connector cost model，便可以实现智能下推的功能。
▶︎ FilterPushDownSelection
这个模块负责将所有的conjunction以及其selectivity和reliability输入给相应的connector cost model，然后以conjunction为最小单元枚举下推组合，模型算出代价，最后根据代价去选择开销最低的下推方案。这样下来，ADB便有之前的全下推，演变为现在的智能下推。
全下推 VS 智能下推效果

下图展示了一些索引扫描耗时占比大的查询使用智能下推后的加速效果。数据来源于内部灰度客户在智能下推开启前后，线上sql的平均RT变化。可以看到有着十分明显的性能提升。

结语
在数据库和大数据等相关领域，查询优化十分重要。实际生产中的问题，远比本文提到的要复杂。篇幅有限，更多技术细节没有深究。AnalyticDB 作为国内领先的云原生数仓和 TPC-DS 世界记录保持者，在查询优化技术上不断投入和创新。对技术感兴趣的同学，欢迎加入 AnalyticDB 社区讨论。（云数据仓库ADB-开发者群：钉钉群号 23128105）