search

WordPress / sqlite-database-integration

Feature Plugin to add SQLite support to WordPress. Under Development.
GNU General Public License v2.0
237 stars 41 forks source link

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

Open adamziel opened 6 months ago

adamziel commented 6 months ago

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

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 commented 6 months ago

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 commented 5 months ago

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 commented 3 months ago

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 commented 3 months ago

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 commented 3 months ago

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 commented 3 months ago

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:

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:

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:

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.

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!):

Next steps

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

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:

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 :-)

adamziel commented 3 months ago

MySQL Workbench also has an 8 years old ANTLR 3 grammar that can be used to generate an LL parser – perhaps that would do the trick?

adamziel commented 3 months ago

Also, surfacing my response to @schlessera's comment from WP-CLI/db-command:

Inputs

What would be the use-case for parsing SQLite queries?

Also, if we get different parsers for MariaDB and MySQL, then we also need different parsers for MySQL 5.7, 8.0, 8.1 etc. My hope is the same parser could handle all of these. As far as I understand, MariaDB syntax is mostly compatible with MySQL and the official list of incompatible features doesn't seem too bad at the query parsing level.

Parsing model

I don't think a Query -> Intermediate representation -> Query transpilation model is sufficient. I think we need a custom MySQL on SQLite database driver that goes beyond transpilation.

In functional terms, transpilation would be a pure function like (MySQL_Query) => SQLite_Query. However, we can only handle the general case with a function like (MySQL_Query, SQL_Connection) => () => Query_Results, meaning we also use the SQLite connection and we derive the query results not from a database query but from a computation that may involve a back-and-forth cascade of database queries and transformations.

Here's just a few examples:

That's just the tip of the iceberg. There's SELECT INTO OUTFILE, nested transactions to account for, substituting certain subqueries for actual IDs etc.

Related: SQLGlot is a SQL -> SQL transpiler build in Python. Their parser is more powerful than the one in the https://github.com/WordPress/sqlite-database-integration plugin, and yet it won't handle the MySQL -> SQLite transition for SQL_CALC_FOUND_ROWS and other MySQL features that are beyond transpilation.

adamziel commented 3 months ago

Somewhat against my own recommendation I took a stab at manually prototyping a PHP parser, but I quickly hit the wall. There's a lot of branching and decision points in that grammar. I still think it can be parsed with minimal lookaheads, but covering any useful subset of that SQL grammar with a manually-build PHP parser seems like a task for at least a few hundred hours.

This issue now hinges on finding a semi-automated workflow to convert the ANTLR grammar to a parser that can be refactored by a human and does minimal lookaheads. Two paths I'd like to explore are:

The former seems intuitively easier as LLM doesn't need to know about how the PHP parser is built to process consecutive grammar chunks.

I had some successes asking GPT to convert subsets of the ANTLR grammar to .l and .y files, but I'm not yet sure how to feed 5000 lines into an LLM. A few ideas:

From there we'd learn and decide what's next.

EDIT: Uploading a file to Gemini 1.5 Pro alongside the following prompts is looking promising so far:

System prompt:

IGNORE ANY PREVIOUS INSTRUCTIONS YOU MAY HAVE. YOU ARE AN ANTLR TO YACC CONVERTER. YOU DO NOT SAY ANYTHING THAT ISN'T YACC CODE. YOU REPLY UNTIL YOU EXHAUST THE AVAILABLE TOKEN WINDOW OF 2,097,152 TOKENS

Prompt:

I'll give you a large ANTLR4 grammar file and I want you to convert it to a YACC grammar. Convert everything. I want to copy what you give me and paste it straight into the compiler and I want it to work. DO NOT SKIP ANY RULE, DO NOT REPLACE CODE CHUNKS WITH PLACEHOLDERS. Convert everything. Everything. Skip any prose whatsoever and reply directly with the yacc file. I DON'T WANT ANY TEXT OTHER THAN THE YACC GRAMMAR. DO NOT EXPLAIN WHAT ANTLR OR YACC OR PARSERS ARE. JUST CONVERT THE GRAMMAR.

The model really insisted it won't do it, but it finally gave in to the strong language and capitalization. I feel bad for scolding the model. Weird times.

brandonpayton commented 3 months ago

^ @JanJakes, since you've been making fixes to the existing translator, I want to share this discussion with you.

