[Tracking] Refactor SQL Parser

[leiysky]

Part of #1217

Background

To provide a more generic parser abstraction, we need to do some refactor on the current implementation.

Generally, all of the SQL dialects follow some basic rules, with which we can design our own SQL IR(i.e. datafuse specific AST).

With this IR, we can transform the SQL queries in different dialects into the same representation.

The major idea is provide series of standard AST of Datafuse that can be directly parsed from Datafuse SQL dialect. The elements can be catagorized as:

• Expressions, represents expression entries in a SQL query including identifier, arithmetic operators and functions etc.
• Statements, represents SQL clauses, including SELECT, FROM, WHERE, GROUP BY, HAVING, ORDER BY, LIMIT and DDL statements.

Beyond this, we can provide interface like ASTTransformer to transform AST produced by other parsers(e.g. MySQL, ClickHouse, Postgres) into the standard AST.

Update: 2021.8.20

We have introduced a series of standard AST API in #1478 .

The main work during this stage is:

• Provide ability to analyze an query with AST(e.g. simple rewrting, expression binding)
• Provide a framework to build logical plan from AST, with normalization.
• Design Datafuse standard SQL Specification of Datafuse SQL #1492 and implement a parser for it (under discussing in [sqlparser] better sql parser? #866).

Tasks

High priority:

• Implement SQL parser for Datafuse standard SQL [sqlparser] better sql parser? #866
  • Evaluate SQL dialect framework [improvement]Double quotation marks are supported in arguments #1551
• Standard SQL AST
  • Introduce Datafuse standard SQL AST API @leiysky sql: introduce datafuse standard SQL AST #1477
  • Fold table references in FROM clause with CROSS JOIN @leiysky parser: Fold table references in FROM clause #1523
  • Refine object name with qualified typed fields @leiysky parser: refine object names with qualified type #1540
  • Implement Visitor utility for AST @jackwener Implement Visitor for SQL AST #1511
• Expression binding and normalization
  • Bind expression with catalog @leiysky Support expression binding with catalog #1537
  • Do type check for expressions @leiysky Support type check of expressions #1538
  • Implement rewriter for AST to help normalizing query @leiysky Introduce a framework to rewrite AST to support normalizing expressions #1539

Low priority:

• SQL dialect transformer for ClickHouse SQL
• SQL dialect transformer for MySQL
• SQL dialect transformer for Postgres
• Complete TransformerSqlparser @SGZW Implement TransformerSqlparser::transform_ddl #1512

[leiysky]

Related to #866

[leiysky]

I've just filed a PR #1478, which introduces a bunch of Datafuse standard SQL AST and a transformer from sqlparser-rs.

Welcome to review and comment.

[leiysky]

The tokenizer has been introduced in #4024

[leiysky]

Closed by #4983