[TECH DEBT]: Handle the precedence of the INTERSECT set operation in the grammar(s) rather than in code

[asnare]

Current Behavior

As part of #1227 it became clear that our grammars for set operations treat INTERSECT, UNION and EXCEPT as equivalent. However it turns out that INTERSECT has higher precedence than the others. Although this can be dealt with in code during conversion to the IR, it would be better if this was reflected by the grammar (which also simplifies the conversion to IR).

Expected Behavior

The grammars should treat INTERSECT as having higher precedence than UNION and EXCEPT.

The rules of precedence for set operations are:

1. Parentheses
2. INTERSECT
3. EXCEPT and UNION ordered from left-to-right.

Given that INTERSECT is commutative, ordering is unimportant.

Needs to be fixed in:

• TSQL (Update TSQL grammar so that INTERSECT precedence is handled there #1259)
• Snowflake (Fix Snowflake precedence of INTERSECT with respect to other set operations #1288)

References:

• https://learn.microsoft.com/en-us/sql/t-sql/language-elements/set-operators-except-and-intersect-transact-sql?view=sql-server-ver16#:~:text=following%20precedence
• https://docs.snowflake.com/en/sql-reference/operators-query#:~:text=precedence

Relevant grammar rules:

remorph/core/src/main/antlr4/com/databricks/labs/remorph/parsers/snowflake/SnowflakeParser.g4

Lines 3154 to 3158 in 932080a

	setOperators
	// TODO: Handle INTERSECT precedence in the grammar; it has higher precedence than EXCEPT and UNION ALL.
	// Reference: https://docs.snowflake.com/en/sql-reference/operators-query#:~:text=precedence
	: (UNION ALL? | EXCEPT | MINUS_ | INTERSECT) selectStatement //EXCEPT and MINUS have same SQL meaning
	;

remorph/core/src/main/antlr4/com/databricks/labs/remorph/parsers/tsql/TSqlParser.g4

Lines 2796 to 2800 in 932080a

	sqlUnion
	// TODO: Handle INTERSECT precedence in the grammar; it has higher precedence than EXCEPT and UNION ALL.
	// Reference: https://learn.microsoft.com/en-us/sql/t-sql/language-elements/set-operators-except-and-intersect-transact-sql?view=sql-server-ver16#:~:text=following%20precedence
	: (UNION ALL? | EXCEPT | INTERSECT) (querySpecification | (LPAREN queryExpression RPAREN))
	;

Changing the grammar will mean refactoring this code:

remorph/core/src/main/scala/com/databricks/labs/remorph/parsers/tsql/TSqlRelationBuilder.scala

Lines 79 to 134 in 932080a

	@tailrec
	private[this] def buildIntersectOperations(
	lhs: ir.LogicalPlan,
	remainingContexts: Seq[TSqlParser.SqlUnionContext]): ir.LogicalPlan = {
	/*
	* The sqlUnion* rule needs to be handled carefully because the grammar does not completely implement the
	* precedence rules for set operations:
	* 1. Brackets.
	* 2. INTERSECT
	* 3. UNION and EXCEPT, from left to right.
	*
	* Specifically the grammar treats INTERSECT as having the same precedence as UNION and EXCEPT, so we need to
	* handle that specially. (Brackets and left-right precedence is handled by the grammar.)
	*/
	// Start by finding the contexts up to the first INTERSECT op (if any), and gather them into a plan covering the LHS
	// of the INTERSECT op.
	val (beforeFirstIntersect, fromFirstIntersect) = remainingContexts.span(_.INTERSECT() == null)
	val gatheredLhs = beforeFirstIntersect.foldLeft(lhs)(buildSetOperation)
	// If there is no INTERSECT operation, nothing further to do.
	if (fromFirstIntersect.isEmpty) {
	gatheredLhs
	} else {
	// Before proceeding, we need to account for subsequent INTERSECT operations: to preserve left-to-right
	// precedence we can only immediately handle up to the next INTERSECT operation, if any.
	val (beforeNextIntersect, fromNextIntersect) = fromFirstIntersect.tail.span(_.INTERSECT() == null)
	val thisLogicalPlan = thisSetOperation(fromFirstIntersect.head)
	val gatheredRhs = beforeNextIntersect.foldLeft(thisLogicalPlan)(buildSetOperation)
	val thisOp = ir.SetOperation(
	gatheredLhs,
	gatheredRhs,
	ir.IntersectSetOp,
	is_all = false,
	by_name = false,
	allow_missing_columns = false)
	buildIntersectOperations(thisOp, fromNextIntersect)
	}
	}
	private[this] def thisSetOperation(ctx: TSqlParser.SqlUnionContext): ir.LogicalPlan = {
	val rhsContext = ctx match {
	case qs if qs.querySpecification() != null => qs.querySpecification()
	case qe if qe.queryExpression() != null => qe.queryExpression()
	}
	rhsContext.accept(this)
	}
	private[this] def buildSetOperation(lhs: ir.LogicalPlan, ctx: TSqlParser.SqlUnionContext): ir.LogicalPlan = {
	val setOp = ctx match {
	case u if u.UNION() != null => ir.UnionSetOp
	case e if e.EXCEPT() != null => ir.ExceptSetOp
	}
	val isAll = ctx.ALL() != null
	val rhs = thisSetOperation(ctx)
	ir.SetOperation(lhs, rhs, setOp, is_all = isAll, by_name = false, allow_missing_columns = false)
	}