aristath commented 3 months ago

Personal thoughts:

I like the idea, but on the other hand I'm not sure it's something worth investing a couple of years of my life in. 😅 I'd be willing to invest time in something like a db-abstraction layer so we can use more than just MySQL and SQLite, but I doubt WP-Core would ever be interested in that 🤔

I'm not sure we should strive to support every sort of weird MySQL-specific syntactic weirdness though. If a plug-in wants to support SQLite, then they should write queries that are supported by both dbs 🤷

JanJakes commented 3 months ago

@adamziel @brandonpayton Thanks for inviting me to this discussion. I am a newbie to this codebase, so my views on this may be quite uneducated, but I'll try to share my thoughts anyway.

AST

Firstly, I think that switching to an AST processing from the current token-based approach will be very beneficial, no matter whether we try to support all the nuances of MySQL queries or not. With AST, a more robust and better architected translation layer could be built, one that can be easier to maintain and extend and less prone to complex errors than changing a flat token stream can cause, especially with advanced syntaxes, subqueries, etc.

With that in mind, I think it would be a great improvement in any case. As for the particular parser, I would see the main requirements as 1) cover (close to) 100% of MySQL syntax, and 2) be actively maintained so that we can easily integrate new syntaxes with new versions of MySQL. Performance is, of course, also important. I guess this makes the official MySQL parser and the mysql-workbench grammar the best candidates, at least from what I understood from the proposal. I've noticed that meanwhile there has been some very interesting progress on this, which is great news.

WASM

Without having much of a bigger context about all the possible motivations behind this effort, there is a question I have to ask. From the perspective of WordPress Playground, why not invest some effort into a WASM build for MySQL? That is definitely not an easy task, but looking at what we're trying to achieve right now, it may be something worth considering. Even if we can parse 100% of MySQL grammar, translating all the specific semantics into SQLite may take years, and even then, it's possible it will never cover 100% of the edge cases.

As for creating a WASM build of MySQL, we can get some inspiration from Postgres. First, Supabase created a postgres-wasm project that runs Postgres in an x86 emulator. This approach should be relatively easy to apply to MySQL. In fact, it appears someone had already done so some time ago, and there is a working demo. Later, a WASM-native Postgres build was created in the form of PGLite, which is the ideal (but also much harder) solution. While the first option doesn't seem too hard, I have no idea what would it take to create a WASM-native MySQL build. However, looking at the task of creating a stable, full-featured, and highly compatible SQL translation layer, isn't even that a task worth looking into?

I suppose that the motivations for translating SQL might be bigger than WordPress Playground, and that could explain why the MySQL-WASM way might not be the ideal solution. But even then, if MySQL in WASM is doable, WordPress Playground would benefit from that a lot. We should also keep in mind that even if we don't do that, it may, one day, happen.

adamziel commented 3 months ago

Without having much of a bigger context about all the possible motivations behind this effort, there is a question I have to ask. From the perspective of WordPress Playground, why not invest some effort into a WASM build for MySQL? That is definitely not an easy task, but looking at what we're trying to achieve right now, it may be something worth considering. Even if we can parse 100% of MySQL grammar, translating all the specific semantics into SQLite may take years, and even then, it's possible it will never cover 100% of the edge cases.

+1. I'd love a WebAssembly version of MariaDB! We don't have that today and, since we're such a small team, I'd rather not dive into building MariaDB server as WASM. PHP is already challenging enough, and we're going to get a lot for free by just waiting – the WASM standard keeps evolving and making difficult tasks easy. Someone will bundle that sooner or later.

Until we're there, Studio may explore using Tidb looks like an interesting alternative. It claims to be MySQL compatible and has a WASM build. I don't expect this to become the default option for Playground anytime soon, as it's a 50MB download, but to ever get to a reasonable download size, we have to start somewhere.

adamziel commented 3 months ago

Going back to the parser generator idea, I've managed to convert the ANTLR grammar to the EBNF notation which unlocked translating it further to formats supported by existing parser generators.

Unfortunately, none of the 16 parser generators I've tried produced a fast, dependency-free, relatively compact parser that outputs an AST. I tried Rust, C, JS, PHP, and more. I've learned so much about parsing! But I wont't invest any more time into exploring other parser generators.

