Repository: tobymao/sqlglot
Pull request: fix(optimizer): Fix merge_subqueries.py::rename_inner_sources()
Fixes #4245

Consider this minimum repro, for the optimizer rules `[qualify, eliminate_subqueries, merge_subqueries]`:

```SQL
WITH tbl AS (select 1 as id)
SELECT
  id
FROM (
  SELECT OTBL.id
  FROM (
    SELECT OTBL.id
    FROM (
      SELECT OTBL.id
      FROM tbl AS OTBL
      LEFT OUTER JOIN tbl AS ITBL ON OTBL.id = ITBL.id
    ) AS OTBL
    LEFT OUTER JOIN tbl AS ITBL ON OTBL.id = ITBL.id
  ) AS OTBL
  LEFT OUTER JOIN tbl AS ITBL ON OTBL.id = ITBL.id
) AS ITBL
```

After `eliminate_subqueries`, the derived tables have been lifted up as CTEs:

```SQL
WITH tbl AS (
  SELECT
    1 AS id
), otbl AS (
  SELECT
    otbl.id AS id
  FROM tbl AS otbl
  LEFT OUTER JOIN tbl AS itbl
    ON otbl.id = itbl.id
), otbl_2 AS (
  SELECT
    otbl.id AS id
  FROM otbl AS otbl
  LEFT OUTER JOIN tbl AS itbl
    ON otbl.id = itbl.id
), itbl AS (
  SELECT
    otbl.id AS id
  FROM otbl_2 AS otbl
  LEFT OUTER JOIN tbl AS itbl
    ON otbl.id = itbl.id
)
SELECT
  itbl.id AS id
FROM itbl AS itbl
```


The `merge_ctes` subrule of `merge_subqueries` will attempt to merge each inner scope/CTE to the outer scope, 
which (ignoring the OptimizerError) would ideally generate the following:

```SQL
WITH tbl AS (
  SELECT
    1 AS id
)
SELECT
  otbl.id AS id
FROM tbl AS otbl
LEFT OUTER JOIN tbl AS itbl_2
  ON otbl.id = itbl_2.id
LEFT OUTER JOIN tbl AS itbl_3
  ON otbl.id = itbl_3.id
LEFT OUTER JOIN tbl AS itbl
  ON otbl.id = itbl.id
```

To safely move parts from the inner scopes outwards the helper function `_rename_inner_sources()` is used, which attempts to rename the inner sources in case of name collisions. The bug in this procedure has to do with the fact that the `taken` set is built only from the _outer_ sources. For the example above, this is what happens in the function call that leads to the OptimizerError:

``` 
Upon entering _rename_inner_sources(outer_scope, inner_scope, alias):
----------------------------
@param alias: otbl
@param outer_scope: Scope<SELECT otbl.id AS id FROM otbl_2 AS otbl LEFT JOIN tbl AS itbl ON itbl.id = otbl.id>
Outer selected sources / taken set: {'otbl', 'itbl'}

@param inner_scope: Scope<SELECT otbl.id AS id FROM tbl AS otbl LEFT JOIN tbl AS itbl_2 ON itbl_2.id = otbl.id LEFT JOIN tbl AS itbl ON itbl.id = otbl.id>
Inner selected sources: {'itbl_2', 'otbl', 'itbl'} 

conflicts:  (outer_sources ∩ inner_sources) - alias = {'itbl'}

Upon leaving
----------------------------
new_name = find_new_name(taken={'otbl', 'itbl'}, conflict='itbl') -> 'itbl_2'

Renamed inner scope: Scope<SELECT otbl.id AS id FROM tbl AS otbl LEFT JOIN tbl AS itbl_2 ON itbl_2.id = otbl.id LEFT JOIN tbl AS itbl_2 ON itbl_2.id = otbl.id> 
```

Notice how `itbl_2` was already an _inner_ source but was incorrectly generated again to replace `ITBL` as it wasn't a part of `taken`, leading to duplicate aliases.

This PR solves this by extending the `taken` set to be the union of outer & inner selected sources.

Problem statement:
Optimizer fails when trying to optimize a query with joins and reused alias
Optimizer fails to run when a table alias is reused:
Read dialect: trino

