Support nuances of the SELECT syntax: WITH, UNION, subqueries etc.

[adamziel]

Let's go through the MySQL documentation pages and make sure even the complex SELECT queries are supported by the SQLite integration plugin:

• https://dev.mysql.com/doc/refman/8.0/en/select.html
• https://dev.mysql.com/doc/refman/8.0/en/join.html
• https://dev.mysql.com/doc/refman/8.0/en/union.html
• https://dev.mysql.com/doc/refman/8.0/en/intersect.html
• https://dev.mysql.com/doc/refman/8.0/en/except.html
• https://dev.mysql.com/doc/refman/8.0/en/with.html

This likely means rewriting execute_select as more of a grammar parser or a state machine and reason about each encountered token. In contrast, the current approach is to consume all the tokens unless a tactical adjustment applies. This way we could reuse the SELECT logic for WITH, UNIONs, subqueries, etc. Currently we cannot, because the execute_select method assumes it acts on an entire query, not on a part of it.

The implementation could look like this:

// Parse WITH
if($next_token->is_operator('WITH')) {
    $this->consume_with_clause();
}

/**
 * Processes the WITH clause (https://dev.mysql.com/doc/refman/8.0/en/with.html):
 *      WITH [RECURSIVE]
 *          cte_name [(col_name [, col_name] ...)] AS (subquery)
 *          [, cte_name [(col_name [, col_name] ...)] AS (subquery)] ...
 */
protected function consume_with_clause() {
    $token = $this->rewriter->consume();
    if($token->is_operator('RECURSIVE')) {
        $token = $this->rewriter->consume();
    }
    
    while(true) {
        $table_alias = $this->rewriter->consume();
        $token = $this->rewriter->consume();
        $column_aliases = null;
        if($token->is_operator('(')) {
            $column_aliases = [];
            // ...parse column aliases...
        }

        $token = $this->rewriter->consume_assert_is_keyword( 'AS' );
        $this->consume_sub_query();
        $comma_maybe = $this->rewriter->peek();
        if(!$comma_maybe->is_operator(',')) {
            break;
        }
    }
}

/**
 * Processes the SELECT statement (https://dev.mysql.com/doc/refman/8.0/en/select.html)
 *    SELECT
 *       [ALL | DISTINCT | DISTINCTROW ]
 *       [HIGH_PRIORITY]
 *       [STRAIGHT_JOIN]
 *       [SQL_SMALL_RESULT] [SQL_BIG_RESULT] [SQL_BUFFER_RESULT]
 *       [SQL_NO_CACHE] [SQL_CALC_FOUND_ROWS]
 *        select_expr [, select_expr] ...
 */
protected function consume_select_query() {
    $this->rewriter->consume_assert_is_keyword( 'SELECT' );
    $token = $this->rewriter->peek();
    if($token->is_keyword(['ALL', 'DISTINCT', 'DISTINCTROW'])) {
         $this->rewriter->consume();
         $token = $this->rewriter->peek();
    }
    if($token->is_keyword('HIGH_PRIORITY')) {
         $this->rewriter->skip();
         $token = $this->rewriter->peek();
    }
    // ... keep going token by token, don't just skip over things like we do now
    //     with a while loop ...
    if($is_subquery) {
        $this->consume_sub_query();
    }
    // inevitably at some point:
    if($token->is_keyword('UNION')) {
        $this->consume_select_query();
    }
}

protected function consume_sub_query() {
    // ... consume a nested query ...
    // ... can it be just a SELECT query? Or can it also be something else? ...
    // ... can it have a WITH clause? ...
    // ...
    // inevitably at some point:
    $this->consume_select_query();
}

For starters, just migrating to a state machine approach would be more than enough as it would unlock support for UNIONs and easy ignoring of tokens like HIGH_PRIORITY or SQL_SMALL_RESULT.

[adamziel]

Perhaps the Rewriter model is no longer useful for this approach. Here's an alternative idea:

/**
 * Processes the SELECT statement (https://dev.mysql.com/doc/refman/8.0/en/select.html)
 *    SELECT
 *       [ALL | DISTINCT | DISTINCTROW ]
 *       [HIGH_PRIORITY]
 *       [STRAIGHT_JOIN]
 *       [SQL_SMALL_RESULT] [SQL_BIG_RESULT] [SQL_BUFFER_RESULT]
 *       [SQL_NO_CACHE] [SQL_CALC_FOUND_ROWS]
 *        select_expr [, select_expr] ...
 */
