[CALCITE-6372] Support ASOF joins #3883

mihaibudiu · 2024-07-25T04:15:43Z

This PR is probably easiest to review commit by commit. The 4 commits correspond to various Calcite program representations.

mihaibudiu · 2024-07-25T17:24:31Z

The CI failures are not fundamental, I will try to fix them today

caicancai · 2024-07-27T00:44:26Z

I am very interested in this PR and I may need to spend some time reviewing it.

mihaibudiu · 2024-07-27T00:45:42Z

Go ahead

YiwenWu · 2024-07-31T16:06:09Z

core/src/main/java/org/apache/calcite/rel/metadata/RelMdUtil.java

    double innerRowCount = left * right * selectivity;
    switch (join.getJoinType()) {
+    case ASOF:
+    case LEFT_ASOF:


Is ASOF similar to inner join or left join?

In this implementation we have both ASOF and LEFT ASOF.
ASOF itself is an INNER join.

I agree that LEFT_ASOF returns left. Would it be more accurate for asof to return (left * selectivity)?

I am not familiar with this part of the code, I see that other places use 1 - selectivity.

My understanding is that for a regular inner join, selectivity means the probability of the condition being true in the result, and 1 - selectivity is because for an outer join we need to add the unmatched rows on the null side.
For asof join, we should consider how many matches there are against the left table, and we also could to consider the matchCondition, which is more complicated. Perhaps this optimization can be discussed in another issue.

YiwenWu · 2024-08-07T14:14:41Z

core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableAsofJoin.java

+import java.util.List;
+import java.util.Set;
+
+/** Implementation of {@link LogicalAsofJoin} in


minor: Implementation of {@link Join} not LogicalAsofJoin

well, this doesn't implement a generic join, it only implements an ASOF join.

Should consider introducing a new AsofJoin class? Both LogicalAsofJoin and EnumerableAsofJoin can extends this class

YiwenWu · 2024-08-07T14:17:16Z

core/src/main/codegen/templates/Parser.jj

+                    condition,
+                    matchCondition);
+            } else {
+                if (type == JoinType.ASOF && type != JoinType.LEFT_ASOF) {


The condition is type == JoinType.ASOF || type == JoinType.LEFT_ASOF ?

YiwenWu · 2024-08-07T14:20:29Z

core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableAsofJoin.java

+/** Implementation of {@link LogicalAsofJoin} in
+ * {@link EnumerableConvention enumerable calling convention}. */
+public class EnumerableAsofJoin extends Join implements EnumerableRel {
+  // This implementation is based on {@link EnumerableHashJoin}


This implementation is based on {@link EnumerableHashJoin},
Can this class directly extends EnumerableHashJoin?

I don't think there would be much code reuse.

YiwenWu · 2024-08-07T14:27:46Z

core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableAsofJoin.java

+  @Override public EnumerableAsofJoin copy(RelTraitSet traitSet, RexNode condition,
+                                           RelNode left, RelNode right, JoinRelType joinType,
+                                           boolean semiJoinDone) {
+    // This method does not know about the matchCondition, so it should not be called


Is it necessary to support the copy of changing matchCondition?

Certainly this method cannot be right, so it's better to catch attempts to call it.

YiwenWu · 2024-08-08T01:51:19Z

core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableAsofJoin.java

+                    // match comparator
+                    .append(matchPredicate)
+                    // timestamp comparator
+                    .append(timestampComparator)


Is the comparison limited to timestamp only?

"timestamp" is just a name for a pair of columns from each side that are being compared.
It has nothing to do with the TIMESTAMP data type.
The MATCH_CONDITION is restricted to one comparison between a pair of columns from either side. That's enforced by the validator, and part of the spec.

YiwenWu · 2024-08-08T01:57:56Z

core/src/main/java/org/apache/calcite/sql/JoinType.java

+
+  /**
+   * An ASOF JOIN operation combines rows from two tables based on comparable timestamp values.
+   * For each row in the left table, the join finds a single row in the right table that has the


Is there any confusion in this description? From the description, it may be understood as left join.

YiwenWu · 2024-08-08T02:02:50Z

core/src/main/java/org/apache/calcite/sql/SqlAsofJoin.java

+      if (joinCondition != null) {
+        switch (join.getConditionType()) {
+        case ON:
+          writer.keyword("ON");


Does this restriction need to be processed in sql Parser.jj?

I think it is, right now only ON is supported in the parser.
I plan to add USING later.

YiwenWu · 2024-08-08T02:06:05Z

core/src/main/java/org/apache/calcite/rel/core/RelFactories.java

+     * @param right            Right input
+     * @param hints            Hints
+     * @param condition        Join condition
+     * @param matchCondition   ASOF join match condition


missing joinType

YiwenWu · 2024-08-08T02:10:00Z

core/src/main/java/org/apache/calcite/rel/logical/LogicalAsofJoin.java

+      ImmutableList<RelDataTypeField> systemFieldList) {
+    super(cluster, traitSet, hints, left, right, condition, ImmutableSet.of(), joinType);
+    this.systemFieldList = requireNonNull(systemFieldList, "systemFieldList");
+    this.matchCondition = matchCondition;


limit requireNonNull(matchCondition)?

YiwenWu · 2024-08-08T02:13:21Z

core/src/main/java/org/apache/calcite/rel/rel2sql/SqlImplementor.java

    case FULL:
      return JoinType.FULL;
+    case ASOF:
+      return JoinType.ASOF;


missing LEFT_ASOF case?

caicancai · 2024-08-08T02:34:10Z

I will review this PR this weekend, sorry for the delay

mihaibudiu · 2024-08-08T03:37:51Z

@YiwenWu thank you for the review, I have pushed a commit with fixes for problems you found.

YiwenWu · 2024-08-08T11:47:18Z

core/src/main/java/org/apache/calcite/adapter/enumerable/EnumerableAsofJoin.java

+import java.util.List;
+import java.util.Set;
+
+/** Implementation of {@link LogicalAsofJoin} in


Should consider introducing a new AsofJoin class? Both LogicalAsofJoin and EnumerableAsofJoin can extends this class

YiwenWu · 2024-08-08T12:07:20Z

core/src/main/java/org/apache/calcite/sql2rel/RelFieldTrimmer.java

        + join.getRight().getRowType().getFieldCount();
    final RexNode conditionExpr = join.getCondition();
+    final RexNode matchConditionExpr = (join instanceof LogicalAsofJoin)
+        ? ((LogicalAsofJoin) join).getMatchCondition()


Directly limit ((LogicalAsofJoin) join).getMatchCondition() always not null?

Do you suggest an Objects.requireNonNull? I am not sure what you would gain from that.

YiwenWu · 2024-08-08T12:17:33Z

core/src/main/codegen/templates/Parser.jj

    joinType = JoinType()
    e2 = TableRef1(ExprContext.ACCEPT_QUERY_OR_JOIN)
    (
+        [ <MATCH_CONDITION> matchCondition = Expression(ExprContext.ACCEPT_SUB_QUERY) ]


(1). Is it consistent with snowflake, also uses parentheses?
(2). Whether MATCH_CONDITION support multiple conditions?

(1) This grammar does not require parentheses, but accepts them, I think it's more general this way. We can add them if desired.

(2) The grammar accepts any expression, but the validator will reject complex expressions, accepting only expressions that contain a single comparison. This would be very hard to do using the grammar

(1). This is a minor issue. The current implementation is based on Snowflake syntax, so keeping it consistent can help more users avoid confusion and learning new syntax.

This implementation accepts the Snowflake syntax, so users familiar with that syntax don't have to learn anything new. I think in general it's ok to be put as few constraints as possible on the programs you accept (the Jon Postel principle: https://en.wikipedia.org/wiki/Robustness_principle).

Also, please note that the Snowflake construct is deemed experimental in their documentation, so I don't think we should strive too much to adhere to it, maybe they will change their syntax too. (I hope they will, and, who knows, maybe we can even influence them?)

mihaibudiu · 2024-08-08T17:30:36Z

I have added a base AsofJoin class as suggested

YiwenWu

LGTM

suibianwanwank · 2024-08-09T06:03:29Z

core/src/main/java/org/apache/calcite/sql/validate/SqlValidatorImpl.java

+      matchCondition = expand(matchCondition, joinScope);
+      join.setOperand(6, matchCondition);
+      validateWhereOrOn(joinScope, matchCondition, "MATCH_CONDITION");
+      ConjunctionOfEqualities conj = new ConjunctionOfEqualities();


Would it be better to replace RelOptUtil.conjunctions() and match equal here.
Maybe the bool filed type affects like bool_column3 = (bool_column1 and bool_column2). WDYT

Of course, this is a rare case

"and' is not the same as "=" for booleans, since "and" returns "false" for "false = false".
But maybe I misunderstand your question.

I'm guessing that the checks here refer to snowflake's specification, i.e. "ON clause for ASOF JOIN must contain conjunctions of equality conditions only. Each side of an equality condition must only refer to either the left table or the right table. (S.STATE = P.STATE) OR (S.LOCATION = P.LOCATION) is invalid."
We expect that condition needs to satisfy
l.c1 = r.c1 and l.c2 = r.c2
But if you just check if sqlcall is equal / and, may a case like the following would also pass, if the types of c1 and c2 would both be boolean
(l.c1 and r.c1 ) and (l.c2 and r.c2 )

Good point. I will add a test case to make sure this doesn't happen.

Unfortunately I can't reuse RelOptUtil because that works on RexNode, and here I only have SqlNode objects.
I will improve the ConjunctionOfEqualities visitor.

mihaibudiu · 2024-08-13T06:33:17Z

Thank you @suibianwanwank, I hope I have fixed the problems you highlighted.

mihaibudiu · 2024-08-13T06:34:08Z

Does anyone else plan to review this PR or can I merge it?
More work may be needed, but this implementation is fairly functional and useful.
The only thing I am aware that can be improved is handing USING joins, which can be done in a separate PR - this one is big enough as it is.

mihaibudiu · 2024-08-13T06:40:54Z

I have tagged this with "will merge soon", please untag if you plan to review or disagree.

suibianwanwank

LGTM

suibianwanwank · 2024-08-14T03:07:13Z

core/src/main/java/org/apache/calcite/sql/validate/SqlValidatorImpl.java

+      }
+      if (kind == SqlKind.AND) {
+        List<SqlNode> operands = call.getOperandList();
+        for (SqlNode operand : operands) {


It seems that there might still be an issue here. If the condition is a.id = b.id AND a.id2 = b.id2 AND a.id3 = b.id3, this might not pass as expected because the conditions in SqlNode are not in the same operandList.

In Calcite AND can have N operands and I believe that there is a pass prior to this which will make sure that a sequence of AND operators is flattened into a single operator.

It look like that is only true for RexNodes, so you are right, I will have to handle this case too.

I have fixed this case and added a test. Great observation.

Looks good✅

Signed-off-by: Mihai Budiu <[email protected]>

sonarqubecloud · 2024-08-14T19:06:16Z

Quality Gate passed

Issues
39 New issues
0 Accepted issues

Measures
0 Security Hotspots
85.5% Coverage on New Code
1.5% Duplication on New Code

See analysis details on SonarCloud

yashmayya · 2025-04-24T06:42:31Z

core/src/main/codegen/templates/Parser.jj

    e2 = TableRef1(ExprContext.ACCEPT_QUERY_OR_JOIN)
    (
+        [ <MATCH_CONDITION> matchCondition = Expression(ExprContext.ACCEPT_SUB_QUERY) ]
        <ON> { on = JoinConditionType.ON.symbol(getPos()); }


@mihaibudiu this means that the ON clause is mandatory for ASOF joins as well, is that intentional? Snowflake's ASOF JOIN only requires the MATCH_CONDITION, with ON / USING being optional - https://docs.snowflake.com/en/sql-reference/constructs/asof-join#syntax.

I guess that it is mandatory with this implementation
And you can't just use 'true' either, since it requires an equijoin

And you can't just use 'true' either, since it requires an equijoin

Actually, this does seem to work because the ConjunctionOfEqualities class in SqlValidatorImpl doesn't override the literal visit method of SqlShuttle so ConjunctionOfEqualities.illegal retains its default value of false for a join condition like ON true.

mihaibudiu mentioned this pull request Jul 25, 2024

Support incremental AsOf joins in the compiler feldera/feldera#2009

Closed

14 tasks

mihaibudiu force-pushed the issue6372 branch from e5ca23e to 1943825 Compare July 25, 2024 05:10

mihaibudiu force-pushed the issue6372 branch 3 times, most recently from 26a1aa6 to d4ec7aa Compare July 25, 2024 20:58

YiwenWu reviewed Jul 31, 2024

View reviewed changes

mihaibudiu force-pushed the issue6372 branch from d4ec7aa to a91353a Compare August 7, 2024 20:28

YiwenWu reviewed Aug 8, 2024

View reviewed changes

mihaibudiu force-pushed the issue6372 branch from c043c23 to 3cbf0ee Compare August 8, 2024 17:30

YiwenWu approved these changes Aug 9, 2024

View reviewed changes

suibianwanwank reviewed Aug 9, 2024

View reviewed changes

caicancai approved these changes Aug 10, 2024

View reviewed changes

mihaibudiu force-pushed the issue6372 branch from a4c02ff to 6a0d306 Compare August 13, 2024 06:32

mihaibudiu added the LGTM-will-merge-soon Overall PR looks OK. Only minor things left. label Aug 13, 2024

suibianwanwank approved these changes Aug 13, 2024

View reviewed changes

suibianwanwank reviewed Aug 14, 2024

View reviewed changes

mihaibudiu force-pushed the issue6372 branch from 6a0d306 to 0eceb14 Compare August 14, 2024 03:50

mihaibudiu added 3 commits August 14, 2024 11:47

[CALCITE-6372] Add ASOF join to the Calcite parser

87eee9d

Signed-off-by: Mihai Budiu <[email protected]>

[CALCITE-6372] Add ASOF join to the Calcite validator

78f6427

Signed-off-by: Mihai Budiu <[email protected]>

[CALCITE-6372] Add ASOF join to the Calcite sql2rel converter

564a5f5

Signed-off-by: Mihai Budiu <[email protected]>

[CALCITE-6372] Add ASOF join to the Calcite enumerable

224fd83

Signed-off-by: Mihai Budiu <[email protected]>

mihaibudiu force-pushed the issue6372 branch from 0eceb14 to 224fd83 Compare August 14, 2024 18:52

mihaibudiu merged commit fb37dc3 into apache:main Aug 14, 2024

mihaibudiu deleted the issue6372 branch August 14, 2024 19:44

yashmayya reviewed Apr 24, 2025

View reviewed changes

yashmayya mentioned this pull request Apr 24, 2025

ASOF JOIN apache/pinot#15630

Merged

[CALCITE-6372] Support ASOF joins #3883

[CALCITE-6372] Support ASOF joins #3883

Uh oh!

Conversation

mihaibudiu commented Jul 25, 2024

Uh oh!

mihaibudiu commented Jul 25, 2024

Uh oh!

caicancai commented Jul 27, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

mihaibudiu commented Jul 27, 2024

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

caicancai commented Aug 8, 2024

Uh oh!

mihaibudiu commented Aug 8, 2024

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mihaibudiu Aug 8, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

YiwenWu Aug 9, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mihaibudiu commented Aug 8, 2024

Uh oh!

YiwenWu left a comment

caicancai commented Jul 27, 2024 •

edited

Loading

mihaibudiu Aug 8, 2024 •

edited

Loading

YiwenWu Aug 9, 2024 •

edited

Loading