zstan commented on code in PR #13389:
URL: https://github.com/apache/ignite/pull/13389#discussion_r3854178738
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -72,48 +88,263 @@ 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 = mq.getRowCount(rel.getRight());
- 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();
+ Map<Integer, KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq,
rel.getLeft(), joinInfo.leftKeys);
+ Map<Integer, KeyColumnOrigin> columnsFromRight = resolveOrigins(mq,
rel.getRight(), joinInfo.rightKeys);
+
+ if (columnsFromLeft.isEmpty() || columnsFromRight.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ 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;
+
+ int leftPkSize = leftTable.distribution().getKeys().size();
+ int rightPkSize =
rightTable.distribution().getKeys().size();
+
+ return new JoinContext(leftPkSize, rightPkSize);
+ }
+ ).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;
+
+ 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;
+ default:
+ break;
+ }
+
+ double baseRowCnt = 0.0;
+ Double percentageAdjustment = null;
+ if (joinCtx.joinType() == JoiningRelationType.PK_ON_PK) {
+ postFiltrationAdjustment = EQUI_COEFF;
+
+ if (rel.getJoinType() == JoinRelType.INNER || rel.getJoinType() ==
JoinRelType.SEMI) {
+ // 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 =
mq.getPercentageOriginalRows(rel.getRight());
+ }
+ }
+ 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());
+ }
+
+ baseRowCnt = rightRowCnt + leftRowCnt;
+ percentageAdjustment = 1.0 - selectivity;
+ }
+ }
+ 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 =
mq.getPercentageOriginalRows(rel.getRight());
+ }
+ 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) {
+ baseRowCnt = rightRowCnt;
+ 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) {
+ // No info, let's be conservative.
+ percentageAdjustment = 1.0;
+ }
+
+ return baseRowCnt * percentageAdjustment * postFiltrationAdjustment;
+ }
+ /** */
+ private static Map<Integer, KeyColumnOrigin>
resolveOrigins(RelMetadataQuery mq, RelNode joinShoulder, ImmutableIntList
keys) {
+ GridLeanMap<Integer, KeyColumnOrigin> origins = new GridLeanMap<>();
+
+ for (int i : keys) {
+ if (origins.containsKey(i)) {
+ continue;
+ }
+
+ RelColumnOrigin origin = mq.getColumnOrigin(joinShoulder, i);
+ if (origin == null) {
+ continue;
+ }
+
+ IgniteTable table =
origin.getOriginTable().unwrap(IgniteTable.class);
+ if (table == null || !table.distribution().function().affinity())
+ continue;
+
+ // Keys can relate to affinity not pk, just assumption here.
+ ImmutableIntList distKeys = table.distribution().getKeys();
+
+ int idx = distKeys.indexOf(origin.getOriginColumnOrdinal());
+
+ origins.put(i, new KeyColumnOrigin(origin, idx));
+ }
+
+ return origins;
+ }
+
+ /**
+ * @param origin
+ * @param positionInKey
+ */
+ private record KeyColumnOrigin(RelColumnOrigin origin, int positionInKey)
{ }
+
+ /** This part of estimation is applicable for distributions different from
hash, i.e. broadcast, single. */
+ private static double crudeEstimation(RelMetadataQuery mq, JoinInfo
joinInfo, Join rel, Double leftRowCnt, Double rightRowCnt) {
ImmutableIntList leftKeys = joinInfo.leftKeys;
ImmutableIntList rightKeys = joinInfo.rightKeys;
- double selectivity = mq.getSelectivity(rel, rel.getCondition());
+ Double selectivity = mq.getSelectivity(rel, rel.getCondition());
+
+ if (selectivity == null) {
+ // Fall-back to calcite's implementation.
+ RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
Review Comment:
done, thanks
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/metadata/IgniteMdRowCount.java:
##########
@@ -72,48 +88,263 @@ 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 = mq.getRowCount(rel.getRight());
- 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();
+ Map<Integer, KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq,
rel.getLeft(), joinInfo.leftKeys);
+ Map<Integer, KeyColumnOrigin> columnsFromRight = resolveOrigins(mq,
rel.getRight(), joinInfo.rightKeys);
+
+ if (columnsFromLeft.isEmpty() || columnsFromRight.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ 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;
+
+ int leftPkSize = leftTable.distribution().getKeys().size();
+ int rightPkSize =
rightTable.distribution().getKeys().size();
+
+ return new JoinContext(leftPkSize, rightPkSize);
+ }
+ ).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;
+
+ 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;
+ default:
+ break;
+ }
+
+ double baseRowCnt = 0.0;
+ Double percentageAdjustment = null;
+ if (joinCtx.joinType() == JoiningRelationType.PK_ON_PK) {
+ postFiltrationAdjustment = EQUI_COEFF;
Review Comment:
done
--
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]
