[GitHub] rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez)
rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez) URL: https://github.com/apache/calcite/pull/1020#discussion_r258437869 ## File path: core/src/main/java/org/apache/calcite/tools/RelBuilder.java ## @@ -1616,6 +1619,58 @@ public RelBuilder minus(boolean all, int n) { return setOp(all, SqlKind.EXCEPT, n); } + /** + * Creates a {@link LogicalDeltaTableScan} of a delta work table (used to accumulate results in + * recursive union operation), using as its row type the top of the stack. + * Returns this builder. + */ + public RelBuilder deltaScan(String tableName) { Review comment: Agree, `*delta*` renamed as `*transient*` This is an automated message from the Apache Git Service. To respond to the message, please log on GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services
[GitHub] rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez)
rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez) URL: https://github.com/apache/calcite/pull/1020#discussion_r258437869 ## File path: core/src/main/java/org/apache/calcite/tools/RelBuilder.java ## @@ -1616,6 +1619,58 @@ public RelBuilder minus(boolean all, int n) { return setOp(all, SqlKind.EXCEPT, n); } + /** + * Creates a {@link LogicalDeltaTableScan} of a delta work table (used to accumulate results in + * recursive union operation), using as its row type the top of the stack. + * Returns this builder. + */ + public RelBuilder deltaScan(String tableName) { Review comment: Agree, *delta* renamed as *transient* This is an automated message from the Apache Git Service. To respond to the message, please log on GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services
[GitHub] rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez)
rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez) URL: https://github.com/apache/calcite/pull/1020#discussion_r258412422 ## File path: core/src/test/java/org/apache/calcite/test/JdbcTest.java ## @@ -6837,6 +6837,36 @@ public TranslatableTable view(String s) { } } + public static class HierarchySchema { +@Override public String toString() { + return "HierarchySchema"; +} + +public final Employee[] emps = { +new Employee(1, 10, "Emp1", 1, 1000), +new Employee(2, 10, "Emp2", 8000, 500), +new Employee(3, 10, "Emp3", 7000, null), +new Employee(4, 10, "Emp4", 8000, 500), +new Employee(5, 10, "Emp5", 7000, null), +}; +public final Department[] depts = { +new Department(10, "Dept", Arrays.asList(emps[0], emps[1], emps[2], emps[3], emps[4]), +new Location(-122, 38)), +}; + +// Emp1 +// / \ +//Emp2 Emp4 +/// \ +// Emp3 Emp5 +public final Hierarchy[] hierarchies = { Review comment: I think this design has two (small) advantages: - It can represent more complicated hierarchies, e.g. one employee with more than one manager (although this is currently not used in the test cases) - It requires 2 joins (instead of 1) to compute the hierarchy paths, so it allows us to show a trickier use case of recursive union + transient table scan This is an automated message from the Apache Git Service. To respond to the message, please log on GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services
[GitHub] rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez)
rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez) URL: https://github.com/apache/calcite/pull/1020#discussion_r258410547 ## File path: core/src/test/java/org/apache/calcite/test/enumerable/EnumerableRecursiveUnionTest.java ## @@ -0,0 +1,357 @@ +/* + * 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.test.enumerable; + +import org.apache.calcite.adapter.java.ReflectiveSchema; +import org.apache.calcite.rel.RelNode; +import org.apache.calcite.rel.core.JoinRelType; +import org.apache.calcite.schema.Schema; +import org.apache.calcite.sql.fun.SqlStdOperatorTable; +import org.apache.calcite.test.CalciteAssert; +import org.apache.calcite.test.JdbcTest; +import org.apache.calcite.tools.RelBuilder; + +import org.junit.Test; + +import java.util.Arrays; +import java.util.function.Function; + +/** + * Unit tests for + * {@link org.apache.calcite.adapter.enumerable.EnumerableRecursiveUnion} + * and {@link org.apache.calcite.adapter.enumerable.EnumerableDeltaTableScan} + * https://issues.apache.org/jira/browse/CALCITE-2812;>[CALCITE-2812] + * Add algebraic operators to allow expressing recursive queries. + */ +public class EnumerableRecursiveUnionTest { + + @Test public void testGenerateNumbers() { +CalciteAssert.that() +.query("?") +.withRel( +// WITH RECURSIVE delta(n) AS ( +// VALUES (1) +// UNION ALL +// SELECT n+1 FROM delta WHERE n < 10 +// ) +// SELECT * FROM delta +builder -> builder +.values(new String[] { "i" }, 1) +.deltaScan("DELTA") +.filter( +builder.call( + SqlStdOperatorTable.LESS_THAN, +builder.field(0), +builder.literal(10))) +.project( +builder.call(SqlStdOperatorTable.PLUS, +builder.field(0), +builder.literal(1))) +.recursiveUnion("DELTA") +.build() +) +.returnsOrdered("i=1", "i=2", "i=3", "i=4", "i=5", "i=6", "i=7", "i=8", "i=9", "i=10"); + } + + @Test public void testFactorial() { +CalciteAssert.that() +.query("?") +.withRel( +// WITH RECURSIVE delta (n, fact) AS ( +// VALUES (0, 1) +// UNION ALL +// SELECT n+1, (n+1)*fact FROM delta WHERE n < 7 +// ) +// SELECT * FROM delta +builder -> builder +.values(new String[] { "n", "fact" }, 0, 1) +.deltaScan("D") +.filter( +builder.call( +SqlStdOperatorTable.LESS_THAN, +builder.field("n"), +builder.literal(7))) +.project( +Arrays.asList( +builder.call(SqlStdOperatorTable.PLUS, +builder.field("n"), +builder.literal(1)), + builder.call(SqlStdOperatorTable.MULTIPLY, + builder.call(SqlStdOperatorTable.PLUS, +builder.field("n"), +builder.literal(1)), +builder.field("fact"))), +Arrays.asList("n", "fact")) +.recursiveUnion("D") +.build() +
[GitHub] rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez)
rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez) URL: https://github.com/apache/calcite/pull/1020#discussion_r255524984 ## File path: core/src/test/java/org/apache/calcite/test/enumerable/EnumerableRecursiveUnionTest.java ## @@ -0,0 +1,157 @@ +/* + * 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.test.enumerable; + +import org.apache.calcite.sql.fun.SqlStdOperatorTable; +import org.apache.calcite.test.CalciteAssert; + +import org.junit.Test; + +import java.util.Arrays; + +/** + * Unit tests for + * {@link org.apache.calcite.adapter.enumerable.EnumerableRecursiveUnion} + * and {@link org.apache.calcite.adapter.enumerable.EnumerableDeltaTableScan} + * https://issues.apache.org/jira/browse/CALCITE-2812;>[CALCITE-2812] + * Add algebraic operators to allow expressing recursive queries. + */ +public class EnumerableRecursiveUnionTest { Review comment: New unit tests have been added This is an automated message from the Apache Git Service. To respond to the message, please log on GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services
[GitHub] rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez)
rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez) URL: https://github.com/apache/calcite/pull/1020#discussion_r255430050 ## File path: linq4j/src/main/java/org/apache/calcite/linq4j/EnumerableDefaults.java ## @@ -3329,6 +3329,167 @@ public void reset() { public void close() { } } + + /** + * Enumerator that performs a recursive union. Inspired by PostgreSQL's "WITH RECURSIVE" + * implementation. See https://www.postgresql.org/docs/11/queries-with.html + * + * The general form of a recursive WITH query is always: a non-recursive term, then UNION [ALL] + * (in our case only UNION ALL is supported for the moment), then a recursive term; + * where only the recursive term can contain a reference to the query's own output. + * Such an operation is executed as follows: + * - Evaluate the non-recursive term (seed). Include all rows in the result of the recursive + * union, and also place them in a transient work table (aka delta table) that gets added to + * the schema. + * - So long as the working table is not empty, repeat: + * - Evaluate the recursive term, using the current content of the transient table for + * the recursive self-reference. Include all resulting rows in the result of the recursive + * union, and also place them in the transient table, they will be the input for the + * next iteration. + * + * Note: strictly speaking, this process is iteration not recursion, but RECURSIVE is the + * terminology chosen by the SQL standards committee. + */ + public static Enumerable recursiveUnion( + Enumerable seed, + Enumerable recursion, + Collection deltaCollection) { +return new AbstractEnumerable() { + @Override public Enumerator enumerator() { +return new Enumerator() { + private TSource current = null; + private boolean seedProcessed = false; + private final Enumerator seedEnumerator = seed.enumerator(); + private final Enumerator recursionEnumerator = recursion.enumerator(); + private final Collection delta = deltaCollection; + + // flag to avoid adding the current item multiple times to delta collection + // in case of consecutive current() calls + private boolean currentAddedToDelta = false; + + @Override public TSource current() { +if (this.current == null) { + throw new NoSuchElementException(); +} + +if (!this.currentAddedToDelta) { + // add 'current' to the delta work table (so that it will be fetched + // by the delta table scan later) + this.delta.add(this.current); + this.currentAddedToDelta = true; +} + +return this.current; + } + + @Override public boolean moveNext() { +// if we are not done with the seed (non-recursive term) moveNext on it +if (!this.seedProcessed) { + if (this.seedEnumerator.moveNext()) { +this.currentAddedToDelta = false; +this.current = this.seedEnumerator.current(); +return true; + } else { +this.seedProcessed = true; + } +} + +// if we are done with the seed, moveNext on the recursive part +if (this.recursionEnumerator.moveNext()) { Review comment: @zabetak I agree, I have committed a new version with a refactoring using this approach. This is an automated message from the Apache Git Service. To respond to the message, please log on GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services
[GitHub] rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez)
rubenada commented on a change in pull request #1020: [CALCITE-2812] Add algebraic operators to allow expressing recursive queries (Ruben Quesada Lopez) URL: https://github.com/apache/calcite/pull/1020#discussion_r255429972 ## File path: core/src/main/java/org/apache/calcite/tools/RelBuilder.java ## @@ -1616,6 +1619,68 @@ public RelBuilder minus(boolean all, int n) { return setOp(all, SqlKind.EXCEPT, n); } + /** + * Creates a {@link LogicalDeltaTableScan} of a delta work table (used to accumulate results in + * recursive union operation), using as its row type the top of the stack, and not max depth + * Returns this builder. + */ + public RelBuilder deltaScan(String tableName) { +return this.deltaScan(tableName, this.peek().getRowType()); + } + + /** + * Creates a {@link LogicalDeltaTableScan} of a delta work table (used to accumulate results in + * recursive union operation), using as its row type the top of the stack, and a certain max depth + * Returns this builder. + */ + public RelBuilder deltaScan(String tableName, int maxDepth) { Review comment: @zabetak you're right, I have committed a new version with a refactoring using this approach. This is an automated message from the Apache Git Service. To respond to the message, please log on GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services