Repository: tobymao/sqlglot
Issue category: Performance Issue

Issue:
Parsing APPLY doubles execution time per APPLY statement
SQLGlot versions: tested with 25.9.0 and 25.8.1

Dialect: "tsql" 
Description: When parsing SQL using an APPLY statement, each successive APPLY seems to double parsing time.

I was parsing a (really badly written) SQL query and noticed my code sort of just stopped. I realized that the query had an excessive number of APPLY statements (a really ridiculous number). I broke it down and wrote a dummy query where I slowly started adding apply statements one by one and noticed the query times doubled every time I added an APPLY statement.

Some quick numbers slowly adding 0..15 APPLY statements to the query:

- Testing with 0 APPLY statements
- test_apply executed in 0.001636 seconds
- Testing with 1 APPLY statements
- test_apply executed in 0.002330 seconds
- Testing with 2 APPLY statements
- test_apply executed in 0.004563 seconds
- Testing with 3 APPLY statements
- test_apply executed in 0.009903 seconds
- Testing with 4 APPLY statements
- test_apply executed in 0.019378 seconds
- Testing with 5 APPLY statements
- test_apply executed in 0.035283 seconds
- Testing with 6 APPLY statements
- test_apply executed in 0.065637 seconds
- Testing with 7 APPLY statements
- test_apply executed in 0.128544 seconds
- Testing with 8 APPLY statements
- test_apply executed in 0.258765 seconds
- Testing with 9 APPLY statements
- test_apply executed in 0.499099 seconds
- Testing with 10 APPLY statements
- test_apply executed in 1.008456 seconds
- Testing with 11 APPLY statements
- test_apply executed in 2.009916 seconds
- Testing with 12 APPLY statements
- test_apply executed in 3.927725 seconds
- Testing with 13 APPLY statements
- test_apply executed in 7.998525 seconds
- Testing with 14 APPLY statements
- test_apply executed in 16.154987 seconds
- Testing with 15 APPLY statements
- test_apply executed in 31.792223 seconds


Each time I add one more APPLY, it takes 2x longer than the prior run.

I'm attaching my sample "apply generator" that just spins out N APPLY blocks and does some very basic timing.


```
from sqlglot import parse_one
import time

num_apply = 15

def generate_apply(apply_n=0):

    apply_template = """
        OUTER APPLY (
            SELECT TOP 1
                *
            FROM my_other_catalog.my_other_schema.my_other_table_{i} b
            WHERE
                b.id = a.id
        ORDER BY
            b.a_date desc
        ) b{i}
    """
    apply = ""
    for i in range(apply_n):
        apply = apply + eval(f'f"""{apply_template}"""')

    query_template = f"""
    SELECT
        *
    FROM
        my_catalog.my_schema.my_table a
    {apply}
    """

    return query_template

def timing_decorator(func):
    def wrapper(*args, **kwargs):
        start_time = time.time()
        result = func(*args, **kwargs)
        end_time = time.time()
        print(f"{func.__name__} executed in {end_time - start_time:.6f} seconds")
        return result
    return wrapper

@timing_decorator
def test_apply(sql):
    x = parse_one(sql=sql, dialect="tsql")

for i in range(num_apply+1):
    sql = generate_apply(apply_n=i)
    print(f"Testing with {i} APPLY statements")
    #print(sql)
    test_apply(sql=sql)
```





Hints:
Also tested this using a LEFT JOIN LATERAL and dialect set to "databricks" - same timing
Thanks for the detailed report, I can reproduce these times. We'll take a look.

Patch:
diff --git a/sqlglot/parser.py b/sqlglot/parser.py
index c6b5198977..11a58346aa 100644
--- a/sqlglot/parser.py
+++ b/sqlglot/parser.py
@@ -3267,8 +3267,10 @@ def _parse_join(
             kwargs["on"] = self._parse_assignment()
         elif self._match(TokenType.USING):
             kwargs["using"] = self._parse_using_identifiers()
-        elif not isinstance(kwargs["this"], exp.Unnest) and not (
-            kind and kind.token_type == TokenType.CROSS
+        elif (
+            not (outer_apply or cross_apply)
+            and not isinstance(kwargs["this"], exp.Unnest)
+            and not (kind and kind.token_type == TokenType.CROSS)
         ):
             index = self._index
             joins: t.Optional[list] = list(self._parse_joins())


Test patch:
diff --git a/tests/test_parser.py b/tests/test_parser.py
index f06f1e11b5..ff82e08cc5 100644
--- a/tests/test_parser.py
+++ b/tests/test_parser.py
@@ -699,77 +699,19 @@ def test_pivot_columns(self):
 
     def test_parse_nested(self):
         now = time.time()
-        query = parse_one(
-            """
-            SELECT *
-            FROM a
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            LEFT JOIN b ON a.id = b.id
-            """
-        )
-
+        query = parse_one("SELECT * FROM a " + ("LEFT JOIN b ON a.id = b.id " * 38))
         self.assertIsNotNone(query)
+        self.assertLessEqual(time.time() - now, 0.1)
 
-        query = parse_one(
-            """
-            SELECT *
-            FROM a
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            LEFT JOIN UNNEST(ARRAY[])
-            """
-        )
+        now = time.time()
+        query = parse_one("SELECT * FROM a " + ("LEFT JOIN UNNEST(ARRAY[]) " * 15))
+        self.assertIsNotNone(query)
+        self.assertLessEqual(time.time() - now, 0.1)
 
+        now = time.time()
+        query = parse_one("SELECT * FROM a " + ("OUTER APPLY (SELECT * FROM b) " * 30))
         self.assertIsNotNone(query)
-        self.assertLessEqual(time.time() - now, 0.2)
+        self.assertLessEqual(time.time() - now, 0.1)
 
     def test_parse_properties(self):
         self.assertEqual(