protected function consume_select_query() {
    $token = $this->next_token();
    $token->assert_is_keyword('SELECT');

    $token = $this->next_token();
    if($token->is_keyword(['ALL', 'DISTINCT', 'DISTINCTROW'])) {
         $this->append( $token );
         $token = $this->rewriter->next_token();
    }
    if($token->is_keyword('HIGH_PRIORITY')) {
         $token = $this->rewriter->next_token();
    }
    // ... keep going token by token, don't just skip over things like we do now
    //     with a while loop ...
    if($is_subquery) {
        $this->consume_sub_query();
    }
    // inevitably at some point:
    if($token->is_keyword('UNION')) {
        $this->consume_select_query();
    }
}

Importantly, we cannot just operate on strings and translate the MySQL query into the SQLite query. Some transformations require acting on the SQLite database and executing SELECTs, INSERTs etc. Therefore, the input may be a MySQL query string, but the output should be the query result, not the corresponding SQL query for SQLite.

[brandonpayton]

Intuitively, it feels like we need a thorough but lightweight syntax tree and an interpreter that explicitly handles each case.

I've started poking at that idea but don't yet have a working example to share.

[adamziel]

I've explored this and don't see any way other than switching to a full MySQL parser like the PHPMyAdmin one where we originally sourced the tokenizer from.

This is a recursive transformation problem where we need to know the subquery tree – either to rewrite them in place, or to execute them and substitute the subquery for its results.

Here's a fairly complex query that would be rather difficult to process without a parsed query tree:

WITH monthly_sales AS (
    SELECT
        employee_id,
        MONTH(sale_date) AS sale_month,
        YEAR(sale_date) AS sale_year,
        SUM(sale_amount) AS total_sales
    FROM
        sales
    GROUP BY
        employee_id, sale_month, sale_year
),
ranked_sales AS (
    SELECT
        employee_id,
        sale_month,
        sale_year,
        total_sales,
        RANK() OVER (PARTITION BY sale_year, sale_month ORDER BY total_sales DESC) AS sales_rank
    FROM
        monthly_sales
)
SELECT
    e.employee_id,
    e.first_name,
    e.last_name,
    e.department_id,
    d.department_name,
    s.sale_date,
    s.sale_amount,
    m.manager_name,
    r.total_sales,
    r.sales_rank,
    (select 2 as a from dual) as x
FROM
    employees e
    INNER JOIN sales s ON e.employee_id = s.employee_id
    LEFT JOIN departments d ON e.department_id = d.department_id
    LEFT JOIN managers m ON e.manager_id = m.manager_id
    INNER JOIN ranked_sales r ON e.employee_id = r.employee_id
    AND MONTH(s.sale_date) = r.sale_month
    AND YEAR(s.sale_date) = r.sale_year
WHERE
    e.status = 'active'
    AND r.sales_rank <= 3
    AND s.sale_date BETWEEN '2024-01-01' AND '2024-12-31'
GROUP BY
    e.employee_id,
    s.sale_date
HAVING
    SUM(s.sale_amount) > 1000
ORDER BY
    r.sale_year DESC,
    r.sale_month DESC,
    r.sales_rank ASC;
UNION
SELECT
    1
FROM DUAL
FOR UPDATE 
LOCK IN SHARE MODE

The PHPMyAdmin parser can process it just fine:

$parser = new PhpMyAdmin\SqlParser\Parser($query1);

foreach($parser->statements as $stmt) {
    // Get the first subquery in the first SELECT 
    var_dump($stmt->cteStatementParser->statements[0]->expr[10]);

	// Parse it (the Parser class is lazy)
    $subquery = $stmt->cteStatementParser->statements[0]->expr[10]->expr;
    $subparser = new PhpMyAdmin\SqlParser\Parser($subquery);

	// Get all the structured information we need:
    print_r($subparser);
}

[adamziel]

This would also make it easier to clearly reject any unsupported queries. We'd only expect values to show up in specific places of the parsed data structure, and if we get more than that then it's an unsupported query and we can bale out with a clear error message.

[adamziel]

