Repository: tobymao/sqlglot
Pull request: Fix!(parser, optimizer): improve parsing, optimizing of nested tables, joins
Fixes #1879

Problem statement:
Using optimizer with nested joins
When using a nested join, where table b and c need to be joined before making the join to table a is not working without using parenthesis, as it will result in a parsing error. This has been filed as separate bug. However when using parenthesis at this nested join, the query is actually wrongly parsed. As the parenthesis is currently parsed as a subquery, while it is not. 

When using the optimizer on this AST, an error occurs `OptimizeError: Column 'c.id' could not be resolved for table: 'c'`, this is due to the fact that table alias c does not exist anymore if you parse the parenthesis as a subquery. 

```
import sqlglot
from sqlglot import optimizer
expr = sqlglot.parse_one("""
SELECT
 a.id
,b.test
,c.test2
FROM a
LEFT JOIN (
    b
    INNER JOIN c
        ON c.id = b.id
)
    ON b.id = a.id
""", read="tsql")

schema={
    "testcat": {
        "testdb": {
            "a": {
                "id": "INT",
            },
            "b": {
                "id": "INT",
                "test": "STRING",
            },
            "c": {
                "id": "INT",
                "test2": "STRING",
            },
        }
    }
}

expr = optimizer.optimize(
    expression=expr,
    schema=schema,
)
```

Hints from issue discussion:
maybe need to expand this out into (select * from b join c) as b
Shouldnt the scope component also be able to handle such statements and identify tables a, b and c in its most outer scope?
The problem is that `c` is used as a source (e.g. in `c.test2`), but it's not in scope because we parse it as a subquery.
FYI @10bas10 this is in-progress, I'll have a fix soon hopefully.
> FYI @10bas10 this is in-progress, I'll have a fix soon hopefully.

Hey George,

Great, thanks alot. Ill have a look as soon as its available.

Commit message: Remove retreat, manually attach alias to subquery if it's already parsed

Patch to review:
diff --git a/sqlglot/expressions.py b/sqlglot/expressions.py
index fdf02c8184..d0f8ff886e 100644
--- a/sqlglot/expressions.py
+++ b/sqlglot/expressions.py
@@ -274,12 +274,16 @@ def append(self, arg_key: str, value: t.Any) -> None:
 
     def set(self, arg_key: str, value: t.Any) -> None:
         """
-        Sets `arg_key` to `value`.
+        Sets arg_key to value.
 
         Args:
-            arg_key (str): name of the expression arg.
+            arg_key: name of the expression arg.
             value: value to set the arg to.
         """
+        if value is None:
+            self.args.pop(arg_key, None)
+            return
+
         self.args[arg_key] = value
         self._set_parent(arg_key, value)
 
diff --git a/sqlglot/optimizer/qualify_tables.py b/sqlglot/optimizer/qualify_tables.py
index 9c931d6c85..6d6a9d2903 100644
--- a/sqlglot/optimizer/qualify_tables.py
+++ b/sqlglot/optimizer/qualify_tables.py
@@ -15,8 +15,7 @@ def qualify_tables(
     schema: t.Optional[Schema] = None,
 ) -> E:
     """
-    Rewrite sqlglot AST to have fully qualified tables. Additionally, this
-    replaces "join constructs" (*) by equivalent SELECT * subqueries.
+    Rewrite sqlglot AST to have fully qualified, unnested tables.
 
     Examples:
         >>> import sqlglot
@@ -24,9 +23,18 @@ def qualify_tables(
         >>> qualify_tables(expression, db="db").sql()
         'SELECT 1 FROM db.tbl AS tbl'
         >>>
+        >>> expression = sqlglot.parse_one("SELECT * FROM (tbl)")
+        >>> qualify_tables(expression).sql()
+        'SELECT * FROM tbl AS tbl'
+        >>>
         >>> expression = sqlglot.parse_one("SELECT * FROM (tbl1 JOIN tbl2 ON id1 = id2)")
         >>> qualify_tables(expression).sql()
-        'SELECT * FROM (SELECT * FROM tbl1 AS tbl1 JOIN tbl2 AS tbl2 ON id1 = id2) AS _q_0'
+        'SELECT * FROM tbl1 AS tbl1 JOIN tbl2 AS tbl2 ON id1 = id2'
+
+    Note:
+        This rule effectively enforces a left-to-right join order, since all joins
+        are unnested. This means that the optimizer doesn't necessarily preserve the
+        original join order, e.g. when parentheses are used to specify it explicitly.
 
     Args:
         expression: Expression to qualify
@@ -36,19 +44,11 @@ def qualify_tables(
 
     Returns:
         The qualified expression.
-
-    (*) See section 7.2.1.2 in https://www.postgresql.org/docs/current/queries-table-expressions.html
     """
     next_alias_name = name_sequence("_q_")
 
     for scope in traverse_scope(expression):
         for derived_table in itertools.chain(scope.ctes, scope.derived_tables):
