mihaibudiu commented on code in PR #5396:
URL: https://github.com/apache/calcite/pull/5396#discussion_r4498587670
##########
core/src/main/java/org/apache/calcite/rel/metadata/RelMdExpressionLineage.java:
##########
@@ -506,6 +521,24 @@ protected RelMdExpressionLineage() {}
return ImmutableSet.of(expr);
}
+ if (maxExpansions >= 0) {
+ // Every referenced column adds a dimension to the Cartesian product.
+ // Count before copying RexNodes, even if equal candidates would later
Review Comment:
estimate the count before...
the comment about division should be on the division operator.
it should say that instead of computing the product of counts and comparing
with remaining you rather divide remaining to avoid overflow in the product
##########
core/src/test/java/org/apache/calcite/rel/metadata/ExpressionLineageProgram.java:
##########
@@ -0,0 +1,83 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rel.type.RelDataTypeFactory;
+import org.apache.calcite.schema.SchemaPlus;
+import org.apache.calcite.schema.impl.AbstractTable;
+import org.apache.calcite.sql.SqlNode;
+import org.apache.calcite.sql.type.SqlTypeName;
+import org.apache.calcite.tools.Frameworks;
+import org.apache.calcite.tools.Planner;
+
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+/** Generates storage-free SQL programs whose expression lineage has
+ * {@code branches ^ columns} candidate substitutions. Shared by regression
+ * tests and standalone measurements. */
+final class ExpressionLineageProgram {
+ private ExpressionLineageProgram() {
+ }
+
+ /** Generates a SQL program with passthrough columns and a final computed
+ * column, either an arithmetic expression or a window expression. */
+ static String sql(int branches, int columns, boolean window) {
Review Comment:
can you show in a comment an example program generated for a small value of
branches?
##########
core/src/test/java/org/apache/calcite/rel/metadata/RelMdExpressionLineageTest.java:
##########
@@ -0,0 +1,243 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.jdbc.JavaTypeFactoryImpl;
+import org.apache.calcite.plan.RelOptPredicateList;
+import org.apache.calcite.plan.hep.HepPlanner;
+import org.apache.calcite.plan.hep.HepProgramBuilder;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Calc;
+import org.apache.calcite.rel.logical.LogicalFilter;
+import org.apache.calcite.rel.rules.CoreRules;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.sql.fun.SqlStdOperatorTable;
+import org.apache.calcite.sql.type.SqlTypeName;
+
+import com.google.common.collect.ImmutableSet;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+import java.math.BigDecimal;
+import java.util.AbstractSet;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.Random;
+import java.util.Set;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+/** Tests for bounded expression-lineage expansion. */
+class RelMdExpressionLineageTest {
+ private final RexBuilder rexBuilder = new RexBuilder(new
JavaTypeFactoryImpl());
+
+ @ParameterizedTest
+ @CsvSource({"1, 1", "2, 2", "2, 4", "4, 4", "8, 4", "16, 4", "90, 4", "2,
16"})
+ void testGeneratedPrograms(int branches, int columns) throws Exception {
+ for (boolean window : new boolean[] {false, true}) {
+ for (boolean calc : new boolean[] {false, true}) {
+ RelNode rel = ExpressionLineageProgram.rel(branches, columns, window);
+ if (calc) {
+ HepPlanner planner = new HepPlanner(new HepProgramBuilder()
+ .addRuleInstance(CoreRules.PROJECT_TO_CALC).build());
+ planner.setRoot(rel);
+ rel = planner.findBestExp();
+ assertTrue(rel instanceof Calc, "Expected the Calc metadata path");
+ }
+ RelMetadataQuery mq = rel.getCluster().getMetadataQuery();
+ RexNode result = RexInputRef.of(columns,
rel.getRowType().getFieldList());
+ Set<RexNode> lineage = mq.getExpressionLineage(rel, result);
+ if (Math.pow(branches, columns) > 10_000) {
Review Comment:
can you use the value of the property instead of 10K?
##########
core/src/test/java/org/apache/calcite/rel/metadata/RelMdExpressionLineageTest.java:
##########
@@ -0,0 +1,243 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.jdbc.JavaTypeFactoryImpl;
+import org.apache.calcite.plan.RelOptPredicateList;
+import org.apache.calcite.plan.hep.HepPlanner;
+import org.apache.calcite.plan.hep.HepProgramBuilder;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Calc;
+import org.apache.calcite.rel.logical.LogicalFilter;
+import org.apache.calcite.rel.rules.CoreRules;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.sql.fun.SqlStdOperatorTable;
+import org.apache.calcite.sql.type.SqlTypeName;
+
+import com.google.common.collect.ImmutableSet;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+import java.math.BigDecimal;
+import java.util.AbstractSet;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.Random;
+import java.util.Set;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+/** Tests for bounded expression-lineage expansion. */
+class RelMdExpressionLineageTest {
+ private final RexBuilder rexBuilder = new RexBuilder(new
JavaTypeFactoryImpl());
+
+ @ParameterizedTest
+ @CsvSource({"1, 1", "2, 2", "2, 4", "4, 4", "8, 4", "16, 4", "90, 4", "2,
16"})
+ void testGeneratedPrograms(int branches, int columns) throws Exception {
+ for (boolean window : new boolean[] {false, true}) {
+ for (boolean calc : new boolean[] {false, true}) {
+ RelNode rel = ExpressionLineageProgram.rel(branches, columns, window);
+ if (calc) {
+ HepPlanner planner = new HepPlanner(new HepProgramBuilder()
+ .addRuleInstance(CoreRules.PROJECT_TO_CALC).build());
+ planner.setRoot(rel);
+ rel = planner.findBestExp();
+ assertTrue(rel instanceof Calc, "Expected the Calc metadata path");
+ }
+ RelMetadataQuery mq = rel.getCluster().getMetadataQuery();
+ RexNode result = RexInputRef.of(columns,
rel.getRowType().getFieldList());
+ Set<RexNode> lineage = mq.getExpressionLineage(rel, result);
+ if (Math.pow(branches, columns) > 10_000) {
+ // No truncated subset may escape as complete metadata.
+ assertNull(lineage);
+ } else {
+ assertNotNull(lineage);
+ assertEquals((int) Math.pow(branches, columns), lineage.size());
+ }
+ // An expensive result must not poison other columns or later queries.
+ Set<RexNode> passthrough = mq.getExpressionLineage(rel,
+ RexInputRef.of(0, rel.getRowType().getFieldList()));
+ assertNotNull(passthrough);
+ assertEquals(branches, passthrough.size());
+ assertEquals(lineage, mq.getExpressionLineage(rel, result));
+ rel.getCluster().invalidateMetadataQuery();
+ assertEquals(lineage, rel.getCluster().getMetadataQuery()
+ .getExpressionLineage(rel, result));
+ }
+ }
+ }
+
+ @Test void testBudgetBoundaryAndMappingUnchanged() {
+ RexInputRef a = ref(0);
+ RexInputRef b = ref(1);
+ RexNode expression = rexBuilder.makeCall(SqlStdOperatorTable.MINUS, a, b);
+ Map<RexInputRef, Set<RexNode>> mapping = mapping(a, b);
+ Map<RexInputRef, Set<RexNode>> original = new LinkedHashMap<>(mapping);
+ Set<RexNode> unlimited = expand(expression, mapping, -1);
+ assertNotNull(unlimited);
+ assertEquals(4, unlimited.size());
+ assertEquals(unlimited, expand(expression, mapping, 4));
+ assertNull(expand(expression, mapping, 3));
+ assertEquals(original, mapping);
+ assertEquals(unlimited, expand(expression, mapping, 5));
+ }
+
+ @Test void testGeneratedProgramExceedsBudget() throws Exception {
+ RelNode rel = ExpressionLineageProgram.rel(16, 4, true);
+ Set<RexNode> lineage =
rel.getCluster().getMetadataQuery().getExpressionLineage(rel,
+ RexInputRef.of(4, rel.getRowType().getFieldList()));
+ assertTrue(lineage == null, () -> "Expected unknown lineage, not "
+ + (lineage == null ? "null" : lineage.size()) + " candidates");
+ }
+
+ @Test void testBudgetCountsAttemptsBeforeDeduplication() {
+ RexInputRef a = ref(0);
+ RexInputRef b = ref(1);
+ RexNode expression = rexBuilder.makeCall(SqlStdOperatorTable.PLUS, a, b);
+ Map<RexInputRef, Set<RexNode>> mapping = mapping(a, b);
+ // Commutative normalization merges 1 + 10 and 10 + 1, but constructing
+ // both still takes work. Budgeting the result Set size would miss this.
+ Set<RexNode> unlimited = expand(expression, mapping, -1);
+ assertNotNull(unlimited);
+ assertEquals(3, unlimited.size());
+ assertEquals(unlimited, expand(expression, mapping, 4));
+ assertNull(expand(expression, mapping, 3));
+ }
+
+ @Test void testRepeatedAndUnusedReferences() {
+ RexInputRef a = ref(0);
+ RexInputRef b = ref(1);
+ RexNode expression = rexBuilder.makeCall(SqlStdOperatorTable.MINUS, a, a);
+ Map<RexInputRef, Set<RexNode>> mapping = mapping(a, b);
+ // Only a is referenced: repeated occurrences share a substitution, and
+ // unused b must not contribute a dimension to the product.
+ assertEquals(expand(expression, mapping, -1), expand(expression, mapping,
2));
+ assertNull(expand(expression, mapping, 1));
+ }
+
+ @Test void testZeroBudgetAndConstants() {
Review Comment:
this is also a low-value test
##########
core/src/test/java/org/apache/calcite/rel/metadata/RelMdExpressionLineageTest.java:
##########
@@ -0,0 +1,243 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.jdbc.JavaTypeFactoryImpl;
+import org.apache.calcite.plan.RelOptPredicateList;
+import org.apache.calcite.plan.hep.HepPlanner;
+import org.apache.calcite.plan.hep.HepProgramBuilder;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Calc;
+import org.apache.calcite.rel.logical.LogicalFilter;
+import org.apache.calcite.rel.rules.CoreRules;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.sql.fun.SqlStdOperatorTable;
+import org.apache.calcite.sql.type.SqlTypeName;
+
+import com.google.common.collect.ImmutableSet;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+import java.math.BigDecimal;
+import java.util.AbstractSet;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.Random;
+import java.util.Set;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+/** Tests for bounded expression-lineage expansion. */
+class RelMdExpressionLineageTest {
+ private final RexBuilder rexBuilder = new RexBuilder(new
JavaTypeFactoryImpl());
+
+ @ParameterizedTest
+ @CsvSource({"1, 1", "2, 2", "2, 4", "4, 4", "8, 4", "16, 4", "90, 4", "2,
16"})
+ void testGeneratedPrograms(int branches, int columns) throws Exception {
+ for (boolean window : new boolean[] {false, true}) {
+ for (boolean calc : new boolean[] {false, true}) {
+ RelNode rel = ExpressionLineageProgram.rel(branches, columns, window);
+ if (calc) {
+ HepPlanner planner = new HepPlanner(new HepProgramBuilder()
+ .addRuleInstance(CoreRules.PROJECT_TO_CALC).build());
+ planner.setRoot(rel);
+ rel = planner.findBestExp();
+ assertTrue(rel instanceof Calc, "Expected the Calc metadata path");
+ }
+ RelMetadataQuery mq = rel.getCluster().getMetadataQuery();
+ RexNode result = RexInputRef.of(columns,
rel.getRowType().getFieldList());
+ Set<RexNode> lineage = mq.getExpressionLineage(rel, result);
+ if (Math.pow(branches, columns) > 10_000) {
+ // No truncated subset may escape as complete metadata.
+ assertNull(lineage);
+ } else {
+ assertNotNull(lineage);
+ assertEquals((int) Math.pow(branches, columns), lineage.size());
+ }
+ // An expensive result must not poison other columns or later queries.
+ Set<RexNode> passthrough = mq.getExpressionLineage(rel,
+ RexInputRef.of(0, rel.getRowType().getFieldList()));
+ assertNotNull(passthrough);
+ assertEquals(branches, passthrough.size());
+ assertEquals(lineage, mq.getExpressionLineage(rel, result));
+ rel.getCluster().invalidateMetadataQuery();
+ assertEquals(lineage, rel.getCluster().getMetadataQuery()
+ .getExpressionLineage(rel, result));
+ }
+ }
+ }
+
+ @Test void testBudgetBoundaryAndMappingUnchanged() {
Review Comment:
is this test and the next one needed? Doesn't the previous one cover them?
##########
core/src/test/java/org/apache/calcite/rel/metadata/RelMdExpressionLineageTest.java:
##########
@@ -0,0 +1,243 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.jdbc.JavaTypeFactoryImpl;
+import org.apache.calcite.plan.RelOptPredicateList;
+import org.apache.calcite.plan.hep.HepPlanner;
+import org.apache.calcite.plan.hep.HepProgramBuilder;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Calc;
+import org.apache.calcite.rel.logical.LogicalFilter;
+import org.apache.calcite.rel.rules.CoreRules;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.sql.fun.SqlStdOperatorTable;
+import org.apache.calcite.sql.type.SqlTypeName;
+
+import com.google.common.collect.ImmutableSet;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+import java.math.BigDecimal;
+import java.util.AbstractSet;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.Random;
+import java.util.Set;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+/** Tests for bounded expression-lineage expansion. */
+class RelMdExpressionLineageTest {
+ private final RexBuilder rexBuilder = new RexBuilder(new
JavaTypeFactoryImpl());
+
+ @ParameterizedTest
+ @CsvSource({"1, 1", "2, 2", "2, 4", "4, 4", "8, 4", "16, 4", "90, 4", "2,
16"})
+ void testGeneratedPrograms(int branches, int columns) throws Exception {
+ for (boolean window : new boolean[] {false, true}) {
+ for (boolean calc : new boolean[] {false, true}) {
+ RelNode rel = ExpressionLineageProgram.rel(branches, columns, window);
+ if (calc) {
+ HepPlanner planner = new HepPlanner(new HepProgramBuilder()
+ .addRuleInstance(CoreRules.PROJECT_TO_CALC).build());
+ planner.setRoot(rel);
+ rel = planner.findBestExp();
+ assertTrue(rel instanceof Calc, "Expected the Calc metadata path");
+ }
+ RelMetadataQuery mq = rel.getCluster().getMetadataQuery();
+ RexNode result = RexInputRef.of(columns,
rel.getRowType().getFieldList());
+ Set<RexNode> lineage = mq.getExpressionLineage(rel, result);
+ if (Math.pow(branches, columns) > 10_000) {
+ // No truncated subset may escape as complete metadata.
+ assertNull(lineage);
+ } else {
+ assertNotNull(lineage);
+ assertEquals((int) Math.pow(branches, columns), lineage.size());
+ }
+ // An expensive result must not poison other columns or later queries.
+ Set<RexNode> passthrough = mq.getExpressionLineage(rel,
+ RexInputRef.of(0, rel.getRowType().getFieldList()));
+ assertNotNull(passthrough);
+ assertEquals(branches, passthrough.size());
+ assertEquals(lineage, mq.getExpressionLineage(rel, result));
+ rel.getCluster().invalidateMetadataQuery();
+ assertEquals(lineage, rel.getCluster().getMetadataQuery()
+ .getExpressionLineage(rel, result));
+ }
+ }
+ }
+
+ @Test void testBudgetBoundaryAndMappingUnchanged() {
+ RexInputRef a = ref(0);
+ RexInputRef b = ref(1);
+ RexNode expression = rexBuilder.makeCall(SqlStdOperatorTable.MINUS, a, b);
+ Map<RexInputRef, Set<RexNode>> mapping = mapping(a, b);
+ Map<RexInputRef, Set<RexNode>> original = new LinkedHashMap<>(mapping);
+ Set<RexNode> unlimited = expand(expression, mapping, -1);
+ assertNotNull(unlimited);
+ assertEquals(4, unlimited.size());
+ assertEquals(unlimited, expand(expression, mapping, 4));
+ assertNull(expand(expression, mapping, 3));
+ assertEquals(original, mapping);
+ assertEquals(unlimited, expand(expression, mapping, 5));
+ }
+
+ @Test void testGeneratedProgramExceedsBudget() throws Exception {
+ RelNode rel = ExpressionLineageProgram.rel(16, 4, true);
+ Set<RexNode> lineage =
rel.getCluster().getMetadataQuery().getExpressionLineage(rel,
+ RexInputRef.of(4, rel.getRowType().getFieldList()));
+ assertTrue(lineage == null, () -> "Expected unknown lineage, not "
+ + (lineage == null ? "null" : lineage.size()) + " candidates");
+ }
+
+ @Test void testBudgetCountsAttemptsBeforeDeduplication() {
+ RexInputRef a = ref(0);
+ RexInputRef b = ref(1);
+ RexNode expression = rexBuilder.makeCall(SqlStdOperatorTable.PLUS, a, b);
+ Map<RexInputRef, Set<RexNode>> mapping = mapping(a, b);
+ // Commutative normalization merges 1 + 10 and 10 + 1, but constructing
+ // both still takes work. Budgeting the result Set size would miss this.
+ Set<RexNode> unlimited = expand(expression, mapping, -1);
+ assertNotNull(unlimited);
+ assertEquals(3, unlimited.size());
+ assertEquals(unlimited, expand(expression, mapping, 4));
+ assertNull(expand(expression, mapping, 3));
+ }
+
+ @Test void testRepeatedAndUnusedReferences() {
Review Comment:
how is this test related to the current change?
##########
core/src/test/java/org/apache/calcite/rel/metadata/RelMdExpressionLineageTest.java:
##########
@@ -0,0 +1,243 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.jdbc.JavaTypeFactoryImpl;
+import org.apache.calcite.plan.RelOptPredicateList;
+import org.apache.calcite.plan.hep.HepPlanner;
+import org.apache.calcite.plan.hep.HepProgramBuilder;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Calc;
+import org.apache.calcite.rel.logical.LogicalFilter;
+import org.apache.calcite.rel.rules.CoreRules;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.sql.fun.SqlStdOperatorTable;
+import org.apache.calcite.sql.type.SqlTypeName;
+
+import com.google.common.collect.ImmutableSet;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+import java.math.BigDecimal;
+import java.util.AbstractSet;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.Random;
+import java.util.Set;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+/** Tests for bounded expression-lineage expansion. */
+class RelMdExpressionLineageTest {
+ private final RexBuilder rexBuilder = new RexBuilder(new
JavaTypeFactoryImpl());
+
+ @ParameterizedTest
+ @CsvSource({"1, 1", "2, 2", "2, 4", "4, 4", "8, 4", "16, 4", "90, 4", "2,
16"})
+ void testGeneratedPrograms(int branches, int columns) throws Exception {
+ for (boolean window : new boolean[] {false, true}) {
+ for (boolean calc : new boolean[] {false, true}) {
+ RelNode rel = ExpressionLineageProgram.rel(branches, columns, window);
+ if (calc) {
+ HepPlanner planner = new HepPlanner(new HepProgramBuilder()
+ .addRuleInstance(CoreRules.PROJECT_TO_CALC).build());
+ planner.setRoot(rel);
+ rel = planner.findBestExp();
+ assertTrue(rel instanceof Calc, "Expected the Calc metadata path");
+ }
+ RelMetadataQuery mq = rel.getCluster().getMetadataQuery();
+ RexNode result = RexInputRef.of(columns,
rel.getRowType().getFieldList());
+ Set<RexNode> lineage = mq.getExpressionLineage(rel, result);
+ if (Math.pow(branches, columns) > 10_000) {
+ // No truncated subset may escape as complete metadata.
Review Comment:
this comment does not make sense, but why not just say "metadata was not
computed"?
##########
core/src/test/java/org/apache/calcite/rel/metadata/ExpressionLineageProgram.java:
##########
@@ -0,0 +1,83 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rel.type.RelDataTypeFactory;
+import org.apache.calcite.schema.SchemaPlus;
+import org.apache.calcite.schema.impl.AbstractTable;
+import org.apache.calcite.sql.SqlNode;
+import org.apache.calcite.sql.type.SqlTypeName;
+import org.apache.calcite.tools.Frameworks;
+import org.apache.calcite.tools.Planner;
+
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+/** Generates storage-free SQL programs whose expression lineage has
+ * {@code branches ^ columns} candidate substitutions. Shared by regression
+ * tests and standalone measurements. */
+final class ExpressionLineageProgram {
+ private ExpressionLineageProgram() {
+ }
+
+ /** Generates a SQL program with passthrough columns and a final computed
+ * column, either an arithmetic expression or a window expression. */
+ static String sql(int branches, int columns, boolean window) {
+ checkArgument(branches >= 1, "branches must be positive");
+ checkArgument(columns >= 1, "columns must be positive");
+ String fields = IntStream.range(0, columns).mapToObj(i -> "c" + i)
+ .collect(Collectors.joining(", "));
+ String expression;
+ if (window) {
+ String partition = columns == 1 ? "" : "partition by "
+ + IntStream.range(0, columns - 1).mapToObj(i -> "c" + i)
+ .collect(Collectors.joining(", ")) + " ";
+ expression = "row_number() over (" + partition + "order by c" + (columns
- 1) + ")";
+ } else {
+ expression = IntStream.range(0, columns).mapToObj(i -> "c" + i)
+ .collect(Collectors.joining(" + "));
+ }
+ String inputs = IntStream.range(0, branches)
+ .mapToObj(i -> "select " + fields + " from events")
+ .collect(Collectors.joining(" union all "));
+ return "select " + fields + ", " + expression + " as computed_value from
(" + inputs + ") u";
+ }
+
+ /** Parses and validates the generated SQL using only Calcite. */
Review Comment:
reading this javadoc I don't know what this function does.
Either refer to `sql()` above or describe what this function returns: the
representation of a large SQL program which requires exponential cost to
analyze lineage
##########
core/src/test/java/org/apache/calcite/rel/metadata/RelMdExpressionLineageTest.java:
##########
@@ -0,0 +1,243 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.jdbc.JavaTypeFactoryImpl;
+import org.apache.calcite.plan.RelOptPredicateList;
+import org.apache.calcite.plan.hep.HepPlanner;
+import org.apache.calcite.plan.hep.HepProgramBuilder;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Calc;
+import org.apache.calcite.rel.logical.LogicalFilter;
+import org.apache.calcite.rel.rules.CoreRules;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.sql.fun.SqlStdOperatorTable;
+import org.apache.calcite.sql.type.SqlTypeName;
+
+import com.google.common.collect.ImmutableSet;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+import java.math.BigDecimal;
+import java.util.AbstractSet;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.Random;
+import java.util.Set;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+/** Tests for bounded expression-lineage expansion. */
+class RelMdExpressionLineageTest {
+ private final RexBuilder rexBuilder = new RexBuilder(new
JavaTypeFactoryImpl());
+
+ @ParameterizedTest
+ @CsvSource({"1, 1", "2, 2", "2, 4", "4, 4", "8, 4", "16, 4", "90, 4", "2,
16"})
+ void testGeneratedPrograms(int branches, int columns) throws Exception {
+ for (boolean window : new boolean[] {false, true}) {
+ for (boolean calc : new boolean[] {false, true}) {
+ RelNode rel = ExpressionLineageProgram.rel(branches, columns, window);
+ if (calc) {
+ HepPlanner planner = new HepPlanner(new HepProgramBuilder()
+ .addRuleInstance(CoreRules.PROJECT_TO_CALC).build());
+ planner.setRoot(rel);
+ rel = planner.findBestExp();
+ assertTrue(rel instanceof Calc, "Expected the Calc metadata path");
+ }
+ RelMetadataQuery mq = rel.getCluster().getMetadataQuery();
+ RexNode result = RexInputRef.of(columns,
rel.getRowType().getFieldList());
+ Set<RexNode> lineage = mq.getExpressionLineage(rel, result);
+ if (Math.pow(branches, columns) > 10_000) {
+ // No truncated subset may escape as complete metadata.
+ assertNull(lineage);
+ } else {
+ assertNotNull(lineage);
+ assertEquals((int) Math.pow(branches, columns), lineage.size());
+ }
+ // An expensive result must not poison other columns or later queries.
Review Comment:
I don't know how results poison columns or queries.
##########
core/src/test/java/org/apache/calcite/rel/metadata/RelMdExpressionLineageTest.java:
##########
@@ -0,0 +1,243 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.jdbc.JavaTypeFactoryImpl;
+import org.apache.calcite.plan.RelOptPredicateList;
+import org.apache.calcite.plan.hep.HepPlanner;
+import org.apache.calcite.plan.hep.HepProgramBuilder;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Calc;
+import org.apache.calcite.rel.logical.LogicalFilter;
+import org.apache.calcite.rel.rules.CoreRules;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.sql.fun.SqlStdOperatorTable;
+import org.apache.calcite.sql.type.SqlTypeName;
+
+import com.google.common.collect.ImmutableSet;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+import java.math.BigDecimal;
+import java.util.AbstractSet;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.Map;
+import java.util.Random;
+import java.util.Set;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+/** Tests for bounded expression-lineage expansion. */
+class RelMdExpressionLineageTest {
+ private final RexBuilder rexBuilder = new RexBuilder(new
JavaTypeFactoryImpl());
+
+ @ParameterizedTest
+ @CsvSource({"1, 1", "2, 2", "2, 4", "4, 4", "8, 4", "16, 4", "90, 4", "2,
16"})
+ void testGeneratedPrograms(int branches, int columns) throws Exception {
+ for (boolean window : new boolean[] {false, true}) {
+ for (boolean calc : new boolean[] {false, true}) {
+ RelNode rel = ExpressionLineageProgram.rel(branches, columns, window);
+ if (calc) {
+ HepPlanner planner = new HepPlanner(new HepProgramBuilder()
+ .addRuleInstance(CoreRules.PROJECT_TO_CALC).build());
+ planner.setRoot(rel);
+ rel = planner.findBestExp();
+ assertTrue(rel instanceof Calc, "Expected the Calc metadata path");
+ }
+ RelMetadataQuery mq = rel.getCluster().getMetadataQuery();
+ RexNode result = RexInputRef.of(columns,
rel.getRowType().getFieldList());
+ Set<RexNode> lineage = mq.getExpressionLineage(rel, result);
+ if (Math.pow(branches, columns) > 10_000) {
+ // No truncated subset may escape as complete metadata.
+ assertNull(lineage);
+ } else {
+ assertNotNull(lineage);
+ assertEquals((int) Math.pow(branches, columns), lineage.size());
+ }
+ // An expensive result must not poison other columns or later queries.
+ Set<RexNode> passthrough = mq.getExpressionLineage(rel,
+ RexInputRef.of(0, rel.getRowType().getFieldList()));
+ assertNotNull(passthrough);
+ assertEquals(branches, passthrough.size());
+ assertEquals(lineage, mq.getExpressionLineage(rel, result));
+ rel.getCluster().invalidateMetadataQuery();
+ assertEquals(lineage, rel.getCluster().getMetadataQuery()
+ .getExpressionLineage(rel, result));
+ }
+ }
+ }
+
+ @Test void testBudgetBoundaryAndMappingUnchanged() {
+ RexInputRef a = ref(0);
+ RexInputRef b = ref(1);
+ RexNode expression = rexBuilder.makeCall(SqlStdOperatorTable.MINUS, a, b);
+ Map<RexInputRef, Set<RexNode>> mapping = mapping(a, b);
+ Map<RexInputRef, Set<RexNode>> original = new LinkedHashMap<>(mapping);
+ Set<RexNode> unlimited = expand(expression, mapping, -1);
+ assertNotNull(unlimited);
+ assertEquals(4, unlimited.size());
+ assertEquals(unlimited, expand(expression, mapping, 4));
+ assertNull(expand(expression, mapping, 3));
+ assertEquals(original, mapping);
+ assertEquals(unlimited, expand(expression, mapping, 5));
+ }
+
+ @Test void testGeneratedProgramExceedsBudget() throws Exception {
+ RelNode rel = ExpressionLineageProgram.rel(16, 4, true);
+ Set<RexNode> lineage =
rel.getCluster().getMetadataQuery().getExpressionLineage(rel,
+ RexInputRef.of(4, rel.getRowType().getFieldList()));
+ assertTrue(lineage == null, () -> "Expected unknown lineage, not "
+ + (lineage == null ? "null" : lineage.size()) + " candidates");
+ }
+
+ @Test void testBudgetCountsAttemptsBeforeDeduplication() {
+ RexInputRef a = ref(0);
+ RexInputRef b = ref(1);
+ RexNode expression = rexBuilder.makeCall(SqlStdOperatorTable.PLUS, a, b);
+ Map<RexInputRef, Set<RexNode>> mapping = mapping(a, b);
+ // Commutative normalization merges 1 + 10 and 10 + 1, but constructing
+ // both still takes work. Budgeting the result Set size would miss this.
+ Set<RexNode> unlimited = expand(expression, mapping, -1);
+ assertNotNull(unlimited);
+ assertEquals(3, unlimited.size());
+ assertEquals(unlimited, expand(expression, mapping, 4));
+ assertNull(expand(expression, mapping, 3));
+ }
+
+ @Test void testRepeatedAndUnusedReferences() {
+ RexInputRef a = ref(0);
+ RexInputRef b = ref(1);
+ RexNode expression = rexBuilder.makeCall(SqlStdOperatorTable.MINUS, a, a);
+ Map<RexInputRef, Set<RexNode>> mapping = mapping(a, b);
+ // Only a is referenced: repeated occurrences share a substitution, and
+ // unused b must not contribute a dimension to the product.
+ assertEquals(expand(expression, mapping, -1), expand(expression, mapping,
2));
+ assertNull(expand(expression, mapping, 1));
+ }
+
+ @Test void testZeroBudgetAndConstants() {
+ Map<RexInputRef, Set<RexNode>> mapping = mapping(ref(0), ref(1));
+ assertNull(expand(ref(0), mapping, 0));
+ RexNode one = rexBuilder.makeExactLiteral(BigDecimal.ONE);
+ assertEquals(ImmutableSet.of(one), expand(one, mapping, 0));
+ assertThrows(IllegalArgumentException.class, () -> expand(one, mapping,
-2));
+ }
+
+ @Test void testProductDoesNotOverflowOrEnumerate() {
+ RexInputRef a = ref(0);
+ RexInputRef b = ref(1);
+ RexNode expression = rexBuilder.makeCall(SqlStdOperatorTable.MINUS, a, b);
+ Set<RexNode> many = new AbstractSet<RexNode>() {
+ @Override public int size() {
+ return 65_536;
+ }
+
+ @Override public Iterator<RexNode> iterator() {
+ throw new AssertionError("Over-budget candidates must not be
enumerated");
+ }
+ };
+ Map<RexInputRef, Set<RexNode>> mapping = new LinkedHashMap<>();
+ mapping.put(a, many);
+ mapping.put(b, many);
+ // 65,536 squared wraps to zero in int arithmetic.
+ assertNull(expand(expression, mapping, Integer.MAX_VALUE));
+ assertEquals(2, mapping.size());
+ }
+
+ @Test void testGeneratorRejectsInvalidDimensions() {
+ assertThrows(IllegalArgumentException.class, () ->
ExpressionLineageProgram.sql(0, 4, true));
+ assertThrows(IllegalArgumentException.class, () ->
ExpressionLineageProgram.sql(2, 0, false));
+ }
+
+ @Test void testAllPredicatesUsesTheSameBudget() throws Exception {
Review Comment:
I am also not sure how this test is relevant for this change. Too many tests
are not good either.
##########
core/src/test/java/org/apache/calcite/rel/metadata/ExpressionLineageProgram.java:
##########
@@ -0,0 +1,83 @@
+/*
+ * 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.calcite.rel.metadata;
+
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rel.type.RelDataTypeFactory;
+import org.apache.calcite.schema.SchemaPlus;
+import org.apache.calcite.schema.impl.AbstractTable;
+import org.apache.calcite.sql.SqlNode;
+import org.apache.calcite.sql.type.SqlTypeName;
+import org.apache.calcite.tools.Frameworks;
+import org.apache.calcite.tools.Planner;
+
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+/** Generates storage-free SQL programs whose expression lineage has
Review Comment:
what is a storage-free SQL program, and why is it important for this test?
I would make this class a static class in `RelMdExpressionLineageTest`
--
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]