I failed to parse the following query using \PhpMyAdmin\SqlParser\Parser:

WITH mytable as (select 1 as a, b from dual)
SELECT HIGH_PRIORITY DISTINCT 
col_a,
UPPERCASE(z),
(SELECT MAX(col_b) FROM mytable),
(SELECT MAX(col_b) FROM mytable) as max_C
FROM mytable, (SELECT hgjba, 997482686 FROM mytable) as subquery
FORCE INDEX (idx_department_id)
LEFT JOIN (select a_column_yo from mytable) as t2 
	ON (t2.id = mytable.id AND t2.id = 1) AND (select 1 from mytable) = 1896
WHERE 1 = 3
AND date_column BETWEEN (SELECT '2024-01-01') AND CONCAT('2024', '-12-31')
GROUP BY col_a, col_b
HAVING 1 = 2
UNION SELECT * from table_b
ORDER BY col_a DESC, col_b ASC 
FOR UPDATE

The output only goes to a certain level of granularity and not further. For example, (select 1 from mytable) = 1896 is treated as a single expression and I didn't find a way of splitting it to a subquery and a comparison.

I had much more luck with the greenlion/php-sql-parser library:

composer require greenlion/php-sql-parser

$parser = new PHPSQLParser();
$parsed = $parser->parse($query);
print_r($parsed);

It exposes a full AST and seems to understand every syntactic nuance, including WITH, index hints, subqueries in random places, etc.

From here, it's all about recursively rewriting the MySQL AST to a SQLite query and baleing out whenever we encounter an unsupported syntax element. This should be much more reliable as we would never accidentally retain any MySQL-specific syntax. We'll still need some of the logic already shipped with the SQLite integration plugin to rewrite function calls, SQL_CALC_FOUND_ROWS, etc.

[adamziel]

Proposal: Switching to AST for SQLite Integration

I believe the most viable path forward for the SQLite integration project is to switch from processing a token stream to processing an Abstract Syntax Tree (AST). The best way to generate an AST appears to be by adapting the MySQLParser.g4 grammar to create a small, performant non-ANTLR parser.

Why Switch from Token Parsing to AST Processing?

Current Approach: Token Stream Processing

Right now, the SQLite database integration plugin processes a stream of MySQL tokens. This method makes the code complex, as each change requires interpreting the tokens in the surrounding context. The challenges include:

• Difficulty in determining the exact meaning of syntactic elements (e.g., parentheses, uppercase text, double-quoted identifiers).
• Difficulty processing subqueries.
• Limited MySQL syntax support.

My guess is that we currently support only a small percentage of the MySQLParser.g4 syntax. While this may be sufficient for running WordPress core, there's a long tail of features we don't support (e.g., WITH, UNION) and can't easily add (e.g., nested queries).

Proposed Approach: AST Processing

Switching to AST processing would simplify and enhance our approach by providing:

• Clear, semantic interpretation of all syntax elements.
• Ability to process the full MySQL syntax.
• Easier and more maintainable code.

Here’s an example of what a declarative transform could look like using an AST:

function MySQLFunctionToSQLite($name, $args) {
    switch (strtoupper($ast['name'])) {
        case 'ASCII': return ['UNICODE', $args];

        case 'CHAR_LENGTH':
        case 'LENGTH':
            return ['LENGTH', $args];

        case 'CONCAT':
            $concatenated = [new Token("(")];
            $k = count($args);
            foreach ($args as $k => $arg) {
                $concatenated[] = $arg;
                if ($k < count($args) - 1) {
                    $concatenated[] = new Token(" || ");
                }
            }
            $concatenated[] = new Token(")");
            return new Expression($concatenated);
    }
}

Supporting another function means adding another case. Supporting another syntax element, such as INTERVAL, would mean adding another case in a different switch statement. There would be no need to reason about what the next token is or how we arrived at the current token.

Compare this to the linear token-based rewriting we do today (which is also spread over multiple locations).

Parsing MySQL queries into an AST

MySQL Workbench ANTLR grammar yields the only MySQL query parser I found that checks all these boxes:

• It produces an AST from a query string.
• It supports the full MySQL syntax.
• It has acceptable speed and memory consumption (sadly, with bad caveats).
• It can be used in Playground and, eventually, WordPress core.

