Repository: tobymao/sqlglot

Issue:
AST + parsing support for `MATCH_RECOGNIZE`
Snowflake implements `MATCH_RECOGNIZE`, which sqlglot doesn't seem to currently parse. I believe Oracle also implements `MATCH_RECOGNIZE`.

https://docs.snowflake.com/en/sql-reference/constructs/match_recognize.html

I'd be happy to provide a PR for this, but won't be able to get to it for a few weeks.

Discussion:
tobymao: @barakalon i'm not sure how to parse a regex for example

select 
match_recognize(
pattern (^+$s) 
)

i'm thinking of two ways... in snowflake/oracle tokenizers, hardcode looking for regex in pattern (i'll just serialize the strings)

another more radical approach is by leveraging the parser's debug sql string (we use parser.sql in order show more context in debug / error messages) the parser has access to the original SQL string which i could extract the text as is.

the latter idea is interesting and could have other uses
barakalon: Interesting.

"hardcode looking for regex in pattern" feels purer to me. I.e. it seems reasonable that certain token types would kickoff sub-tokenizers. 

"leveraging the parser's debug sql string" feels hacky but practical if the first option is too invasive.

(Take that all with a grain of salt - I haven't spent much time with the tokenizer)
tobymao: @barakalon i ended up going with the sql string approach. the issue is the tokenizer has not context so i don't know to kick off something

Patch:
diff --git a/sqlglot/dialects/oracle.py b/sqlglot/dialects/oracle.py
index 86caa6b1..67d791d2 100644
--- a/sqlglot/dialects/oracle.py
+++ b/sqlglot/dialects/oracle.py
@@ -74,13 +74,16 @@ class Oracle(Dialect):
         def query_modifiers(self, expression, *sqls):
             return csv(
                 *sqls,
-                *[self.sql(sql) for sql in expression.args.get("laterals", [])],
-                *[self.sql(sql) for sql in expression.args.get("joins", [])],
+                *[self.sql(sql) for sql in expression.args.get("joins") or []],
+                self.sql(expression, "match"),
+                *[self.sql(sql) for sql in expression.args.get("laterals") or []],
                 self.sql(expression, "where"),
                 self.sql(expression, "group"),
                 self.sql(expression, "having"),
                 self.sql(expression, "qualify"),
-                self.sql(expression, "window"),
+                self.seg("WINDOW ") + self.expressions(expression, "windows", flat=True)
+                if expression.args.get("windows")
+                else "",
                 self.sql(expression, "distribute"),
                 self.sql(expression, "sort"),
                 self.sql(expression, "cluster"),
@@ -99,6 +102,7 @@ class Oracle(Dialect):
     class Tokenizer(tokens.Tokenizer):
         KEYWORDS = {
             **tokens.Tokenizer.KEYWORDS,
+            "MATCH_RECOGNIZE": TokenType.MATCH_RECOGNIZE,
             "MINUS": TokenType.EXCEPT,
             "START": TokenType.BEGIN,
             "TOP": TokenType.TOP,
diff --git a/sqlglot/dialects/snowflake.py b/sqlglot/dialects/snowflake.py
index 6225a53f..9ffe784c 100644
--- a/sqlglot/dialects/snowflake.py
+++ b/sqlglot/dialects/snowflake.py
@@ -195,6 +195,7 @@ class Snowflake(Dialect):
         KEYWORDS = {
             **tokens.Tokenizer.KEYWORDS,
             "EXCLUDE": TokenType.EXCEPT,
+            "MATCH_RECOGNIZE": TokenType.MATCH_RECOGNIZE,
             "RENAME": TokenType.REPLACE,
             "TIMESTAMP_LTZ": TokenType.TIMESTAMPLTZ,
             "TIMESTAMP_NTZ": TokenType.TIMESTAMP,
diff --git a/sqlglot/expressions.py b/sqlglot/expressions.py
index b93f00fe..6aef4361 100644
--- a/sqlglot/expressions.py
+++ b/sqlglot/expressions.py
@@ -1232,6 +1232,18 @@ class Lateral(UDTF):
     arg_types = {"this": True, "view": False, "outer": False, "alias": False}
 
 
+class MatchRecognize(Expression):
+    arg_types = {
+        "partition_by": False,
+        "order": False,
+        "measures": False,
+        "rows": False,
+        "after": False,
+        "pattern": False,
+        "define": False,
+    }
+
+
 # Clickhouse FROM FINAL modifier
 # https://clickhouse.com/docs/en/sql-reference/statements/select/from/#final-modifier
 class Final(Expression):
@@ -1510,6 +1522,7 @@ class Subqueryable(Unionable):
 
 
 QUERY_MODIFIERS = {
+    "match": False,
     "laterals": False,
     "joins": False,
     "pivots": False,
diff --git a/sqlglot/generator.py b/sqlglot/generator.py
index 540ae784..3adc1cb3 100644
--- a/sqlglot/generator.py
+++ b/sqlglot/generator.py
@@ -979,10 +979,37 @@ class Generator:
 
         return f"{self.sql(expression, 'this')}{sort_order}{nulls_sort_change}"
 
+    def matchrecognize_sql(self, expression: exp.MatchRecognize) -> str:
+        partition = self.partition_by_sql(expression)
+        order = self.sql(expression, "order")
+        measures = self.sql(expression, "measures")
+        measures = self.seg(f"MEASURES {measures}") if measures else ""
+        rows = self.sql(expression, "rows")
+        rows = self.seg(rows) if rows else ""
+        after = self.sql(expression, "after")
+        after = self.seg(after) if after else ""
+        pattern = self.sql(expression, "pattern")
+        pattern = self.seg(f"PATTERN ({pattern})") if pattern else ""
+        define = self.sql(expression, "define")
+        define = self.seg(f"DEFINE {define}") if define else ""
+        body = "".join(
+            (
+                partition,
+                order,
+                measures,
+                rows,
+                after,
+                pattern,
+                define,
+            )
+        )
+        return f"{self.seg('MATCH_RECOGNIZE')} {self.wrap(body)}"
+
     def query_modifiers(self, expression: exp.Expression, *sqls: str) -> str:
         return csv(
             *sqls,
             *[self.sql(sql) for sql in expression.args.get("joins") or []],
+            self.sql(expression, "match"),
             *[self.sql(sql) for sql in expression.args.get("laterals") or []],
             self.sql(expression, "where"),
             self.sql(expression, "group"),
@@ -1091,8 +1118,7 @@ class Generator:
     def window_sql(self, expression: exp.Window) -> str:
         this = self.sql(expression, "this")
 
-        partition = self.expressions(expression, key="partition_by", flat=True)
-        partition = f"PARTITION BY {partition}" if partition else ""
+        partition = self.partition_by_sql(expression)
 
         order = expression.args.get("order")
         order_sql = self.order_sql(order, flat=True) if order else ""
@@ -1112,6 +1138,10 @@ class Generator:
 
         return f"{this} ({window_args.strip()})"
 
+    def partition_by_sql(self, expression: exp.Window | exp.MatchRecognize) -> str:
+        partition = self.expressions(expression, key="partition_by", flat=True)
+        return f"PARTITION BY {partition}" if partition else ""
+
     def window_spec_sql(self, expression: exp.WindowSpec) -> str:
         kind = self.sql(expression, "kind")
         start = csv(self.sql(expression, "start"), self.sql(expression, "start_side"), sep=" ")
diff --git a/sqlglot/parser.py b/sqlglot/parser.py
index 77ddb2b1..078e1c79 100644
--- a/sqlglot/parser.py
+++ b/sqlglot/parser.py
@@ -585,6 +585,7 @@ class Parser(metaclass=_Parser):
     }
 
     QUERY_MODIFIER_PARSERS = {
+        "match": lambda self: self._parse_match_recognize(),
         "where": lambda self: self._parse_where(),
         "group": lambda self: self._parse_group(),
         "having": lambda self: self._parse_having(),
@@ -1038,6 +1039,11 @@ class Parser(metaclass=_Parser):
             this=self._parse_var_or_string() or self._parse_number() or self._parse_id_var(),
         )
 
+    def _parse_partition_by(self) -> t.List[t.Optional[exp.Expression]]:
+        if self._match(TokenType.PARTITION_BY):
+            return self._parse_csv(self._parse_conjunction)
+        return []
+
     def _parse_partitioned_by(self) -> exp.Expression:
         self._match(TokenType.EQ)
         return self.expression(
@@ -1457,6 +1463,87 @@ class Parser(metaclass=_Parser):
             exp.From, comments=self._prev_comments, expressions=self._parse_csv(self._parse_table)
         )
 
+    def _parse_match_recognize(self) -> t.Optional[exp.Expression]:
+        if not self._match(TokenType.MATCH_RECOGNIZE):
+            return None
+        self._match_l_paren()
+
+        partition = self._parse_partition_by()
+        order = self._parse_order()
+        measures = (
+            self._parse_alias(self._parse_conjunction())
+            if self._match_text_seq("MEASURES")
+            else None
+        )
+
+        if self._match_text_seq("ONE", "ROW", "PER", "MATCH"):
+            rows = exp.Var(this="ONE ROW PER MATCH")
+        elif self._match_text_seq("ALL", "ROWS", "PER", "MATCH"):
+            text = "ALL ROWS PER MATCH"
+            if self._match_text_seq("SHOW", "EMPTY", "MATCHES"):
+                text += f" SHOW EMPTY MATCHES"
+            elif self._match_text_seq("OMIT", "EMPTY", "MATCHES"):
+                text += f" OMIT EMPTY MATCHES"
+            elif self._match_text_seq("WITH", "UNMATCHED", "ROWS"):
+                text += f" WITH UNMATCHED ROWS"
+            rows = exp.Var(this=text)
+        else:
+            rows = None
+
+        if self._match_text_seq("AFTER", "MATCH", "SKIP"):
+            text = "AFTER MATCH SKIP"
+            if self._match_text_seq("PAST", "LAST", "ROW"):
+                text += f" PAST LAST ROW"
+            elif self._match_text_seq("TO", "NEXT", "ROW"):
+                text += f" TO NEXT ROW"
+            elif self._match_text_seq("TO", "FIRST"):
+                text += f" TO FIRST {self._advance_any().text}"  # type: ignore
+            elif self._match_text_seq("TO", "LAST"):
+                text += f" TO LAST {self._advance_any().text}"  # type: ignore
+            after = exp.Var(this=text)
+        else:
+            after = None
+
+        if self._match_text_seq("PATTERN"):
+            self._match_l_paren()
+
+            if not self._curr:
+                self.raise_error("Expecting )", self._curr)
+
+            paren = 1
+            start = self._find_token(self._curr, self.sql)
+
+            while self._curr and paren > 0:
+                if self._curr.token_type == TokenType.L_PAREN:
+                    paren += 1
+                if self._curr.token_type == TokenType.R_PAREN:
+                    paren -= 1
+                self._advance()
+            if paren > 0:
+                self.raise_error("Expecting )", self._curr)
+            if not self._curr:
+                self.raise_error("Expecting pattern", self._curr)
+            end = self._find_token(self._prev, self.sql)
+            pattern = exp.Var(this=self.sql[start:end])
+        else:
+            pattern = None
+
+        define = (
+            self._parse_alias(self._parse_conjunction()) if self._match_text_seq("DEFINE") else None
+        )
+        self._match_r_paren()
+
+        return self.expression(
+            exp.MatchRecognize,
+            partition_by=partition,
+            order=order,
+            measures=measures,
+            rows=rows,
+            after=after,
+            pattern=pattern,
+            define=define,
+        )
+
     def _parse_lateral(self) -> t.Optional[exp.Expression]:
         outer_apply = self._match_pair(TokenType.OUTER, TokenType.APPLY)
         cross_apply = self._match_pair(TokenType.CROSS, TokenType.APPLY)
@@ -2797,14 +2884,8 @@ class Parser(metaclass=_Parser):
             return self.expression(exp.Window, this=this, alias=self._parse_id_var(False))
 
         window_alias = self._parse_id_var(any_token=False, tokens=self.WINDOW_ALIAS_TOKENS)
-
-        partition = None
-        if self._match(TokenType.PARTITION_BY):
-            partition = self._parse_csv(self._parse_conjunction)
-
+        partition = self._parse_partition_by()
         order = self._parse_order()
-
-        spec = None
         kind = self._match_set((TokenType.ROWS, TokenType.RANGE)) and self._prev.text
 
         if kind:
@@ -2821,6 +2902,8 @@ class Parser(metaclass=_Parser):
                 end=end["value"],
                 end_side=end["side"],
             )
+        else:
+            spec = None
 
         self._match_r_paren()
 
diff --git a/sqlglot/tokens.py b/sqlglot/tokens.py
index 19dd1d61..80ca3034 100644
--- a/sqlglot/tokens.py
+++ b/sqlglot/tokens.py
@@ -22,6 +22,7 @@ class TokenType(AutoName):
     DCOLON = auto()
     SEMICOLON = auto()
     STAR = auto()
+    BACKSLASH = auto()
     SLASH = auto()
     LT = auto()
     LTE = auto()
@@ -219,6 +220,7 @@ class TokenType(AutoName):
     LOCAL = auto()
     LOCATION = auto()
     MAP = auto()
+    MATCH_RECOGNIZE = auto()
     MATERIALIZED = auto()
     MERGE = auto()
     MOD = auto()
@@ -414,6 +416,7 @@ class Tokenizer(metaclass=_Tokenizer):
         "+": TokenType.PLUS,
         ";": TokenType.SEMICOLON,
         "/": TokenType.SLASH,
+        "\\": TokenType.BACKSLASH,
         "*": TokenType.STAR,
         "~": TokenType.TILDA,
         "?": TokenType.PLACEHOLDER,


Test patch:
diff --git a/tests/dialects/test_dialect.py b/tests/dialects/test_dialect.py
index f1144cec..5a13655c 100644
--- a/tests/dialects/test_dialect.py
+++ b/tests/dialects/test_dialect.py
@@ -9,9 +9,9 @@ class Validator(unittest.TestCase):
     def parse_one(self, sql):
         return parse_one(sql, read=self.dialect)
 
-    def validate_identity(self, sql, write_sql=None):
+    def validate_identity(self, sql, write_sql=None, pretty=False):
         expression = self.parse_one(sql)
-        self.assertEqual(write_sql or sql, expression.sql(dialect=self.dialect))
+        self.assertEqual(write_sql or sql, expression.sql(dialect=self.dialect, pretty=pretty))
         return expression
 
     def validate_all(self, sql, read=None, write=None, pretty=False, identify=False):
diff --git a/tests/dialects/test_snowflake.py b/tests/dialects/test_snowflake.py
index 7bac1663..f3e8e24e 100644
--- a/tests/dialects/test_snowflake.py
+++ b/tests/dialects/test_snowflake.py
@@ -571,3 +571,35 @@ FROM persons AS p, LATERAL FLATTEN(input => p.c, path => 'contact') AS f, LATERA
                 "spark": "DESCRIBE db.table",
             },
         )
+
+    def test_match_recognize(self):
+        for row in (
+            "ONE ROW PER MATCH",
+            "ALL ROWS PER MATCH",
+            "ALL ROWS PER MATCH SHOW EMPTY MATCHES",
+            "ALL ROWS PER MATCH OMIT EMPTY MATCHES",
+            "ALL ROWS PER MATCH WITH UNMATCHED ROWS",
+        ):
+            for after in (
+                "AFTER MATCH SKIP",
+                "AFTER MATCH SKIP PAST LAST ROW",
+                "AFTER MATCH SKIP TO NEXT ROW",
+                "AFTER MATCH SKIP TO FIRST x",
+                "AFTER MATCH SKIP TO LAST x",
+            ):
+                self.validate_identity(
+                    f"""SELECT
+  *
+FROM x
+MATCH_RECOGNIZE (
+  PARTITION BY a, b
+  ORDER BY
+    x DESC
+  MEASURES y AS b
+  {row}
+  {after}
+  PATTERN (^ S1 S2*? ( {{- S3 -}} S4 )+ | PERMUTE(S1, S2){{1,2}} $)
+  DEFINE x AS y
+)""",
+                    pretty=True,
+                )