You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@doris.apache.org by GitBox <gi...@apache.org> on 2022/04/26 11:52:49 UTC
[GitHub] [incubator-doris] zhengshiJ opened a new issue, #9241: [Feature] Statistics derivation
zhengshiJ opened a new issue, #9241:
URL: https://github.com/apache/incubator-doris/issues/9241
### Search before asking
- [X] I had searched in the [issues](https://github.com/apache/incubator-doris/issues?q=is%3Aissue) and found no similar issues.
### Description
背景
统计信息推导
统计信息推导，是依赖于收集到的表中各个列的统计信息值，根据查询的需要，推导出各个算子的统计信息。通常包含输出的行数信息(OutPutRowCount)、cardinality(ndv)等信息。
其中算子的统计信息推导方式各有不同，对于scan算子，直接通过收集到的统计信息值，构建该表对应列的统计信息。对于join算子，则需要依靠其两个子节点的统计信息值，计算推导出该算子的统计信息。其他算子的计算方法也需要逐一实现。
目前的问题
当前 Doris 统计信息推导包括架构和精准度两方面问题。
架构
当前统计信息的推导耦合在plan node的生成流程中。原因是在当前的架构中，只有在构建逻辑计划时，才会将表达式构建成一颗树的形式，因此只能将获取统计信息的流程耦合在对应node的初始化过程中。但实际上推导统计信息的流程并不依赖于node的生成，因此可以将统计信息的推导流程单独提取出来。
解决方法：参考orca的统计信息获取方法。首先表达式是一棵树，从根节点依次自顶向下获取其子节点的统计信息。当子节点的统计信息为scan算子时，直接获取其对应的统计信息。随后根据子算子的统计信息，自底向上推导出父算子的统计信息。从而完成整个表达式的各个算子的统计信息推导。
精准度
当前join reorder的逻辑依赖于统计信息推导中的cardinality值以及ndv。这就导致cardinality和ndv的值需要精准。
scan算子的统计信息计算方式：
cardinality的计算方法：
cardinality = Math.round(cardinality * selectivity);
原始cardinality为扫描的行数。
选择率计算方法：
selectivity = 1 * (s1)^(1/1) * (s2)^(1/2) * ... * (sn-1)^(1/(n-1)) * (sn)^(1/n)
其中sn等代表各个表达式的选择率，不同类型表达式有不同的选择率。
join算子统计信息计算方式：
遍历每个等值连接对应的列，每个列的cardinality的计算方式如下：
cardinality = |child(0)| * |child(1)| / max(NDV(L.c), NDV(R.d))
依次比较每个等值连接的cardinality，选择出最小的cardinality作为join的cardinality。
但是该join算子的计算方法并不能调用到，原因是调度该方法前，会对左右节点的ndv进行判断，然而ndv的获取是通过mock的方式，直接等于cardinality值。再进一步该cardinality一直是一个无效值。就导致整体方法出现错误，选择的join顺序有问题。
SlotDescriptor.java
public ColumnStats getStats() {
if (stats == null) {
if (column != null) {
stats = column.getStats();
} else {
stats = new ColumnStats();
}
}
// FIXME(dhc): mock ndv
stats.setNumDistinctValues(parent.getCardinality());
return stats;
}
其中parent是TupleDescriptor的实例。
其cardinality的赋值是在最后的finalize阶段进行的。
即已经完成了join reorder等流程。
因此所有通过该方法调用得到的cardinality均是无效值。
以tpch中的q5为例
语句的执行顺序为
原始顺序(括号中的数据代表cardinality(行数))
customer
orders
lineitem
supplier
nation
region
未打开join order的开关时的顺序为，此时为best plan
lineitem (59986052)
join orders (15000000)
join customer (1500000)
join supplier (100000)
join nation (25)
join region (5)
当开启join reorder时执行顺序为，此时反而不是best plan
lineitem (59986052)
join supplier (100000)
join nation (25)
join region (5)
join customer (1500000)
join orders (15000000)
关闭join_reorder开关要比打开join_reorder开关速度快很多，造成这个问题的根本原因是当前获取列的ndv的操作是错误的。
为什么会选择成此种顺序
执行流程如下
计算所有表scan_node节点的cardinality。提取需要分区的行数，根据各个表达式选择率以及计算公式计算出节点的cardinality值。
根据cardinality的值对node的顺序进行降序排列，将cardinality最大的作为最左表。该例子中lineitem为最左表。node的顺序排序后为（lineitem、orders、customer、supplier、nation、region）。
后续按序遍历非最左表的其他表，目标是找出和最左表join后cardinality最小的，但是此处由于生成join节点时，计算其cardinality的方式存在问题，导致出现错误。
根据遍历的表与lineitem的等值连接，尝试构建EqJoinConjunctScanSlots。在此过程中会去比较左右slot的ndv是否是有效值。上面已经介绍了，此处的值会始终保持无效值，导致一直不能创建EqJoinConjunctScanSlots，使join节点的cardinality一直返回的都是左slot的cardinality值。
后续比较新构建的hash节点和之前cardinality最小的hash节点，谁的cardinality更小，将小的更新给最小的节点，进行后续的比较（前提条件是两者class相同）。额外更新的场景是当前是cross join，新的join为hash join，同样更新。
经上述错误逻辑，代码的表现形式为：所有右表和当前表（join的表）有等值连接的，则按序更新，进行join。eg：
lineitem首先和orders，计算cardinality。更新newRoot为orders。
lineitem和customer，计算cardinality，customer的cardinality要比orders的小，更新newRoot为customer。
lineitem和supplier，计算cardinality，supplier的cardinality要比customer的小，更新newRoot为supplier。
lineitem和nation，计算cardinality，两者没有等值连接，不更新。
lineitem和region，计算cardinality，两者没有等值连接，不更新。
所以会第一个join supplier。后续按照相同的逻辑，依次将supplier和其他的表进行join，计算cardinality，得到最终的join顺序。
改进方法：直接去获取列的统计信息，而不是采用mock的方式。
详细设计
（分步骤解释当前步骤的输入输出，相关数据结构，及流程）
统计信息流程与scan_node解耦
scan_node的生成过程中不再计算其cardinality。
新增统计信息计算流程。
依次递归遍历PlanNode的所有孩子。直到遍历到scan节点，获取scan节点的统计信息。
通过cardinality等信息是否为有效值来判定节点是否已经遍历。
将孩子节点的统计信息依次向上返回，计算父节点的统计信息。
直到所有节点的统计均计算完成，返回rootPlanNode。
对于当前架构的支持，并没有树的结构，因此可以再每次构建scan_node以及hash_node后，调用统计信息计算的方法，为对应的节点计算统计信息，这样可以不影响当前的整体执行流程。详细调用方法：为不大量改动当前的执行流程，将会在每个节点创建好之后，调用每个节点的统计信息收集方法。对于scan节点，由于其没有子节点，则直接对该节点进行统计信息推导即可，对于hash_join等包含子孩子的节点，创建好之后，同样调用统计信息推导接口，递归的遍历所有的子节点。
新统计信息推导流程举例
同样以tpch的q5进行举例。
依次对所有的表构建scan节点，此时不进行统计信息的推导。
在每个scan节点创建完成后，调用统计信息推导方法，将推导出的统计信息结果存入在StatsDeriveResult中，并赋值给节点上。
依据统计信息中cardinality，对scan节点进行排序，按cardinality从大到小。原始顺序为：customer、orders、lineitem、supplier、nation、region。调整后的顺序为：lineitem、orders、customer、supplier、nation、region。
依次将orders、customer、supplier、nation、region和lineitem构建hash_join_node，同样此时不在进行统计信息推导，在构建完成后，调用统计信息推导的方法。比较各个节点的cardinality，选择出cardinality最小的，将结果作为lineitem的右表。此处选择的结果为orders。随后将orders作为左表，依次和customer、supplier、nation、region按照相同的方法进行计算，最终得到join的顺序为：lineitem、orders、customer、supplier、nation、region。
完成plan的生成。
### Use case
_No response_
### Related issues
_No response_
### Are you willing to submit PR?
- [X] Yes I am willing to submit a PR!
### Code of Conduct
- [X] I agree to follow this project's [Code of Conduct](https://www.apache.org/foundation/policies/conduct)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [incubator-doris] yiguolei closed issue #9241: [Feature] Statistics derivation
Posted by GitBox <gi...@apache.org>.
yiguolei closed issue #9241: [Feature] Statistics derivation
URL: https://github.com/apache/incubator-doris/issues/9241
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org
[GitHub] [incubator-doris] THELEMITED commented on issue #9241: [Feature] Statistics derivation
Posted by GitBox <gi...@apache.org>.
THELEMITED commented on issue #9241:
URL: https://github.com/apache/incubator-doris/issues/9241#issuecomment-1109745468
I use the threat extrapolation process called schema that is owned by Interpol.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@doris.apache.org
For additional commands, e-mail: commits-help@doris.apache.org