On the upside, that grammar is official and exhaustive. On the downside, it's too large, slow, and memory-hungry to use as-is. However, we can still reuse it!

Issues with the ANTLR-generated MySQL query parser

ANTLR can generate code for PHP, TypeScript, and other languages. However, the mysql-workbench grammar depends on a few .c and .h files. The generated PHP and TypeScript parsers won't work without manually porting those dependencies. It wasn't too difficult, so I did it for both languages.

ANTLR parser performance

The PHP parser needs significant performance improvements before it can be used effectively, and the TypeScript parser isn't great yet, but it seems acceptable for a Playground-centric experiment.

• File size:
  • PHP parser + tokenizer: 4MB
  • TypeScript parser + tokenizer: 3.2MB
  • Minified TypeScript parser: 2MB, 355KB gzipped, and 209KB brotli-compressed
• Loading time:
  • PHP parser: 2 seconds initially; runs out of memory on complex queries.
  • TypeScript parser: Instant load time.
• Tokenization speed:
  • ~60ms for 500 test queries. That's decent, and it could be optimized further using the same techniques as WP_HTML_Tag_Processor to move character-by-character processing from a slow language like PHP or JavaScript to the underlying fast language like C.
• Parsing speed:
  • The PHP parser is quite slow, but I can't tell how slow because it runs out of memory on my test query.
  • The TypeScript parser initially took 3.3 seconds to parse, but I reduced that to 1ms – more details below.

ANTLR parser caveats

