alex-plekhanov commented on code in PR #13389:
URL: https://github.com/apache/ignite/pull/13389#discussion_r4421411484
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -72,48 +117,335 @@ public class IgniteMdRowCount extends RelMdRowCount {
mq.getRowCount(rel.getLeft()));
}
+ JoinInfo joinInfo = rel.analyzeCondition();
+
+ if (joinInfo.pairs().isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
// Row count estimates of 0 will be rounded up to 1.
// So, use maxRowCount where the product is very small.
- final Double left = mq.getRowCount(rel.getLeft());
- final Double right = mq.getRowCount(rel.getRight());
+ final Double leftRowCnt = mq.getRowCount(rel.getLeft());
+ final Double rightRowCnt = multiply(mq.getRowCount(rel.getRight()),
rightAdjust);
- if (left == null || right == null)
+ if (leftRowCnt == null || rightRowCnt == null)
return null;
- if (left <= 1D || right <= 1D) {
+ if (leftRowCnt <= 1D || rightRowCnt <= 1D) {
Double max = mq.getMaxRowCount(rel);
if (max != null && max <= 1D)
return max;
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ // Primary key columns per table.
+ Map<IgniteTable, List<Integer>> pkColsPerTable = new
IdentityHashMap<>(2);
+
+ Map<Integer, KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq,
rel.getLeft(), joinInfo.leftKeys, pkColsPerTable);
+ Map<Integer, KeyColumnOrigin> columnsFromRight = resolveOrigins(mq,
rel.getRight(), joinInfo.rightKeys, pkColsPerTable);
+
+ if (columnsFromLeft.isEmpty() || columnsFromRight.isEmpty()) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ Map<TablesPair, JoinContext> joinCtxts = new HashMap<>();
+ for (IntPair joinKeys : joinInfo.pairs()) {
+ KeyColumnOrigin leftKey = columnsFromLeft.get(joinKeys.source);
+ KeyColumnOrigin rightKey = columnsFromRight.get(joinKeys.target);
+
+ if (leftKey == null || rightKey == null) {
+ continue;
+ }
+
+ joinCtxts.computeIfAbsent(
+ new TablesPair(
+ leftKey.origin.getOriginTable(),
+ rightKey.origin.getOriginTable()
+ ),
+ key -> {
+ IgniteTable leftTable = key.left.unwrap(IgniteTable.class);
+ IgniteTable rightTable =
key.right.unwrap(IgniteTable.class);
+
+ assert leftTable != null && rightTable != null;
+
+ List<Integer> leftPkCols = pkColsPerTable.get(leftTable);
+ List<Integer> rightPkCols = pkColsPerTable.get(rightTable);
+
+ assert leftPkCols != null && rightPkCols != null :
leftPkCols + " " + rightPkCols;
+
+ return new JoinContext(leftPkCols.size(),
rightPkCols.size());
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinCtxts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinCtxts.values().iterator();
+ JoinContext joinCtx = it.next();
+ while (it.hasNext()) {
+ JoinContext nextCtx = it.next();
+ if (nextCtx.joinType().strength > joinCtx.joinType().strength) {
+ joinCtx = nextCtx;
+ }
+
+ if (joinCtx.joinType().strength ==
JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (joinCtx.joinType() == JoiningRelationType.UNKNOWN) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ double postFiltrationAdjustment = 1.0;
+
+ // Outer joins return every row of the preserved side(s), the result
can't be smaller than that.
+ double preservedRowCnt = 0.0;
+
+ switch (rel.getJoinType()) {
+ case INNER:
+ case SEMI:
+ // Extra join keys as well as non-equi conditions serves as
post-filtration,
+ // therefore we need to adjust final result with a little
factor.
+ if (joinCtxts.size() != 1 || !joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+
+ break;
+ case LEFT:
+ preservedRowCnt = leftRowCnt;
+
+ break;
+ case RIGHT:
+ preservedRowCnt = rightRowCnt;
+
+ break;
+ case FULL:
+ preservedRowCnt = Math.max(leftRowCnt, rightRowCnt);
+
+ break;
+ default:
+ break;
+ }
+
+ double baseRowCnt = 0.0;
+ Double percentageAdjustment = null;
+ if (joinCtx.joinType() == JoiningRelationType.PK_ON_PK) {
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ if (!joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
Review Comment:
Looks like it's already set above
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -72,48 +117,335 @@ public class IgniteMdRowCount extends RelMdRowCount {
mq.getRowCount(rel.getLeft()));
}
+ JoinInfo joinInfo = rel.analyzeCondition();
+
+ if (joinInfo.pairs().isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
// Row count estimates of 0 will be rounded up to 1.
// So, use maxRowCount where the product is very small.
- final Double left = mq.getRowCount(rel.getLeft());
- final Double right = mq.getRowCount(rel.getRight());
+ final Double leftRowCnt = mq.getRowCount(rel.getLeft());
+ final Double rightRowCnt = multiply(mq.getRowCount(rel.getRight()),
rightAdjust);
- if (left == null || right == null)
+ if (leftRowCnt == null || rightRowCnt == null)
return null;
- if (left <= 1D || right <= 1D) {
+ if (leftRowCnt <= 1D || rightRowCnt <= 1D) {
Double max = mq.getMaxRowCount(rel);
if (max != null && max <= 1D)
return max;
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ // Primary key columns per table.
+ Map<IgniteTable, List<Integer>> pkColsPerTable = new
IdentityHashMap<>(2);
+
+ Map<Integer, KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq,
rel.getLeft(), joinInfo.leftKeys, pkColsPerTable);
+ Map<Integer, KeyColumnOrigin> columnsFromRight = resolveOrigins(mq,
rel.getRight(), joinInfo.rightKeys, pkColsPerTable);
+
+ if (columnsFromLeft.isEmpty() || columnsFromRight.isEmpty()) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ Map<TablesPair, JoinContext> joinCtxts = new HashMap<>();
+ for (IntPair joinKeys : joinInfo.pairs()) {
+ KeyColumnOrigin leftKey = columnsFromLeft.get(joinKeys.source);
+ KeyColumnOrigin rightKey = columnsFromRight.get(joinKeys.target);
+
+ if (leftKey == null || rightKey == null) {
+ continue;
+ }
+
+ joinCtxts.computeIfAbsent(
+ new TablesPair(
+ leftKey.origin.getOriginTable(),
+ rightKey.origin.getOriginTable()
+ ),
+ key -> {
+ IgniteTable leftTable = key.left.unwrap(IgniteTable.class);
+ IgniteTable rightTable =
key.right.unwrap(IgniteTable.class);
+
+ assert leftTable != null && rightTable != null;
+
+ List<Integer> leftPkCols = pkColsPerTable.get(leftTable);
+ List<Integer> rightPkCols = pkColsPerTable.get(rightTable);
+
+ assert leftPkCols != null && rightPkCols != null :
leftPkCols + " " + rightPkCols;
+
+ return new JoinContext(leftPkCols.size(),
rightPkCols.size());
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinCtxts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinCtxts.values().iterator();
+ JoinContext joinCtx = it.next();
+ while (it.hasNext()) {
+ JoinContext nextCtx = it.next();
+ if (nextCtx.joinType().strength > joinCtx.joinType().strength) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -72,48 +117,335 @@ public class IgniteMdRowCount extends RelMdRowCount {
mq.getRowCount(rel.getLeft()));
}
+ JoinInfo joinInfo = rel.analyzeCondition();
+
+ if (joinInfo.pairs().isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
// Row count estimates of 0 will be rounded up to 1.
// So, use maxRowCount where the product is very small.
- final Double left = mq.getRowCount(rel.getLeft());
- final Double right = mq.getRowCount(rel.getRight());
+ final Double leftRowCnt = mq.getRowCount(rel.getLeft());
+ final Double rightRowCnt = multiply(mq.getRowCount(rel.getRight()),
rightAdjust);
- if (left == null || right == null)
+ if (leftRowCnt == null || rightRowCnt == null)
return null;
- if (left <= 1D || right <= 1D) {
+ if (leftRowCnt <= 1D || rightRowCnt <= 1D) {
Double max = mq.getMaxRowCount(rel);
if (max != null && max <= 1D)
return max;
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ // Primary key columns per table.
+ Map<IgniteTable, List<Integer>> pkColsPerTable = new
IdentityHashMap<>(2);
+
+ Map<Integer, KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq,
rel.getLeft(), joinInfo.leftKeys, pkColsPerTable);
+ Map<Integer, KeyColumnOrigin> columnsFromRight = resolveOrigins(mq,
rel.getRight(), joinInfo.rightKeys, pkColsPerTable);
+
+ if (columnsFromLeft.isEmpty() || columnsFromRight.isEmpty()) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ Map<TablesPair, JoinContext> joinCtxts = new HashMap<>();
+ for (IntPair joinKeys : joinInfo.pairs()) {
+ KeyColumnOrigin leftKey = columnsFromLeft.get(joinKeys.source);
+ KeyColumnOrigin rightKey = columnsFromRight.get(joinKeys.target);
+
+ if (leftKey == null || rightKey == null) {
+ continue;
+ }
+
+ joinCtxts.computeIfAbsent(
+ new TablesPair(
+ leftKey.origin.getOriginTable(),
+ rightKey.origin.getOriginTable()
+ ),
+ key -> {
+ IgniteTable leftTable = key.left.unwrap(IgniteTable.class);
+ IgniteTable rightTable =
key.right.unwrap(IgniteTable.class);
+
+ assert leftTable != null && rightTable != null;
+
+ List<Integer> leftPkCols = pkColsPerTable.get(leftTable);
+ List<Integer> rightPkCols = pkColsPerTable.get(rightTable);
+
+ assert leftPkCols != null && rightPkCols != null :
leftPkCols + " " + rightPkCols;
+
+ return new JoinContext(leftPkCols.size(),
rightPkCols.size());
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinCtxts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinCtxts.values().iterator();
+ JoinContext joinCtx = it.next();
+ while (it.hasNext()) {
+ JoinContext nextCtx = it.next();
+ if (nextCtx.joinType().strength > joinCtx.joinType().strength) {
+ joinCtx = nextCtx;
+ }
+
+ if (joinCtx.joinType().strength ==
JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (joinCtx.joinType() == JoiningRelationType.UNKNOWN) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ double postFiltrationAdjustment = 1.0;
+
+ // Outer joins return every row of the preserved side(s), the result
can't be smaller than that.
+ double preservedRowCnt = 0.0;
+
+ switch (rel.getJoinType()) {
+ case INNER:
+ case SEMI:
+ // Extra join keys as well as non-equi conditions serves as
post-filtration,
+ // therefore we need to adjust final result with a little
factor.
+ if (joinCtxts.size() != 1 || !joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+
+ break;
+ case LEFT:
+ preservedRowCnt = leftRowCnt;
+
+ break;
+ case RIGHT:
+ preservedRowCnt = rightRowCnt;
+
+ break;
+ case FULL:
+ preservedRowCnt = Math.max(leftRowCnt, rightRowCnt);
+
+ break;
+ default:
+ break;
+ }
+
+ double baseRowCnt = 0.0;
+ Double percentageAdjustment = null;
+ if (joinCtx.joinType() == JoiningRelationType.PK_ON_PK) {
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ if (!joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+ // Assume we have two fact tables SALES and RETURNS sharing
the same primary key. Every item
+ // can be sold, but only items which were sold can be returned
back, therefore
+ // size(SALES) > size(RETURNS). When joining SALES on RETURNS
by primary key, the estimated
+ // result size will be the same as the size of the smallest
table (RETURNS in this case),
+ // adjusted by the percentage of rows of the biggest table
(SALES in this case; percentage
+ // adjustment is required to account for predicates pushed
down to the table, e.g. we are
+ // interested in returns of items with certain category)
+ if (leftRowCnt > rightRowCnt) {
+ baseRowCnt = rightRowCnt;
+ percentageAdjustment =
mq.getPercentageOriginalRows(rel.getLeft());
+ }
+ else {
+ baseRowCnt = leftRowCnt;
+ percentageAdjustment = rightPercentage(mq, rel,
rightAdjust);
+ }
+ }
+ else if (rel.getJoinType() == JoinRelType.LEFT) {
+ baseRowCnt = leftRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.RIGHT) {
+ baseRowCnt = rightRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.FULL) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+
+ // Fall-back.
+ if (selectivity == null) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel,
rel.getCondition());
+ }
+
+ Double leftPercentage =
mq.getPercentageOriginalRows(rel.getLeft());
+ Double rightPercentage =
mq.getPercentageOriginalRows(rel.getRight());
Review Comment:
FULL can't be used for CNLJ, but maybe still use here `rightPercentage` for
similarity with other branches?
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -72,48 +117,335 @@ public class IgniteMdRowCount extends RelMdRowCount {
mq.getRowCount(rel.getLeft()));
}
+ JoinInfo joinInfo = rel.analyzeCondition();
+
+ if (joinInfo.pairs().isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
// Row count estimates of 0 will be rounded up to 1.
// So, use maxRowCount where the product is very small.
- final Double left = mq.getRowCount(rel.getLeft());
- final Double right = mq.getRowCount(rel.getRight());
+ final Double leftRowCnt = mq.getRowCount(rel.getLeft());
+ final Double rightRowCnt = multiply(mq.getRowCount(rel.getRight()),
rightAdjust);
- if (left == null || right == null)
+ if (leftRowCnt == null || rightRowCnt == null)
return null;
- if (left <= 1D || right <= 1D) {
+ if (leftRowCnt <= 1D || rightRowCnt <= 1D) {
Double max = mq.getMaxRowCount(rel);
if (max != null && max <= 1D)
return max;
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ // Primary key columns per table.
+ Map<IgniteTable, List<Integer>> pkColsPerTable = new
IdentityHashMap<>(2);
+
+ Map<Integer, KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq,
rel.getLeft(), joinInfo.leftKeys, pkColsPerTable);
+ Map<Integer, KeyColumnOrigin> columnsFromRight = resolveOrigins(mq,
rel.getRight(), joinInfo.rightKeys, pkColsPerTable);
+
+ if (columnsFromLeft.isEmpty() || columnsFromRight.isEmpty()) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ Map<TablesPair, JoinContext> joinCtxts = new HashMap<>();
+ for (IntPair joinKeys : joinInfo.pairs()) {
+ KeyColumnOrigin leftKey = columnsFromLeft.get(joinKeys.source);
+ KeyColumnOrigin rightKey = columnsFromRight.get(joinKeys.target);
+
+ if (leftKey == null || rightKey == null) {
+ continue;
+ }
+
+ joinCtxts.computeIfAbsent(
+ new TablesPair(
+ leftKey.origin.getOriginTable(),
+ rightKey.origin.getOriginTable()
+ ),
+ key -> {
+ IgniteTable leftTable = key.left.unwrap(IgniteTable.class);
+ IgniteTable rightTable =
key.right.unwrap(IgniteTable.class);
+
+ assert leftTable != null && rightTable != null;
+
+ List<Integer> leftPkCols = pkColsPerTable.get(leftTable);
+ List<Integer> rightPkCols = pkColsPerTable.get(rightTable);
+
+ assert leftPkCols != null && rightPkCols != null :
leftPkCols + " " + rightPkCols;
+
+ return new JoinContext(leftPkCols.size(),
rightPkCols.size());
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinCtxts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinCtxts.values().iterator();
+ JoinContext joinCtx = it.next();
+ while (it.hasNext()) {
+ JoinContext nextCtx = it.next();
+ if (nextCtx.joinType().strength > joinCtx.joinType().strength) {
+ joinCtx = nextCtx;
+ }
+
+ if (joinCtx.joinType().strength ==
JoiningRelationType.PK_ON_PK.strength) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -72,48 +117,335 @@ public class IgniteMdRowCount extends RelMdRowCount {
mq.getRowCount(rel.getLeft()));
}
+ JoinInfo joinInfo = rel.analyzeCondition();
+
+ if (joinInfo.pairs().isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
// Row count estimates of 0 will be rounded up to 1.
// So, use maxRowCount where the product is very small.
- final Double left = mq.getRowCount(rel.getLeft());
- final Double right = mq.getRowCount(rel.getRight());
+ final Double leftRowCnt = mq.getRowCount(rel.getLeft());
+ final Double rightRowCnt = multiply(mq.getRowCount(rel.getRight()),
rightAdjust);
- if (left == null || right == null)
+ if (leftRowCnt == null || rightRowCnt == null)
return null;
- if (left <= 1D || right <= 1D) {
+ if (leftRowCnt <= 1D || rightRowCnt <= 1D) {
Double max = mq.getMaxRowCount(rel);
if (max != null && max <= 1D)
return max;
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ // Primary key columns per table.
+ Map<IgniteTable, List<Integer>> pkColsPerTable = new
IdentityHashMap<>(2);
+
+ Map<Integer, KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq,
rel.getLeft(), joinInfo.leftKeys, pkColsPerTable);
+ Map<Integer, KeyColumnOrigin> columnsFromRight = resolveOrigins(mq,
rel.getRight(), joinInfo.rightKeys, pkColsPerTable);
+
+ if (columnsFromLeft.isEmpty() || columnsFromRight.isEmpty()) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ Map<TablesPair, JoinContext> joinCtxts = new HashMap<>();
+ for (IntPair joinKeys : joinInfo.pairs()) {
+ KeyColumnOrigin leftKey = columnsFromLeft.get(joinKeys.source);
+ KeyColumnOrigin rightKey = columnsFromRight.get(joinKeys.target);
+
+ if (leftKey == null || rightKey == null) {
+ continue;
+ }
+
+ joinCtxts.computeIfAbsent(
+ new TablesPair(
+ leftKey.origin.getOriginTable(),
+ rightKey.origin.getOriginTable()
+ ),
+ key -> {
+ IgniteTable leftTable = key.left.unwrap(IgniteTable.class);
+ IgniteTable rightTable =
key.right.unwrap(IgniteTable.class);
+
+ assert leftTable != null && rightTable != null;
+
+ List<Integer> leftPkCols = pkColsPerTable.get(leftTable);
+ List<Integer> rightPkCols = pkColsPerTable.get(rightTable);
+
+ assert leftPkCols != null && rightPkCols != null :
leftPkCols + " " + rightPkCols;
+
+ return new JoinContext(leftPkCols.size(),
rightPkCols.size());
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinCtxts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinCtxts.values().iterator();
+ JoinContext joinCtx = it.next();
+ while (it.hasNext()) {
+ JoinContext nextCtx = it.next();
+ if (nextCtx.joinType().strength > joinCtx.joinType().strength) {
+ joinCtx = nextCtx;
+ }
+
+ if (joinCtx.joinType().strength ==
JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (joinCtx.joinType() == JoiningRelationType.UNKNOWN) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ double postFiltrationAdjustment = 1.0;
+
+ // Outer joins return every row of the preserved side(s), the result
can't be smaller than that.
+ double preservedRowCnt = 0.0;
+
+ switch (rel.getJoinType()) {
+ case INNER:
+ case SEMI:
+ // Extra join keys as well as non-equi conditions serves as
post-filtration,
+ // therefore we need to adjust final result with a little
factor.
+ if (joinCtxts.size() != 1 || !joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+
+ break;
+ case LEFT:
+ preservedRowCnt = leftRowCnt;
+
+ break;
+ case RIGHT:
+ preservedRowCnt = rightRowCnt;
+
+ break;
+ case FULL:
+ preservedRowCnt = Math.max(leftRowCnt, rightRowCnt);
+
+ break;
+ default:
+ break;
+ }
+
+ double baseRowCnt = 0.0;
+ Double percentageAdjustment = null;
+ if (joinCtx.joinType() == JoiningRelationType.PK_ON_PK) {
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ if (!joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+ // Assume we have two fact tables SALES and RETURNS sharing
the same primary key. Every item
+ // can be sold, but only items which were sold can be returned
back, therefore
+ // size(SALES) > size(RETURNS). When joining SALES on RETURNS
by primary key, the estimated
+ // result size will be the same as the size of the smallest
table (RETURNS in this case),
+ // adjusted by the percentage of rows of the biggest table
(SALES in this case; percentage
+ // adjustment is required to account for predicates pushed
down to the table, e.g. we are
+ // interested in returns of items with certain category)
+ if (leftRowCnt > rightRowCnt) {
+ baseRowCnt = rightRowCnt;
+ percentageAdjustment =
mq.getPercentageOriginalRows(rel.getLeft());
+ }
+ else {
+ baseRowCnt = leftRowCnt;
+ percentageAdjustment = rightPercentage(mq, rel,
rightAdjust);
+ }
+ }
+ else if (rel.getJoinType() == JoinRelType.LEFT) {
+ baseRowCnt = leftRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.RIGHT) {
+ baseRowCnt = rightRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.FULL) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+
+ // Fall-back.
+ if (selectivity == null) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel,
rel.getCondition());
+ }
+
+ Double leftPercentage =
mq.getPercentageOriginalRows(rel.getLeft());
+ Double rightPercentage =
mq.getPercentageOriginalRows(rel.getRight());
+ leftPercentage = leftPercentage == null ? 1.0 : leftPercentage;
+ rightPercentage = rightPercentage == null ? 1.0 :
rightPercentage;
+
+ double intersection = Math.min(leftRowCnt * rightPercentage,
rightRowCnt * leftPercentage);
+
+ return leftRowCnt + rightRowCnt - intersection;
+ }
+ }
+ else if (joinCtx.joinType() == JoiningRelationType.FK_ON_PK) {
+ // For foreign key joins the base table is the one which is joined
by non-primary key columns.
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+ baseRowCnt = leftRowCnt * selectivity;
+ percentageAdjustment = rightPercentage(mq, rel, rightAdjust);
+ }
+ else if (rel.getJoinType() == JoinRelType.LEFT ||
rel.getJoinType() == JoinRelType.RIGHT) {
+ baseRowCnt = leftRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.FULL) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+
+ // Fall-back.
+ if (selectivity == null) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel,
rel.getCondition());
+ }
+
+ baseRowCnt = rightRowCnt + leftRowCnt;
+ percentageAdjustment = 1.0 - selectivity;
+ }
+ }
+ else { // PK_ON_FK
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+ baseRowCnt = rightRowCnt * selectivity;
+ percentageAdjustment =
mq.getPercentageOriginalRows(rel.getLeft());
+ }
+ else if (rel.getJoinType() == JoinRelType.RIGHT ||
rel.getJoinType() == JoinRelType.LEFT) {
+ baseRowCnt = rightRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.FULL) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+
+ // Fall-back.
+ if (selectivity == null) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel,
rel.getCondition());
+ }
+
+ baseRowCnt = rightRowCnt + leftRowCnt;
+ percentageAdjustment = 1.0 - selectivity;
+ }
+ }
+
+ if (percentageAdjustment == null || Double.compare(1.0,
percentageAdjustment) == 0) {
+ // No info or default 1.0, let's estimate. The intersection
estimate is not applicable to outer joins:
+ // the preserved side is returned entirely, no matter how many
rows have a match.
+ percentageAdjustment = preservedRowCnt > 0.0 ? 1.0 :
INTERSECT_ESTIMATE_COEFF;
+ }
+
+ return Math.max(preservedRowCnt, baseRowCnt * percentageAdjustment *
postFiltrationAdjustment);
+ }
+ /** Percentage of original rows of the right input, see {@link
#joinRowCount(RelMetadataQuery, Join, double)}. */
+ @Nullable private static Double rightPercentage(RelMetadataQuery mq, Join
rel, double rightAdjust) {
+ Double percentage = mq.getPercentageOriginalRows(rel.getRight());
+
+ return percentage == null ? null : Math.min(1.0, percentage *
rightAdjust);
+ }
+
+ /** */
+ private static Map<Integer, KeyColumnOrigin> resolveOrigins(
+ RelMetadataQuery mq,
+ RelNode joinSide,
+ ImmutableIntList keys,
+ Map<IgniteTable, List<Integer>> pkColsPerTable
+ ) {
+ GridLeanMap<Integer, KeyColumnOrigin> origins = new GridLeanMap<>();
+
+ for (int i : keys) {
+ if (origins.containsKey(i)) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -157,4 +489,129 @@ public double getRowCount(IgniteLimit rel,
RelMetadataQuery mq) {
public double getRowCount(IgniteTableModify rel, RelMetadataQuery mq) {
return rel.estimateRowCount(mq);
}
+
+ /** */
+ private record TablesPair(RelOptTable left, RelOptTable right) { }
+
+ /** */
+ private static class JoinContext {
+ /** Used columns of primary key of table from left side. */
+ private final BitSet leftKeys;
+
+ /** Used columns of primary key of table from right side. */
+ private final BitSet rightKeys;
+
+ /**
+ * Used columns of primary key in both tables.
+ *
+ * <p>This bitset is initialized when PK of both tables has equal
columns count, and
+ * bits are cleared when join pair contains columns with equal
positions in PK of corresponding
+ * table. For example, having tables T1 and T2 with primary keys in
both tables defined as
+ * CONSTRAINT PRIMARY KEY (a, b), in case of query
+ * {@code SELECT ... FROM t1 JOIN t2 ON t1.a = t2.a AND t1.b = t2.b}
commonKeys will be initialized
+ * and cleared, but in case of query {@code SELECT ... FROM t1 JOIN t2
ON t1.a = t2.b AND t1.b = t2.a}
+ * (mind the join condition, where column A of one table compared with
column B of another), will be
+ * only initialized (since size of the primary keys are equal), but
not cleared.
+ */
+ private final @Nullable BitSet commonKeys;
+
+ /** Whether primary key columns of both tables are known. */
+ private final boolean pkKnown;
+
+ /** */
+ JoinContext(int leftPkSize, int rightPkSize) {
+ pkKnown = leftPkSize > 0 && rightPkSize > 0;
+
+ leftKeys = new BitSet();
+ rightKeys = new BitSet();
+ commonKeys = leftPkSize == rightPkSize && leftPkSize != 0 ? new
BitSet() : null;
+
+ leftKeys.set(0, leftPkSize);
+ rightKeys.set(0, rightPkSize);
+
+ if (commonKeys != null) {
+ assert leftPkSize == rightPkSize;
+
+ commonKeys.set(0, leftPkSize);
+ }
+ }
+
+ /** */
+ void countKeys(KeyColumnOrigin left, KeyColumnOrigin right) {
+ if (left.positionInKey >= 0) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -157,4 +489,129 @@ public double getRowCount(IgniteLimit rel,
RelMetadataQuery mq) {
public double getRowCount(IgniteTableModify rel, RelMetadataQuery mq) {
return rel.estimateRowCount(mq);
}
+
+ /** */
+ private record TablesPair(RelOptTable left, RelOptTable right) { }
+
+ /** */
+ private static class JoinContext {
+ /** Used columns of primary key of table from left side. */
+ private final BitSet leftKeys;
+
+ /** Used columns of primary key of table from right side. */
+ private final BitSet rightKeys;
+
+ /**
+ * Used columns of primary key in both tables.
+ *
+ * <p>This bitset is initialized when PK of both tables has equal
columns count, and
+ * bits are cleared when join pair contains columns with equal
positions in PK of corresponding
+ * table. For example, having tables T1 and T2 with primary keys in
both tables defined as
+ * CONSTRAINT PRIMARY KEY (a, b), in case of query
+ * {@code SELECT ... FROM t1 JOIN t2 ON t1.a = t2.a AND t1.b = t2.b}
commonKeys will be initialized
+ * and cleared, but in case of query {@code SELECT ... FROM t1 JOIN t2
ON t1.a = t2.b AND t1.b = t2.a}
+ * (mind the join condition, where column A of one table compared with
column B of another), will be
+ * only initialized (since size of the primary keys are equal), but
not cleared.
+ */
+ private final @Nullable BitSet commonKeys;
+
+ /** Whether primary key columns of both tables are known. */
+ private final boolean pkKnown;
+
+ /** */
+ JoinContext(int leftPkSize, int rightPkSize) {
+ pkKnown = leftPkSize > 0 && rightPkSize > 0;
+
+ leftKeys = new BitSet();
+ rightKeys = new BitSet();
+ commonKeys = leftPkSize == rightPkSize && leftPkSize != 0 ? new
BitSet() : null;
+
+ leftKeys.set(0, leftPkSize);
+ rightKeys.set(0, rightPkSize);
+
+ if (commonKeys != null) {
+ assert leftPkSize == rightPkSize;
+
+ commonKeys.set(0, leftPkSize);
+ }
+ }
+
+ /** */
+ void countKeys(KeyColumnOrigin left, KeyColumnOrigin right) {
+ if (left.positionInKey >= 0) {
+ leftKeys.clear(left.positionInKey);
+ }
+
+ if (right.positionInKey >= 0) {
+ rightKeys.clear(right.positionInKey);
+ }
+
+ if (commonKeys != null && left.positionInKey ==
right.positionInKey && left.positionInKey >= 0) {
+ commonKeys.clear(left.positionInKey);
+ }
+ }
+
+ /** */
+ JoiningRelationType joinType() {
+ if (!pkKnown) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/JoinRowCountEstimationTest.java:
##########
@@ -0,0 +1,348 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.ignite.internal.processors.query.calcite.planner;
+
+import java.math.BigDecimal;
+import java.util.function.Predicate;
+import java.util.regex.Pattern;
+import org.apache.calcite.plan.RelOptUtil;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.sql.SqlExplainFormat;
+import org.apache.calcite.sql.SqlExplainLevel;
+import org.apache.calcite.util.ImmutableIntList;
+import
org.apache.ignite.internal.processors.query.calcite.rel.IgniteCorrelatedNestedLoopJoin;
+import org.apache.ignite.internal.processors.query.calcite.schema.IgniteSchema;
+import
org.apache.ignite.internal.processors.query.calcite.trait.IgniteDistributions;
+import org.apache.ignite.internal.util.typedef.internal.CU;
+import org.hamcrest.BaseMatcher;
+import org.hamcrest.Description;
+import org.hamcrest.Matcher;
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+import static
org.apache.ignite.internal.processors.query.calcite.metadata.IgniteMdSelectivity.COMPARISON_SELECTIVITY;
+import static
org.apache.ignite.internal.processors.query.calcite.metadata.IgniteMdSelectivity.EQUALS_SELECTIVITY;
+import static
org.apache.ignite.internal.processors.query.calcite.metadata.IgniteMdSelectivity.IS_NOT_NULL_SELECTIVITY;
+
+/**
+ * Tests to check row count estimation for join relation.
+ */
+public class JoinRowCountEstimationTest extends AbstractPlannerTest {
+ /** */
+ private static final int CATALOG_SALES_SIZE = 1_441_548;
+
+ /** */
+ private static final int CATALOG_RETURNS_SIZE = 144_067;
+
+ /** */
+ private static final int DATE_DIM_SIZE = 73_049;
+
+ /** */
+ private static final String SELECT = "SELECT /*+ DISABLE_RULE(" +
+ "'JoinCommuteRule', " +
+ "'MergeJoinConverter', " +
+ "'NestedLoopJoinConverter', " +
+ "'CorrelateToNestedLoopRule'" +
+ ") */ * ";
+
+ /** */
+ private IgniteSchema publicSchema;
+
+ /** {@inheritDoc} */
+ @BeforeEach
+ @Override public void setup() {
+ super.setup();
+
+ TestTable tbl1 = createTable(
+ "CATALOG_SALES",
+ CATALOG_SALES_SIZE,
+ IgniteDistributions.affinity(ImmutableIntList.of(1, 2),
CU.cacheId("default"), 0),
+ "ID", Integer.class,
+ "CS_ITEM_SK", Integer.class,
+ "CS_ORDER_NUMBER", Integer.class,
+ "CS_PROMO_SK", Integer.class
+ );
+
+ TestTable tbl2 = createTable(
+ "CATALOG_RETURNS",
+ CATALOG_RETURNS_SIZE,
+ IgniteDistributions.affinity(ImmutableIntList.of(1, 2),
CU.cacheId("default"), 0),
+ "ID", Integer.class,
+ "CR_ITEM_SK", Integer.class,
+ "CR_ORDER_NUMBER", Integer.class,
+ "CR_RETURNED_DATE_SK", Integer.class,
+ "CR_RETURN_QUANTITY", Integer.class
+ );
+
+ TestTable tbl3 = createTable(
+ "DATE_DIM",
+ DATE_DIM_SIZE,
+ IgniteDistributions.affinity(ImmutableIntList.of(0),
CU.cacheId("default"), 0),
+ "D_DATE_SK", Integer.class,
+ "D_MOY", Integer.class
+ );
+
+ publicSchema = createSchema(tbl1, tbl2, tbl3);
+ }
+
+ /** */
+ @Test
+ public void joinSameTableSimpleAffMergeJoin() throws Exception {
+ assertPlan(SELECT
+ + " FROM catalog_sales"
+ + " ,catalog_returns"
+ + " WHERE cs_item_sk = cr_item_sk"
+ + " AND cs_order_number = cr_order_number",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_RETURNS_SIZE)));
+
+ assertPlan(SELECT
+ + " FROM catalog_sales"
+ + " ,catalog_returns"
+ + " WHERE cs_item_sk = cr_item_sk"
+ + " AND cs_order_number = cr_order_number"
+ + " AND cs_promo_sk IS NOT NULL",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_RETURNS_SIZE * IS_NOT_NULL_SELECTIVITY)));
+ }
+
+ /** */
+ @Test
+ public void joinByPrimaryKeysLeft() throws Exception {
+ assertPlan(SELECT
+ + " FROM catalog_sales LEFT JOIN catalog_returns ON"
+ + " cs_item_sk = cr_item_sk AND cs_order_number =
cr_order_number",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_SALES_SIZE)));
+
+ assertPlan(SELECT
+ + " FROM catalog_sales LEFT JOIN catalog_returns"
+ + " ON cs_item_sk = cr_item_sk"
+ + " AND cs_order_number = cr_order_number"
+ + " AND cs_promo_sk IS NOT NULL",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_SALES_SIZE)));
+
+ assertPlan(SELECT
+ + " FROM catalog_sales LEFT JOIN catalog_returns"
+ + " ON cs_item_sk = cr_item_sk"
+ + " AND cs_order_number = cr_order_number"
+ + " AND cr_order_number > 1",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_SALES_SIZE)));
+ }
+
+ /** */
+ @Test
+ public void joinByPrimaryKeysRight() throws Exception {
+ assertPlan(SELECT
+ + " FROM catalog_returns RIGHT JOIN catalog_sales ON"
+ + " cs_item_sk = cr_item_sk AND cs_order_number =
cr_order_number",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_SALES_SIZE)));
+
+ assertPlan(SELECT
+ + " FROM catalog_returns RIGHT JOIN catalog_sales"
+ + " ON cs_item_sk = cr_item_sk"
+ + " AND cs_order_number = cr_order_number"
+ + " AND cs_promo_sk IS NOT NULL",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_SALES_SIZE)));
+
+ assertPlan(SELECT
+ + " FROM catalog_returns RIGHT JOIN catalog_sales"
+ + " ON cs_item_sk = cr_item_sk"
+ + " AND cs_order_number = cr_order_number"
+ + " AND cr_order_number > 1",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_SALES_SIZE)));
+ }
+
+ /** */
+ @Test
+ public void joinByPrimaryKeysFull() throws Exception {
+ assertPlan(SELECT
+ + " FROM catalog_returns FULL OUTER JOIN catalog_sales ON"
+ + " cs_item_sk = cr_item_sk AND cs_order_number =
cr_order_number",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual((int)((CATALOG_SALES_SIZE + CATALOG_RETURNS_SIZE)
+ * (1.0 - (EQUALS_SELECTIVITY * EQUALS_SELECTIVITY))))));
+
+ assertPlan(SELECT
+ + " FROM catalog_returns FULL OUTER JOIN catalog_sales"
+ + " ON cs_item_sk = cr_item_sk"
+ + " AND cs_order_number = cr_order_number"
+ + " AND cs_promo_sk IS NOT NULL",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual((int)((CATALOG_SALES_SIZE + CATALOG_RETURNS_SIZE)
+ * (1.0 - (EQUALS_SELECTIVITY * EQUALS_SELECTIVITY *
IS_NOT_NULL_SELECTIVITY))))));
+
+ assertPlan(SELECT
+ + " FROM catalog_returns FULL OUTER JOIN catalog_sales"
+ + " ON cs_item_sk = cr_item_sk"
+ + " AND cs_order_number = cr_order_number"
+ + " AND cr_order_number > 1",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual((int)((CATALOG_SALES_SIZE + CATALOG_RETURNS_SIZE)
+ * (1.0 - (EQUALS_SELECTIVITY * EQUALS_SELECTIVITY *
COMPARISON_SELECTIVITY))))));
+ }
+
+ /** */
+ @Test
+ public void joinByForeignKey() throws Exception {
+ assertPlan(SELECT
+ + " FROM catalog_returns"
+ + " ,date_dim"
+ + " WHERE cr_returned_date_sk = d_date_sk",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_RETURNS_SIZE * EQUALS_SELECTIVITY)));
+
+ assertPlan(SELECT
+ + " FROM date_dim"
+ + " ,catalog_returns"
+ + " WHERE cr_returned_date_sk = d_date_sk"
+ + " AND d_moy > 6",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
+ approximatelyEqual(CATALOG_RETURNS_SIZE * EQUALS_SELECTIVITY *
COMPARISON_SELECTIVITY)));
+ }
+
+ /** */
+ @Test
+ public void joinByForeignKeyLeft() throws Exception {
+ assertPlan(SELECT
+ + " FROM catalog_returns LEFT JOIN date_dim ON"
+ + " cr_returned_date_sk = d_date_sk",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_RETURNS_SIZE)));
+
+ assertPlan(SELECT
+ + " FROM date_dim LEFT JOIN catalog_returns ON"
+ + " cr_returned_date_sk = d_date_sk",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_RETURNS_SIZE)));
+
+ assertPlan(SELECT
+ + " FROM catalog_returns LEFT JOIN date_dim ON"
+ + " cr_returned_date_sk = d_date_sk"
+ + " AND cr_return_quantity > 6",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_RETURNS_SIZE)));
+ }
+
+ /** */
+ @Test
+ public void joinByForeignKeyRight() throws Exception {
+ assertPlan(SELECT
+ + " FROM catalog_returns RIGHT JOIN date_dim ON"
+ + " cr_returned_date_sk = d_date_sk",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_RETURNS_SIZE)));
+
+ assertPlan(SELECT
+ + " FROM date_dim RIGHT JOIN catalog_returns ON"
+ + " cr_returned_date_sk = d_date_sk",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_RETURNS_SIZE)));
+
+ assertPlan(SELECT
+ + " FROM date_dim RIGHT JOIN catalog_returns ON"
+ + " cr_returned_date_sk = d_date_sk"
+ + " AND cr_return_quantity > 6",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual(CATALOG_RETURNS_SIZE)));
+ }
+
+ /** */
+ @Test
+ public void joinByForeignKeyFull() throws Exception {
+ assertPlan(SELECT
+ + " FROM date_dim FULL OUTER JOIN catalog_returns ON"
+ + " cr_returned_date_sk = d_date_sk",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual((int)((DATE_DIM_SIZE + CATALOG_RETURNS_SIZE)
+ * (1.0 - (EQUALS_SELECTIVITY))))));
+
+ assertPlan(SELECT
+ + " FROM date_dim FULL OUTER JOIN catalog_returns ON"
+ + " cr_returned_date_sk = d_date_sk"
+ + " AND cr_return_quantity > 6",
+ publicSchema,
+ nodeRowCount("IgniteHashJoin",
approximatelyEqual((int)((DATE_DIM_SIZE + CATALOG_RETURNS_SIZE)
+ * (1.0 - (EQUALS_SELECTIVITY * COMPARISON_SELECTIVITY))))));
+ }
+
+ /** */
+ @Test
+ public void correlatedNestedLoopJoinRowCount() throws Exception {
+ assertPlan(
+ "SELECT /*+ CNL_JOIN */ * FROM catalog_returns"
+ + " ,date_dim"
+ + " WHERE cr_returned_date_sk = d_date_sk",
+ publicSchema,
+ nodeOrAnyChild(isInstanceOf(IgniteCorrelatedNestedLoopJoin.class)
+ .and(nodeRowCount("IgniteCorrelatedNestedLoopJoin",
+ approximatelyEqual(CATALOG_RETURNS_SIZE *
EQUALS_SELECTIVITY)))));
+ }
+
+ /**
+ * Matcher which ensures that node matching the pattern has row count
matching provided matcher.
+ *
+ * @param nodePattern A pattern describing a node of interest.
+ * @param rowCountMatcher Matcher for the estimated row count.
+ * @return Matcher.
+ */
+ static <T extends RelNode> Predicate<RelNode> nodeRowCount(String
nodePattern, Matcher<Integer> rowCountMatcher) {
+ Pattern pattern = Pattern.compile(".*" + nodePattern
+ + "\\(.*?rowcount = (?<rowcount>\\d+).*");
+
+ return node -> {
+ String plan = RelOptUtil.dumpPlan("", node, SqlExplainFormat.TEXT,
SqlExplainLevel.ALL_ATTRIBUTES);
+
+ String sanitized = plan.replaceAll("\\R", "");
+ java.util.regex.Matcher matcher = pattern.matcher(sanitized);
+
+ if (!matcher.matches())
+ return false;
+
+ String rowCntStr = matcher.group("rowcount");
+
+ return rowCountMatcher.matches(new
BigDecimal(rowCntStr).intValue());
+ };
+ }
+
+ /** Approximate equality check. */
+ static Matcher<Integer> approximatelyEqual(double expected) {
+ /** */
+ return new BaseMatcher<>() {
+ @Override public boolean matches(Object o) {
+ if (!(o instanceof Integer)) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -157,4 +489,129 @@ public double getRowCount(IgniteLimit rel,
RelMetadataQuery mq) {
public double getRowCount(IgniteTableModify rel, RelMetadataQuery mq) {
return rel.estimateRowCount(mq);
}
+
+ /** */
+ private record TablesPair(RelOptTable left, RelOptTable right) { }
+
+ /** */
+ private static class JoinContext {
+ /** Used columns of primary key of table from left side. */
+ private final BitSet leftKeys;
+
+ /** Used columns of primary key of table from right side. */
+ private final BitSet rightKeys;
+
+ /**
+ * Used columns of primary key in both tables.
+ *
+ * <p>This bitset is initialized when PK of both tables has equal
columns count, and
+ * bits are cleared when join pair contains columns with equal
positions in PK of corresponding
+ * table. For example, having tables T1 and T2 with primary keys in
both tables defined as
+ * CONSTRAINT PRIMARY KEY (a, b), in case of query
+ * {@code SELECT ... FROM t1 JOIN t2 ON t1.a = t2.a AND t1.b = t2.b}
commonKeys will be initialized
+ * and cleared, but in case of query {@code SELECT ... FROM t1 JOIN t2
ON t1.a = t2.b AND t1.b = t2.a}
+ * (mind the join condition, where column A of one table compared with
column B of another), will be
+ * only initialized (since size of the primary keys are equal), but
not cleared.
+ */
+ private final @Nullable BitSet commonKeys;
+
+ /** Whether primary key columns of both tables are known. */
+ private final boolean pkKnown;
+
+ /** */
+ JoinContext(int leftPkSize, int rightPkSize) {
+ pkKnown = leftPkSize > 0 && rightPkSize > 0;
+
+ leftKeys = new BitSet();
+ rightKeys = new BitSet();
+ commonKeys = leftPkSize == rightPkSize && leftPkSize != 0 ? new
BitSet() : null;
+
+ leftKeys.set(0, leftPkSize);
+ rightKeys.set(0, rightPkSize);
+
+ if (commonKeys != null) {
+ assert leftPkSize == rightPkSize;
+
+ commonKeys.set(0, leftPkSize);
+ }
+ }
+
+ /** */
+ void countKeys(KeyColumnOrigin left, KeyColumnOrigin right) {
+ if (left.positionInKey >= 0) {
+ leftKeys.clear(left.positionInKey);
+ }
+
+ if (right.positionInKey >= 0) {
+ rightKeys.clear(right.positionInKey);
+ }
+
+ if (commonKeys != null && left.positionInKey ==
right.positionInKey && left.positionInKey >= 0) {
+ commonKeys.clear(left.positionInKey);
+ }
+ }
+
+ /** */
+ JoiningRelationType joinType() {
+ if (!pkKnown) {
+ return JoiningRelationType.UNKNOWN;
+ }
+
+ if (commonKeys != null && commonKeys.isEmpty()) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -72,48 +117,335 @@ public class IgniteMdRowCount extends RelMdRowCount {
mq.getRowCount(rel.getLeft()));
}
+ JoinInfo joinInfo = rel.analyzeCondition();
+
+ if (joinInfo.pairs().isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
// Row count estimates of 0 will be rounded up to 1.
// So, use maxRowCount where the product is very small.
- final Double left = mq.getRowCount(rel.getLeft());
- final Double right = mq.getRowCount(rel.getRight());
+ final Double leftRowCnt = mq.getRowCount(rel.getLeft());
+ final Double rightRowCnt = multiply(mq.getRowCount(rel.getRight()),
rightAdjust);
- if (left == null || right == null)
+ if (leftRowCnt == null || rightRowCnt == null)
return null;
- if (left <= 1D || right <= 1D) {
+ if (leftRowCnt <= 1D || rightRowCnt <= 1D) {
Double max = mq.getMaxRowCount(rel);
if (max != null && max <= 1D)
return max;
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ // Primary key columns per table.
+ Map<IgniteTable, List<Integer>> pkColsPerTable = new
IdentityHashMap<>(2);
+
+ Map<Integer, KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq,
rel.getLeft(), joinInfo.leftKeys, pkColsPerTable);
+ Map<Integer, KeyColumnOrigin> columnsFromRight = resolveOrigins(mq,
rel.getRight(), joinInfo.rightKeys, pkColsPerTable);
+
+ if (columnsFromLeft.isEmpty() || columnsFromRight.isEmpty()) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ Map<TablesPair, JoinContext> joinCtxts = new HashMap<>();
+ for (IntPair joinKeys : joinInfo.pairs()) {
+ KeyColumnOrigin leftKey = columnsFromLeft.get(joinKeys.source);
+ KeyColumnOrigin rightKey = columnsFromRight.get(joinKeys.target);
+
+ if (leftKey == null || rightKey == null) {
+ continue;
+ }
+
+ joinCtxts.computeIfAbsent(
+ new TablesPair(
+ leftKey.origin.getOriginTable(),
+ rightKey.origin.getOriginTable()
+ ),
+ key -> {
+ IgniteTable leftTable = key.left.unwrap(IgniteTable.class);
+ IgniteTable rightTable =
key.right.unwrap(IgniteTable.class);
+
+ assert leftTable != null && rightTable != null;
+
+ List<Integer> leftPkCols = pkColsPerTable.get(leftTable);
+ List<Integer> rightPkCols = pkColsPerTable.get(rightTable);
+
+ assert leftPkCols != null && rightPkCols != null :
leftPkCols + " " + rightPkCols;
+
+ return new JoinContext(leftPkCols.size(),
rightPkCols.size());
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinCtxts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinCtxts.values().iterator();
+ JoinContext joinCtx = it.next();
+ while (it.hasNext()) {
+ JoinContext nextCtx = it.next();
+ if (nextCtx.joinType().strength > joinCtx.joinType().strength) {
+ joinCtx = nextCtx;
+ }
+
+ if (joinCtx.joinType().strength ==
JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (joinCtx.joinType() == JoiningRelationType.UNKNOWN) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ double postFiltrationAdjustment = 1.0;
+
+ // Outer joins return every row of the preserved side(s), the result
can't be smaller than that.
+ double preservedRowCnt = 0.0;
+
+ switch (rel.getJoinType()) {
+ case INNER:
+ case SEMI:
+ // Extra join keys as well as non-equi conditions serves as
post-filtration,
+ // therefore we need to adjust final result with a little
factor.
+ if (joinCtxts.size() != 1 || !joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+
+ break;
+ case LEFT:
+ preservedRowCnt = leftRowCnt;
+
+ break;
+ case RIGHT:
+ preservedRowCnt = rightRowCnt;
+
+ break;
+ case FULL:
+ preservedRowCnt = Math.max(leftRowCnt, rightRowCnt);
+
+ break;
+ default:
+ break;
+ }
+
+ double baseRowCnt = 0.0;
+ Double percentageAdjustment = null;
+ if (joinCtx.joinType() == JoiningRelationType.PK_ON_PK) {
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ if (!joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+ // Assume we have two fact tables SALES and RETURNS sharing
the same primary key. Every item
+ // can be sold, but only items which were sold can be returned
back, therefore
+ // size(SALES) > size(RETURNS). When joining SALES on RETURNS
by primary key, the estimated
+ // result size will be the same as the size of the smallest
table (RETURNS in this case),
+ // adjusted by the percentage of rows of the biggest table
(SALES in this case; percentage
+ // adjustment is required to account for predicates pushed
down to the table, e.g. we are
+ // interested in returns of items with certain category)
+ if (leftRowCnt > rightRowCnt) {
+ baseRowCnt = rightRowCnt;
+ percentageAdjustment =
mq.getPercentageOriginalRows(rel.getLeft());
+ }
+ else {
+ baseRowCnt = leftRowCnt;
+ percentageAdjustment = rightPercentage(mq, rel,
rightAdjust);
+ }
+ }
+ else if (rel.getJoinType() == JoinRelType.LEFT) {
+ baseRowCnt = leftRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.RIGHT) {
+ baseRowCnt = rightRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.FULL) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+
+ // Fall-back.
+ if (selectivity == null) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel,
rel.getCondition());
+ }
+
+ Double leftPercentage =
mq.getPercentageOriginalRows(rel.getLeft());
+ Double rightPercentage =
mq.getPercentageOriginalRows(rel.getRight());
+ leftPercentage = leftPercentage == null ? 1.0 : leftPercentage;
+ rightPercentage = rightPercentage == null ? 1.0 :
rightPercentage;
+
+ double intersection = Math.min(leftRowCnt * rightPercentage,
rightRowCnt * leftPercentage);
+
+ return leftRowCnt + rightRowCnt - intersection;
+ }
+ }
+ else if (joinCtx.joinType() == JoiningRelationType.FK_ON_PK) {
+ // For foreign key joins the base table is the one which is joined
by non-primary key columns.
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+ baseRowCnt = leftRowCnt * selectivity;
+ percentageAdjustment = rightPercentage(mq, rel, rightAdjust);
+ }
+ else if (rel.getJoinType() == JoinRelType.LEFT ||
rel.getJoinType() == JoinRelType.RIGHT) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -72,48 +117,335 @@ public class IgniteMdRowCount extends RelMdRowCount {
mq.getRowCount(rel.getLeft()));
}
+ JoinInfo joinInfo = rel.analyzeCondition();
+
+ if (joinInfo.pairs().isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
// Row count estimates of 0 will be rounded up to 1.
// So, use maxRowCount where the product is very small.
- final Double left = mq.getRowCount(rel.getLeft());
- final Double right = mq.getRowCount(rel.getRight());
+ final Double leftRowCnt = mq.getRowCount(rel.getLeft());
+ final Double rightRowCnt = multiply(mq.getRowCount(rel.getRight()),
rightAdjust);
- if (left == null || right == null)
+ if (leftRowCnt == null || rightRowCnt == null)
return null;
- if (left <= 1D || right <= 1D) {
+ if (leftRowCnt <= 1D || rightRowCnt <= 1D) {
Double max = mq.getMaxRowCount(rel);
if (max != null && max <= 1D)
return max;
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ // Primary key columns per table.
+ Map<IgniteTable, List<Integer>> pkColsPerTable = new
IdentityHashMap<>(2);
+
+ Map<Integer, KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq,
rel.getLeft(), joinInfo.leftKeys, pkColsPerTable);
+ Map<Integer, KeyColumnOrigin> columnsFromRight = resolveOrigins(mq,
rel.getRight(), joinInfo.rightKeys, pkColsPerTable);
+
+ if (columnsFromLeft.isEmpty() || columnsFromRight.isEmpty()) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ Map<TablesPair, JoinContext> joinCtxts = new HashMap<>();
+ for (IntPair joinKeys : joinInfo.pairs()) {
+ KeyColumnOrigin leftKey = columnsFromLeft.get(joinKeys.source);
+ KeyColumnOrigin rightKey = columnsFromRight.get(joinKeys.target);
+
+ if (leftKey == null || rightKey == null) {
+ continue;
+ }
+
+ joinCtxts.computeIfAbsent(
+ new TablesPair(
+ leftKey.origin.getOriginTable(),
+ rightKey.origin.getOriginTable()
+ ),
+ key -> {
+ IgniteTable leftTable = key.left.unwrap(IgniteTable.class);
+ IgniteTable rightTable =
key.right.unwrap(IgniteTable.class);
+
+ assert leftTable != null && rightTable != null;
+
+ List<Integer> leftPkCols = pkColsPerTable.get(leftTable);
+ List<Integer> rightPkCols = pkColsPerTable.get(rightTable);
+
+ assert leftPkCols != null && rightPkCols != null :
leftPkCols + " " + rightPkCols;
+
+ return new JoinContext(leftPkCols.size(),
rightPkCols.size());
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinCtxts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinCtxts.values().iterator();
+ JoinContext joinCtx = it.next();
+ while (it.hasNext()) {
+ JoinContext nextCtx = it.next();
+ if (nextCtx.joinType().strength > joinCtx.joinType().strength) {
+ joinCtx = nextCtx;
+ }
+
+ if (joinCtx.joinType().strength ==
JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (joinCtx.joinType() == JoiningRelationType.UNKNOWN) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ double postFiltrationAdjustment = 1.0;
+
+ // Outer joins return every row of the preserved side(s), the result
can't be smaller than that.
+ double preservedRowCnt = 0.0;
+
+ switch (rel.getJoinType()) {
+ case INNER:
+ case SEMI:
+ // Extra join keys as well as non-equi conditions serves as
post-filtration,
+ // therefore we need to adjust final result with a little
factor.
+ if (joinCtxts.size() != 1 || !joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+
+ break;
+ case LEFT:
+ preservedRowCnt = leftRowCnt;
+
+ break;
+ case RIGHT:
+ preservedRowCnt = rightRowCnt;
+
+ break;
+ case FULL:
+ preservedRowCnt = Math.max(leftRowCnt, rightRowCnt);
+
+ break;
+ default:
+ break;
+ }
+
+ double baseRowCnt = 0.0;
+ Double percentageAdjustment = null;
+ if (joinCtx.joinType() == JoiningRelationType.PK_ON_PK) {
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ if (!joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+ // Assume we have two fact tables SALES and RETURNS sharing
the same primary key. Every item
+ // can be sold, but only items which were sold can be returned
back, therefore
+ // size(SALES) > size(RETURNS). When joining SALES on RETURNS
by primary key, the estimated
+ // result size will be the same as the size of the smallest
table (RETURNS in this case),
+ // adjusted by the percentage of rows of the biggest table
(SALES in this case; percentage
+ // adjustment is required to account for predicates pushed
down to the table, e.g. we are
+ // interested in returns of items with certain category)
+ if (leftRowCnt > rightRowCnt) {
+ baseRowCnt = rightRowCnt;
+ percentageAdjustment =
mq.getPercentageOriginalRows(rel.getLeft());
+ }
+ else {
+ baseRowCnt = leftRowCnt;
+ percentageAdjustment = rightPercentage(mq, rel,
rightAdjust);
+ }
+ }
+ else if (rel.getJoinType() == JoinRelType.LEFT) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -72,48 +117,335 @@ public class IgniteMdRowCount extends RelMdRowCount {
mq.getRowCount(rel.getLeft()));
}
+ JoinInfo joinInfo = rel.analyzeCondition();
+
+ if (joinInfo.pairs().isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
// Row count estimates of 0 will be rounded up to 1.
// So, use maxRowCount where the product is very small.
- final Double left = mq.getRowCount(rel.getLeft());
- final Double right = mq.getRowCount(rel.getRight());
+ final Double leftRowCnt = mq.getRowCount(rel.getLeft());
+ final Double rightRowCnt = multiply(mq.getRowCount(rel.getRight()),
rightAdjust);
- if (left == null || right == null)
+ if (leftRowCnt == null || rightRowCnt == null)
return null;
- if (left <= 1D || right <= 1D) {
+ if (leftRowCnt <= 1D || rightRowCnt <= 1D) {
Double max = mq.getMaxRowCount(rel);
if (max != null && max <= 1D)
return max;
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ // Primary key columns per table.
+ Map<IgniteTable, List<Integer>> pkColsPerTable = new
IdentityHashMap<>(2);
+
+ Map<Integer, KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq,
rel.getLeft(), joinInfo.leftKeys, pkColsPerTable);
+ Map<Integer, KeyColumnOrigin> columnsFromRight = resolveOrigins(mq,
rel.getRight(), joinInfo.rightKeys, pkColsPerTable);
+
+ if (columnsFromLeft.isEmpty() || columnsFromRight.isEmpty()) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ Map<TablesPair, JoinContext> joinCtxts = new HashMap<>();
+ for (IntPair joinKeys : joinInfo.pairs()) {
+ KeyColumnOrigin leftKey = columnsFromLeft.get(joinKeys.source);
+ KeyColumnOrigin rightKey = columnsFromRight.get(joinKeys.target);
+
+ if (leftKey == null || rightKey == null) {
+ continue;
+ }
+
+ joinCtxts.computeIfAbsent(
+ new TablesPair(
+ leftKey.origin.getOriginTable(),
+ rightKey.origin.getOriginTable()
+ ),
+ key -> {
+ IgniteTable leftTable = key.left.unwrap(IgniteTable.class);
+ IgniteTable rightTable =
key.right.unwrap(IgniteTable.class);
+
+ assert leftTable != null && rightTable != null;
+
+ List<Integer> leftPkCols = pkColsPerTable.get(leftTable);
+ List<Integer> rightPkCols = pkColsPerTable.get(rightTable);
+
+ assert leftPkCols != null && rightPkCols != null :
leftPkCols + " " + rightPkCols;
+
+ return new JoinContext(leftPkCols.size(),
rightPkCols.size());
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinCtxts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinCtxts.values().iterator();
+ JoinContext joinCtx = it.next();
+ while (it.hasNext()) {
+ JoinContext nextCtx = it.next();
+ if (nextCtx.joinType().strength > joinCtx.joinType().strength) {
+ joinCtx = nextCtx;
+ }
+
+ if (joinCtx.joinType().strength ==
JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (joinCtx.joinType() == JoiningRelationType.UNKNOWN) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ double postFiltrationAdjustment = 1.0;
+
+ // Outer joins return every row of the preserved side(s), the result
can't be smaller than that.
+ double preservedRowCnt = 0.0;
+
+ switch (rel.getJoinType()) {
+ case INNER:
+ case SEMI:
+ // Extra join keys as well as non-equi conditions serves as
post-filtration,
+ // therefore we need to adjust final result with a little
factor.
+ if (joinCtxts.size() != 1 || !joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+
+ break;
+ case LEFT:
+ preservedRowCnt = leftRowCnt;
+
+ break;
+ case RIGHT:
+ preservedRowCnt = rightRowCnt;
+
+ break;
+ case FULL:
+ preservedRowCnt = Math.max(leftRowCnt, rightRowCnt);
+
+ break;
+ default:
+ break;
+ }
+
+ double baseRowCnt = 0.0;
+ Double percentageAdjustment = null;
+ if (joinCtx.joinType() == JoiningRelationType.PK_ON_PK) {
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ if (!joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+ // Assume we have two fact tables SALES and RETURNS sharing
the same primary key. Every item
+ // can be sold, but only items which were sold can be returned
back, therefore
+ // size(SALES) > size(RETURNS). When joining SALES on RETURNS
by primary key, the estimated
+ // result size will be the same as the size of the smallest
table (RETURNS in this case),
+ // adjusted by the percentage of rows of the biggest table
(SALES in this case; percentage
+ // adjustment is required to account for predicates pushed
down to the table, e.g. we are
+ // interested in returns of items with certain category)
+ if (leftRowCnt > rightRowCnt) {
+ baseRowCnt = rightRowCnt;
+ percentageAdjustment =
mq.getPercentageOriginalRows(rel.getLeft());
+ }
+ else {
+ baseRowCnt = leftRowCnt;
+ percentageAdjustment = rightPercentage(mq, rel,
rightAdjust);
+ }
+ }
+ else if (rel.getJoinType() == JoinRelType.LEFT) {
+ baseRowCnt = leftRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.RIGHT) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -72,48 +117,335 @@ public class IgniteMdRowCount extends RelMdRowCount {
mq.getRowCount(rel.getLeft()));
}
+ JoinInfo joinInfo = rel.analyzeCondition();
+
+ if (joinInfo.pairs().isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
// Row count estimates of 0 will be rounded up to 1.
// So, use maxRowCount where the product is very small.
- final Double left = mq.getRowCount(rel.getLeft());
- final Double right = mq.getRowCount(rel.getRight());
+ final Double leftRowCnt = mq.getRowCount(rel.getLeft());
+ final Double rightRowCnt = multiply(mq.getRowCount(rel.getRight()),
rightAdjust);
- if (left == null || right == null)
+ if (leftRowCnt == null || rightRowCnt == null)
return null;
- if (left <= 1D || right <= 1D) {
+ if (leftRowCnt <= 1D || rightRowCnt <= 1D) {
Double max = mq.getMaxRowCount(rel);
if (max != null && max <= 1D)
return max;
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ // Primary key columns per table.
+ Map<IgniteTable, List<Integer>> pkColsPerTable = new
IdentityHashMap<>(2);
+
+ Map<Integer, KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq,
rel.getLeft(), joinInfo.leftKeys, pkColsPerTable);
+ Map<Integer, KeyColumnOrigin> columnsFromRight = resolveOrigins(mq,
rel.getRight(), joinInfo.rightKeys, pkColsPerTable);
+
+ if (columnsFromLeft.isEmpty() || columnsFromRight.isEmpty()) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ Map<TablesPair, JoinContext> joinCtxts = new HashMap<>();
+ for (IntPair joinKeys : joinInfo.pairs()) {
+ KeyColumnOrigin leftKey = columnsFromLeft.get(joinKeys.source);
+ KeyColumnOrigin rightKey = columnsFromRight.get(joinKeys.target);
+
+ if (leftKey == null || rightKey == null) {
+ continue;
+ }
+
+ joinCtxts.computeIfAbsent(
+ new TablesPair(
+ leftKey.origin.getOriginTable(),
+ rightKey.origin.getOriginTable()
+ ),
+ key -> {
+ IgniteTable leftTable = key.left.unwrap(IgniteTable.class);
+ IgniteTable rightTable =
key.right.unwrap(IgniteTable.class);
+
+ assert leftTable != null && rightTable != null;
+
+ List<Integer> leftPkCols = pkColsPerTable.get(leftTable);
+ List<Integer> rightPkCols = pkColsPerTable.get(rightTable);
+
+ assert leftPkCols != null && rightPkCols != null :
leftPkCols + " " + rightPkCols;
+
+ return new JoinContext(leftPkCols.size(),
rightPkCols.size());
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinCtxts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinCtxts.values().iterator();
+ JoinContext joinCtx = it.next();
+ while (it.hasNext()) {
+ JoinContext nextCtx = it.next();
+ if (nextCtx.joinType().strength > joinCtx.joinType().strength) {
+ joinCtx = nextCtx;
+ }
+
+ if (joinCtx.joinType().strength ==
JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (joinCtx.joinType() == JoiningRelationType.UNKNOWN) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ double postFiltrationAdjustment = 1.0;
+
+ // Outer joins return every row of the preserved side(s), the result
can't be smaller than that.
+ double preservedRowCnt = 0.0;
+
+ switch (rel.getJoinType()) {
+ case INNER:
+ case SEMI:
+ // Extra join keys as well as non-equi conditions serves as
post-filtration,
+ // therefore we need to adjust final result with a little
factor.
+ if (joinCtxts.size() != 1 || !joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+
+ break;
+ case LEFT:
+ preservedRowCnt = leftRowCnt;
+
+ break;
+ case RIGHT:
+ preservedRowCnt = rightRowCnt;
+
+ break;
+ case FULL:
+ preservedRowCnt = Math.max(leftRowCnt, rightRowCnt);
+
+ break;
+ default:
+ break;
+ }
+
+ double baseRowCnt = 0.0;
+ Double percentageAdjustment = null;
+ if (joinCtx.joinType() == JoiningRelationType.PK_ON_PK) {
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ if (!joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+ // Assume we have two fact tables SALES and RETURNS sharing
the same primary key. Every item
+ // can be sold, but only items which were sold can be returned
back, therefore
+ // size(SALES) > size(RETURNS). When joining SALES on RETURNS
by primary key, the estimated
+ // result size will be the same as the size of the smallest
table (RETURNS in this case),
+ // adjusted by the percentage of rows of the biggest table
(SALES in this case; percentage
+ // adjustment is required to account for predicates pushed
down to the table, e.g. we are
+ // interested in returns of items with certain category)
+ if (leftRowCnt > rightRowCnt) {
+ baseRowCnt = rightRowCnt;
+ percentageAdjustment =
mq.getPercentageOriginalRows(rel.getLeft());
+ }
+ else {
+ baseRowCnt = leftRowCnt;
+ percentageAdjustment = rightPercentage(mq, rel,
rightAdjust);
+ }
+ }
+ else if (rel.getJoinType() == JoinRelType.LEFT) {
+ baseRowCnt = leftRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.RIGHT) {
+ baseRowCnt = rightRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.FULL) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+
+ // Fall-back.
+ if (selectivity == null) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel,
rel.getCondition());
+ }
+
+ Double leftPercentage =
mq.getPercentageOriginalRows(rel.getLeft());
+ Double rightPercentage =
mq.getPercentageOriginalRows(rel.getRight());
+ leftPercentage = leftPercentage == null ? 1.0 : leftPercentage;
+ rightPercentage = rightPercentage == null ? 1.0 :
rightPercentage;
+
+ double intersection = Math.min(leftRowCnt * rightPercentage,
rightRowCnt * leftPercentage);
+
+ return leftRowCnt + rightRowCnt - intersection;
+ }
+ }
+ else if (joinCtx.joinType() == JoiningRelationType.FK_ON_PK) {
+ // For foreign key joins the base table is the one which is joined
by non-primary key columns.
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+ baseRowCnt = leftRowCnt * selectivity;
+ percentageAdjustment = rightPercentage(mq, rel, rightAdjust);
+ }
+ else if (rel.getJoinType() == JoinRelType.LEFT ||
rel.getJoinType() == JoinRelType.RIGHT) {
+ baseRowCnt = leftRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.FULL) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+
+ // Fall-back.
+ if (selectivity == null) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel,
rel.getCondition());
+ }
+
+ baseRowCnt = rightRowCnt + leftRowCnt;
+ percentageAdjustment = 1.0 - selectivity;
+ }
+ }
+ else { // PK_ON_FK
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+ baseRowCnt = rightRowCnt * selectivity;
+ percentageAdjustment =
mq.getPercentageOriginalRows(rel.getLeft());
+ }
+ else if (rel.getJoinType() == JoinRelType.RIGHT ||
rel.getJoinType() == JoinRelType.LEFT) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -157,4 +489,129 @@ public double getRowCount(IgniteLimit rel,
RelMetadataQuery mq) {
public double getRowCount(IgniteTableModify rel, RelMetadataQuery mq) {
return rel.estimateRowCount(mq);
}
+
+ /** */
+ private record TablesPair(RelOptTable left, RelOptTable right) { }
+
+ /** */
+ private static class JoinContext {
+ /** Used columns of primary key of table from left side. */
+ private final BitSet leftKeys;
+
+ /** Used columns of primary key of table from right side. */
+ private final BitSet rightKeys;
+
+ /**
+ * Used columns of primary key in both tables.
+ *
+ * <p>This bitset is initialized when PK of both tables has equal
columns count, and
+ * bits are cleared when join pair contains columns with equal
positions in PK of corresponding
+ * table. For example, having tables T1 and T2 with primary keys in
both tables defined as
+ * CONSTRAINT PRIMARY KEY (a, b), in case of query
+ * {@code SELECT ... FROM t1 JOIN t2 ON t1.a = t2.a AND t1.b = t2.b}
commonKeys will be initialized
+ * and cleared, but in case of query {@code SELECT ... FROM t1 JOIN t2
ON t1.a = t2.b AND t1.b = t2.a}
+ * (mind the join condition, where column A of one table compared with
column B of another), will be
+ * only initialized (since size of the primary keys are equal), but
not cleared.
+ */
+ private final @Nullable BitSet commonKeys;
+
+ /** Whether primary key columns of both tables are known. */
+ private final boolean pkKnown;
+
+ /** */
+ JoinContext(int leftPkSize, int rightPkSize) {
+ pkKnown = leftPkSize > 0 && rightPkSize > 0;
+
+ leftKeys = new BitSet();
+ rightKeys = new BitSet();
+ commonKeys = leftPkSize == rightPkSize && leftPkSize != 0 ? new
BitSet() : null;
+
+ leftKeys.set(0, leftPkSize);
+ rightKeys.set(0, rightPkSize);
+
+ if (commonKeys != null) {
+ assert leftPkSize == rightPkSize;
+
+ commonKeys.set(0, leftPkSize);
+ }
+ }
+
+ /** */
+ void countKeys(KeyColumnOrigin left, KeyColumnOrigin right) {
+ if (left.positionInKey >= 0) {
+ leftKeys.clear(left.positionInKey);
+ }
+
+ if (right.positionInKey >= 0) {
+ rightKeys.clear(right.positionInKey);
+ }
+
+ if (commonKeys != null && left.positionInKey ==
right.positionInKey && left.positionInKey >= 0) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -72,48 +117,335 @@ public class IgniteMdRowCount extends RelMdRowCount {
mq.getRowCount(rel.getLeft()));
}
+ JoinInfo joinInfo = rel.analyzeCondition();
+
+ if (joinInfo.pairs().isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
// Row count estimates of 0 will be rounded up to 1.
// So, use maxRowCount where the product is very small.
- final Double left = mq.getRowCount(rel.getLeft());
- final Double right = mq.getRowCount(rel.getRight());
+ final Double leftRowCnt = mq.getRowCount(rel.getLeft());
+ final Double rightRowCnt = multiply(mq.getRowCount(rel.getRight()),
rightAdjust);
- if (left == null || right == null)
+ if (leftRowCnt == null || rightRowCnt == null)
return null;
- if (left <= 1D || right <= 1D) {
+ if (leftRowCnt <= 1D || rightRowCnt <= 1D) {
Double max = mq.getMaxRowCount(rel);
if (max != null && max <= 1D)
return max;
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ // Primary key columns per table.
+ Map<IgniteTable, List<Integer>> pkColsPerTable = new
IdentityHashMap<>(2);
+
+ Map<Integer, KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq,
rel.getLeft(), joinInfo.leftKeys, pkColsPerTable);
+ Map<Integer, KeyColumnOrigin> columnsFromRight = resolveOrigins(mq,
rel.getRight(), joinInfo.rightKeys, pkColsPerTable);
+
+ if (columnsFromLeft.isEmpty() || columnsFromRight.isEmpty()) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ Map<TablesPair, JoinContext> joinCtxts = new HashMap<>();
+ for (IntPair joinKeys : joinInfo.pairs()) {
+ KeyColumnOrigin leftKey = columnsFromLeft.get(joinKeys.source);
+ KeyColumnOrigin rightKey = columnsFromRight.get(joinKeys.target);
+
+ if (leftKey == null || rightKey == null) {
+ continue;
+ }
+
+ joinCtxts.computeIfAbsent(
+ new TablesPair(
+ leftKey.origin.getOriginTable(),
+ rightKey.origin.getOriginTable()
+ ),
+ key -> {
+ IgniteTable leftTable = key.left.unwrap(IgniteTable.class);
+ IgniteTable rightTable =
key.right.unwrap(IgniteTable.class);
+
+ assert leftTable != null && rightTable != null;
+
+ List<Integer> leftPkCols = pkColsPerTable.get(leftTable);
+ List<Integer> rightPkCols = pkColsPerTable.get(rightTable);
+
+ assert leftPkCols != null && rightPkCols != null :
leftPkCols + " " + rightPkCols;
+
+ return new JoinContext(leftPkCols.size(),
rightPkCols.size());
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinCtxts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinCtxts.values().iterator();
+ JoinContext joinCtx = it.next();
+ while (it.hasNext()) {
+ JoinContext nextCtx = it.next();
+ if (nextCtx.joinType().strength > joinCtx.joinType().strength) {
+ joinCtx = nextCtx;
+ }
+
+ if (joinCtx.joinType().strength ==
JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (joinCtx.joinType() == JoiningRelationType.UNKNOWN) {
+ // Use crude estimation instead.
+ return crudeEstimation(mq, joinInfo, rel, leftRowCnt, rightRowCnt);
+ }
+
+ double postFiltrationAdjustment = 1.0;
+
+ // Outer joins return every row of the preserved side(s), the result
can't be smaller than that.
+ double preservedRowCnt = 0.0;
+
+ switch (rel.getJoinType()) {
+ case INNER:
+ case SEMI:
+ // Extra join keys as well as non-equi conditions serves as
post-filtration,
+ // therefore we need to adjust final result with a little
factor.
+ if (joinCtxts.size() != 1 || !joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+
+ break;
+ case LEFT:
+ preservedRowCnt = leftRowCnt;
+
+ break;
+ case RIGHT:
+ preservedRowCnt = rightRowCnt;
+
+ break;
+ case FULL:
+ preservedRowCnt = Math.max(leftRowCnt, rightRowCnt);
+
+ break;
+ default:
+ break;
+ }
+
+ double baseRowCnt = 0.0;
+ Double percentageAdjustment = null;
+ if (joinCtx.joinType() == JoiningRelationType.PK_ON_PK) {
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ if (!joinInfo.isEqui())
+ postFiltrationAdjustment = NON_EQUI_COEFF;
+ // Assume we have two fact tables SALES and RETURNS sharing
the same primary key. Every item
+ // can be sold, but only items which were sold can be returned
back, therefore
+ // size(SALES) > size(RETURNS). When joining SALES on RETURNS
by primary key, the estimated
+ // result size will be the same as the size of the smallest
table (RETURNS in this case),
+ // adjusted by the percentage of rows of the biggest table
(SALES in this case; percentage
+ // adjustment is required to account for predicates pushed
down to the table, e.g. we are
+ // interested in returns of items with certain category)
+ if (leftRowCnt > rightRowCnt) {
+ baseRowCnt = rightRowCnt;
+ percentageAdjustment =
mq.getPercentageOriginalRows(rel.getLeft());
+ }
+ else {
+ baseRowCnt = leftRowCnt;
+ percentageAdjustment = rightPercentage(mq, rel,
rightAdjust);
+ }
+ }
+ else if (rel.getJoinType() == JoinRelType.LEFT) {
+ baseRowCnt = leftRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.RIGHT) {
+ baseRowCnt = rightRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.FULL) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+
+ // Fall-back.
+ if (selectivity == null) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel,
rel.getCondition());
+ }
+
+ Double leftPercentage =
mq.getPercentageOriginalRows(rel.getLeft());
+ Double rightPercentage =
mq.getPercentageOriginalRows(rel.getRight());
+ leftPercentage = leftPercentage == null ? 1.0 : leftPercentage;
+ rightPercentage = rightPercentage == null ? 1.0 :
rightPercentage;
+
+ double intersection = Math.min(leftRowCnt * rightPercentage,
rightRowCnt * leftPercentage);
+
+ return leftRowCnt + rightRowCnt - intersection;
+ }
+ }
+ else if (joinCtx.joinType() == JoiningRelationType.FK_ON_PK) {
+ // For foreign key joins the base table is the one which is joined
by non-primary key columns.
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+ baseRowCnt = leftRowCnt * selectivity;
+ percentageAdjustment = rightPercentage(mq, rel, rightAdjust);
+ }
+ else if (rel.getJoinType() == JoinRelType.LEFT ||
rel.getJoinType() == JoinRelType.RIGHT) {
+ baseRowCnt = leftRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.FULL) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+
+ // Fall-back.
+ if (selectivity == null) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel,
rel.getCondition());
+ }
+
+ baseRowCnt = rightRowCnt + leftRowCnt;
+ percentageAdjustment = 1.0 - selectivity;
+ }
+ }
+ else { // PK_ON_FK
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+ baseRowCnt = rightRowCnt * selectivity;
+ percentageAdjustment =
mq.getPercentageOriginalRows(rel.getLeft());
+ }
+ else if (rel.getJoinType() == JoinRelType.RIGHT ||
rel.getJoinType() == JoinRelType.LEFT) {
+ baseRowCnt = rightRowCnt;
+ }
+ else if (rel.getJoinType() == JoinRelType.FULL) {
+ Double selectivity = mq.getSelectivity(rel,
rel.getCondition());
+
+ // Fall-back.
+ if (selectivity == null) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel,
rel.getCondition());
+ }
+
+ baseRowCnt = rightRowCnt + leftRowCnt;
+ percentageAdjustment = 1.0 - selectivity;
+ }
+ }
+
+ if (percentageAdjustment == null || Double.compare(1.0,
percentageAdjustment) == 0) {
+ // No info or default 1.0, let's estimate. The intersection
estimate is not applicable to outer joins:
+ // the preserved side is returned entirely, no matter how many
rows have a match.
+ percentageAdjustment = preservedRowCnt > 0.0 ? 1.0 :
INTERSECT_ESTIMATE_COEFF;
+ }
+
+ return Math.max(preservedRowCnt, baseRowCnt * percentageAdjustment *
postFiltrationAdjustment);
+ }
+ /** Percentage of original rows of the right input, see {@link
#joinRowCount(RelMetadataQuery, Join, double)}. */
+ @Nullable private static Double rightPercentage(RelMetadataQuery mq, Join
rel, double rightAdjust) {
+ Double percentage = mq.getPercentageOriginalRows(rel.getRight());
+
+ return percentage == null ? null : Math.min(1.0, percentage *
rightAdjust);
+ }
+
+ /** */
+ private static Map<Integer, KeyColumnOrigin> resolveOrigins(
+ RelMetadataQuery mq,
+ RelNode joinSide,
+ ImmutableIntList keys,
+ Map<IgniteTable, List<Integer>> pkColsPerTable
+ ) {
+ GridLeanMap<Integer, KeyColumnOrigin> origins = new GridLeanMap<>();
+
+ for (int i : keys) {
+ if (origins.containsKey(i)) {
+ continue;
+ }
+
+ RelColumnOrigin origin = mq.getColumnOrigin(joinSide, i);
+ if (origin == null) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -157,4 +489,129 @@ public double getRowCount(IgniteLimit rel,
RelMetadataQuery mq) {
public double getRowCount(IgniteTableModify rel, RelMetadataQuery mq) {
return rel.estimateRowCount(mq);
}
+
+ /** */
+ private record TablesPair(RelOptTable left, RelOptTable right) { }
+
+ /** */
+ private static class JoinContext {
+ /** Used columns of primary key of table from left side. */
+ private final BitSet leftKeys;
+
+ /** Used columns of primary key of table from right side. */
+ private final BitSet rightKeys;
+
+ /**
+ * Used columns of primary key in both tables.
+ *
+ * <p>This bitset is initialized when PK of both tables has equal
columns count, and
+ * bits are cleared when join pair contains columns with equal
positions in PK of corresponding
+ * table. For example, having tables T1 and T2 with primary keys in
both tables defined as
+ * CONSTRAINT PRIMARY KEY (a, b), in case of query
+ * {@code SELECT ... FROM t1 JOIN t2 ON t1.a = t2.a AND t1.b = t2.b}
commonKeys will be initialized
+ * and cleared, but in case of query {@code SELECT ... FROM t1 JOIN t2
ON t1.a = t2.b AND t1.b = t2.a}
+ * (mind the join condition, where column A of one table compared with
column B of another), will be
+ * only initialized (since size of the primary keys are equal), but
not cleared.
+ */
+ private final @Nullable BitSet commonKeys;
+
+ /** Whether primary key columns of both tables are known. */
+ private final boolean pkKnown;
+
+ /** */
+ JoinContext(int leftPkSize, int rightPkSize) {
+ pkKnown = leftPkSize > 0 && rightPkSize > 0;
+
+ leftKeys = new BitSet();
+ rightKeys = new BitSet();
+ commonKeys = leftPkSize == rightPkSize && leftPkSize != 0 ? new
BitSet() : null;
+
+ leftKeys.set(0, leftPkSize);
+ rightKeys.set(0, rightPkSize);
+
+ if (commonKeys != null) {
+ assert leftPkSize == rightPkSize;
+
+ commonKeys.set(0, leftPkSize);
+ }
+ }
+
+ /** */
+ void countKeys(KeyColumnOrigin left, KeyColumnOrigin right) {
+ if (left.positionInKey >= 0) {
+ leftKeys.clear(left.positionInKey);
+ }
+
+ if (right.positionInKey >= 0) {
+ rightKeys.clear(right.positionInKey);
+ }
+
+ if (commonKeys != null && left.positionInKey ==
right.positionInKey && left.positionInKey >= 0) {
+ commonKeys.clear(left.positionInKey);
+ }
+ }
+
+ /** */
+ JoiningRelationType joinType() {
+ if (!pkKnown) {
+ return JoiningRelationType.UNKNOWN;
+ }
+
+ if (commonKeys != null && commonKeys.isEmpty()) {
+ return JoiningRelationType.PK_ON_PK;
+ }
+
+ if (rightKeys.isEmpty()) {
+ return JoiningRelationType.FK_ON_PK;
+ }
+
+ if (leftKeys.isEmpty()) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -157,4 +489,129 @@ public double getRowCount(IgniteLimit rel,
RelMetadataQuery mq) {
public double getRowCount(IgniteTableModify rel, RelMetadataQuery mq) {
return rel.estimateRowCount(mq);
}
+
+ /** */
+ private record TablesPair(RelOptTable left, RelOptTable right) { }
+
+ /** */
+ private static class JoinContext {
+ /** Used columns of primary key of table from left side. */
+ private final BitSet leftKeys;
+
+ /** Used columns of primary key of table from right side. */
+ private final BitSet rightKeys;
+
+ /**
+ * Used columns of primary key in both tables.
+ *
+ * <p>This bitset is initialized when PK of both tables has equal
columns count, and
+ * bits are cleared when join pair contains columns with equal
positions in PK of corresponding
+ * table. For example, having tables T1 and T2 with primary keys in
both tables defined as
+ * CONSTRAINT PRIMARY KEY (a, b), in case of query
+ * {@code SELECT ... FROM t1 JOIN t2 ON t1.a = t2.a AND t1.b = t2.b}
commonKeys will be initialized
+ * and cleared, but in case of query {@code SELECT ... FROM t1 JOIN t2
ON t1.a = t2.b AND t1.b = t2.a}
+ * (mind the join condition, where column A of one table compared with
column B of another), will be
+ * only initialized (since size of the primary keys are equal), but
not cleared.
+ */
+ private final @Nullable BitSet commonKeys;
+
+ /** Whether primary key columns of both tables are known. */
+ private final boolean pkKnown;
+
+ /** */
+ JoinContext(int leftPkSize, int rightPkSize) {
+ pkKnown = leftPkSize > 0 && rightPkSize > 0;
+
+ leftKeys = new BitSet();
+ rightKeys = new BitSet();
+ commonKeys = leftPkSize == rightPkSize && leftPkSize != 0 ? new
BitSet() : null;
+
+ leftKeys.set(0, leftPkSize);
+ rightKeys.set(0, rightPkSize);
+
+ if (commonKeys != null) {
+ assert leftPkSize == rightPkSize;
+
+ commonKeys.set(0, leftPkSize);
+ }
+ }
+
+ /** */
+ void countKeys(KeyColumnOrigin left, KeyColumnOrigin right) {
+ if (left.positionInKey >= 0) {
+ leftKeys.clear(left.positionInKey);
+ }
+
+ if (right.positionInKey >= 0) {
+ rightKeys.clear(right.positionInKey);
+ }
+
+ if (commonKeys != null && left.positionInKey ==
right.positionInKey && left.positionInKey >= 0) {
+ commonKeys.clear(left.positionInKey);
+ }
+ }
+
+ /** */
+ JoiningRelationType joinType() {
+ if (!pkKnown) {
+ return JoiningRelationType.UNKNOWN;
+ }
+
+ if (commonKeys != null && commonKeys.isEmpty()) {
+ return JoiningRelationType.PK_ON_PK;
+ }
+
+ if (rightKeys.isEmpty()) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -157,4 +489,129 @@ public double getRowCount(IgniteLimit rel,
RelMetadataQuery mq) {
public double getRowCount(IgniteTableModify rel, RelMetadataQuery mq) {
return rel.estimateRowCount(mq);
}
+
+ /** */
+ private record TablesPair(RelOptTable left, RelOptTable right) { }
+
+ /** */
+ private static class JoinContext {
+ /** Used columns of primary key of table from left side. */
+ private final BitSet leftKeys;
+
+ /** Used columns of primary key of table from right side. */
+ private final BitSet rightKeys;
+
+ /**
+ * Used columns of primary key in both tables.
+ *
+ * <p>This bitset is initialized when PK of both tables has equal
columns count, and
+ * bits are cleared when join pair contains columns with equal
positions in PK of corresponding
+ * table. For example, having tables T1 and T2 with primary keys in
both tables defined as
+ * CONSTRAINT PRIMARY KEY (a, b), in case of query
+ * {@code SELECT ... FROM t1 JOIN t2 ON t1.a = t2.a AND t1.b = t2.b}
commonKeys will be initialized
+ * and cleared, but in case of query {@code SELECT ... FROM t1 JOIN t2
ON t1.a = t2.b AND t1.b = t2.a}
+ * (mind the join condition, where column A of one table compared with
column B of another), will be
+ * only initialized (since size of the primary keys are equal), but
not cleared.
+ */
+ private final @Nullable BitSet commonKeys;
+
+ /** Whether primary key columns of both tables are known. */
+ private final boolean pkKnown;
+
+ /** */
+ JoinContext(int leftPkSize, int rightPkSize) {
+ pkKnown = leftPkSize > 0 && rightPkSize > 0;
+
+ leftKeys = new BitSet();
+ rightKeys = new BitSet();
+ commonKeys = leftPkSize == rightPkSize && leftPkSize != 0 ? new
BitSet() : null;
+
+ leftKeys.set(0, leftPkSize);
+ rightKeys.set(0, rightPkSize);
+
+ if (commonKeys != null) {
+ assert leftPkSize == rightPkSize;
+
+ commonKeys.set(0, leftPkSize);
+ }
+ }
+
+ /** */
+ void countKeys(KeyColumnOrigin left, KeyColumnOrigin right) {
+ if (left.positionInKey >= 0) {
+ leftKeys.clear(left.positionInKey);
+ }
+
+ if (right.positionInKey >= 0) {
Review Comment:
Redundant braces for one line statement
##########
modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/UncollectPlannerTest.java:
##########
@@ -112,11 +112,7 @@ public void testHashTableAndUnnestJoin() throws Exception {
assertPlan(sql, publicSchema, nodeOrAnyChild(isInstanceOf(Join.class)
.and(nodeOrAnyChild(isInstanceOf(IgniteExchange.class).negate())
.and(nodeOrAnyChild(isTableScan("hash_tbl"))))
- .and(nodeOrAnyChild(isInstanceOf(IgniteTrimExchange.class))
- .and(nodeOrAnyChild(isInstanceOf(IgniteUncollect.class)
- .and(hasDistribution(broadcast()))
- ))
- )
+ .and(nodeOrAnyChild(isInstanceOf(IgniteUncollect.class)))
Review Comment:
This test checks rehashing of uncollect. Let's add index to HASH_TBL:
```
.addIndex("IDX", 0),
```
And replace table-scan check to index scan check
(`nodeOrAnyChild(isIndexScan("HASH_TBL", "IDX"))`), but keep rehasing
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