SQL:
```
SELECT
  COUNT(DISTINCT (
    "order_detail.count"
  )) AS "C1"
FROM (
  SELECT
    "OTBL"."order_detail.count"
  FROM (
    SELECT
      "OTBL"."order_detail.menu_item_id",
      "OTBL"."order_detail.count",
      "OTBL"."order_header.location_id",
      "OTBL"."order_header.order_date",
      "OTBL"."date.date",
      "OTBL"."date.month_name",
      "ITBL"."location.location_id",
      "ITBL"."location.region"
    FROM (
      SELECT
        "OTBL"."order_detail.menu_item_id",
        "OTBL"."order_detail.count",
        "OTBL"."order_header.location_id",
        "OTBL"."order_header.order_date",
        "ITBL"."date.date",
        "ITBL"."date.month_name",
      FROM "tasty_bytes__pbi_acceleration"."world"."world" AS "OTBL"
      LEFT OUTER JOIN "tasty_bytes__pbi_acceleration"."world"."world" AS "ITBL"
        ON (
          "OTBL"."order_header.order_date" = "ITBL"."date.date"
        )
    ) AS "OTBL"
    LEFT OUTER JOIN "tasty_bytes__pbi_acceleration"."world"."world" AS "ITBL"
      ON (
        "OTBL"."order_header.location_id" = CAST("ITBL"."location.location_id" AS DOUBLE)
      )
  ) AS "OTBL"
  LEFT OUTER JOIN "tasty_bytes__pbi_acceleration"."world"."world" AS "ITBL"
    ON (
      "OTBL"."order_detail.menu_item_id" = "ITBL"."menu.menu_item_id"
    )
  WHERE
    (
      "ITBL"."menu.menu_type" is not null
      AND "OTBL"."date.month_name" = 'Apr'
    )
    AND "OTBL"."location.region" IS NULL
) AS "ITBL"
```

Code:
```
parsed =  parse_one(sql, dialect=Dialects.TRINO)
optimized = optimize(parsed, dialect=Dialects.TRINO)
```

error:
AssertionError: [{'locations': [{'column': 17, 'line': 3}], 'message': 'Alias already used: ITBL_2'

(error raised in merge_subqueries -> merge_ctes -> _merge_order -> scope::selected_sources)

Hints from issue discussion:

Commit message: fix(optimizer): Fix rename_inner_sources for merge_subqueries rule

Patch to review:
diff --git a/sqlglot/optimizer/merge_subqueries.py b/sqlglot/optimizer/merge_subqueries.py
index 603f5df0c4..bd268f63f3 100644
--- a/sqlglot/optimizer/merge_subqueries.py
+++ b/sqlglot/optimizer/merge_subqueries.py
@@ -227,10 +227,13 @@ def _rename_inner_sources(outer_scope, inner_scope, alias):
         inner_scope (sqlglot.optimizer.scope.Scope)
         alias (str)
     """
-    taken = set(outer_scope.selected_sources)
-    conflicts = taken.intersection(set(inner_scope.selected_sources))
+    inner_selected_sources_set = set(inner_scope.selected_sources)
+    outer_selected_sources_set = set(outer_scope.selected_sources)
+    conflicts = outer_selected_sources_set.intersection(inner_selected_sources_set)
     conflicts -= {alias}
 
+    taken = outer_selected_sources_set.union(inner_selected_sources_set)
+
     for conflict in conflicts:
         new_name = find_new_name(taken, conflict)
 
diff --git a/tests/fixtures/optimizer/merge_subqueries.sql b/tests/fixtures/optimizer/merge_subqueries.sql
index ce5a435119..e39e7d1709 100644
--- a/tests/fixtures/optimizer/merge_subqueries.sql
+++ b/tests/fixtures/optimizer/merge_subqueries.sql
@@ -446,3 +446,21 @@ SELECT
   1 AS a;
 WITH q AS (SELECT x.a AS a FROM x AS x ORDER BY x.a) SELECT q.a AS a FROM q AS q UNION ALL SELECT 1 AS a;
 
+# title: Consecutive inner - outer conflicting names
+WITH tbl AS (select 1 as id)
+SELECT
+  id
+FROM (
+  SELECT OTBL.id
+  FROM (
+    SELECT OTBL.id
+    FROM (
+      SELECT OTBL.id
+      FROM tbl AS OTBL
+      LEFT OUTER JOIN tbl AS ITBL ON OTBL.id = ITBL.id
+    ) AS OTBL
+    LEFT OUTER JOIN tbl AS ITBL ON OTBL.id = ITBL.id
+  ) AS OTBL
+  LEFT OUTER JOIN tbl AS ITBL ON OTBL.id = ITBL.id
+) AS ITBL;
+WITH tbl AS (SELECT 1 AS id) SELECT OTBL.id AS id FROM tbl AS OTBL LEFT OUTER JOIN tbl AS ITBL_2 ON OTBL.id = ITBL_2.id LEFT OUTER JOIN tbl AS ITBL_3 ON OTBL.id = ITBL_3.id LEFT OUTER JOIN tbl AS ITBL ON OTBL.id = ITBL.id;


Code review comments:
diff_hunk: @@ -227,10 +227,13 @@ def _rename_inner_sources(outer_scope, inner_scope, alias):
         inner_scope (sqlglot.optimizer.scope.Scope)
         alias (str)
     """
-    taken = set(outer_scope.selected_sources)
-    conflicts = taken.intersection(set(inner_scope.selected_sources))
+    inner_selected_sources_set = set(inner_scope.selected_sources)
+    outer_selected_sources_set = set(outer_scope.selected_sources)
+    conflicts = outer_selected_sources_set.intersection(inner_selected_sources_set)
path: sqlglot/optimizer/merge_subqueries.py
text: @user1:
[Nit] I'd name these as `inner_taken` and `outer_taken` for brevity.