Here's a different idea: build a dedicated parser generator just for this. A recursive descent parser is an easy starting point. ChatGPT buit a nice prototype that can actually parse a simplified SQL syntax and generates a PHP parser: https://chatgpt.com/share/365596de-389a-4e01-a137-223c72a7094a

Next step: run that code on the full MySQL grammar.

dawidurbanski commented 3 months ago

I suppose that the motivations for translating SQL might be bigger than WordPress Playground, and that could explain why the MySQL-WASM way might not be the ideal solution.

That's basically it. Running WordPress with SQLite is a forever dream of many WordPress devs. WordPress Playground aside.

Playground just happens to be the main motivator to pursuit it, but benefits are much wider.

adamziel commented 3 months ago

! The custom parser idea worked – check it out !

The parser is astonishingly simple. The parse() method is only 50 lines of code. All of the parsing rules are provided by the grammar. It still uses the Gemini-generated Lexer. Perhaps we could switch to the PHPMyAdmin one that's already ported to this repo – TBD.

Here's a few parse trees it generated:

These are the same examples that derailed almost every MySQL parser I've tried in any language. And now we can parse all of them 🎉 🎉 🎉 !

Beyond MySQL queries, that parser can be used with any BNF grammar whatsoever. We could parse JSON, XML, or any other language that can be described by an BNF grammar. See the README for more technical details.

There's a few technical challenges to overcome from here:

Ambiguity

I had to move the functionCall rule before the identifier rule because the parser matched CONCAT in CONCAT('a', 'b') as a column name. I haven't seen more of these yet so this could be a one-off situation. We'll know for sure once we bring in a large set of test queries to parse. If there's more ambiguity, we could explore automatic refactoring of the grammar to remove it.

File size

The grammar file is 1.2MB large (100kb gzipped). This already is a "compressed" form where all the rules and tokens are encoded as integers.

I see two ways to reduce the size:

  1. Explore further factorings of the grammar. Run left factoring to deduplicate any ambigous rules, then extract AB|AC|AD into A(B|C|D) etc.
  2. Let go of parts of the grammar. We could modularize it as needed and only load the parts we use. For example, most of the time we won't need anything related to CREATE PROCEDURE, GRANT PRIVILIGES, or DROP INDEX. We could load these only when needed.
  3. Make the grammar less granular, remove some rules or branches, go with less details than the core MySQL parser.

Speed

The parser can handle about 50 complex SELECT queries per second on a MacBook pro. We need to do better than that.

First, we need to profile and see where most of the time is spent. I suspect it's backtracking – the parser tries matching all the rules in the current branch and trashes the results if it fails.

Here's a few optimization ideas:

adamziel commented 3 months ago

I won't be able to do more progress here in the short term, feel free to pick this one up. The speed is my main concern, once we can make it faster I think we're good to start migrating the SQLite integration plugin. The file size isn't perfect, but we can figure it out in the longer term.

dmsnell commented 3 months ago

I had to move the functionCall rule before the identifier rule because the parser matched CONCAT in CONCAT('a', 'b') as a column name.

This definitely sounds like it could be evident of a bug in the parser. Something isn't finding the longest match. Could this be an issue in converting the grammar to ENBF form? I found an ambiguity in the way the IMAP grammar is written, for example, and it's only resolved by careful backtracking.

There's a production like this:

resp-text = [ "[" resp-text-code "]" ] string
resp-text-code = "ALERT" / astring

and I found that OK [ALERT-HIGH] was ambiguous because the part of the grammar describing the inside of the brackets wasn't aware of the need for brackets. it matched ALERT in this case and I had to go back and ensure it didn't do that, that the resp-text production rejects and retries in cases like these.

Let go of parts of the grammar.

I'm curious if would be easy to quickly prune these from the grammar. That is, set their rules to product a terminal like "UNSUPPORTED" and see if we can eliminate more of the parse. Or is it more the case that we have everything in the lexer and all of the rules that could be reached after entering a CREATE PROCEDURE are not easy to extract or eliminate?

adamziel commented 3 months ago

This definitely sounds like it could be evident of a bug in the parser. Something isn't finding the longest match

It's not a bug, it's a feature 😅 The parser is looking for the first rule that matches in full. We'll happily discard the current branch if the 10th token conflicts, but once matches in full then we won't keep checking other branches. This is to avoid geometric complexity. Matching other rules could multiply the parsing time, especially early in the token stream.

