YQL-20307: Support inline subqueries

- Alter grammar to support inline subqueries.
- Support inline subqueries in `sql/v1` (translator).
- Introduce `sql/v1/proto_ast/parse_tree.h` for reusable parse tree predicates.
- Support inline subqueries in `sql/v1/format`.
- Support inline subqueries in `sql/v1/complete`.
- Add some SQL-tests.
- Pass all tests.
commit_hash:075b2240778d071e1c7542f912d3cc83019ef849

19 files changed, 291 insertions, 0 deletions

diff --git a/yql/essentials/tests/sql/suites/select_op/select_op_precedence_named_node.yql b/yql/essentials/tests/sql/suites/select_op/select_op_precedence_named_node.yql
new file mode 100644
index 00000000000..06b36ee3b3f
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/select_op/select_op_precedence_named_node.yql
@@ -0,0 +1,34 @@
+$t1 = (
+    (SELECT * FROM (VALUES (1), (2)) AS t (x))
+UNION
+    (SELECT * FROM (VALUES (2), (3)) AS t (x))
+    INTERSECT
+    (SELECT * FROM (VALUES (3)) AS t (x))
+);
+
+
+$t2 = (
+(SELECT * FROM (VALUES (3)) AS t (x))
+UNION
+(SELECT * FROM (VALUES (2)) AS t (x))
+EXCEPT
+(SELECT * FROM (VALUES (3)) AS t (x))
+);
+
+$t3 = (
+    (SELECT * FROM (VALUES (1)) AS t (x))
+UNION
+    (SELECT * FROM (VALUES (2)) AS t (x))
+    INTERSECT
+    (SELECT * FROM (VALUES (2), (3)) AS t (x))
+EXCEPT
+    (SELECT * FROM (VALUES (3)) AS t (x))
+UNION
+    (SELECT * FROM (VALUES (4), (3)) AS t (x))
+EXCEPT
+    (SELECT * FROM (VALUES (4)) AS t (x))
+);
+
+SELECT * FROM $t1;
+SELECT * FROM $t2;
+SELECT * FROM $t3;
diff --git a/yql/essentials/tests/sql/suites/subselect/aggregate.yql b/yql/essentials/tests/sql/suites/subselect/aggregate.yql
new file mode 100644
index 00000000000..50f529522f3
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/aggregate.yql
@@ -0,0 +1,15 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>,
+    <|k: 2, v: 2|>,
+    <|k: 3, v: 3|>,
+    <|k: 4, v: 4|>,
+    <|k: 5, v: 5|>,
+]);
+
+SELECT Sum(3) AS x FROM $input;
+
+SELECT Sum((SELECT 3)) AS x FROM $input;
+
+SELECT Sum((SELECT Avg(v) FROM $input)) AS x FROM $input;
+
+SELECT Sum((SELECT Avg(v) FROM $input WHERE v == 3)) AS x FROM $input;
diff --git a/yql/essentials/tests/sql/suites/subselect/aggregate_over.yql b/yql/essentials/tests/sql/suites/subselect/aggregate_over.yql
new file mode 100644
index 00000000000..7e81e3a08f0
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/aggregate_over.yql
@@ -0,0 +1,19 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>,
+    <|k: 2, v: 2|>,
+    <|k: 3, v: 3|>,
+    <|k: 4, v: 4|>,
+    <|k: 5, v: 5|>,
+]);
+
+SELECT Sum(3) OVER w AS x FROM $input
+WINDOW w AS (PARTITION BY 3 ORDER BY k);
+
+SELECT Sum((SELECT 3)) OVER w AS x FROM $input
+WINDOW w AS (PARTITION BY 3 ORDER BY k);
+
+SELECT Sum((SELECT Avg(v) FROM $input)) OVER w AS x FROM $input
+WINDOW w AS (PARTITION BY 3 ORDER BY k);
+
+SELECT Sum((SELECT Avg(v) FROM $input WHERE v == 3)) OVER w AS x FROM $input
+WINDOW w AS (PARTITION BY 3 ORDER BY k);
diff --git a/yql/essentials/tests/sql/suites/subselect/default.cfg b/yql/essentials/tests/sql/suites/subselect/default.cfg
new file mode 100644
index 00000000000..617474f8d63
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/default.cfg
@@ -0,0 +1 @@
+langver 2025.04
diff --git a/yql/essentials/tests/sql/suites/subselect/flatten_by.yql b/yql/essentials/tests/sql/suites/subselect/flatten_by.yql
new file mode 100644
index 00000000000..e38cefffb2e
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/flatten_by.yql
@@ -0,0 +1,15 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>,
+    <|k: 1, v: 2|>,
+    <|k: 1, v: 3|>,
+    <|k: 1, v: 4|>,
+    <|k: 1, v: 5|>,
+]);
+
+SELECT * FROM $input FLATTEN BY (ListFromRange(1, 3) AS x);
+
+SELECT * FROM $input FLATTEN BY (ListFromRange(1, (SELECT 3)) AS x);
+
+SELECT * FROM $input FLATTEN BY (ListFromRange(1, (SELECT Avg(v) FROM $input)) AS x);
+
+SELECT * FROM $input FLATTEN BY (ListFromRange(1, (SELECT Avg(v) FROM $input WHERE v == 3)) AS x);
diff --git a/yql/essentials/tests/sql/suites/subselect/group_by_no_source.sqlx b/yql/essentials/tests/sql/suites/subselect/group_by_no_source.sqlx
new file mode 100644
index 00000000000..ceb278835b2
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/group_by_no_source.sqlx
@@ -0,0 +1,9 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>, <|k: 2, v: 1|>,
+    <|k: 1, v: 2|>, <|k: 2, v: 2|>,
+    <|k: 1, v: 3|>, <|k: 2, v: 3|>,
+    <|k: 1, v: 4|>, <|k: 2, v: 4|>,
+    <|k: 1, v: 5|>, <|k: 2, v: 5|>,
+]);
+
+SELECT k, Avg(v) FROM $input GROUP BY (SELECT 3) AS k;
diff --git a/yql/essentials/tests/sql/suites/subselect/group_by_source.sqlx b/yql/essentials/tests/sql/suites/subselect/group_by_source.sqlx
new file mode 100644
index 00000000000..021948f79b1
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/group_by_source.sqlx
@@ -0,0 +1,9 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>, <|k: 2, v: 1|>,
+    <|k: 1, v: 2|>, <|k: 2, v: 2|>,
+    <|k: 1, v: 3|>, <|k: 2, v: 3|>,
+    <|k: 1, v: 4|>, <|k: 2, v: 4|>,
+    <|k: 1, v: 5|>, <|k: 2, v: 5|>,
+]);
+
+SELECT k, Avg(v) FROM $input GROUP BY (SELECT Avg(v) FROM $input) AS k;
diff --git a/yql/essentials/tests/sql/suites/subselect/group_by_source_filter.sqlx b/yql/essentials/tests/sql/suites/subselect/group_by_source_filter.sqlx
new file mode 100644
index 00000000000..20fe7ca9696
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/group_by_source_filter.sqlx
@@ -0,0 +1,9 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>, <|k: 2, v: 1|>,
+    <|k: 1, v: 2|>, <|k: 2, v: 2|>,
+    <|k: 1, v: 3|>, <|k: 2, v: 3|>,
+    <|k: 1, v: 4|>, <|k: 2, v: 4|>,
+    <|k: 1, v: 5|>, <|k: 2, v: 5|>,
+]);
+
+SELECT k, Avg(v) FROM $input GROUP BY (SELECT Avg(v) FROM $input WHERE v == 3) AS k;
diff --git a/yql/essentials/tests/sql/suites/subselect/having.yql b/yql/essentials/tests/sql/suites/subselect/having.yql
new file mode 100644
index 00000000000..a041651aa6e
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/having.yql
@@ -0,0 +1,13 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>, <|k: 2, v: 1|>,
+    <|k: 1, v: 2|>, <|k: 2, v: 2|>,
+    <|k: 1, v: 3|>, <|k: 2, v: 3|>,
+    <|k: 1, v: 4|>, <|k: 2, v: 4|>,
+    <|k: 1, v: 5|>, <|k: 2, v: 5|>,
+]);
+
+SELECT k, Avg(v) FROM $input GROUP BY k HAVING Avg(v) == (SELECT 3);
+
+SELECT k, Avg(v) FROM $input GROUP BY k HAVING Avg(v) == (SELECT Avg(v) FROM $input);
+
+SELECT k, Avg(v) FROM $input GROUP BY k HAVING Avg(v) == (SELECT Avg(v) FROM $input WHERE v == 3);
diff --git a/yql/essentials/tests/sql/suites/subselect/limit.yql b/yql/essentials/tests/sql/suites/subselect/limit.yql
new file mode 100644
index 00000000000..ae8c84cc068
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/limit.yql
@@ -0,0 +1,12 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>,
+    <|k: 2, v: 2|>,
+    <|k: 3, v: 3|>,
+    <|k: 4, v: 4|>,
+    <|k: 5, v: 5|>,
+]);
+
+SELECT * FROM $input LIMIT CAST(3 AS UInt64);
+SELECT * FROM $input LIMIT CAST((SELECT 3) AS UInt64);
+SELECT * FROM $input LIMIT CAST((SELECT Avg(v) FROM $input) AS UInt64);
+SELECT * FROM $input LIMIT CAST((SELECT Avg(v) FROM $input WHERE v == 3) AS UInt64);
diff --git a/yql/essentials/tests/sql/suites/subselect/offset.yql b/yql/essentials/tests/sql/suites/subselect/offset.yql
new file mode 100644
index 00000000000..9a6dd2300f9
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/offset.yql
@@ -0,0 +1,15 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>,
+    <|k: 2, v: 2|>,
+    <|k: 3, v: 3|>,
+    <|k: 4, v: 4|>,
+    <|k: 5, v: 5|>,
+]);
+
+SELECT * FROM $input ORDER BY k LIMIT NULL OFFSET CAST(3 AS Uint64);
+
+SELECT * FROM $input ORDER BY k LIMIT NULL OFFSET CAST((SELECT 3) AS Uint64);
+
+SELECT * FROM $input ORDER BY k LIMIT NULL OFFSET CAST((SELECT Avg(v) FROM $input) AS Uint64);
+
+SELECT * FROM $input ORDER BY k LIMIT NULL OFFSET CAST((SELECT Avg(v) FROM $input WHERE v == 3) AS Uint64);
diff --git a/yql/essentials/tests/sql/suites/subselect/order_by_no_source.sqlx b/yql/essentials/tests/sql/suites/subselect/order_by_no_source.sqlx
new file mode 100644
index 00000000000..cd3e4824fd7
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/order_by_no_source.sqlx
@@ -0,0 +1,9 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>,
+    <|k: 1, v: 2|>,
+    <|k: 1, v: 3|>,
+    <|k: 1, v: 4|>,
+    <|k: 1, v: 5|>,
+]);
+
+SELECT * FROM $input ORDER BY (SELECT 3), k, v;
diff --git a/yql/essentials/tests/sql/suites/subselect/order_by_source.sqlx b/yql/essentials/tests/sql/suites/subselect/order_by_source.sqlx
new file mode 100644
index 00000000000..9f88c26badd
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/order_by_source.sqlx
@@ -0,0 +1,9 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>,
+    <|k: 1, v: 2|>,
+    <|k: 1, v: 3|>,
+    <|k: 1, v: 4|>,
+    <|k: 1, v: 5|>,
+]);
+
+SELECT * FROM $input ORDER BY (SELECT Avg(v) FROM $input), k, v;
diff --git a/yql/essentials/tests/sql/suites/subselect/order_by_source_filter.sqlx b/yql/essentials/tests/sql/suites/subselect/order_by_source_filter.sqlx
new file mode 100644
index 00000000000..44aef1291f0
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/order_by_source_filter.sqlx
@@ -0,0 +1,9 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>,
+    <|k: 1, v: 2|>,
+    <|k: 1, v: 3|>,
+    <|k: 1, v: 4|>,
+    <|k: 1, v: 5|>,
+]);
+
+SELECT * FROM $input ORDER BY (SELECT Avg(v) FROM $input WHERE v == 3), k, v;
diff --git a/yql/essentials/tests/sql/suites/subselect/partition_by.yql b/yql/essentials/tests/sql/suites/subselect/partition_by.yql
new file mode 100644
index 00000000000..2e228bb2ccc
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/partition_by.yql
@@ -0,0 +1,32 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>,
+    <|k: 2, v: 2|>,
+    <|k: 3, v: 3|>,
+    <|k: 4, v: 4|>,
+    <|k: 5, v: 5|>,
+]);
+
+SELECT Count(*) OVER w AS x FROM $input
+WINDOW w AS (
+    PARTITION BY 3
+    ORDER BY k
+);
+
+SELECT Count(*) OVER w AS x FROM $input
+WINDOW w AS (
+    PARTITION BY (SELECT 3)
+    ORDER BY k
+);
+
+SELECT Count(*) OVER w AS x FROM $input
+WINDOW w AS (
+    PARTITION BY (SELECT Avg(v) FROM $input)
+    ORDER BY k
+);
+
+SELECT Count(*) OVER w AS x FROM $input
+WINDOW w AS (
+    PARTITION BY (SELECT Avg(v) FROM $input WHERE v == 3)
+    ORDER BY k
+);
+
diff --git a/yql/essentials/tests/sql/suites/subselect/projection.yql b/yql/essentials/tests/sql/suites/subselect/projection.yql
new file mode 100644
index 00000000000..f7012ec923e
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/projection.yql
@@ -0,0 +1,13 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>,
+    <|k: 2, v: 2|>,
+    <|k: 3, v: 3|>,
+    <|k: 4, v: 4|>,
+    <|k: 5, v: 5|>,
+]);
+
+SELECT (SELECT 3) AS x;
+
+SELECT (SELECT Avg(v) FROM $input) AS x;
+
+SELECT (SELECT Avg(v) FROM $input WHERE v == 3) AS x;
diff --git a/yql/essentials/tests/sql/suites/subselect/union.yql b/yql/essentials/tests/sql/suites/subselect/union.yql
new file mode 100644
index 00000000000..7b11993a149
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/union.yql
@@ -0,0 +1,42 @@
+$t1 = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>,
+    <|k: 2, v: 2|>,
+    <|k: 3, v: 3|>,
+    <|k: 4, v: 4|>,
+    <|k: 5, v: 5|>,
+]);
+
+$t2 = SELECT * FROM AS_TABLE([
+    <|k:  6, v:  6|>,
+    <|k:  7, v:  7|>,
+    <|k:  8, v:  8|>,
+    <|k:  9, v:  9|>,
+    <|k: 10, v: 10|>,
+]);
+
+$t3 = SELECT * FROM AS_TABLE([
+    <|k: 11, v: 11|>,
+    <|k: 12, v: 12|>,
+    <|k: 13, v: 13|>,
+    <|k: 14, v: 14|>,
+    <|k: 15, v: 15|>,
+]);
+
+SELECT
+    1  IN (  SELECT k FROM $t1  ),
+    1  IN (( SELECT k FROM $t1 )),
+    1  IN (((SELECT k FROM $t1))),
+
+    1  IN ( SELECT k FROM $t1  UNION  SELECT k FROM $t2 ),
+    6  IN ( SELECT k FROM $t1  UNION  SELECT k FROM $t2 ),
+    1  IN ( SELECT k FROM $t1  UNION (SELECT k FROM $t2)),
+    6  IN ( SELECT k FROM $t1  UNION (SELECT k FROM $t2)),
+    1  IN ((SELECT k FROM $t1) UNION  SELECT k FROM $t2 ),
+    6  IN ((SELECT k FROM $t1) UNION  SELECT k FROM $t2 ),
+    1  IN ((SELECT k FROM $t1) UNION (SELECT k FROM $t2)),
+    6  IN ((SELECT k FROM $t1) UNION (SELECT k FROM $t2)),
+
+    1  IN (SELECT k FROM $t1 UNION SELECT k FROM $t2 UNION SELECT k FROM $t3),
+    6  IN (SELECT k FROM $t1 UNION SELECT k FROM $t2 UNION SELECT k FROM $t3),
+    11 IN (SELECT k FROM $t1 UNION SELECT k FROM $t2 UNION SELECT k FROM $t3),
+;
diff --git a/yql/essentials/tests/sql/suites/subselect/where.yql b/yql/essentials/tests/sql/suites/subselect/where.yql
new file mode 100644
index 00000000000..01a51f00240
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/where.yql
@@ -0,0 +1,13 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>,
+    <|k: 2, v: 2|>,
+    <|k: 3, v: 3|>,
+    <|k: 4, v: 4|>,
+    <|k: 5, v: 5|>,
+]);
+
+SELECT * FROM $input WHERE v < (SELECT 3);
+
+SELECT * FROM $input WHERE v < (SELECT Avg(v) FROM $input);
+
+SELECT * FROM $input WHERE v < (SELECT Avg(v) FROM $input WHERE v == 3);
diff --git a/yql/essentials/tests/sql/suites/subselect/where_named_node.yql b/yql/essentials/tests/sql/suites/subselect/where_named_node.yql
new file mode 100644
index 00000000000..bb607a82cb1
--- /dev/null
+++ b/yql/essentials/tests/sql/suites/subselect/where_named_node.yql
@@ -0,0 +1,13 @@
+$input = SELECT * FROM AS_TABLE([
+    <|k: 1, v: 1|>,
+    <|k: 2, v: 2|>,
+    <|k: 3, v: 3|>,
+    <|k: 4, v: 4|>,
+    <|k: 5, v: 5|>,
+]);
+
+$x = SELECT Avg(v) FROM $input;
+
+SELECT * FROM $input WHERE v < $x;
+SELECT * FROM $input WHERE v < ($x);
+SELECT * FROM $input WHERE v < (($x));