This is an automated email from the ASF dual-hosted git repository. mbudiu pushed a commit to branch main in repository https://gitbox.apache.org/repos/asf/calcite.git
commit 59358529cbe784519d319c2e28b038018d757806 Author: Mihai Budiu <[email protected]> AuthorDate: Wed Aug 14 11:47:30 2024 -0700 [CALCITE-6372] Add ASOF join to the Calcite parser Signed-off-by: Mihai Budiu <[email protected]> --- core/src/main/codegen/templates/Parser.jj | 31 +++- .../apache/calcite/runtime/CalciteResource.java | 17 ++- .../main/java/org/apache/calcite/sql/JoinType.java | 23 ++- .../java/org/apache/calcite/sql/SqlAsofJoin.java | 164 +++++++++++++++++++++ .../calcite/sql/parser/SqlAbstractParserImpl.java | 2 +- .../calcite/runtime/CalciteResource.properties | 7 +- .../apache/calcite/sql/test/SqlAdvisorTest.java | 2 + core/src/test/resources/sql/lateral.iq | 12 +- site/_docs/reference.md | 27 +++- .../apache/calcite/sql/parser/SqlParserTest.java | 31 ++++ 10 files changed, 305 insertions(+), 11 deletions(-) diff --git a/core/src/main/codegen/templates/Parser.jj b/core/src/main/codegen/templates/Parser.jj index 49ef4f6f1a..92ca7faa35 100644 --- a/core/src/main/codegen/templates/Parser.jj +++ b/core/src/main/codegen/templates/Parser.jj @@ -40,6 +40,7 @@ import org.apache.calcite.runtime.CalciteContextException; import org.apache.calcite.sql.JoinConditionType; import org.apache.calcite.sql.JoinType; import org.apache.calcite.sql.SqlAlter; +import org.apache.calcite.sql.SqlAsofJoin; import org.apache.calcite.sql.SqlBasicTypeNameSpec; import org.apache.calcite.sql.SqlBinaryOperator; import org.apache.calcite.sql.SqlCall; @@ -1999,6 +2000,7 @@ SqlLiteral Natural() : SqlLiteral JoinType() : { JoinType joinType; + boolean asof = false; } { ( @@ -2011,7 +2013,9 @@ SqlLiteral JoinType() : | <INNER> <JOIN> { joinType = JoinType.INNER; } | - <LEFT> [ <OUTER> ] <JOIN> { joinType = JoinType.LEFT; } + <ASOF> <JOIN> { joinType = JoinType.ASOF; } + | + <LEFT> [ <OUTER> | <ASOF> { asof = true; } ] <JOIN> { joinType = asof ? JoinType.LEFT_ASOF : JoinType.LEFT; } | <RIGHT> [ <OUTER> ] <JOIN> { joinType = JoinType.RIGHT; } | @@ -2075,7 +2079,7 @@ SqlNode JoinOrCommaTable(SqlNode e) : /** Matches "LEFT JOIN t ON ...", "RIGHT JOIN t USING ...", "JOIN t". */ SqlNode JoinTable(SqlNode e) : { - SqlNode e2, condition; + SqlNode e2, condition, matchCondition = null; final SqlLiteral natural, joinType, on, using; SqlNodeList list; } @@ -2092,13 +2096,32 @@ SqlNode JoinTable(SqlNode e) : // // We allow CROSS JOIN (joinType = CROSS_JOIN) to have a join condition, // even though that is not valid SQL; the validator will catch it. - LOOKAHEAD(3) + LOOKAHEAD(4) natural = Natural() joinType = JoinType() e2 = TableRef1(ExprContext.ACCEPT_QUERY_OR_JOIN) ( + [ <MATCH_CONDITION> matchCondition = Expression(ExprContext.ACCEPT_SUB_QUERY) ] <ON> { on = JoinConditionType.ON.symbol(getPos()); } condition = Expression(ExprContext.ACCEPT_SUB_QUERY) { + JoinType type = joinType.getValueAs(JoinType.class); + if (matchCondition != null) { + if (type != JoinType.ASOF && type != JoinType.LEFT_ASOF) { + throw SqlUtil.newContextException(getPos(), RESOURCE.matchConditionRequiresAsof()); + } + return new SqlAsofJoin(joinType.getParserPosition(), + e, + natural, + joinType, + e2, + on, + condition, + matchCondition); + } else { + if (type == JoinType.ASOF || type == JoinType.LEFT_ASOF) { + throw SqlUtil.newContextException(getPos(), RESOURCE.asofRequiresMatchCondition()); + } + } return new SqlJoin(joinType.getParserPosition(), e, natural, @@ -8019,6 +8042,7 @@ SqlPostfixOperator PostfixRowOperator() : | < ARRAY_CONCAT_AGG: "ARRAY_CONCAT_AGG" > | < ARRAY_MAX_CARDINALITY: "ARRAY_MAX_CARDINALITY" > | < AS: "AS" > +| < ASOF: "ASOF" > | < ASC: "ASC" > | < ASENSITIVE: "ASENSITIVE" > | < ASSERTION: "ASSERTION" > @@ -8319,6 +8343,7 @@ SqlPostfixOperator PostfixRowOperator() : | < MATCH: "MATCH" > | < MATCHED: "MATCHED" > | < MATCHES: "MATCHES" > +| < MATCH_CONDITION: "MATCH_CONDITION"> | < MATCH_NUMBER: "MATCH_NUMBER"> | < MATCH_RECOGNIZE: "MATCH_RECOGNIZE"> | < MAX: "MAX" > diff --git a/core/src/main/java/org/apache/calcite/runtime/CalciteResource.java b/core/src/main/java/org/apache/calcite/runtime/CalciteResource.java index 2e132c81b6..b0a2a00a0c 100644 --- a/core/src/main/java/org/apache/calcite/runtime/CalciteResource.java +++ b/core/src/main/java/org/apache/calcite/runtime/CalciteResource.java @@ -322,7 +322,7 @@ public interface CalciteResource { @BaseMessage("Duplicate name ''{0}'' in column alias list") ExInst<SqlValidatorException> aliasListDuplicate(String a0); - @BaseMessage("INNER, LEFT, RIGHT or FULL join requires a condition (NATURAL keyword or ON or USING clause)") + @BaseMessage("INNER, LEFT, RIGHT, FULL, or ASOF join requires a condition (NATURAL keyword or ON or USING clause)") ExInst<SqlValidatorException> joinRequiresCondition(); @BaseMessage("Cannot qualify common column ''{0}''") @@ -1108,4 +1108,19 @@ public interface CalciteResource { @BaseMessage("BIT_GET/GETBIT error: position {0,number} exceeds the bit upper limit {1,number}") ExInst<CalciteException> illegalBitGetPositionExceedsLimit(int position, int size); + + @BaseMessage("MATCH_CONDITION only allowed with ASOF JOIN") + ExInst<CalciteException> matchConditionRequiresAsof(); + + @BaseMessage("ASOF JOIN missing MATCH_CONDITION") + ExInst<CalciteException> asofRequiresMatchCondition(); + + @BaseMessage("ASOF JOIN MATCH_CONDITION must be a comparison between columns from the two inputs") + ExInst<SqlValidatorException> asofMatchMustBeComparison(); + + @BaseMessage("ASOF JOIN condition must be a conjunction of equality comparisons") + ExInst<SqlValidatorException> asofConditionMustBeComparison(); + + @BaseMessage("ASOF JOIN does not support correlated subqueries") + ExInst<CalciteException> asofCannotBeCorrelated(); } diff --git a/core/src/main/java/org/apache/calcite/sql/JoinType.java b/core/src/main/java/org/apache/calcite/sql/JoinType.java index bb75755a35..6f3084e5d0 100644 --- a/core/src/main/java/org/apache/calcite/sql/JoinType.java +++ b/core/src/main/java/org/apache/calcite/sql/JoinType.java @@ -66,7 +66,28 @@ public enum JoinType implements Symbolizable { * where table expressions are specified with commas between them, and * join conditions are specified in the <code>WHERE</code> clause. */ - COMMA; + COMMA, + + /** + * An ASOF JOIN operation combines rows from two tables based on comparable timestamp values. + * For each row in the left table, the join finds at most one row in the right table that has the + * "closest" timestamp value. The matched row on the right side is the closest match, + * which could less than or equal or greater than or equal in the timestamp column, + * as specified by the comparison operator. + * + * <p>Example: + * <blockquote><pre> + * FROM left_table ASOF JOIN right_table + * MATCH_CONDITION ( left_table.timecol ≤ right_table.timecol ) + * ON left_table.col = right_table.col</pre> + * </blockquote> + */ + ASOF, + + /** + * The left version of an ASOF join, where each row from the left table is part of the output. + */ + LEFT_ASOF; /** Lower-case name. */ public final String lowerName = name().toLowerCase(Locale.ROOT); diff --git a/core/src/main/java/org/apache/calcite/sql/SqlAsofJoin.java b/core/src/main/java/org/apache/calcite/sql/SqlAsofJoin.java new file mode 100644 index 0000000000..14f9723d37 --- /dev/null +++ b/core/src/main/java/org/apache/calcite/sql/SqlAsofJoin.java @@ -0,0 +1,164 @@ +/* + * 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.sql; + +import org.apache.calcite.sql.parser.SqlParserPos; +import org.apache.calcite.sql.util.SqlString; +import org.apache.calcite.util.ImmutableNullableList; +import org.apache.calcite.util.Util; + +import org.checkerframework.checker.nullness.qual.Nullable; + +import java.util.List; +import java.util.function.UnaryOperator; + +/** + * Parse tree node representing a {@code ASOF JOIN} clause. + */ +public class SqlAsofJoin extends SqlJoin { + SqlNode matchCondition; + static final SqlAsofJoinOperator ASOF_OPERATOR = + new SqlAsofJoinOperator("ASOF-JOIN", 16); + + //~ Constructors ----------------------------------------------------------- + + public SqlAsofJoin(SqlParserPos pos, SqlNode left, SqlLiteral natural, + SqlLiteral joinType, SqlNode right, SqlLiteral conditionType, + @Nullable SqlNode condition, SqlNode matchCondition) { + super(pos, left, natural, joinType, right, conditionType, condition); + this.matchCondition = matchCondition; + } + + @SuppressWarnings("nullness") + @Override public List<SqlNode> getOperandList() { + return ImmutableNullableList.of(left, natural, joinType, right, + conditionType, condition, matchCondition); + } + + @Override public SqlOperator getOperator() { + return ASOF_OPERATOR; + } + + @SuppressWarnings("assignment.type.incompatible") + @Override public void setOperand(int i, @Nullable SqlNode operand) { + switch (i) { + case 0: + left = operand; + break; + case 1: + natural = (SqlLiteral) operand; + break; + case 2: + joinType = (SqlLiteral) operand; + break; + case 3: + right = operand; + break; + case 4: + conditionType = (SqlLiteral) operand; + break; + case 5: + condition = operand; + break; + case 6: + matchCondition = operand; + break; + default: + throw new AssertionError(i); + } + } + + /** + * The match condition of the ASOF JOIN. + * + * @return The match condition of the ASOF join. + */ + public final SqlNode getMatchCondition() { + return matchCondition; + } + + /** + * Describes the syntax of the SQL ASOF JOIN operator. + */ + public static class SqlAsofJoinOperator extends SqlOperator { + //~ Constructors ----------------------------------------------------------- + + private SqlAsofJoinOperator(String name, int prec) { + super(name, SqlKind.JOIN, prec, true, null, null, null); + } + + //~ Methods ---------------------------------------------------------------- + + @Override public SqlSyntax getSyntax() { + return SqlSyntax.SPECIAL; + } + + @SuppressWarnings("argument.type.incompatible") + @Override public SqlCall createCall( + @Nullable SqlLiteral functionQualifier, + SqlParserPos pos, + @Nullable SqlNode... operands) { + assert functionQualifier == null; + return new SqlAsofJoin(pos, operands[0], (SqlLiteral) operands[1], + (SqlLiteral) operands[2], operands[3], (SqlLiteral) operands[4], + operands[5], operands[6]); + } + + @Override public void unparse( + SqlWriter writer, + SqlCall call, + int leftPrec, + int rightPrec) { + final SqlAsofJoin join = (SqlAsofJoin) call; + + join.left.unparse( + writer, + leftPrec, + getLeftPrec()); + if (join.getJoinType() == JoinType.LEFT_ASOF) { + writer.sep("LEFT ASOF JOIN"); + } else { + writer.sep("ASOF JOIN"); + } + join.right.unparse(writer, getRightPrec(), rightPrec); + SqlNode matchCondition = join.matchCondition; + writer.keyword("MATCH_CONDITION"); + matchCondition.unparse(writer, 0, 0); + + SqlNode joinCondition = join.condition; + if (joinCondition != null) { + switch (join.getConditionType()) { + case ON: + writer.keyword("ON"); + joinCondition.unparse(writer, leftPrec, rightPrec); + break; + + default: + throw Util.unexpected(join.getConditionType()); + } + } + } + } + + @Override public SqlString toSqlString(UnaryOperator<SqlWriterConfig> transform) { + SqlNode selectWrapper = + new SqlSelect(SqlParserPos.ZERO, SqlNodeList.EMPTY, + SqlNodeList.SINGLETON_STAR, this, null, null, null, + SqlNodeList.EMPTY, null, null, null, null, SqlNodeList.EMPTY); + return selectWrapper.toSqlString(transform); + } +} diff --git a/core/src/main/java/org/apache/calcite/sql/parser/SqlAbstractParserImpl.java b/core/src/main/java/org/apache/calcite/sql/parser/SqlAbstractParserImpl.java index bd9b0bdb32..389a6fa561 100644 --- a/core/src/main/java/org/apache/calcite/sql/parser/SqlAbstractParserImpl.java +++ b/core/src/main/java/org/apache/calcite/sql/parser/SqlAbstractParserImpl.java @@ -56,7 +56,7 @@ import java.util.TreeSet; import static org.apache.calcite.util.Static.RESOURCE; /** - * Abstract base for parsers generated from CommonParser.jj. + * Abstract base for parsers. */ public abstract class SqlAbstractParserImpl { //~ Static fields/initializers --------------------------------------------- diff --git a/core/src/main/resources/org/apache/calcite/runtime/CalciteResource.properties b/core/src/main/resources/org/apache/calcite/runtime/CalciteResource.properties index 773c3bc6b0..0bd6a170bf 100644 --- a/core/src/main/resources/org/apache/calcite/runtime/CalciteResource.properties +++ b/core/src/main/resources/org/apache/calcite/runtime/CalciteResource.properties @@ -112,7 +112,7 @@ AliasMustBeSimpleIdentifier=Table or column alias must be a simple identifier CharLiteralAliasNotValid=Expecting alias, found character literal AliasListDegree=List of column aliases must have same degree as table; table has {0,number,#} columns {1}, whereas alias list has {2,number,#} columns AliasListDuplicate=Duplicate name ''{0}'' in column alias list -JoinRequiresCondition=INNER, LEFT, RIGHT or FULL join requires a condition (NATURAL keyword or ON or USING clause) +JoinRequiresCondition=INNER, LEFT, RIGHT, FULL, or ASOF join requires a condition (NATURAL keyword or ON or USING clause) DisallowsQualifyingCommonColumn=Cannot qualify common column ''{0}'' CrossJoinDisallowsCondition=Cannot specify condition (NATURAL keyword, or ON or USING clause) following CROSS JOIN NaturalDisallowsOnOrUsing=Cannot specify NATURAL keyword with ON or USING clause @@ -363,4 +363,9 @@ MustFilterFieldsMissing=SQL statement did not contain filters on the following f IllegalNegativeBitGetPosition=BIT_GET/GETBIT error: negative position {0,number} not allowed IllegalBitGetPositionExceedsLimit=BIT_GET/GETBIT error: position {0,number} exceeds the bit upper limit {1,number} WindowInHavingNotAllowed=Window expressions are not permitted in the HAVING clause; use the QUALIFY clause instead +MatchConditionRequiresAsof=MATCH_CONDITION only allowed with ASOF JOIN +AsofRequiresMatchCondition=ASOF JOIN missing MATCH_CONDITION +AsofMatchMustBeComparison=ASOF JOIN MATCH_CONDITION must be a comparison between columns from the two inputs +AsofConditionMustBeComparison=ASOF JOIN condition must be a conjunction of equality comparisons +AsofCannotBeCorrelated=ASOF JOIN does not support correlated subqueries # End CalciteResource.properties diff --git a/core/src/test/java/org/apache/calcite/sql/test/SqlAdvisorTest.java b/core/src/test/java/org/apache/calcite/sql/test/SqlAdvisorTest.java index b58a409dcc..fefbe34fd8 100644 --- a/core/src/test/java/org/apache/calcite/sql/test/SqlAdvisorTest.java +++ b/core/src/test/java/org/apache/calcite/sql/test/SqlAdvisorTest.java @@ -366,6 +366,7 @@ class SqlAdvisorTest extends SqlValidatorTestCase { "KEYWORD(EXTEND)", "KEYWORD(/*+)", "KEYWORD(AS)", + "KEYWORD(ASOF)", "KEYWORD(USING)", "KEYWORD(OUTER)", "KEYWORD(RIGHT)", @@ -378,6 +379,7 @@ class SqlAdvisorTest extends SqlValidatorTestCase { "KEYWORD(HAVING)", "KEYWORD(LEFT)", "KEYWORD(EXCEPT)", + "KEYWORD(MATCH_CONDITION)", "KEYWORD(MATCH_RECOGNIZE)", "KEYWORD(MINUS)", "KEYWORD(JOIN)", diff --git a/core/src/test/resources/sql/lateral.iq b/core/src/test/resources/sql/lateral.iq index b4b9d3b952..2dcdf1beac 100644 --- a/core/src/test/resources/sql/lateral.iq +++ b/core/src/test/resources/sql/lateral.iq @@ -33,9 +33,15 @@ Was expecting one of: # Bad: LATERAL TABLE select * from "scott".emp join lateral table "scott".dept using (deptno); -parse failed: Encountered "\"scott\"" at line 1, column 46. -Was expecting: - "(" ... +parse failed: Encountered "join lateral table \"scott\"" at line 1, column 27. +Was expecting one of: + "AS" ... + "CROSS" ... + "EXTEND" ... + "FOR" ... + "MATCH_RECOGNIZE" ... + "OUTER" ... + "TABLESAMPLE" ... !error # Good: LATERAL (subQuery) diff --git a/site/_docs/reference.md b/site/_docs/reference.md index 2ceabcc97a..0288d1f88d 100644 --- a/site/_docs/reference.md +++ b/site/_docs/reference.md @@ -224,12 +224,13 @@ projectItem: tableExpression: tableReference [, tableReference ]* - | tableExpression [ NATURAL ] [ { LEFT | RIGHT | FULL } [ OUTER ] ] JOIN tableExpression [ joinCondition ] + | tableExpression [ NATURAL ] [ { LEFT | RIGHT | FULL } [ OUTER ] ] [ ASOF ] JOIN tableExpression [ joinCondition ] | tableExpression CROSS JOIN tableExpression | tableExpression [ CROSS | OUTER ] APPLY tableExpression joinCondition: ON booleanExpression + | MATCH_CONDITION booleanExpression ON booleanExpression | USING '(' column [, column ]* ')' tableReference: @@ -411,6 +412,28 @@ VALUE is equivalent to VALUES, but is not standard SQL and is only allowed in certain [conformance levels]({{ site.apiRoot }}/org/apache/calcite/sql/validate/SqlConformance.html#isValueAllowed--). +An "ASOF JOIN" operation combines rows from two tables based on +comparable timestamp values. For each row in the left table, the join +finds at most a single row in the right table that has the "closest" +timestamp value. The matched row on the right side is the closest +match whose timestamp column is compared using one of the operations +<, ≤, >, or ≥, as specified by the comparison operator in +the `MATCH_CONDITION` clause. The comparison is performed using SQL +semantics, which returns 'false' when comparing NULL values with any +other values. Thus a 'NULL' timestamp in the left table will not +match any timestamps in the right table. + +ASOF JOIN statements can also be LEFT ASOF JOIN. In this case, when there +is no match for a row in the left table, the columns from the right table +are null-padded. + +There are no RIGHT ASOF joins. + +SELECT * +FROM left_table [ LEFT ] ASOF JOIN right_table +MATCH_CONDITION ( left_table.timecol ≤ right_table.timecol ) +ON left_table.col = right_table.col + ## Keywords The following is a list of SQL keywords. @@ -442,6 +465,7 @@ ARRAY_CONCAT_AGG, **AS**, ASC, **ASENSITIVE**, +**ASOF**, ASSERTION, ASSIGNMENT, **ASYMMETRIC**, @@ -740,6 +764,7 @@ MAP, **MATCH**, MATCHED, **MATCHES**, +**MATCH_CONDITION**, **MATCH_NUMBER**, **MATCH_RECOGNIZE**, **MAX**, diff --git a/testkit/src/main/java/org/apache/calcite/sql/parser/SqlParserTest.java b/testkit/src/main/java/org/apache/calcite/sql/parser/SqlParserTest.java index 31b628b3b8..ebc56e690b 100644 --- a/testkit/src/main/java/org/apache/calcite/sql/parser/SqlParserTest.java +++ b/testkit/src/main/java/org/apache/calcite/sql/parser/SqlParserTest.java @@ -136,6 +136,7 @@ public class SqlParserTest { "AS", "92", "99", "2003", "2011", "2014", "c", "ASC", "92", "99", "ASENSITIVE", "99", "2003", "2011", "2014", "c", + "ASOF", "c", "ASSERTION", "92", "99", "ASYMMETRIC", "99", "2003", "2011", "2014", "c", "AT", "92", "99", "2003", "2011", "2014", "c", @@ -356,6 +357,7 @@ public class SqlParserTest { "MAP", "99", "MATCH", "92", "99", "2003", "2011", "2014", "c", "MATCHES", "2014", "c", + "MATCH_CONDITION", "c", "MATCH_NUMBER", "2014", "c", "MATCH_RECOGNIZE", "2014", "c", "MAX", "92", "2011", "2014", "c", @@ -4600,6 +4602,35 @@ public class SqlParserTest { sql(sql4).ok(expected4); } + @Test void testAsofJoinTable() { + final String sql0 = "select * from orders asof join products\n" + + "match_condition orders.ts <= products.expiry\n" + + "on orders.productid = products.productid"; + final String expected0 = "SELECT *\n" + + "FROM (`ORDERS` " + + "ASOF JOIN `PRODUCTS` " + + "MATCH_CONDITION (`ORDERS`.`TS` <= `PRODUCTS`.`EXPIRY`) " + + "ON (`ORDERS`.`PRODUCTID` = `PRODUCTS`.`PRODUCTID`))"; + sql(sql0).ok(expected0); + final String sql1 = "select * from orders left asof join products\n" + + "match_condition orders.ts <= products.expiry\n" + + "on orders.productid = products.productid"; + final String expected1 = "SELECT *\n" + + "FROM (`ORDERS` " + + "LEFT ASOF JOIN `PRODUCTS` " + + "MATCH_CONDITION (`ORDERS`.`TS` <= `PRODUCTS`.`EXPIRY`) " + + "ON (`ORDERS`.`PRODUCTID` = `PRODUCTS`.`PRODUCTID`))"; + sql(sql1).ok(expected1); + + sql("select * from orders asof join products\n" + + "on orders.productid = products.^productid^") + .fails("ASOF JOIN missing MATCH_CONDITION"); + sql("select * from orders join products\n" + + "match_condition orders.ts <= products.expiry\n" + + "on orders.productid = products_temporal.^productid^") + .fails("MATCH_CONDITION only allowed with ASOF JOIN"); + } + @Test void testCollectionTableWithLateral() { final String sql = "select * from dept, lateral table(ramp(dept.deptno))"; final String expected = "SELECT *\n"