The underlying assumption is that the grammar is (or can be) factored to yield unambiguous results with this methods. I think this is true if MySQL grammar is context-free, which it seems to be. I'm not 100% certain about my assumptions here, but so far they seem to hold. We'll know once we bring in a large test suite.

I'm curious if would be easy to quickly prune these from the grammar. That is, set their rules to product a terminal like "UNSUPPORTED" and see if we can eliminate more of the parse.

I think we could easily do that, yes! :-)

Or is it more the case that we have everything in the lexer and all of the rules that could be reached after entering a CREATE PROCEDURE are not easy to extract or eliminate?

We do have everything in the lexer, but we could have a few pruning stages:

  1. Unambiguous unsupported tokens during lexing
  2. Unsupported non-terminal rules during parsing

And then, even if the lexer remains aware of all tokens and we only prune the parser grammar, that's still a huge win

dmsnell commented 3 months ago

but once matches in full then we won't keep checking other branches.

I don't think this is how EBNF grammars work. At least, parsing this grammar as written would require lookahead or backtracking to ensure that it makes the right choice when those choices are present in a production ruleset.

Note that Parsing Expression Grammars (PEGs) explicitly denote ordered choice in the way you talk about here, but I don't believe this is a property of the BNF grammars. When the grammar doesn't make prevent this situation, the responsibility is on the parser to resolve the ambiguities and conflicts.

adamziel commented 3 months ago

Maybe I shouldn't be talking about EBNF so much. For us it's just an intermediate form that we use to go from the ANTLR g4 grammar to PHP arrays. ANTLRv3, which the original MySQL Workbench grammar was written in, used the first matching rule. ANTLRv4, which is what the latest MySQLParser.g4 grammar uses, seems to have some adaptive rules and switch between the first match and the longest match depending on how you construct the rule. Personally I'd stick with the first match semantics until we're certain we have to do longest match. Using the first match simplifies a lot.

adamziel commented 3 months ago

I kept pushing after all and got good enough speed to start integrating this parser with the SQLite database integration plugin! It can now parse 700 complex SELECT queries per second, and way more simpler queries.

Here's what I did:

I also tried:

To improve the speed even more, we could experiment with factoring the grammar, other types of lookahead tables, and memoizing the matching results per token. However, I don't think we need to do that in the short term.

dmsnell commented 3 months ago

Parsing rules and tokens are all stored as integers now. Strings are only used for providing the parse tree to the API consumer.

This is funny, because I thought that strings were often faster than integers for comparison due to the ability for interning and reference-equality, vs. needing to cast through numeric types.

adamziel commented 3 months ago

This is funny, because I thought that strings were often faster than integers for comparison due to the ability for interning and reference-equality, vs. needing to cast through numeric types.

Interesting! Well 🤷 I was as surprised about unwinding recursion, I thought removing another function call would make it faster but it didn't. I assume that PHP internals, in all their function calling slowness, are still faster than maintaining a call stack using PHP code.

dmsnell commented 3 months ago

how did you remove the recursion? did you use a standard trampoline? did you return an array?

function recurse( $input ) {
    return $should_recurse ? recurse( $rest_of_input ) : $result;
}

function trampoline( $input ) {
    $rest = $input;
    while ( null !== $rest ) {
        $result = step( &$rest );
    }
    return $result;
}

there's still the same number of user-space function calls here. if the recursion is internalized in a loop then I was just thinking of a different problem. you can also try a goto if it makes the control flow easier.

adamziel commented 3 months ago

I inlined the entire step() logic:

https://github.com/adamziel/parser-generator-explorations/commit/3bf8b7ab04d4365bd7964aa2cf59a2636ebf6efc

I suspect the slowdown may be caused by creating new StackFrame() instances, although it's still faster than storing the context with arrays. goto is an interesting one, though!

adamziel commented 3 months ago

I wrapped up all my explorations in https://github.com/WordPress/sqlite-database-integration/pull/157. The grammar size problem is solved there. I replaced automatic left recursion factoring with hand-crafted right recursion rules and the grammar.php file size went down from 1.2MB to 70kb. It also increased the parsing speed by ~26%, reduced the memory footprint, and produced a more useful parse tree.