-            # Expand join construct
-            if isinstance(derived_table, exp.Subquery):
-                unnested = derived_table.unnest()
-                if isinstance(unnested, exp.Table):
-                    derived_table.this.replace(exp.select("*").from_(unnested.copy(), copy=False))
-
             if not derived_table.args.get("alias"):
                 alias_ = next_alias_name()
                 derived_table.set("alias", exp.TableAlias(this=exp.to_identifier(alias_)))
@@ -66,13 +66,20 @@ def qualify_tables(
                     if not source.args.get("catalog"):
                         source.set("catalog", exp.to_identifier(catalog))
 
+                # Unnest parenthesized table
+                if isinstance(source.parent, exp.Paren):
+                    source.parent.replace(source)
+
+                # Unnest joins attached in tables by appending them to the closest query
+                for join in source.args.get("joins") or []:
+                    scope.expression.append("joins", join)
+
+                source.set("joins", None)
+
                 if not source.alias:
                     source = source.replace(
                         alias(
-                            source,
-                            name or source.name or next_alias_name(),
-                            copy=True,
-                            table=True,
+                            source, name or source.name or next_alias_name(), copy=True, table=True
                         )
                     )
 
diff --git a/sqlglot/optimizer/scope.py b/sqlglot/optimizer/scope.py
index bc649e43ea..91f2e79c83 100644
--- a/sqlglot/optimizer/scope.py
+++ b/sqlglot/optimizer/scope.py
@@ -548,9 +548,6 @@ def _traverse_scope(scope):
         yield from _traverse_union(scope)
     elif isinstance(scope.expression, exp.Subquery):
         yield from _traverse_subqueries(scope)
-    elif isinstance(scope.expression, exp.Table):
-        # This case corresponds to a "join construct", i.e. (tbl1 JOIN tbl2 ON ..)
-        yield from _traverse_tables(scope)
     elif isinstance(scope.expression, exp.UDTF):
         pass
     else:
@@ -632,8 +629,9 @@ def _traverse_tables(scope):
     if from_:
         expressions.append(from_.this)
 
-    for join in scope.expression.args.get("joins") or []:
-        expressions.append(join.this)
+    for expression in (scope.expression, *scope.find_all(exp.Table)):
+        for join in expression.args.get("joins") or []:
+            expressions.append(join.this)
 
     if isinstance(scope.expression, exp.Table):
         expressions.append(scope.expression)
@@ -641,6 +639,9 @@ def _traverse_tables(scope):
     expressions.extend(scope.expression.args.get("laterals") or [])
 
     for expression in expressions:
+        if isinstance(expression, exp.Paren):
+            expression = expression.unnest()
+
         if isinstance(expression, exp.Table):
             table_name = expression.name
             source_name = expression.alias_or_name
diff --git a/sqlglot/parser.py b/sqlglot/parser.py
index f7fd6ba6b4..be58f97ee9 100644
--- a/sqlglot/parser.py
+++ b/sqlglot/parser.py
@@ -1969,10 +1969,35 @@ def _parse_select(
 
             self._match_r_paren()
 
-            # early return so that subquery unions aren't parsed again
-            # SELECT * FROM (SELECT 1) UNION ALL SELECT 1
-            # Union ALL should be a property of the top select node, not the subquery
-            return self._parse_subquery(this, parse_alias=parse_subquery_alias)
+            alias = None
+
+            # Parse a wrapped table as a Paren, instead of a Subquery. The exception to this
+            # is when there's an alias that can be applied to the parentheses, because that
+            # would shadow all wrapped table names, and so we want to parse it as a Subquery
+            # to represent the inner scope appropriately. Additionally, we want the node under
+            # the Subquery to be an actual query, so we will replace the table reference with
+            # a star query that selects from it.
+            if isinstance(this, (exp.Table, exp.Paren)):
+                # Removes redundant parentheses, e.g. in "SELECT * FROM ((tbl1 JOIN tbl2)) AS t"
+                this = t.cast(exp.Expression, this.unnest())
+
+                alias = self._parse_table_alias()
+                if not alias:
+                    return exp.paren(this, copy=False)
+
+                joins = this.args.get("joins")
+                this.set("joins", None)
+
+                this = this.replace(exp.select("*").from_(this.copy()))
+                this.set("joins", joins)
+
+            subquery = self._parse_subquery(this, parse_alias=parse_subquery_alias and not alias)
+            if subquery and alias:
+                subquery.set("alias", alias)
+
+            # We return early here so that the UNION isn't attached to the subquery by the
+            # following call to _parse_set_operations, but instead becomes the parent node
+            return subquery
         elif self._match(TokenType.VALUES):
             this = self.expression(
                 exp.Values,
@@ -2292,6 +2317,7 @@ def _parse_join(self, skip_join_token: bool = False) -> t.Optional[exp.Join]:
             else:
                 joins = None
                 self._retreat(index)
+
             kwargs["this"].set("joins", joins)
 
         return self.expression(exp.Join, **kwargs)
diff --git a/tests/fixtures/identity.sql b/tests/fixtures/identity.sql
index 162d627e38..d232a097d6 100644
--- a/tests/fixtures/identity.sql
+++ b/tests/fixtures/identity.sql
@@ -423,7 +423,6 @@ SELECT 1 INTERSECT SELECT 2
 SELECT 1 INTERSECT SELECT 2
 SELECT 1 AS delete, 2 AS alter
 SELECT * FROM (x)
-SELECT * FROM ((x))
 SELECT * FROM ((SELECT 1))
 SELECT * FROM (x CROSS JOIN foo LATERAL VIEW EXPLODE(y))
 SELECT * FROM (SELECT 1) AS x
diff --git a/tests/fixtures/optimizer/qualify_tables.sql b/tests/fixtures/optimizer/qualify_tables.sql
index 24d1b65884..7e99be9f42 100644
--- a/tests/fixtures/optimizer/qualify_tables.sql
+++ b/tests/fixtures/optimizer/qualify_tables.sql
@@ -19,25 +19,46 @@ SELECT (SELECT y.c FROM c.db.y AS y) FROM c.db.x AS x;
 SELECT * FROM x PIVOT (SUM(a) FOR b IN ('a', 'b'));
 SELECT * FROM c.db.x AS x PIVOT(SUM(a) FOR b IN ('a', 'b')) AS _q_0;
 
-----------------------------
--- Expand join constructs
-----------------------------
+----------------------------------------------------------
+-- Unnest wrapped tables / joins, expand join constructs
+----------------------------------------------------------
 
--- This is valid in Trino, so we treat the (tbl AS tbl) as a "join construct" per postgres' terminology.
-SELECT * FROM (tbl AS tbl) AS _q_0;
-SELECT * FROM (SELECT * FROM c.db.tbl AS tbl) AS _q_0;
+# title: redundant parentheses (1)
+SELECT * FROM (tbl AS tbl);
+SELECT * FROM c.db.tbl AS tbl;
+
+# title: redundant parentheses (2)
+SELECT * FROM ((((tbl AS tbl))));
+SELECT * FROM c.db.tbl AS tbl;
+
+# title: redundant parentheses around join construct
+SELECT * FROM a LEFT JOIN (b INNER JOIN c ON c.id = b.id) ON b.id = a.id;
+SELECT * FROM c.db.a AS a LEFT JOIN c.db.b AS b ON b.id = a.id INNER JOIN c.db.c AS c ON c.id = b.id;
+
+# title: nested joins converted to canonical form
+SELECT * FROM a LEFT JOIN b INNER JOIN c ON c.id = b.id ON b.id = a.id;
+SELECT * FROM c.db.a AS a LEFT JOIN c.db.b AS b ON b.id = a.id INNER JOIN c.db.c AS c ON c.id = b.id;
+
+# title: parentheses can't be omitted because alias shadows inner table names
+SELECT t.a FROM (tbl AS tbl) AS t;
+SELECT t.a FROM (SELECT * FROM c.db.tbl AS tbl) AS t;
 
+# title: outermost set of parentheses can't be omitted due to shadowing (1)
 SELECT * FROM ((tbl AS tbl)) AS _q_0;
 SELECT * FROM (SELECT * FROM c.db.tbl AS tbl) AS _q_0;
 
-SELECT * FROM (((tbl AS tbl))) AS _q_0;
+# title: outermost set of parentheses can't be omitted due to shadowing (2)
+SELECT * FROM ((((tbl AS tbl)))) AS _q_0;
 SELECT * FROM (SELECT * FROM c.db.tbl AS tbl) AS _q_0;
 
+# title: join construct with three tables in canonical form
 SELECT * FROM (tbl1 AS tbl1 JOIN tbl2 AS tbl2 ON id1 = id2 JOIN tbl3 AS tbl3 ON id1 = id3) AS _q_0;
 SELECT * FROM (SELECT * FROM c.db.tbl1 AS tbl1 JOIN c.db.tbl2 AS tbl2 ON id1 = id2 JOIN c.db.tbl3 AS tbl3 ON id1 = id3) AS _q_0;
 
+# title: join construct with three tables in canonical form and redundant set of parentheses
 SELECT * FROM ((tbl1 AS tbl1 JOIN tbl2 AS tbl2 ON id1 = id2 JOIN tbl3 AS tbl3 ON id1 = id3)) AS _q_0;
 SELECT * FROM (SELECT * FROM c.db.tbl1 AS tbl1 JOIN c.db.tbl2 AS tbl2 ON id1 = id2 JOIN c.db.tbl3 AS tbl3 ON id1 = id3) AS _q_0;
 
+# title: nested join construct in canonical form
 SELECT * FROM (tbl1 AS tbl1 JOIN (tbl2 AS tbl2 JOIN tbl3 AS tbl3 ON id2 = id3) AS _q_0 ON id1 = id3) AS _q_1;
 SELECT * FROM (SELECT * FROM c.db.tbl1 AS tbl1 JOIN (SELECT * FROM c.db.tbl2 AS tbl2 JOIN c.db.tbl3 AS tbl3 ON id2 = id3) AS _q_0 ON id1 = id3) AS _q_1;
diff --git a/tests/test_expressions.py b/tests/test_expressions.py
index f050c0ba9e..2150b2cc35 100644
--- a/tests/test_expressions.py
+++ b/tests/test_expressions.py
@@ -442,12 +442,15 @@ def test_replace(self):
         expression.find(exp.Table).replace(parse_one("y"))
         self.assertEqual(expression.sql(), "SELECT c, b FROM y")
 
-    def test_pop(self):
+    def test_arg_deletion(self):
+        # Using the pop helper method
         expression = parse_one("SELECT a, b FROM x")
         expression.find(exp.Column).pop()
         self.assertEqual(expression.sql(), "SELECT b FROM x")
+
         expression.find(exp.Column).pop()
         self.assertEqual(expression.sql(), "SELECT FROM x")
+
         expression.pop()
         self.assertEqual(expression.sql(), "SELECT FROM x")
 
@@ -455,6 +458,15 @@ def test_pop(self):
         expression.find(exp.With).pop()
         self.assertEqual(expression.sql(), "SELECT * FROM x")
 
+        # Manually deleting by setting to None
+        expression = parse_one("SELECT * FROM foo JOIN bar")
+        self.assertEqual(len(expression.args.get("joins", [])), 1)
+
+        expression.set("joins", None)
+        self.assertEqual(expression.sql(), "SELECT * FROM foo")
+        self.assertEqual(expression.args.get("joins", []), [])
+        self.assertIsNone(expression.args.get("joins"))
+
     def test_walk(self):
         expression = parse_one("SELECT * FROM (SELECT * FROM x)")
         self.assertEqual(len(list(expression.walk())), 9)
diff --git a/tests/test_parser.py b/tests/test_parser.py
index 2fa6a09604..3d8ba00806 100644
--- a/tests/test_parser.py
+++ b/tests/test_parser.py
@@ -580,3 +580,28 @@ def test_parse_properties(self):
 
     def test_parse_floats(self):
         self.assertTrue(parse_one("1. ").is_number)
+
+    def test_parse_wrapped_tables(self):
+        expr = parse_one("select * from (table)")
+        self.assertIsInstance(expr.args["from"].this, exp.Paren)
+        self.assertIsInstance(expr.args["from"].this.this, exp.Table)
+
+        expr = parse_one("select * from (((table)))")
+        self.assertIsInstance(expr.args["from"].this, exp.Paren)
+        self.assertIsInstance(expr.args["from"].this.this, exp.Table)
+
+        self.assertEqual(expr.sql(), "SELECT * FROM (table)")
+
+        expr = parse_one("select * from (tbl1 join tbl2)")
+        self.assertIsInstance(expr.args["from"].this, exp.Paren)
+
+        expr = parse_one("select * from (tbl1 join tbl2) t")
+        self.assertIsInstance(expr.args["from"].this, exp.Subquery)
+        self.assertIsInstance(expr.args["from"].this.this, exp.Select)
+
+        self.assertEqual(expr.sql(), "SELECT * FROM (SELECT * FROM tbl1, tbl2) AS t")
+
+        self.assertEqual(
+            parse_one("select * from (tbl as tbl) t").sql(),
+            "SELECT * FROM (SELECT * FROM tbl AS tbl) AS t",
+        )


Code review comments:
diff_hunk: @@ -1969,10 +1969,35 @@ def _parse_select(
 
             self._match_r_paren()
 
-            # early return so that subquery unions aren't parsed again
-            # SELECT * FROM (SELECT 1) UNION ALL SELECT 1
-            # Union ALL should be a property of the top select node, not the subquery
-            return self._parse_subquery(this, parse_alias=parse_subquery_alias)
+            alias = None
+
+            # Parse a wrapped table as a Paren, instead of a Subquery. The exception to this
+            # is when there's an alias that can be applied to the parentheses, because that
+            # would shadow all wrapped table names, and so we want to parse it as a Subquery
+            # to represent the inner scope appropriately. Additionally, we want the node under
+            # the Subquery to be an actual query, so we will replace the table reference with
+            # a star query that selects from it.
+            if isinstance(this, (exp.Table, exp.Paren)):
+                # Removes redundant parentheses, e.g. in "SELECT * FROM ((tbl1 JOIN tbl2)) AS t"
+                this = t.cast(exp.Expression, this.unnest())
+
+                alias = self._parse_table_alias()
+                if not alias:
+                    return exp.paren(this, copy=False)
+
+                joins = this.args.get("joins")
path: sqlglot/parser.py
text: @user1:
joins = this.args.pop("joins", None), don't need the set right?

diff_hunk: @@ -1969,10 +1969,35 @@ def _parse_select(
 
             self._match_r_paren()
 
-            # early return so that subquery unions aren't parsed again
-            # SELECT * FROM (SELECT 1) UNION ALL SELECT 1
-            # Union ALL should be a property of the top select node, not the subquery
-            return self._parse_subquery(this, parse_alias=parse_subquery_alias)
+            alias = None
+
+            # Parse a wrapped table as a Paren, instead of a Subquery. The exception to this
+            # is when there's an alias that can be applied to the parentheses, because that
+            # would shadow all wrapped table names, and so we want to parse it as a Subquery
+            # to represent the inner scope appropriately. Additionally, we want the node under
+            # the Subquery to be an actual query, so we will replace the table reference with
+            # a star query that selects from it.
+            if isinstance(this, (exp.Table, exp.Paren)):
+                # Removes redundant parentheses, e.g. in "SELECT * FROM ((tbl1 JOIN tbl2)) AS t"
+                this = t.cast(exp.Expression, this.unnest())
+
+                alias = self._parse_table_alias()
+                if not alias:
+                    return exp.paren(this, copy=False)
+
+                joins = this.args.get("joins")
+                this.set("joins", None)
+
+                this = this.replace(exp.select("*").from_(this.copy()))
path: sqlglot/parser.py
text: @user1:
from_ copy = False ? why do you need to call this.copy

@author:
> why do you need to call this.copy

Because otherwise we get an infinite loop.

Without the copy you first construct an AST where `this`'s parent becomes the `FROM` and then you try to replace `this` with the produced `Select` expression, which contains a reference to it.

diff_hunk: @@ -19,25 +19,46 @@ SELECT (SELECT y.c FROM c.db.y AS y) FROM c.db.x AS x;
 SELECT * FROM x PIVOT (SUM(a) FOR b IN ('a', 'b'));
 SELECT * FROM c.db.x AS x PIVOT(SUM(a) FOR b IN ('a', 'b')) AS _q_0;
 
-----------------------------
--- Expand join constructs
-----------------------------
+----------------------------------------------------------
+-- Unnest wrapped tables / joins, expand join constructs
+----------------------------------------------------------
 
--- This is valid in Trino, so we treat the (tbl AS tbl) as a "join construct" per postgres' terminology.
-SELECT * FROM (tbl AS tbl) AS _q_0;
-SELECT * FROM (SELECT * FROM c.db.tbl AS tbl) AS _q_0;
+# title: redundant parentheses (1)
+SELECT * FROM (tbl AS tbl);
+SELECT * FROM c.db.tbl AS tbl;
+
+# title: redundant parentheses (2)
+SELECT * FROM ((((tbl AS tbl))));
+SELECT * FROM c.db.tbl AS tbl;
+
+# title: redundant parentheses around join construct
+SELECT * FROM a LEFT JOIN (b INNER JOIN c ON c.id = b.id) ON b.id = a.id;
path: tests/fixtures/optimizer/qualify_tables.sql
text: @user1:
do we also handle

select from ( (b join c) join d)

so join d is not on a table, but on a paren / subquery?

@author:
Nope, parser error, good catch! Working on a fix

@user1:
can you check if it's valids ql?

@author:
Already did, it runs on postgres:

```
georgesittas=# with b as (select 1), c as (select 1), d as (select 1) select * from ( (b cross join c) cross join d);
 ?column? | ?column? | ?column?
----------+----------+----------
        1 |        1 |        1
(1 row)
```

@author:
Tried to resolve this in https://github.com/tobymao/sqlglot/pull/1894/commits/a481a6c62de037f7000470b81156bf90b3bdff7f