zstan commented on code in PR #13389:
URL: https://github.com/apache/ignite/pull/13389#discussion_r4423348323
##########
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:
done
##########
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:
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]
