王润基-⽤ egg 孵化你的 SQL 优化器.pdf

1、第三届中国Rust开发者会 egg 孵化你的 SQL 优化器王润基 RisingWave 内核开发程师ParserBinderOptimizerExecutorSQLASTLogical PlanPhysical PlanTableCatalogStorageRisingLight 查询引擎的整体结构SELECT name,url FROM t1 JOIN t2 WHERE t1.id=t2.id AND name=BobSQLLogical PlanPhysical PlanProjection name,urlFilter t1.id=t2.id name=“Bob”JoinScan t1

2、(id,name)Scan t2(id,url)Filter#1=“Bob”Hash Join#0=#2Scan$1.1,$1.2Scan$2.1,$2.2Projection#1,#3个 SQL 语句优化的例基于规则的优化(RBO)基于代价的优化(CBO)谓词下推JoinFilterABJoinFilterABFilterJoinAJoinBCJoinCJoinABJoinHash JoinSort-merge JoinNested Loop Join连接重排序连接算法选择TopNAOrderTopNALimit查询优化定义计划节点定义重写规则纯 Rust 编写的第代优化器Visitor 模

3、式纯 Rust 编写的第代优化器e-classe-nodeRewritingRewriting(*?x 2)=(Equality Saturation (*?x 2)=(*?x(/?y?z)(/?x?x)=1 (*?x 1)=?xEquality Saturation (*?x 2)=(*?x(/?y?z)(/?x?x)=1 (*?x 1)=?x SaturationEquality Saturation (*?x 2)=(*?x(/?y?z)(/?x?x)=1 (*?x 1)=?x Saturation Extraction(/(*a 2)2)=aAnalysisSome(1)Some(2)

4、NoneNoneNoneConstant AnalysisAnalysisSome(1)Some(2)NoneNoneConstant FoldingSome(3)NoneSome(6)Some(3)3SELECT name,url FROM t1 JOIN t2 WHERE t1.id=t2.id AND name=Bob(proj(list$1.2$2.2)(filter(and(=$1.1$2.1)(=$1.2“Bob”)(join inner true (scan$1(list$1.1$1.2)(scan$2(list$2.1$2.2)定义语构造表达式2+xy+*定义规则：表达式化简定

5、义规则：算化简JoinFilterABJoinFilter aABJoin ABa&b&cJoinFilter aABFilter bcb&c(filter(and(=$1.1$2.1)(=$1.2“Bob”)(join inner true (scan$1(list$1.1$1.2)(scan$2(list$2.1$2.2)(join inner(=$1.1$2.1)(filter(=$1.2“Bob”)(scan$1(list$1.1$1.2)(scan$2(list$2.1$2.2)定义规则：谓词下推分析：Column Analysis(join inner(and(=$1.1$2.1)

6、(=$1.2“Bob”)(scan$1(list$1.1$1.2)(scan$2(list$2.1$2.2)$1.1,$2.1$1.2$1.1,$1.2$2.1,$2.2表达式节点：到的所有列算节点：输出的所有列Hash Join L_key:A.id,A.id R_key:B.id,C.id Join A.id=C.id AND B.id=C.idCABJoinJoin A.id=C.idCABJoinJoin B.id=C.idABCHash Join A.id=C.idHash Join B.id=C.idABCcost=N2+2Ncost=2N+