You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@ignite.apache.org by "korlov42 (via GitHub)" <gi...@apache.org> on 2025/01/02 13:55:00 UTC
[PR] IGNITE-23968 Sql. Improve row count estimation for joins [ignite-3]
korlov42 opened a new pull request, #4992:
URL: https://github.com/apache/ignite-3/pull/4992
https://issues.apache.org/jira/browse/IGNITE-23968
------
Thank you for submitting the pull request.
To streamline the review process of the patch and ensure better code quality
we ask both an author and a reviewer to verify the following:
### The Review Checklist
- [ ] **Formal criteria:** TC status, codestyle, mandatory documentation. Also make sure to complete the following:
\- There is a single JIRA ticket related to the pull request.
\- The web-link to the pull request is attached to the JIRA ticket.
\- The JIRA ticket has the Patch Available state.
\- The description of the JIRA ticket explains WHAT was made, WHY and HOW.
\- The pull request title is treated as the final commit message. The following pattern must be used: IGNITE-XXXX Change summary where XXXX - number of JIRA issue.
- [ ] **Design:** new code conforms with the design principles of the components it is added to.
- [ ] **Patch quality:** patch cannot be split into smaller pieces, its size must be reasonable.
- [ ] **Code quality:** code is clean and readable, necessary developer documentation is added if needed.
- [ ] **Tests code quality:** test set covers positive/negative scenarios, happy/edge cases. Tests are effective in terms of execution time and resources.
### Notes
- [Apache Ignite Coding Guidelines](https://cwiki.apache.org/confluence/display/IGNITE/Java+Code+Style+Guide)
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-23968 Sql. Improve row count estimation for joins [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #4992:
URL: https://github.com/apache/ignite-3/pull/4992#discussion_r1905363421
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/metadata/IgniteMdRowCount.java:
##########
@@ -100,68 +106,334 @@ public double getRowCount(IgniteLimit rel, RelMetadataQuery mq) {
}
/**
- * JoinRowCount.
- * TODO Documentation https://issues.apache.org/jira/browse/IGNITE-15859
+ * Estimates the number of rows produced by a join operation.
Review Comment:
link to `JoiningRelationType` has been added
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-23968 Sql. Improve row count estimation for joins [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 merged PR #4992:
URL: https://github.com/apache/ignite-3/pull/4992
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-23968 Sql. Improve row count estimation for joins [ignite-3]
Posted by "ygerzhedovich (via GitHub)" <gi...@apache.org>.
ygerzhedovich commented on code in PR #4992:
URL: https://github.com/apache/ignite-3/pull/4992#discussion_r1901668559
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/metadata/IgniteMdRowCount.java:
##########
@@ -100,68 +106,334 @@ public double getRowCount(IgniteLimit rel, RelMetadataQuery mq) {
}
/**
- * JoinRowCount.
- * TODO Documentation https://issues.apache.org/jira/browse/IGNITE-15859
+ * Estimates the number of rows produced by a join operation.
Review Comment:
It will be good to add an explanation of what a `foreign key` is from Ignite perspective, due to we don't support such relations now
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/metadata/IgniteMdRowCount.java:
##########
@@ -100,68 +106,334 @@ public double getRowCount(IgniteLimit rel, RelMetadataQuery mq) {
}
/**
- * JoinRowCount.
- * TODO Documentation https://issues.apache.org/jira/browse/IGNITE-15859
+ * Estimates the number of rows produced by a join operation.
+ *
+ * <p>This method calculates an estimated row count for a join by analyzing the join type,
+ * join keys, and the cardinality of the left and right inputs. It provides specialized
+ * handling for primary key and foreign key relationships. When certain metadata is unavailable
+ * or when specific conditions are not met, it falls back to Calcite's default implementation
+ * for estimating the row count.
+ *
+ * <p>Implementation details:</p>
+ * <ul>
+ * <li>If the join type is not {@link JoinRelType#INNER}, Calcite's default implementation is used.</li>
+ * <li>If the join is non-equi join, Calcite's default implementation is used.</li>
+ * <li>The row counts of the left and right inputs are retrieved using
+ * {@link RelMetadataQuery#getRowCount}. If either value is unavailable, the result is {@code null}.</li>
+ * <li>If the row counts are very small (≤ 1.0), the method uses the maximum row count as a fallback.</li>
Review Comment:
why fallback to maximum row count used here instead of just 1
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/metadata/IgniteMdRowCount.java:
##########
@@ -100,68 +106,334 @@ public double getRowCount(IgniteLimit rel, RelMetadataQuery mq) {
}
/**
- * JoinRowCount.
- * TODO Documentation https://issues.apache.org/jira/browse/IGNITE-15859
+ * Estimates the number of rows produced by a join operation.
Review Comment:
I see mention in JoiningRelationType, but I should understand it when I read just this javadoc. Maybe will be good just to add link to the enum here
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-23968 Sql. Improve row count estimation for joins [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #4992:
URL: https://github.com/apache/ignite-3/pull/4992#discussion_r1905364002
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/metadata/IgniteMdRowCount.java:
##########
@@ -100,68 +106,334 @@ public double getRowCount(IgniteLimit rel, RelMetadataQuery mq) {
}
/**
- * JoinRowCount.
- * TODO Documentation https://issues.apache.org/jira/browse/IGNITE-15859
+ * Estimates the number of rows produced by a join operation.
+ *
+ * <p>This method calculates an estimated row count for a join by analyzing the join type,
+ * join keys, and the cardinality of the left and right inputs. It provides specialized
+ * handling for primary key and foreign key relationships. When certain metadata is unavailable
+ * or when specific conditions are not met, it falls back to Calcite's default implementation
+ * for estimating the row count.
+ *
+ * <p>Implementation details:</p>
+ * <ul>
+ * <li>If the join type is not {@link JoinRelType#INNER}, Calcite's default implementation is used.</li>
+ * <li>If the join is non-equi join, Calcite's default implementation is used.</li>
+ * <li>The row counts of the left and right inputs are retrieved using
+ * {@link RelMetadataQuery#getRowCount}. If either value is unavailable, the result is {@code null}.</li>
+ * <li>If the row counts are very small (≤ 1.0), the method uses the maximum row count as a fallback.</li>
Review Comment:
this is inlined fallback to Calcite's default implementation, see `org.apache.calcite.rel.metadata.RelMdUtil#getJoinRowCount`
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-23968 Sql. Improve row count estimation for joins [ignite-3]
Posted by "lowka (via GitHub)" <gi...@apache.org>.
lowka commented on code in PR #4992:
URL: https://github.com/apache/ignite-3/pull/4992#discussion_r1903669268
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/metadata/IgniteMdRowCount.java:
##########
@@ -100,68 +106,334 @@ public double getRowCount(IgniteLimit rel, RelMetadataQuery mq) {
}
/**
- * JoinRowCount.
- * TODO Documentation https://issues.apache.org/jira/browse/IGNITE-15859
+ * Estimates the number of rows produced by a join operation.
+ *
+ * <p>This method calculates an estimated row count for a join by analyzing the join type,
+ * join keys, and the cardinality of the left and right inputs. It provides specialized
+ * handling for primary key and foreign key relationships. When certain metadata is unavailable
+ * or when specific conditions are not met, it falls back to Calcite's default implementation
+ * for estimating the row count.
+ *
+ * <p>Implementation details:</p>
+ * <ul>
+ * <li>If the join type is not {@link JoinRelType#INNER}, Calcite's default implementation is used.</li>
+ * <li>If the join is non-equi join, Calcite's default implementation is used.</li>
+ * <li>The row counts of the left and right inputs are retrieved using
+ * {@link RelMetadataQuery#getRowCount}. If either value is unavailable, the result is {@code null}.</li>
+ * <li>If the row counts are very small (≤ 1.0), the method uses the maximum row count as a fallback.</li>
+ * <li>Join key origins are resolved for the left and right inputs, and relationships between tables
+ * (e.g., primary key or foreign key associations) are identified and grouped into join contexts.</li>
+ * <li>If no valid join context is found, the method falls back to Calcite's implementation.</li>
+ * <li>The base row count is determined by the type of join relationship:
+ * <ul>
+ * <li>For primary key-to-primary key joins, the row count is based on the smaller table,
+ * adjusted by a percentage of the larger table's rows.</li>
+ * <li>For foreign key joins, the base table is determined based on which table is
+ * joined using non-primary key columns.</li>
+ * </ul>
+ * </li>
+ * <li>An additional adjustment factor is applied for post-filtration conditions, such as extra join keys
+ * or non-equi conditions.</li>
+ * <li>If metadata for the percentage of original rows is unavailable, the adjustment defaults to 1.0.</li>
+ * </ul>
+ *
+ * <p>If none of the above criteria are satisfied, the method defaults to
+ * {@link RelMdUtil#getJoinRowCount} for the estimation.</p>
+ *
+ * @param mq The {@link RelMetadataQuery} used to retrieve metadata about relational expressions.
+ * @param rel The {@link Join} relational expression representing the join operation.
+ * @return The estimated number of rows resulting from the join, or {@code null} if the estimation cannot be determined.
+ *
+ * @see RelMetadataQuery#getRowCount
+ * @see RelMdUtil#getJoinRowCount
*/
- @Nullable
- public static Double joinRowCount(RelMetadataQuery mq, Join rel) {
- if (!rel.getJoinType().projectsRight()) {
- // Create a RexNode representing the selectivity of the
- // semijoin filter and pass it to getSelectivity
- RexNode semiJoinSelectivity =
- RelMdUtil.makeSemiJoinSelectivityRexNode(mq, rel);
+ public static @Nullable Double joinRowCount(RelMetadataQuery mq, Join rel) {
+ if (rel.getJoinType() != JoinRelType.INNER) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
- return multiply(mq.getSelectivity(rel.getLeft(), semiJoinSelectivity),
- 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());
+ Double leftRowCount = mq.getRowCount(rel.getLeft());
+ Double rightRowCount = mq.getRowCount(rel.getRight());
- if (left == null || right == null) {
+ if (leftRowCount == null || rightRowCount == null) {
return null;
}
- if (left <= 1D || right <= 1D) {
+ // Row count estimates of 0 will be rounded up to 1.
+ // So, use maxRowCount where the product is very small.
+ if (leftRowCount <= 1.0 || rightRowCount <= 1.0) {
Double max = mq.getMaxRowCount(rel);
- if (max != null && max <= 1D) {
+ if (max != null && max <= 1.0) {
return max;
}
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ Int2ObjectMap<KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq, rel.getLeft(), joinInfo.leftKeys);
+ Int2ObjectMap<KeyColumnOrigin> columnsFromRight = resolveOrigins(mq, rel.getRight(), joinInfo.rightKeys);
+
+ Map<TablesPair, JoinContext> joinContexts = 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;
+ }
+
+ joinContexts.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.keyColumns().size();
+ int rightPkSize = rightTable.keyColumns().size();
+
+ return new JoinContext(leftPkSize, rightPkSize);
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinContexts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinContexts.values().iterator();
+ JoinContext context = it.next();
+ while (it.hasNext()) {
+ JoinContext nextContext = it.next();
+ if (nextContext.joinType().strength > context.joinType().strength) {
+ context = nextContext;
+ }
+
+ if (context.joinType().strength == JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (context.joinType() == JoiningRelationType.UNKNOWN) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ double postFiltrationAdjustment = joinContexts.size() == 1 && joinInfo.isEqui() ? 1.0
+ // Extra join keys as well as non-equi conditions serves azs post-filtration,
Review Comment:
> asz
A typo
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/metadata/IgniteMdRowCount.java:
##########
@@ -100,68 +106,334 @@ public double getRowCount(IgniteLimit rel, RelMetadataQuery mq) {
}
/**
- * JoinRowCount.
- * TODO Documentation https://issues.apache.org/jira/browse/IGNITE-15859
+ * Estimates the number of rows produced by a join operation.
+ *
+ * <p>This method calculates an estimated row count for a join by analyzing the join type,
+ * join keys, and the cardinality of the left and right inputs. It provides specialized
+ * handling for primary key and foreign key relationships. When certain metadata is unavailable
+ * or when specific conditions are not met, it falls back to Calcite's default implementation
+ * for estimating the row count.
+ *
+ * <p>Implementation details:</p>
+ * <ul>
+ * <li>If the join type is not {@link JoinRelType#INNER}, Calcite's default implementation is used.</li>
+ * <li>If the join is non-equi join, Calcite's default implementation is used.</li>
+ * <li>The row counts of the left and right inputs are retrieved using
+ * {@link RelMetadataQuery#getRowCount}. If either value is unavailable, the result is {@code null}.</li>
+ * <li>If the row counts are very small (≤ 1.0), the method uses the maximum row count as a fallback.</li>
+ * <li>Join key origins are resolved for the left and right inputs, and relationships between tables
+ * (e.g., primary key or foreign key associations) are identified and grouped into join contexts.</li>
+ * <li>If no valid join context is found, the method falls back to Calcite's implementation.</li>
+ * <li>The base row count is determined by the type of join relationship:
+ * <ul>
+ * <li>For primary key-to-primary key joins, the row count is based on the smaller table,
+ * adjusted by a percentage of the larger table's rows.</li>
+ * <li>For foreign key joins, the base table is determined based on which table is
+ * joined using non-primary key columns.</li>
+ * </ul>
+ * </li>
+ * <li>An additional adjustment factor is applied for post-filtration conditions, such as extra join keys
+ * or non-equi conditions.</li>
+ * <li>If metadata for the percentage of original rows is unavailable, the adjustment defaults to 1.0.</li>
+ * </ul>
+ *
+ * <p>If none of the above criteria are satisfied, the method defaults to
+ * {@link RelMdUtil#getJoinRowCount} for the estimation.</p>
+ *
+ * @param mq The {@link RelMetadataQuery} used to retrieve metadata about relational expressions.
+ * @param rel The {@link Join} relational expression representing the join operation.
+ * @return The estimated number of rows resulting from the join, or {@code null} if the estimation cannot be determined.
+ *
+ * @see RelMetadataQuery#getRowCount
+ * @see RelMdUtil#getJoinRowCount
*/
- @Nullable
- public static Double joinRowCount(RelMetadataQuery mq, Join rel) {
- if (!rel.getJoinType().projectsRight()) {
- // Create a RexNode representing the selectivity of the
- // semijoin filter and pass it to getSelectivity
- RexNode semiJoinSelectivity =
- RelMdUtil.makeSemiJoinSelectivityRexNode(mq, rel);
+ public static @Nullable Double joinRowCount(RelMetadataQuery mq, Join rel) {
+ if (rel.getJoinType() != JoinRelType.INNER) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
- return multiply(mq.getSelectivity(rel.getLeft(), semiJoinSelectivity),
- 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());
+ Double leftRowCount = mq.getRowCount(rel.getLeft());
+ Double rightRowCount = mq.getRowCount(rel.getRight());
- if (left == null || right == null) {
+ if (leftRowCount == null || rightRowCount == null) {
return null;
}
- if (left <= 1D || right <= 1D) {
+ // Row count estimates of 0 will be rounded up to 1.
+ // So, use maxRowCount where the product is very small.
+ if (leftRowCount <= 1.0 || rightRowCount <= 1.0) {
Double max = mq.getMaxRowCount(rel);
- if (max != null && max <= 1D) {
+ if (max != null && max <= 1.0) {
return max;
}
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ Int2ObjectMap<KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq, rel.getLeft(), joinInfo.leftKeys);
+ Int2ObjectMap<KeyColumnOrigin> columnsFromRight = resolveOrigins(mq, rel.getRight(), joinInfo.rightKeys);
+
+ Map<TablesPair, JoinContext> joinContexts = 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;
+ }
+
+ joinContexts.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.keyColumns().size();
+ int rightPkSize = rightTable.keyColumns().size();
+
+ return new JoinContext(leftPkSize, rightPkSize);
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinContexts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinContexts.values().iterator();
+ JoinContext context = it.next();
+ while (it.hasNext()) {
+ JoinContext nextContext = it.next();
+ if (nextContext.joinType().strength > context.joinType().strength) {
+ context = nextContext;
+ }
+
+ if (context.joinType().strength == JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (context.joinType() == JoiningRelationType.UNKNOWN) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ double postFiltrationAdjustment = joinContexts.size() == 1 && joinInfo.isEqui() ? 1.0
+ // Extra join keys as well as non-equi conditions serves azs post-filtration,
Review Comment:
> asz
A typo.
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-23968 Sql. Improve row count estimation for joins [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #4992:
URL: https://github.com/apache/ignite-3/pull/4992#discussion_r1905362633
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/metadata/IgniteMdRowCount.java:
##########
@@ -100,68 +106,334 @@ public double getRowCount(IgniteLimit rel, RelMetadataQuery mq) {
}
/**
- * JoinRowCount.
- * TODO Documentation https://issues.apache.org/jira/browse/IGNITE-15859
+ * Estimates the number of rows produced by a join operation.
+ *
+ * <p>This method calculates an estimated row count for a join by analyzing the join type,
+ * join keys, and the cardinality of the left and right inputs. It provides specialized
+ * handling for primary key and foreign key relationships. When certain metadata is unavailable
+ * or when specific conditions are not met, it falls back to Calcite's default implementation
+ * for estimating the row count.
+ *
+ * <p>Implementation details:</p>
+ * <ul>
+ * <li>If the join type is not {@link JoinRelType#INNER}, Calcite's default implementation is used.</li>
+ * <li>If the join is non-equi join, Calcite's default implementation is used.</li>
+ * <li>The row counts of the left and right inputs are retrieved using
+ * {@link RelMetadataQuery#getRowCount}. If either value is unavailable, the result is {@code null}.</li>
+ * <li>If the row counts are very small (≤ 1.0), the method uses the maximum row count as a fallback.</li>
+ * <li>Join key origins are resolved for the left and right inputs, and relationships between tables
+ * (e.g., primary key or foreign key associations) are identified and grouped into join contexts.</li>
+ * <li>If no valid join context is found, the method falls back to Calcite's implementation.</li>
+ * <li>The base row count is determined by the type of join relationship:
+ * <ul>
+ * <li>For primary key-to-primary key joins, the row count is based on the smaller table,
+ * adjusted by a percentage of the larger table's rows.</li>
+ * <li>For foreign key joins, the base table is determined based on which table is
+ * joined using non-primary key columns.</li>
+ * </ul>
+ * </li>
+ * <li>An additional adjustment factor is applied for post-filtration conditions, such as extra join keys
+ * or non-equi conditions.</li>
+ * <li>If metadata for the percentage of original rows is unavailable, the adjustment defaults to 1.0.</li>
+ * </ul>
+ *
+ * <p>If none of the above criteria are satisfied, the method defaults to
+ * {@link RelMdUtil#getJoinRowCount} for the estimation.</p>
+ *
+ * @param mq The {@link RelMetadataQuery} used to retrieve metadata about relational expressions.
+ * @param rel The {@link Join} relational expression representing the join operation.
+ * @return The estimated number of rows resulting from the join, or {@code null} if the estimation cannot be determined.
+ *
+ * @see RelMetadataQuery#getRowCount
+ * @see RelMdUtil#getJoinRowCount
*/
- @Nullable
- public static Double joinRowCount(RelMetadataQuery mq, Join rel) {
- if (!rel.getJoinType().projectsRight()) {
- // Create a RexNode representing the selectivity of the
- // semijoin filter and pass it to getSelectivity
- RexNode semiJoinSelectivity =
- RelMdUtil.makeSemiJoinSelectivityRexNode(mq, rel);
+ public static @Nullable Double joinRowCount(RelMetadataQuery mq, Join rel) {
+ if (rel.getJoinType() != JoinRelType.INNER) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
- return multiply(mq.getSelectivity(rel.getLeft(), semiJoinSelectivity),
- 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());
+ Double leftRowCount = mq.getRowCount(rel.getLeft());
+ Double rightRowCount = mq.getRowCount(rel.getRight());
- if (left == null || right == null) {
+ if (leftRowCount == null || rightRowCount == null) {
return null;
}
- if (left <= 1D || right <= 1D) {
+ // Row count estimates of 0 will be rounded up to 1.
+ // So, use maxRowCount where the product is very small.
+ if (leftRowCount <= 1.0 || rightRowCount <= 1.0) {
Double max = mq.getMaxRowCount(rel);
- if (max != null && max <= 1D) {
+ if (max != null && max <= 1.0) {
return max;
}
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ Int2ObjectMap<KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq, rel.getLeft(), joinInfo.leftKeys);
+ Int2ObjectMap<KeyColumnOrigin> columnsFromRight = resolveOrigins(mq, rel.getRight(), joinInfo.rightKeys);
+
+ Map<TablesPair, JoinContext> joinContexts = 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;
+ }
+
+ joinContexts.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.keyColumns().size();
+ int rightPkSize = rightTable.keyColumns().size();
+
+ return new JoinContext(leftPkSize, rightPkSize);
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinContexts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinContexts.values().iterator();
+ JoinContext context = it.next();
+ while (it.hasNext()) {
+ JoinContext nextContext = it.next();
+ if (nextContext.joinType().strength > context.joinType().strength) {
+ context = nextContext;
+ }
+
+ if (context.joinType().strength == JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (context.joinType() == JoiningRelationType.UNKNOWN) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ double postFiltrationAdjustment = joinContexts.size() == 1 && joinInfo.isEqui() ? 1.0
+ // Extra join keys as well as non-equi conditions serves azs post-filtration,
Review Comment:
fixed, thanks
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/metadata/IgniteMdRowCount.java:
##########
@@ -100,68 +106,334 @@ public double getRowCount(IgniteLimit rel, RelMetadataQuery mq) {
}
/**
- * JoinRowCount.
- * TODO Documentation https://issues.apache.org/jira/browse/IGNITE-15859
+ * Estimates the number of rows produced by a join operation.
+ *
+ * <p>This method calculates an estimated row count for a join by analyzing the join type,
+ * join keys, and the cardinality of the left and right inputs. It provides specialized
+ * handling for primary key and foreign key relationships. When certain metadata is unavailable
+ * or when specific conditions are not met, it falls back to Calcite's default implementation
+ * for estimating the row count.
+ *
+ * <p>Implementation details:</p>
+ * <ul>
+ * <li>If the join type is not {@link JoinRelType#INNER}, Calcite's default implementation is used.</li>
+ * <li>If the join is non-equi join, Calcite's default implementation is used.</li>
+ * <li>The row counts of the left and right inputs are retrieved using
+ * {@link RelMetadataQuery#getRowCount}. If either value is unavailable, the result is {@code null}.</li>
+ * <li>If the row counts are very small (≤ 1.0), the method uses the maximum row count as a fallback.</li>
+ * <li>Join key origins are resolved for the left and right inputs, and relationships between tables
+ * (e.g., primary key or foreign key associations) are identified and grouped into join contexts.</li>
+ * <li>If no valid join context is found, the method falls back to Calcite's implementation.</li>
+ * <li>The base row count is determined by the type of join relationship:
+ * <ul>
+ * <li>For primary key-to-primary key joins, the row count is based on the smaller table,
+ * adjusted by a percentage of the larger table's rows.</li>
+ * <li>For foreign key joins, the base table is determined based on which table is
+ * joined using non-primary key columns.</li>
+ * </ul>
+ * </li>
+ * <li>An additional adjustment factor is applied for post-filtration conditions, such as extra join keys
+ * or non-equi conditions.</li>
+ * <li>If metadata for the percentage of original rows is unavailable, the adjustment defaults to 1.0.</li>
+ * </ul>
+ *
+ * <p>If none of the above criteria are satisfied, the method defaults to
+ * {@link RelMdUtil#getJoinRowCount} for the estimation.</p>
+ *
+ * @param mq The {@link RelMetadataQuery} used to retrieve metadata about relational expressions.
+ * @param rel The {@link Join} relational expression representing the join operation.
+ * @return The estimated number of rows resulting from the join, or {@code null} if the estimation cannot be determined.
+ *
+ * @see RelMetadataQuery#getRowCount
+ * @see RelMdUtil#getJoinRowCount
*/
- @Nullable
- public static Double joinRowCount(RelMetadataQuery mq, Join rel) {
- if (!rel.getJoinType().projectsRight()) {
- // Create a RexNode representing the selectivity of the
- // semijoin filter and pass it to getSelectivity
- RexNode semiJoinSelectivity =
- RelMdUtil.makeSemiJoinSelectivityRexNode(mq, rel);
+ public static @Nullable Double joinRowCount(RelMetadataQuery mq, Join rel) {
+ if (rel.getJoinType() != JoinRelType.INNER) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
- return multiply(mq.getSelectivity(rel.getLeft(), semiJoinSelectivity),
- 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());
+ Double leftRowCount = mq.getRowCount(rel.getLeft());
+ Double rightRowCount = mq.getRowCount(rel.getRight());
- if (left == null || right == null) {
+ if (leftRowCount == null || rightRowCount == null) {
return null;
}
- if (left <= 1D || right <= 1D) {
+ // Row count estimates of 0 will be rounded up to 1.
+ // So, use maxRowCount where the product is very small.
+ if (leftRowCount <= 1.0 || rightRowCount <= 1.0) {
Double max = mq.getMaxRowCount(rel);
- if (max != null && max <= 1D) {
+ if (max != null && max <= 1.0) {
return max;
}
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ Int2ObjectMap<KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq, rel.getLeft(), joinInfo.leftKeys);
+ Int2ObjectMap<KeyColumnOrigin> columnsFromRight = resolveOrigins(mq, rel.getRight(), joinInfo.rightKeys);
+
+ Map<TablesPair, JoinContext> joinContexts = 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;
+ }
+
+ joinContexts.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.keyColumns().size();
+ int rightPkSize = rightTable.keyColumns().size();
+
+ return new JoinContext(leftPkSize, rightPkSize);
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinContexts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinContexts.values().iterator();
+ JoinContext context = it.next();
+ while (it.hasNext()) {
+ JoinContext nextContext = it.next();
+ if (nextContext.joinType().strength > context.joinType().strength) {
+ context = nextContext;
+ }
+
+ if (context.joinType().strength == JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (context.joinType() == JoiningRelationType.UNKNOWN) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ double postFiltrationAdjustment = joinContexts.size() == 1 && joinInfo.isEqui() ? 1.0
+ // Extra join keys as well as non-equi conditions serves azs post-filtration,
+ // therefore we need to adjust final result with a little factor.
+ : 0.7;
+
+ double baseRowCount;
+ Double percentageAdjustment;
+ if (context.joinType() == JoiningRelationType.PK_ON_PK) {
+ // 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 (leftRowCount > rightRowCount) {
+ baseRowCount = rightRowCount;
+ percentageAdjustment = mq.getPercentageOriginalRows(rel.getLeft());
+ } else {
+ baseRowCount = leftRowCount;
+ percentageAdjustment = mq.getPercentageOriginalRows(rel.getRight());
+ }
+ } else {
+ // For foreign key joins the base table is the one which is joined by non-primary key columns.
+ if (context.joinType() == JoiningRelationType.FK_ON_PK) {
+ baseRowCount = leftRowCount;
+ percentageAdjustment = mq.getPercentageOriginalRows(rel.getRight());
+ } else {
+ assert context.joinType() == JoiningRelationType.PK_ON_FK : context.joinType();
+ baseRowCount = rightRowCount;
+ percentageAdjustment = mq.getPercentageOriginalRows(rel.getLeft());
+ }
+ }
+
+ if (percentageAdjustment == null) {
+ percentageAdjustment = 1.0; // No info, let's be conservative
+ }
+
+ return baseRowCount * percentageAdjustment * postFiltrationAdjustment;
+ }
+
+ private static Int2ObjectMap<KeyColumnOrigin> resolveOrigins(RelMetadataQuery mq, RelNode joinShoulder, ImmutableIntList keys) {
+ Int2ObjectMap<KeyColumnOrigin> origins = new Int2ObjectOpenHashMap<>();
+ 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) {
+ continue;
+ }
+
+ int positionInKey = table.keyColumns().indexOf(origin.getOriginColumnOrdinal());
+ origins.put(i, new KeyColumnOrigin(origin, positionInKey));
+ }
+
+ return origins;
+ }
+
+ private static class KeyColumnOrigin {
+ private final RelColumnOrigin origin;
+ private final int positionInKey;
+
+ KeyColumnOrigin(RelColumnOrigin origin, int positionInKey) {
+ this.origin = origin;
+ this.positionInKey = positionInKey;
+ }
+ }
+
+ private static class TablesPair {
+ private final RelOptTable left;
+ private final RelOptTable right;
+
+ TablesPair(RelOptTable left, RelOptTable right) {
+ this.left = left;
+ this.right = right;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o == null || getClass() != o.getClass()) {
+ return false;
+ }
+ TablesPair that = (TablesPair) o;
+ // Reference equality on purpose.
+ return left == that.left && right == that.right;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(left, 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;
+
+ JoinContext(int leftPkSize, int rightPkSize) {
+ this.leftKeys = new BitSet();
+ this.rightKeys = new BitSet();
+ this.commonKeys = leftPkSize == rightPkSize ? new BitSet() : null;
- ImmutableIntList leftKeys = joinInfo.leftKeys;
- ImmutableIntList rightKeys = joinInfo.rightKeys;
+ leftKeys.set(0, leftPkSize);
+ rightKeys.set(0, rightPkSize);
- double selectivity = mq.getSelectivity(rel, rel.getCondition());
+ if (commonKeys != null) {
+ assert leftPkSize == rightPkSize;
- if (nullOrEmpty(leftKeys) || nullOrEmpty(rightKeys)) {
- return left * right * selectivity;
+ commonKeys.set(0, leftPkSize);
+ }
}
- double leftDistinct = Util.first(
- mq.getDistinctRowCount(rel.getLeft(), ImmutableBitSet.of(leftKeys), null), left);
- double rightDistinct = Util.first(
- mq.getDistinctRowCount(rel.getRight(), ImmutableBitSet.of(rightKeys), null), right);
+ void countKeys(KeyColumnOrigin left, KeyColumnOrigin right) {
+ if (left.positionInKey >= 0) {
+ leftKeys.clear(left.positionInKey);
+ }
- double leftCardinality = leftDistinct / left;
- double rightCardinality = rightDistinct / right;
+ if (right.positionInKey >= 0) {
+ rightKeys.clear(right.positionInKey);
+ }
- double rowsCount = (Math.min(left, right) / (leftCardinality * rightCardinality)) * selectivity;
+ if (commonKeys != null && left.positionInKey == right.positionInKey && left.positionInKey >= 0) {
+ commonKeys.clear(left.positionInKey);
+ }
+ }
- JoinRelType type = rel.getJoinType();
+ JoiningRelationType joinType() {
+ if (commonKeys != null && commonKeys.isEmpty()) {
+ return JoiningRelationType.PK_ON_PK;
+ }
+
+ if (rightKeys.isEmpty()) {
+ return JoiningRelationType.FK_ON_PK;
+ }
+
+ if (leftKeys.isEmpty()) {
+ return JoiningRelationType.PK_ON_FK;
+ }
- if (type == JoinRelType.LEFT) {
- rowsCount += left;
- } else if (type == JoinRelType.RIGHT) {
- rowsCount += right;
- } else if (type == JoinRelType.FULL) {
- rowsCount += left + right;
+ return JoiningRelationType.UNKNOWN;
}
+ }
+
+ /** Enumeration of join types by their semantic. */
+ private enum JoiningRelationType {
+ /**
+ * Join by non-primary key columns.
+ *
+ * <p>Semantic is unknown.
+ */
+ UNKNOWN(0),
+ /**
+ * Join by primary keys on non-primary keys.
+ *
+ * <p>Currently we don't support Foreign Keys, thus will assume such types of joins
Review Comment:
fixed
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-23968 Sql. Improve row count estimation for joins [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #4992:
URL: https://github.com/apache/ignite-3/pull/4992#discussion_r1905363421
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/metadata/IgniteMdRowCount.java:
##########
@@ -100,68 +106,334 @@ public double getRowCount(IgniteLimit rel, RelMetadataQuery mq) {
}
/**
- * JoinRowCount.
- * TODO Documentation https://issues.apache.org/jira/browse/IGNITE-15859
+ * Estimates the number of rows produced by a join operation.
Review Comment:
like to `JoiningRelationType` has been added
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-23968 Sql. Improve row count estimation for joins [ignite-3]
Posted by "lowka (via GitHub)" <gi...@apache.org>.
lowka commented on code in PR #4992:
URL: https://github.com/apache/ignite-3/pull/4992#discussion_r1903669268
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/metadata/IgniteMdRowCount.java:
##########
@@ -100,68 +106,334 @@ public double getRowCount(IgniteLimit rel, RelMetadataQuery mq) {
}
/**
- * JoinRowCount.
- * TODO Documentation https://issues.apache.org/jira/browse/IGNITE-15859
+ * Estimates the number of rows produced by a join operation.
+ *
+ * <p>This method calculates an estimated row count for a join by analyzing the join type,
+ * join keys, and the cardinality of the left and right inputs. It provides specialized
+ * handling for primary key and foreign key relationships. When certain metadata is unavailable
+ * or when specific conditions are not met, it falls back to Calcite's default implementation
+ * for estimating the row count.
+ *
+ * <p>Implementation details:</p>
+ * <ul>
+ * <li>If the join type is not {@link JoinRelType#INNER}, Calcite's default implementation is used.</li>
+ * <li>If the join is non-equi join, Calcite's default implementation is used.</li>
+ * <li>The row counts of the left and right inputs are retrieved using
+ * {@link RelMetadataQuery#getRowCount}. If either value is unavailable, the result is {@code null}.</li>
+ * <li>If the row counts are very small (≤ 1.0), the method uses the maximum row count as a fallback.</li>
+ * <li>Join key origins are resolved for the left and right inputs, and relationships between tables
+ * (e.g., primary key or foreign key associations) are identified and grouped into join contexts.</li>
+ * <li>If no valid join context is found, the method falls back to Calcite's implementation.</li>
+ * <li>The base row count is determined by the type of join relationship:
+ * <ul>
+ * <li>For primary key-to-primary key joins, the row count is based on the smaller table,
+ * adjusted by a percentage of the larger table's rows.</li>
+ * <li>For foreign key joins, the base table is determined based on which table is
+ * joined using non-primary key columns.</li>
+ * </ul>
+ * </li>
+ * <li>An additional adjustment factor is applied for post-filtration conditions, such as extra join keys
+ * or non-equi conditions.</li>
+ * <li>If metadata for the percentage of original rows is unavailable, the adjustment defaults to 1.0.</li>
+ * </ul>
+ *
+ * <p>If none of the above criteria are satisfied, the method defaults to
+ * {@link RelMdUtil#getJoinRowCount} for the estimation.</p>
+ *
+ * @param mq The {@link RelMetadataQuery} used to retrieve metadata about relational expressions.
+ * @param rel The {@link Join} relational expression representing the join operation.
+ * @return The estimated number of rows resulting from the join, or {@code null} if the estimation cannot be determined.
+ *
+ * @see RelMetadataQuery#getRowCount
+ * @see RelMdUtil#getJoinRowCount
*/
- @Nullable
- public static Double joinRowCount(RelMetadataQuery mq, Join rel) {
- if (!rel.getJoinType().projectsRight()) {
- // Create a RexNode representing the selectivity of the
- // semijoin filter and pass it to getSelectivity
- RexNode semiJoinSelectivity =
- RelMdUtil.makeSemiJoinSelectivityRexNode(mq, rel);
+ public static @Nullable Double joinRowCount(RelMetadataQuery mq, Join rel) {
+ if (rel.getJoinType() != JoinRelType.INNER) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
- return multiply(mq.getSelectivity(rel.getLeft(), semiJoinSelectivity),
- 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());
+ Double leftRowCount = mq.getRowCount(rel.getLeft());
+ Double rightRowCount = mq.getRowCount(rel.getRight());
- if (left == null || right == null) {
+ if (leftRowCount == null || rightRowCount == null) {
return null;
}
- if (left <= 1D || right <= 1D) {
+ // Row count estimates of 0 will be rounded up to 1.
+ // So, use maxRowCount where the product is very small.
+ if (leftRowCount <= 1.0 || rightRowCount <= 1.0) {
Double max = mq.getMaxRowCount(rel);
- if (max != null && max <= 1D) {
+ if (max != null && max <= 1.0) {
return max;
}
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ Int2ObjectMap<KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq, rel.getLeft(), joinInfo.leftKeys);
+ Int2ObjectMap<KeyColumnOrigin> columnsFromRight = resolveOrigins(mq, rel.getRight(), joinInfo.rightKeys);
+
+ Map<TablesPair, JoinContext> joinContexts = 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;
+ }
+
+ joinContexts.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.keyColumns().size();
+ int rightPkSize = rightTable.keyColumns().size();
+
+ return new JoinContext(leftPkSize, rightPkSize);
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinContexts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinContexts.values().iterator();
+ JoinContext context = it.next();
+ while (it.hasNext()) {
+ JoinContext nextContext = it.next();
+ if (nextContext.joinType().strength > context.joinType().strength) {
+ context = nextContext;
+ }
+
+ if (context.joinType().strength == JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (context.joinType() == JoiningRelationType.UNKNOWN) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ double postFiltrationAdjustment = joinContexts.size() == 1 && joinInfo.isEqui() ? 1.0
+ // Extra join keys as well as non-equi conditions serves azs post-filtration,
Review Comment:
> asz
A typo
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/metadata/IgniteMdRowCount.java:
##########
@@ -100,68 +106,334 @@ public double getRowCount(IgniteLimit rel, RelMetadataQuery mq) {
}
/**
- * JoinRowCount.
- * TODO Documentation https://issues.apache.org/jira/browse/IGNITE-15859
+ * Estimates the number of rows produced by a join operation.
+ *
+ * <p>This method calculates an estimated row count for a join by analyzing the join type,
+ * join keys, and the cardinality of the left and right inputs. It provides specialized
+ * handling for primary key and foreign key relationships. When certain metadata is unavailable
+ * or when specific conditions are not met, it falls back to Calcite's default implementation
+ * for estimating the row count.
+ *
+ * <p>Implementation details:</p>
+ * <ul>
+ * <li>If the join type is not {@link JoinRelType#INNER}, Calcite's default implementation is used.</li>
+ * <li>If the join is non-equi join, Calcite's default implementation is used.</li>
+ * <li>The row counts of the left and right inputs are retrieved using
+ * {@link RelMetadataQuery#getRowCount}. If either value is unavailable, the result is {@code null}.</li>
+ * <li>If the row counts are very small (≤ 1.0), the method uses the maximum row count as a fallback.</li>
+ * <li>Join key origins are resolved for the left and right inputs, and relationships between tables
+ * (e.g., primary key or foreign key associations) are identified and grouped into join contexts.</li>
+ * <li>If no valid join context is found, the method falls back to Calcite's implementation.</li>
+ * <li>The base row count is determined by the type of join relationship:
+ * <ul>
+ * <li>For primary key-to-primary key joins, the row count is based on the smaller table,
+ * adjusted by a percentage of the larger table's rows.</li>
+ * <li>For foreign key joins, the base table is determined based on which table is
+ * joined using non-primary key columns.</li>
+ * </ul>
+ * </li>
+ * <li>An additional adjustment factor is applied for post-filtration conditions, such as extra join keys
+ * or non-equi conditions.</li>
+ * <li>If metadata for the percentage of original rows is unavailable, the adjustment defaults to 1.0.</li>
+ * </ul>
+ *
+ * <p>If none of the above criteria are satisfied, the method defaults to
+ * {@link RelMdUtil#getJoinRowCount} for the estimation.</p>
+ *
+ * @param mq The {@link RelMetadataQuery} used to retrieve metadata about relational expressions.
+ * @param rel The {@link Join} relational expression representing the join operation.
+ * @return The estimated number of rows resulting from the join, or {@code null} if the estimation cannot be determined.
+ *
+ * @see RelMetadataQuery#getRowCount
+ * @see RelMdUtil#getJoinRowCount
*/
- @Nullable
- public static Double joinRowCount(RelMetadataQuery mq, Join rel) {
- if (!rel.getJoinType().projectsRight()) {
- // Create a RexNode representing the selectivity of the
- // semijoin filter and pass it to getSelectivity
- RexNode semiJoinSelectivity =
- RelMdUtil.makeSemiJoinSelectivityRexNode(mq, rel);
+ public static @Nullable Double joinRowCount(RelMetadataQuery mq, Join rel) {
+ if (rel.getJoinType() != JoinRelType.INNER) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
- return multiply(mq.getSelectivity(rel.getLeft(), semiJoinSelectivity),
- 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());
+ Double leftRowCount = mq.getRowCount(rel.getLeft());
+ Double rightRowCount = mq.getRowCount(rel.getRight());
- if (left == null || right == null) {
+ if (leftRowCount == null || rightRowCount == null) {
return null;
}
- if (left <= 1D || right <= 1D) {
+ // Row count estimates of 0 will be rounded up to 1.
+ // So, use maxRowCount where the product is very small.
+ if (leftRowCount <= 1.0 || rightRowCount <= 1.0) {
Double max = mq.getMaxRowCount(rel);
- if (max != null && max <= 1D) {
+ if (max != null && max <= 1.0) {
return max;
}
}
- JoinInfo joinInfo = rel.analyzeCondition();
+ Int2ObjectMap<KeyColumnOrigin> columnsFromLeft = resolveOrigins(mq, rel.getLeft(), joinInfo.leftKeys);
+ Int2ObjectMap<KeyColumnOrigin> columnsFromRight = resolveOrigins(mq, rel.getRight(), joinInfo.rightKeys);
+
+ Map<TablesPair, JoinContext> joinContexts = 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;
+ }
+
+ joinContexts.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.keyColumns().size();
+ int rightPkSize = rightTable.keyColumns().size();
+
+ return new JoinContext(leftPkSize, rightPkSize);
+ }
+ ).countKeys(leftKey, rightKey);
+ }
+
+ if (joinContexts.isEmpty()) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ Iterator<JoinContext> it = joinContexts.values().iterator();
+ JoinContext context = it.next();
+ while (it.hasNext()) {
+ JoinContext nextContext = it.next();
+ if (nextContext.joinType().strength > context.joinType().strength) {
+ context = nextContext;
+ }
+
+ if (context.joinType().strength == JoiningRelationType.PK_ON_PK.strength) {
+ break;
+ }
+ }
+
+ if (context.joinType() == JoiningRelationType.UNKNOWN) {
+ // Fall-back to calcite's implementation.
+ return RelMdUtil.getJoinRowCount(mq, rel, rel.getCondition());
+ }
+
+ double postFiltrationAdjustment = joinContexts.size() == 1 && joinInfo.isEqui() ? 1.0
+ // Extra join keys as well as non-equi conditions serves azs post-filtration,
+ // therefore we need to adjust final result with a little factor.
+ : 0.7;
+
+ double baseRowCount;
+ Double percentageAdjustment;
+ if (context.joinType() == JoiningRelationType.PK_ON_PK) {
+ // 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 (leftRowCount > rightRowCount) {
+ baseRowCount = rightRowCount;
+ percentageAdjustment = mq.getPercentageOriginalRows(rel.getLeft());
+ } else {
+ baseRowCount = leftRowCount;
+ percentageAdjustment = mq.getPercentageOriginalRows(rel.getRight());
+ }
+ } else {
+ // For foreign key joins the base table is the one which is joined by non-primary key columns.
+ if (context.joinType() == JoiningRelationType.FK_ON_PK) {
+ baseRowCount = leftRowCount;
+ percentageAdjustment = mq.getPercentageOriginalRows(rel.getRight());
+ } else {
+ assert context.joinType() == JoiningRelationType.PK_ON_FK : context.joinType();
+ baseRowCount = rightRowCount;
+ percentageAdjustment = mq.getPercentageOriginalRows(rel.getLeft());
+ }
+ }
+
+ if (percentageAdjustment == null) {
+ percentageAdjustment = 1.0; // No info, let's be conservative
+ }
+
+ return baseRowCount * percentageAdjustment * postFiltrationAdjustment;
+ }
+
+ private static Int2ObjectMap<KeyColumnOrigin> resolveOrigins(RelMetadataQuery mq, RelNode joinShoulder, ImmutableIntList keys) {
+ Int2ObjectMap<KeyColumnOrigin> origins = new Int2ObjectOpenHashMap<>();
+ 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) {
+ continue;
+ }
+
+ int positionInKey = table.keyColumns().indexOf(origin.getOriginColumnOrdinal());
+ origins.put(i, new KeyColumnOrigin(origin, positionInKey));
+ }
+
+ return origins;
+ }
+
+ private static class KeyColumnOrigin {
+ private final RelColumnOrigin origin;
+ private final int positionInKey;
+
+ KeyColumnOrigin(RelColumnOrigin origin, int positionInKey) {
+ this.origin = origin;
+ this.positionInKey = positionInKey;
+ }
+ }
+
+ private static class TablesPair {
+ private final RelOptTable left;
+ private final RelOptTable right;
+
+ TablesPair(RelOptTable left, RelOptTable right) {
+ this.left = left;
+ this.right = right;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o == null || getClass() != o.getClass()) {
+ return false;
+ }
+ TablesPair that = (TablesPair) o;
+ // Reference equality on purpose.
+ return left == that.left && right == that.right;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(left, 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;
+
+ JoinContext(int leftPkSize, int rightPkSize) {
+ this.leftKeys = new BitSet();
+ this.rightKeys = new BitSet();
+ this.commonKeys = leftPkSize == rightPkSize ? new BitSet() : null;
- ImmutableIntList leftKeys = joinInfo.leftKeys;
- ImmutableIntList rightKeys = joinInfo.rightKeys;
+ leftKeys.set(0, leftPkSize);
+ rightKeys.set(0, rightPkSize);
- double selectivity = mq.getSelectivity(rel, rel.getCondition());
+ if (commonKeys != null) {
+ assert leftPkSize == rightPkSize;
- if (nullOrEmpty(leftKeys) || nullOrEmpty(rightKeys)) {
- return left * right * selectivity;
+ commonKeys.set(0, leftPkSize);
+ }
}
- double leftDistinct = Util.first(
- mq.getDistinctRowCount(rel.getLeft(), ImmutableBitSet.of(leftKeys), null), left);
- double rightDistinct = Util.first(
- mq.getDistinctRowCount(rel.getRight(), ImmutableBitSet.of(rightKeys), null), right);
+ void countKeys(KeyColumnOrigin left, KeyColumnOrigin right) {
+ if (left.positionInKey >= 0) {
+ leftKeys.clear(left.positionInKey);
+ }
- double leftCardinality = leftDistinct / left;
- double rightCardinality = rightDistinct / right;
+ if (right.positionInKey >= 0) {
+ rightKeys.clear(right.positionInKey);
+ }
- double rowsCount = (Math.min(left, right) / (leftCardinality * rightCardinality)) * selectivity;
+ if (commonKeys != null && left.positionInKey == right.positionInKey && left.positionInKey >= 0) {
+ commonKeys.clear(left.positionInKey);
+ }
+ }
- JoinRelType type = rel.getJoinType();
+ JoiningRelationType joinType() {
+ if (commonKeys != null && commonKeys.isEmpty()) {
+ return JoiningRelationType.PK_ON_PK;
+ }
+
+ if (rightKeys.isEmpty()) {
+ return JoiningRelationType.FK_ON_PK;
+ }
+
+ if (leftKeys.isEmpty()) {
+ return JoiningRelationType.PK_ON_FK;
+ }
- if (type == JoinRelType.LEFT) {
- rowsCount += left;
- } else if (type == JoinRelType.RIGHT) {
- rowsCount += right;
- } else if (type == JoinRelType.FULL) {
- rowsCount += left + right;
+ return JoiningRelationType.UNKNOWN;
}
+ }
+
+ /** Enumeration of join types by their semantic. */
+ private enum JoiningRelationType {
+ /**
+ * Join by non-primary key columns.
+ *
+ * <p>Semantic is unknown.
+ */
+ UNKNOWN(0),
+ /**
+ * Join by primary keys on non-primary keys.
+ *
+ * <p>Currently we don't support Foreign Keys, thus will assume such types of joins
Review Comment:
> thus will assume such types of joins ...
A subject in missing here, you probably meant:
> thus **we** will assume such types of joins ...
--
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: notifications-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org