本篇详细介绍一下新的基于Hypergraph的算法DPhyp。
例如：R1.a + R2.b + R3.c = R4.d + R5.e + R6.f ；只支持inner joins；
select *
from R1 r1, R2 r2, R3 r3,
R4 r4, R5 r5, R6 r6
where r1.a=r2.a and r2.b=r3.c and
r4.d=r5.d and r5.e=r6.e and
abs(r1.f + r3.f )
= abs(r4.g + r6.g)
介绍算法先介绍下基本概念超图（hypergraph）相比普通的图，其特点是图中的节点是一个集合，称为超节点（hypernode），图中的边所连接的是超节点，即连接两个集合。这类边称为超边（hyperedge）。超图就是由超节点和超边作为最基本元素而构成的。有了超图那么上面的Join Graph可以变成：
由于使用DPccp和Top-Down Partition Search，不能够解决outer join，antijoin的不能自由重排的算法。
MySQL目前采用Bitmap（64bit）来表示，假设Join table个数不会超过61个，看下它的定义
+struct Hyperedge {
+ // The endpoints (hypernodes) of this hyperedge. See the comment about
+ // duplicated edges in Node.
+ //
+ // left and right may not overlap, and both must have at least one bit set.
+ NodeMap left;
+ NodeMap right;
+};
+
+struct Hypergraph {
+ std::vector<Node> nodes; // Maximum 8*sizeof(NodeMap) elements.
+ std::vector<Hyperedge> edges;
+
+ void AddNode();
+ void AddEdge(NodeMap left, NodeMap right);
+};
基本算法流程如下：
- 找到一个图中种子节点Ri
- 不断增加i去找hyperedges，不考虑不连接的和已经处理过的。
- 对于每一个连通子图subgraph (csg)，再重复1和2步骤，找出一个仍然可以连通子图(complement, cmp)，然后连接这个图的cmp成为更大的连通子图(csg-cmp-pair).
- 当找到一个csg-cmp-pair，就形成一个可以进行估算的subjoin
感兴趣可以阅读相应的论文和MySQL的代码（sql/join_optimizer）。
QEP_TAB和执行器Iterator解藕，重新来设置InnoDB row buffer
众所周知，QEB_TAB结构上承载了很多信息，除了上面表访问和Join方法的信息之外，还有InnoDB row buffer、表访问的优化访问方式（ref/range/loose scan/first match/materialize）、附加属性（having/distinct/sort/icp/lateral derived/mrr/cte）、基本物理表结构TABLE_LIST等。作为删除QEP_TAB的基础，首先先做了和执行器的解藕工作，Iterator和QEP_TAB分离。
class TableScanIterator final : public TableRowIterator {
public:
- // Accepts nullptr for qep_tab; qep_tab is used only for setting up record
- // buffers.
- //
- // The pushed condition can be nullptr.
+ // “expected_rows” is used for scaling the record buffer.
+ // If zero or less, no record buffer will be set up.
//
// "examined_rows", if not nullptr, is incremented for each successful Read().
- TableScanIterator(THD *thd, TABLE *table, QEP_TAB *qep_tab,
+ TableScanIterator(THD *thd, TABLE *table, double expected_rows,
ha_rows *examined_rows);
接下来解藕
-static bool init_index_and_record_buffer(const QEP_TAB *qep_tab, handler *file,
+static bool init_index(TABLE *table, handler *file, uint idx, bool sorted) {
-bool set_record_buffer(const QEP_TAB *tab);
+bool set_record_buffer(TABLE *table, double expected_rows_to_fetch);
=>
- return init_index_and_record_buffer(m_qep_tab, m_qep_tab->table()->file,
- m_ref->key, m_use_order);
+ if (table()->file->inited) return false;
+ if (init_index(table(), table()->file, m_ref->key, m_use_order)) {
+ return true;
+ }
+ return set_record_buffer(table(), m_expected_rows);
实现CostingReceiver和转化查询块select_lex成为超图hypergraph
MySQL 8.0.23提供了支持hypergraph的优化器模型的第一个原型版本，通过set optimizer_switch=”hypergraph_optimizer=on”;来打开，主要和原有的优化器区别在于：
- 不再局限于左深树的执行计划
- 用DPhyp动态规划算法代替了强力算和启发式的剪枝方式，减少了搜索空间，当然还有一些限制
- Hash join成为主要的选择方式
- 直接和AccessPath互通，而非直接生成Iterators
主要通过FindBestQueryPlan函数来实现，逻辑如下：
- 先判断是否属于新优化器可以支持的Query语法（CheckSupportedQuery），不支持的直接返回错误ER_HYPERGRAPH_NOT_SUPPORTED_YET
- 转化top_join_list变成JoinHypergraph结构。由于Hypergraph是比较独立的算法层面的实现，JoinHypergraph结构用来更好的把数据库的结构包装到Hypergraph的edges和nodes的概念上的。
- 通过EnumerateAllConnectedPartitions实现论文中的DPhyp算法
- CostingReceiver类包含了过去JOIN planning的主要逻辑，包括根据cost选择相应的访问路径，根据DPhyp生成的子计划进行评估，保留cost最小的子计划。
- 得到root_path后，接下来处理group/agg/having/sort/limit的。对于Group by操作，目前Hypergraph使用sorting first + streaming aggregation的方式。
FindBestQueryPlan最终返回确定的执行计划root_path后，通过CreateIteratorFromAccessPath函数生成对应的执行Iterator树，在Iterator执行器中执行。
举例说明：
两个连通子图
root:test> explain format=tree select * from t1,t2,t3,t4 where t2.f2 = t1.a and t1.a = t3.a;
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Hash cartesian product (no condition) (cost=1.83 rows=2)
-> Inner hash join (t2.f2 = t1.a) (cost=1.55 rows=2)
-> Table scan on t2 (cost=0.25 rows=2)
-> Hash
-> Inner hash join (t1.a = t3.a) (cost=1.27 rows=1)
-> Table scan on t1 (cost=1.00 rows=1)
-> Hash
-> Table scan on t3 (cost=0.25 rows=1)
-> Hash
-> Table scan on t4 (cost=0.25 rows=1)
|
一个连通子图
root:test> explain format=tree select * from t1,t2,t3,t4 where t2.f2 = t1.a and t1.a = t3.a and t2.f2 = t4.pk and t1.a = t4.pk;
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Inner hash join (t2.f2 = t4.pk), (t1.a = t4.pk) (cost=1.83 rows=2)
-> Inner hash join (t2.f2 = t1.a) (cost=1.55 rows=2)
-> Table scan on t2 (cost=0.25 rows=2)
-> Hash
-> Inner hash join (t1.a = t3.a) (cost=1.27 rows=1)
-> Table scan on t1 (cost=1.00 rows=1)
-> Hash
-> Table scan on t3 (cost=0.25 rows=1)
-> Hash
-> Table scan on t4 (cost=0.25 rows=1)
|
通过打开opt_trace来看下整个过程
{
"steps": [
{
"join_preparation": {
"select#": 1,
"steps": [
{
"expanded_query": "/* select#1 */ select `t1`.`a` AS `a`,`t2`.`f2` AS `f2`,`t3`.`a` AS `a`,`t3`.`b` AS `b`,`t4`.`pk` AS `pk`,`t4`.`col_int_nokey` AS `col_int_nokey`,`t4`.`col_int_key` AS `col_int_key`,`t4`.`col_varchar_nokey` AS `col_varchar_nokey` from `t1` join `t2` join `t3` join `t4` where ((`t2`.`f2` = `t1`.`a`) and (`t2`.`f2` = `t4`.`col_int_key`))"
}
]
}
},
{
"join_optimization": {
"select#": 1,
"steps": [
{
"condition_processing": {
"condition": "WHERE",
"original_condition": "((`t2`.`f2` = `t1`.`a`) and (`t2`.`f2` = `t4`.`col_int_key`))",
"steps": [
{
"transformation": "equality_propagation",
"resulting_condition": "((`t2`.`f2` = `t1`.`a`) and (`t2`.`f2` = `t4`.`col_int_key`))"
},
{
"transformation": "trivial_condition_removal",
"resulting_condition": "((`t2`.`f2` = `t1`.`a`) and (`t2`.`f2` = `t4`.`col_int_key`))"
}
]
}
},
{
"substitute_generated_columns": {
}
},
{
"join_optimizer": [
"Join list after simplification:",
"* t4 join_type=inner",
"* t3 join_type=inner",
"* t2 join_type=inner",
"* t1 join_type=inner",
"",
"Made this relational tree; WHERE condition is ((t2.f2 = t1.a) and (t2.f2 = t4.col_int_key)):",
"* Inner join (no join conditions)",
" * Inner join (no join conditions)",
" * Inner join (no join conditions)",
" * t1",
" * t2",
" * t3",
" * t4",
"",
"After pushdown; remaining WHERE conditions are (none):",
"* Inner join (equijoin condition = (t2.f2 = t4.col_int_key))",
" * Cartesian product",
" * Inner join (equijoin condition = (t2.f2 = t1.a))",
" * t1",
" * t2",
" * t3",
" * t4",
"",
"Selectivity of join (t2.f2 = t1.a):",
" - found an index in t1.a for (t2.f2 = t1.a), selectivity = 1.000",
"Selectivity of join [cartesian product]:",
"Selectivity of join (t2.f2 = t4.col_int_key):",
" - found an index in t4.col_int_key for (t2.f2 = t4.col_int_key), selectivity = 1.000",
"",
"Constructed hypergraph:",
"digraph G { # 3 edges",
" t1 -> t2 [label=\"(t2.f2 = t1.a)\"]",
" e2 [shape=circle,width=.001,height=.001,label=\"\"]",
" t1 -> e2 [arrowhead=none,label=\"\"]",
" t2 -> e2 [arrowhead=none,label=\"\"]",
" e2 -> t3 [label=\"[cartesian product]\"]",
" t2 -> t4 [label=\"(t2.f2 = t4.col_int_key)\"]",
"}",
"",
"Enumerating subplans:",
"Found node t4 [rows=1, cost=0.2]",
"Found node t3 [rows=1, cost=0.2]",
"Found node t2 [rows=2, cost=0.2]",
"Found sets {t2} and {t4}, connected by condition (t2.f2 = t4.col_int_key) [rows=2, cost=0.5]",
" - first alternative for this join, keeping",
"Found node t1 [rows=1, cost=1.0]",
"Found sets {t2} and {t1}, connected by condition (t2.f2 = t1.a) [rows=2, cost=1.3]",
" - first alternative for this join, keeping",
"Found sets {t2,t4} and {t1}, connected by condition (t2.f2 = t1.a) [rows=2, cost=1.6]",
" - first alternative for this join, keeping",
"Found sets {t1,t2} and {t4}, connected by condition (t2.f2 = t4.col_int_key) [rows=2, cost=1.6]",
" - more expensive than old cost 1.6, discarding",
"Found sets {t1,t2} and {t3}, connected by condition [cartesian product] [rows=2, cost=1.6]",
" - first alternative for this join, keeping",
"Found sets {t1,t2,t3} and {t4}, connected by condition (t2.f2 = t4.col_int_key) [rows=2, cost=1.8]",
" - first alternative for this join, keeping",
"Found sets {t1,t2,t4} and {t3}, connected by condition [cartesian product] [rows=2, cost=1.8]",
" - more expensive than old cost 1.8, discarding",
"",
"Enumerated 9 subplans."
]
}
]
}
}
]
}
可以看到官方MySQL还提供了查看Graph图的Json格式可视化脚本，我们可以通过online graph看到连通图：
参考资料：
文章转载自ZzzMickey，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
