Steve Carlin has uploaded this change for review. (
http://gerrit.cloudera.org:8080/22942
Change subject: IMPALA-14094: Calcite planner: Use table and column statistics
for optimization
......................................................................
IMPALA-14094: Calcite planner: Use table and column statistics for optimization
This commit enables the Calcite planner join optimization rule to make use
of table and column statistics in Impala.
The ImpalaRelMetadataProvider class provides the metadata classes to the
rule optimizer.
All the ImpalaRelMd* classes are extensions of Calcite Metadata classes. The
ones overridden are:
ImpalaRelMdRowCount:
This provides the cardinality of a given type of RelNode.
The default implementation in the RelMdRowCount is used for some of the
RelNodes. The ones overridden are:
TableScan: Gets the row count from the Table object. returns null if no
stats are defined.
Filter: Calls the FilterSelectivityEstimator and adjusts the number of
rows based on the selectivity of the filter condition.
Join: Uses our own algorithm to determine the number of rows that will
be created by the join condition using the JoinRelationInfo (more on this
below).
ImpalaRelMdDistinctRowCount:
This provides the number of distinct rows returned by the RelNode.
The default implementation in the RelMdDistinct RowCount is used for
some of the RelNodes. The ones overridden are:
TableScan: Uses the stats, return null if no stats are defined.
Aggregate: For some reason, Calcite sometimes returns a number of
distinct rows greater than the number of rows, which doesn't make
sense. So this ensures the number of distinct rows never exceeds
the number of rows.
Filter: The number of distinct rows is reduced by the calculated
selectivity.
Join: same as aggregate.
ImpalaRelMdRowSize:
Provides the Impala interprested size of the Calcite datatypes.
ImpalaRelMdSelectivity:
The selectivity is calculated within the RowCount. An initial atttempt
was done to use this class for selectivity, but it was seemed rather clunky
since the row counts and selectivity are very closely intertwined and
the pruned row counts (a future commit) made this even more complicated.
So the selectivity metadata is overridden or all our RelNodes as full
selectivity (1.0).
As mentioned above, the FilterSelectivityEstimator class tries to approximate
the number of rows filtered out with the given condition. Some work still
needs to be done to make this more in line with the Expr seletivities, a Jira
will be filed for this.
The JoinRelationInfo is the helper class that estimates the number of rows
that will be output of the Join RelNode. The join condition is split up into
multiple conditions broken up by the AND keyword. This first pass has some major
flaws which need to be corrected, including:
- Only equality conditions limit the number of rows. Non-equality conditions
will be ignored. If there are only non-equality conditions, the cardinality
will be the equivalent of a cross join.
- Left joins take the maximum of the calculated join and the total number
of rows on the left side. This can probably be improved upon if we find
the matching rows provide a cardinality that is greater than one for each
row. (Of course, right joins and outer joins have this same logic).
Change-Id: Ic8daa7e33ae7b819d59848c247f329a8049e034d
---
M fe/src/main/java/org/apache/impala/planner/JoinNode.java
M
java/calcite-planner/src/main/java/org/apache/impala/calcite/schema/CalciteTable.java
A
java/calcite-planner/src/main/java/org/apache/impala/calcite/schema/FilterSelectivityEstimator.java
A
java/calcite-planner/src/main/java/org/apache/impala/calcite/schema/ImpalaRelMdDistinctRowCount.java
A
java/calcite-planner/src/main/java/org/apache/impala/calcite/schema/ImpalaRelMdRowCount.java
A
java/calcite-planner/src/main/java/org/apache/impala/calcite/schema/ImpalaRelMdSelectivity.java
A
java/calcite-planner/src/main/java/org/apache/impala/calcite/schema/ImpalaRelMdSize.java
A
java/calcite-planner/src/main/java/org/apache/impala/calcite/schema/ImpalaRelMetadataProvider.java
A
java/calcite-planner/src/main/java/org/apache/impala/calcite/schema/JoinRelationInfo.java
M
java/calcite-planner/src/main/java/org/apache/impala/calcite/service/CalciteJniFrontend.java
M
java/calcite-planner/src/main/java/org/apache/impala/calcite/service/CalciteRelNodeConverter.java
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q01.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q02.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q03.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q04.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q05.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q06.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q07.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q08.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q10a.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q11.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q12.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q13.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q14a.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q14b.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q15.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q16.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q17.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q18.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q19.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q20.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q21.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q22.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q23a.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q23b.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q24a.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q24b.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q25.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q26.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q27.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q29.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q32.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q33.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q34.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q36.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q37.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q38.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q39a.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q39b.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q40.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q41.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q42.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q43-verbose.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q43.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q44.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q45.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q46.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q47.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q48.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q49.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q50.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q52.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q53.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q54.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q55.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q56.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q57.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q58.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q59.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q60.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q61.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q62.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q63.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q64.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q65.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q66.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q67.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q68.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q69.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q70.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q71.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q72.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q73.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q74.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q75.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q76.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q77.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q79.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q80.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q82.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q83.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q84.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q85.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q86.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q87.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q88.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q89.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q90.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q91.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q92.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q94.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q95.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q96.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q98.test
M
testdata/workloads/functional-planner/queries/PlannerTest/calcite_tpcds/tpcds-q99.test
105 files changed, 47,452 insertions(+), 46,465 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/42/22942/2
--
To view, visit http://gerrit.cloudera.org:8080/22942
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: Ic8daa7e33ae7b819d59848c247f329a8049e034d
Gerrit-Change-Number: 22942
Gerrit-PatchSet: 2
Gerrit-Owner: Steve Carlin <[email protected]>