The generated TypeScript parser needed some manual adjustments, e.g., adding a missing this. prefix before the method calls, or implementing a MySQLRecognizerCommon mixin (the generated C parser would inherit from two classes, but we can't do that in TypeScript). Once adjusted, it loads instantly and parses most queries. However, it fails to parse SELECT queries including the WITH clause (as in WITH table AS (select 1) SELECT 1). The PHP parser doesn't have that issue, so I assume it can be fixed with a patch to the ANTLR TypeScript library.

A larger problem with the TypeScript parser was the parsing speed. My test query took 3.3 seconds to parse! I tracked it down to a general pitfall all predictive ALL(*) parsers suffer from – when there's a syntactic ambiguity, they perform lookaheads to figure out which branch of the grammar can resolve it. I simplified the functionCall and textStringLiteral definitions in the MySQLParser.g4 grammar file to remove the ambiguity, and the parsing time dropped to 1 millisecond! We may encounter more ambiguities, though.

The TypeScript parser is almost in good enough shape to use in Playground. That doesn't help WordPress core, though. For a reusable PHP WordPress plugin, we'd need a more performant version of the PHP parser.

Other parsers

I tested all the trustworthy-looking MySQL query parsers I could find, both PHP and non-PHP ones. Almost none could parse this valid MySQL query:

WITH mytable as (select 1 as a, b from dual)
SELECT HIGH_PRIORITY DISTINCT
	CONCAT("a", "b"),
	UPPER(z),
	col_a,
	(SELECT MAX(col_b) FROM mytable),
	(SELECT MAX(col_b) FROM mytable) as max_C
FROM 
mytable FORCE INDEX (idx_department_id),
(SELECT hgjba, 997482686 FROM mytable) as subquery
LEFT JOIN (select a_column_yo from mytable) as t2 
    ON (t2.id = mytable.id AND t2.id = 1) AND (select 1 from mytable) = 1896
WHERE 1 = 3
GROUP BY col_a, col_b
HAVING 1 = 2
FOR UPDATE
UNION SELECT * from table_cde
ORDER BY col_a DESC, col_b ASC 

Here's a list of some of the parsers I tried (yes, there was more!):

• PHP Parsers
  • phpmyadmin/sql-parser doesn't parse subqueries, doesn't support index hints, has errors with parentheses around select statements, has issues with CREATE TABLE statements, and more.
  • greenlion/PHP-SQL-Parser parses more than the PHPMyAdmin parser, e.g., subqueries, complex JOIN conditions, etc. It has critical issues, too, like incredibly slow parsing, CREATE TABLE mytable SELECT ... throws exception in PositionCalulator Line 199, Creator fails on INSERT with SET and ON DUPLICATE KEY, Identification of PRIMARY KEY depends on order, and more.
• The official MySQL-Server parser is generated from a sql_yacc.yy file. Unfortunately, that .yy file includes a lot of MySQL-Server code. It's so tightly integrated with the entire system that I don't see an easy way to reuse it as a library or generate a PHP (PHP-Yacc, pacc), JavaScript, or a WASM parser from it.
• Other parsers:
  • SQLGlot (Python) parsed all the queries I threw at it. I'm sure there are syntax nuances it wouldn't handle correctly, but it's encouraging that it only has 2 open issues and 1622 closed ones.
    • It even has a SQL -> SQL transpilation feature, but that's not useful for us here. MySQL->SQLite goes beyond transpilation. A MySQL query may require 7 SQLite queries and additional computations.
    • It's a Python library, and we can't easily reuse it. Even as WebAssembly, it would take at least a few megabytes. We could port it to PHP, but there are better places to put that effort in.
  • sqlparser-rs (Rust) couldn't correctly handle MySQL index hints and many other syntax nuances.
  • node-sql-parser (JavaScript) is generated from a PEG grammar file. It seems to be written from scratch, though, and failed to parse at least HIGH_PRIORITY DISTINCT and FORCE INDEX in my test query. Too bad! If it worked well, we could generate a PHP parser from a PEG grammar.
  • TIDB Parser (Go) parsed my test query and can even be built to WASM, but it produces a 22MB binary. I got it down to 10MB, but it's still a far cry from the bundle size we'd need for Playground. I would keep pushing if we could use WASM in PHP today, but we can't, so I don't think this is the right way forward.
  • hyrise/sql-parser (C++). It failed to parse my test query.
  • antlr/grammars-v4 MySQL grammar goes deeper into the MySQL syntax than most other parsers. Note this is a different ANTLR grammar than I discuss in the rest of this post. Unfortunately, the generated PHP parser needs 2 seconds to load and exhausts the memory limit when parsing my test query, and the TypeScript parser needed 700ms to parse it. That time grows linearly as I run more iterations, so unfortunately, it's not a cold start problem.

Next steps

I think generating a smaller and faster PHP parser is the only viable path forward.

• I wouldn't try to improve the existing MySQL parsers or build a new parser by hand. The syntax is so nuanced that we'd likely get stuck for months and always have one more issue to address.
• I wouldn't try to optimize the ANTLR-generated parser. The amount of work seems comparable to generating another parser. The ANTLR-generated parser uses a computer-generated decision table that's a huge list of numbers – therefore, we would be optimizing the parser generator itself. That's difficult! Furthermore, ANTLR outputs a predictive ALL(*) parser, which needs more lookaheads than an LALR parser would. Even a single costly ambiguity in the grammar could create a DOS attack vector for SQLite-enabled sites. MySQL queries seem to be parse-able with an LALR parser, and I would explore that direction instead.
• I wouldn't continue developing the token-processing system we have today. We're implicitly encoding the AST-building logic into the system anyway, only in a way that's difficult to modify. Every change requires interpreting the tokens in the surrounding context – something an AST would give us for free. My guess is we only support a few percent of the MySQLParser.g4 syntax currently. That may be enough to run WordPress core, but there's an extremely long tail of things we don't support (e.g., WITH, UNION) and can't easily start supporting (e.g., nested queries).

How to generate another parser from an ANTLR grammar?

The ANTLR MySQL grammar is the best resource we can lean on. It seems to be the only complete MySQL grammar definition available.

The two approaches I can think of are:

• Translate MySQLParser.g4 grammar to another format and use another parser generator. It should be possible – even though ANTLR is a tool for building ALL(*) parsers that are incompatible with LL parsers, MySQL queries seem to be fundamentally parse-able by an LALR parser – MySQL server uses a yacc-generated one. GPT might help us with the initial translation, just to validate the approach. If it proves viable, we'd need a coordinated human effort to ensure the resulting grammar is still correct.
• Use GPT to convert the grammar file straight to PHP code. Doing it by hand without validating the approach first is risky given the monumental effort it would take.

We'd also need a comprehensive test suite – I wonder if we could reuse the one from mysql-server or mysql-workbench.

CC @aristath @dmsnell @schlessera @OllieJones @brandonpayton @bgrgicak @griffbrad @akirk off the top of my head – feel free to loop in more folks as needed :-)