YQL-17269: support INTERSECT and EXCEPT without PositionalUnionAll

commit_hash:632e24794e8bcf6ef0502b7e8c031e964d28d36a

5 files changed, 145 insertions, 20 deletions

diff --git a/yql/essentials/sql/v1/format/sql_format_ut.h b/yql/essentials/sql/v1/format/sql_format_ut.h
index b61cc593936..35e95634e63 100644
--- a/yql/essentials/sql/v1/format/sql_format_ut.h
+++ b/yql/essentials/sql/v1/format/sql_format_ut.h
@@ -1548,6 +1548,34 @@ Y_UNIT_TEST(Union) {
     setup.Run(cases);
 }
 
+Y_UNIT_TEST(Intersect) {
+    TCases cases = {
+        {"select 1 intersect all select 2 intersect select 3 intersect all select 4 intersect select 5",
+            "SELECT\n\t1\nINTERSECT ALL\nSELECT\n\t2\nINTERSECT\nSELECT\n\t3\nINTERSECT ALL\nSELECT\n\t4\nINTERSECT\nSELECT\n\t5\n;\n"},
+        {"select 1 intersect all (select 2)",
+            "SELECT\n\t1\nINTERSECT ALL\n(\n\tSELECT\n\t\t2\n);\n"},
+        {"select 1 intersect distinct select 2 intersect select 3 intersect distinct select 4 intersect select 5",
+            "SELECT\n\t1\nINTERSECT DISTINCT\nSELECT\n\t2\nINTERSECT\nSELECT\n\t3\nINTERSECT DISTINCT\nSELECT\n\t4\nINTERSECT\nSELECT\n\t5\n;\n"},
+    };
+
+    TSetup setup;
+    setup.Run(cases);
+}
+
+Y_UNIT_TEST(Except) {
+    TCases cases = {
+        {"select 1 except all select 2 except select 3 except all select 4 except select 5",
+            "SELECT\n\t1\nEXCEPT ALL\nSELECT\n\t2\nEXCEPT\nSELECT\n\t3\nEXCEPT ALL\nSELECT\n\t4\nEXCEPT\nSELECT\n\t5\n;\n"},
+        {"select 1 except all (select 2)",
+            "SELECT\n\t1\nEXCEPT ALL\n(\n\tSELECT\n\t\t2\n);\n"},
+        {"select 1 except distinct select 2 except select 3 except distinct select 4 except select 5",
+            "SELECT\n\t1\nEXCEPT DISTINCT\nSELECT\n\t2\nEXCEPT\nSELECT\n\t3\nEXCEPT DISTINCT\nSELECT\n\t4\nEXCEPT\nSELECT\n\t5\n;\n"},
+    };
+
+    TSetup setup;
+    setup.Run(cases);
+}
+
 Y_UNIT_TEST(Comment) {
     TCases cases = {
         {"/*\nmulti\nline\ncomment\n*/\npragma foo = \"true\";\npragma bar = \"1\"",
diff --git a/yql/essentials/sql/v1/select.cpp b/yql/essentials/sql/v1/select.cpp
index 5a17bba297c..a2207d9ef76 100644
--- a/yql/essentials/sql/v1/select.cpp
+++ b/yql/essentials/sql/v1/select.cpp
@@ -2807,11 +2807,12 @@ TSourcePtr BuildSelectCore(
         having, std::move(winSpecs), legacyHoppingWindowSpec, std::move(terms), distinct, std::move(without), forceWithout, selectStream, settings, std::move(uniqueSets), std::move(distinctSets));
 }
 
-class TUnion: public IRealSource {
+class TSelectOp: public IRealSource {
 public:
-    TUnion(TPosition pos, TVector<TSourcePtr>&& sources, bool quantifierAll, const TWriteSettings& settings)
+    TSelectOp(TPosition pos, TVector<TSourcePtr>&& sources, const TString& op, bool quantifierAll, const TWriteSettings& settings)
         : IRealSource(pos)
         , Sources_(std::move(sources))
+        , Operator_(op)
         , QuantifierAll_(quantifierAll)
         , Settings_(settings)
     {
@@ -2848,14 +2849,30 @@ public:
 
     TNodePtr Build(TContext& ctx) override {
         TPtr res;
-        if (QuantifierAll_) {
-            if (ctx.EmitUnionMerge) {
-                res = ctx.PositionalUnionAll ? Y("UnionMergePositional") : Y("UnionMerge");
+        if (Operator_ == "union") {
+            if (QuantifierAll_) {
+                if (ctx.EmitUnionMerge) {
+                    res = ctx.PositionalUnionAll ? Y("UnionMergePositional") : Y("UnionMerge");
+                } else {
+                    res = ctx.PositionalUnionAll ? Y("UnionAllPositional") : Y("UnionAll");
+                }
+            } else {
+                res = ctx.PositionalUnionAll ? Y("UnionPositional") : Y("Union");
+            }
+        } else if (Operator_ == "intersect") {
+            if (QuantifierAll_) {
+                res = Y("IntersectAll");
+            } else {
+                res = Y("Intersect");
+            }
+        } else if (Operator_ == "except") {
+            if (QuantifierAll_) {
+                res = Y("ExceptAll");
             } else {
-                res = ctx.PositionalUnionAll ? Y("UnionAllPositional") : Y("UnionAll");
+                res = Y("Except");
             }
         } else {
-            res = ctx.PositionalUnionAll ? Y("UnionPositional") : Y("Union");
+            Y_ABORT("Invalid operator: %s", Operator_.c_str());
         }
 
         for (auto& s: Sources_) {
@@ -2879,7 +2896,7 @@ public:
     }
 
     TNodePtr DoClone() const final {
-        return MakeIntrusive<TUnion>(Pos_, CloneContainer(Sources_), QuantifierAll_, Settings_);
+        return MakeIntrusive<TSelectOp>(Pos_, CloneContainer(Sources_), Operator_, QuantifierAll_, Settings_);
     }
 
     bool IsSelect() const override {
@@ -2896,17 +2913,19 @@ public:
 
 private:
     TVector<TSourcePtr> Sources_;
+    const TString Operator_;
     bool QuantifierAll_;
     const TWriteSettings Settings_;
 };
 
-TSourcePtr BuildUnion(
+TSourcePtr BuildSelectOp(
     TPosition pos,
     TVector<TSourcePtr>&& sources,
+    const TString& op,
     bool quantifierAll,
     const TWriteSettings& settings
 ) {
-    return new TUnion(pos, std::move(sources), quantifierAll, settings);
+    return new TSelectOp(pos, std::move(sources), op, quantifierAll, settings);
 }
 
 class TOverWindowSource: public IProxySource {
diff --git a/yql/essentials/sql/v1/source.h b/yql/essentials/sql/v1/source.h
index ac69ed2eaf3..2c42dda0877 100644
--- a/yql/essentials/sql/v1/source.h
+++ b/yql/essentials/sql/v1/source.h
@@ -246,7 +246,7 @@ namespace NSQLTranslationV1 {
     TSourcePtr BuildTableSource(TPosition pos, const TTableRef& table, const TString& label = TString());
     TSourcePtr BuildInnerSource(TPosition pos, TNodePtr node, const TString& service, const TDeferredAtom& cluster, const TString& label = TString());
     TSourcePtr BuildRefColumnSource(TPosition pos, const TString& partExpression);
-    TSourcePtr BuildUnion(TPosition pos, TVector<TSourcePtr>&& sources, bool quantifierAll, const TWriteSettings& settings);
+    TSourcePtr BuildSelectOp(TPosition pos, TVector<TSourcePtr>&& sources, const TString& op, bool quantifierAll, const TWriteSettings& settings);
     TSourcePtr BuildOverWindowSource(TPosition pos, const TString& windowName, ISource* origSource);
 
     TNodePtr BuildOrderBy(TPosition pos, const TVector<TNodePtr>& keys, const TVector<bool>& order);
diff --git a/yql/essentials/sql/v1/sql_select.cpp b/yql/essentials/sql/v1/sql_select.cpp
index 04a8b1e38af..b9be35f76f1 100644
--- a/yql/essentials/sql/v1/sql_select.cpp
+++ b/yql/essentials/sql/v1/sql_select.cpp
@@ -1368,6 +1368,7 @@ TSourcePtr TSqlSelect::Build(const TRule& node, TPosition pos, TSelectKindResult
 
     TVector<TSourcePtr> sources{ std::move(first.Source)};
     bool currentQuantifier = false;
+    TString currentSelectOperator;
 
     for (int i = 0; i < blocks.size(); ++i) {
         auto& b = blocks[i];
@@ -1389,14 +1390,16 @@ TSourcePtr TSqlSelect::Build(const TRule& node, TPosition pos, TSelectKindResult
         }
 
         auto selectOp = b.GetRule_select_op1();
-        const TString token = ToLowerUTF8(Token(selectOp.GetToken1()));
-        if (token == "union") {
+        const TString selectOperator = ToLowerUTF8(Token(selectOp.GetToken1()));
+        if (selectOperator == "union") {
             // nothing
-        } else if (token == "intersect" || token == "except") {
-            Ctx_.Error() << "INTERSECT and EXCEPT are not implemented yet";
-            return nullptr;
+        } else if (selectOperator == "intersect" || selectOperator == "except") {
+            if (!IsBackwardCompatibleFeatureAvailable(Ctx_.Settings.LangVer, MakeLangVersion(2025, 3), Ctx_.Settings.BackportMode)) {
+                Ctx_.Error() << "INTERSECT and EXCEPT are available starting from 2025.03 version";
+                return nullptr;
+            }
         } else {
-            Y_ABORT("You should change implementation according to grammar changes. Invalid token: %s", token.c_str());
+            Y_ABORT("You should change implementation according to grammar changes. Invalid token: %s", selectOperator.c_str());
         }
 
         bool quantifier = false;
@@ -1411,17 +1414,19 @@ TSourcePtr TSqlSelect::Build(const TRule& node, TPosition pos, TSelectKindResult
             }
         }
 
-        if (!second && quantifier != currentQuantifier) {
-            auto source = BuildUnion(pos, std::move(sources), currentQuantifier, {});
+        // currentSelectOperator == "" <=> second == true
+        if (!second && (currentSelectOperator != selectOperator || quantifier != currentQuantifier)) {
+            auto source = BuildSelectOp(pos, std::move(sources), currentSelectOperator, currentQuantifier, {});
             sources.clear();
             sources.emplace_back(std::move(source));
         }
 
         sources.emplace_back(std::move(next.Source));
         currentQuantifier = quantifier;
+        currentSelectOperator = selectOperator;
     }
 
-    auto result = BuildUnion(pos, std::move(sources), currentQuantifier, outermostSettings);
+    auto result = BuildSelectOp(pos, std::move(sources), currentSelectOperator, currentQuantifier, outermostSettings);
 
     if (orderBy) {
         TVector<TNodePtr> groupByExpr;
diff --git a/yql/essentials/sql/v1/sql_ut_common.h b/yql/essentials/sql/v1/sql_ut_common.h
index 8b33aa8be0d..223aaa52b3b 100644
--- a/yql/essentials/sql/v1/sql_ut_common.h
+++ b/yql/essentials/sql/v1/sql_ut_common.h
@@ -1724,6 +1724,8 @@ Y_UNIT_TEST_SUITE(SqlParsingOnly) {
         UNIT_ASSERT_NO_DIFF(Err2Str(res), "<main>:1:6: Error: BATCH UPDATE is unsupported with ON\n");
     }
 
+    // UNION
+
     Y_UNIT_TEST(UnionAllTest) {
         NYql::TAstParseResult res = SqlToYql("PRAGMA DisableEmitUnionMerge; SELECT key FROM plato.Input UNION ALL select subkey FROM plato.Input;");
         UNIT_ASSERT(res.Root);
@@ -1798,6 +1800,77 @@ Y_UNIT_TEST_SUITE(SqlParsingOnly) {
         UNIT_ASSERT_VALUES_EQUAL(3, elementStat["Union"]);
     }
 
+    // INTERSECT
+
+    Y_UNIT_TEST(IntersectAllTest) {
+        NSQLTranslation::TTranslationSettings settings;
+        settings.LangVer = 202503;
+        NYql::TAstParseResult res = SqlToYqlWithSettings("SELECT key FROM plato.Input INTERSECT ALL select subkey FROM plato.Input;", settings);
+        UNIT_ASSERT(res.Root);
+
+        TWordCountHive elementStat = {{TString("IntersectAll"), 0}};
+        VerifyProgram(res, elementStat, {});
+        UNIT_ASSERT_VALUES_EQUAL(1, elementStat["IntersectAll"]);
+    }
+
+    Y_UNIT_TEST(IntersectTest) {
+        NSQLTranslation::TTranslationSettings settings;
+        settings.LangVer = 202503;
+        NYql::TAstParseResult res = SqlToYqlWithSettings("SELECT key FROM plato.Input INTERSECT select subkey FROM plato.Input;", settings);
+        UNIT_ASSERT(res.Root);
+
+        TWordCountHive elementStat = {{TString("Intersect"), 0}};
+        VerifyProgram(res, elementStat, {});
+        UNIT_ASSERT_VALUES_EQUAL(1, elementStat["Intersect"]);
+    }
+
+    Y_UNIT_TEST(IntersectDistinctTest) {
+        NSQLTranslation::TTranslationSettings settings;
+        settings.LangVer = 202503;
+        NYql::TAstParseResult res = SqlToYqlWithSettings("SELECT key FROM plato.Input INTERSECT DISTINCT select subkey FROM plato.Input;", settings);
+        UNIT_ASSERT(res.Root);
+
+        TWordCountHive elementStat = {{TString("Intersect"), 0}};
+        VerifyProgram(res, elementStat, {});
+        UNIT_ASSERT_VALUES_EQUAL(1, elementStat["Intersect"]);
+    }
+
+    // EXCEPT
+
+    Y_UNIT_TEST(ExceptAllTest) {
+        NSQLTranslation::TTranslationSettings settings;
+        settings.LangVer = 202503;
+        NYql::TAstParseResult res = SqlToYqlWithSettings("SELECT key FROM plato.Input EXCEPT ALL select subkey FROM plato.Input;", settings);
+        UNIT_ASSERT(res.Root);
+
+        TWordCountHive elementStat = {{TString("ExceptAll"), 0}};
+        VerifyProgram(res, elementStat, {});
+        UNIT_ASSERT_VALUES_EQUAL(1, elementStat["ExceptAll"]);
+    }
+
+    Y_UNIT_TEST(ExceptTest) {
+        NSQLTranslation::TTranslationSettings settings;
+        settings.LangVer = 202503;
+        NYql::TAstParseResult res = SqlToYqlWithSettings("SELECT key FROM plato.Input EXCEPT select subkey FROM plato.Input;", settings);
+        UNIT_ASSERT(res.Root);
+
+        TWordCountHive elementStat = {{TString("Except"), 0}};
+        VerifyProgram(res, elementStat, {});
+        UNIT_ASSERT_VALUES_EQUAL(1, elementStat["Except"]);
+    }
+
+    Y_UNIT_TEST(ExceptDistinctTest) {
+        NSQLTranslation::TTranslationSettings settings;
+        settings.LangVer = 202503;
+        NYql::TAstParseResult res = SqlToYqlWithSettings("SELECT key FROM plato.Input EXCEPT DISTINCT select subkey FROM plato.Input;", settings);
+        UNIT_ASSERT(res.Root);
+
+        TWordCountHive elementStat = {{TString("Except"), 0}};
+        VerifyProgram(res, elementStat, {});
+        UNIT_ASSERT_VALUES_EQUAL(1, elementStat["Except"]);
+    }
+
+
     Y_UNIT_TEST(DeclareDecimalParameter) {
         NYql::TAstParseResult res = SqlToYql("declare $value as Decimal(22,9); select $value as cnt;");
         UNIT_ASSERT(res.Root);