[The Splitgraph Console](https://www.splitgraph.com/splitgraph/domestic_us_flights/-/console) now analyzes the SQL query on the fly and displays the referenced tables in the sidebar for easier query comprehension. The feature is powered by [tree-sitter](https://tree-sitter.github.io/tree-sitter/) running in WASM. Try it out live
Interested in how we got it working? Read on! [The Splitgraph Console](https://www.splitgraph.com/splitgraph/domestic_us_flights/-/console) offers an IDE-like experience for interacting with Splitgraph and the data it exposes. One fundamental feature is [the query editor](https://www.splitgraph.com/query?sqlQuery=SELECT%0A++++%22EmployeeId%22%2C%0A++++%22LastName%22%2C%0A++++%22FirstName%22%2C%0A++++%22Title%22%2C%0A++++%22ReportsTo%22%2C%0A++++%22BirthDate%22%2C%0A++++%22HireDate%22%2C%0A++++%22Address%22%2C%0A++++%22City%22%2C%0A++++%22State%22%2C%0A++++%22Country%22%2C%0A++++%22PostalCode%22%2C%0A++++%22Phone%22%2C%0A++++%22Fax%22%2C%0A++++%22Email%22%0AFROM%0A++++%22demodemo123%2Fchinook-from-sqlite%3A0df8bfcc3c837a68d20be83830af20781f6f6d4515ee0da60b06cc9850c31918%22.%22Employee%22%0ALIMIT+100%3B&id=006102fd-c5ef-47e7-ada3-40a7040006d6&flavor=splitgraph&initial-namespace=demodemo123). It resembles a code editor and is used for editing SQL (PostgreSQL, in fact) queries, rather than files. The query editor has smart features like: - autocomplete We use [`pgcli`](https://pypi.org/project/pgcli/) on the backend to retrieve the completions. - syntax highlighting We use [the SQL Monaco language configuration](https://github.com/microsoft/monaco-editor/blob/38e1e3d097f84e336c311d071a9ffb5191d4ffd1/src/basic-languages/sql/sql.ts), which uses [the Monarch library](https://microsoft.github.io/monaco-editor/monarch.html) under the hood. One interesting feature we wanted to have was to introspect the query and display the tables it references. This would let the user quickly understand and interact with a subset of repositories and tables, rather than all repositories and tables within some namespace. We implemented this feature using [tree-sitter](https://tree-sitter.github.io/tree-sitter/) compiled to WASM ([web-tree-sitter](https://github.com/tree-sitter/tree-sitter/tree/master/lib/binding_web)) so the parsing happens within the user's browser. The rest of this article outlines the problems faced and the decisions we took to get the feature working. ## Parsing in the browser or on the server The first question we had to answer was whether the parsing process should happen in the browser, like our syntax highlighting, or on the server, like our autocomplete. There are pros and cons to both approaches: - parsing in the browser has a higher initial cost (fetching and initializing the parser), but offers faster feedback during editing, and transfers less data during long editing sessions - the browser can only execute JavaScript or WASM. The parser would have to be compiled to either of these languages. This limits our choices, as we cannot run arbitrary existing parsers. - either the browser or the server have to do more work to parse the query. For in-browser parsing, this could be slow for low-end devices. For server parsing, we could DDoS our servers by having many users ask for parsing of their queries. At this point, either approach would work. We had a slight preference for doing in-browser parsing for its lower latency and being able to use the parsed AST for more features in the future. ## Existing SQL parsers Parsing SQL is a popular problem which has many solutions in various languages. ### libpg_query and its bindings [libpg_query](https://github.com/pganalyze/libpg_query) is a C library for parsing PostgreSQL. It uses the same code that the PostgreSQL server uses. This makes the parsing the most accurate and spec-compliant. There are bindings for using libpg_query in other languages: - [pgsql-parser](https://github.com/pyramation/pgsql-parser) for Node.js - [pg-query-emscripten](https://github.com/pganalyze/pg-query-emscripten) for WASM (available in the browser) - [pg_query.rs](https://github.com/pganalyze/pg_query.rs) for Rust Trivia: this is what [Supabase's postgres_lsp](https://github.com/supabase/postgres_lsp) uses to parse pgSQL. #### The importance of syntax error recovery One major downside behind using any library based on `libpg_query` is that it has no syntax error recovery when the query contains syntax errors. If the parser encounters an error, it does not attempt to parse the rest of the code. It all comes down to [libpg_query having a single `error` field per parse tree](https://github.com/pganalyze/libpg_query/blob/9b21e3295402a0d0ee9a50c468d426c2dbb73ee6/src/pg_query_internal.h#L14). This makes it unsuitable for usage in code editors. When editing, most of the time the code has a syntax error, because the user is still typing the word, or is editing some more complex statement. For example, given the following query: ```sql SELECT "gid", "state" FROM "splitgraph/election-geodata:79724cbf5dcd2b260ac0d60e58135123d527ff4d2e1dc709f6da47fa8f4ee71f"."nation" LIMIT 100; ``` When the user wants to select one more column in a `SELECT` statement: ```sql SELECT "gid", , -- look, a syntax error. There cannot be a trailing comma above "state" FROM "splitgraph/election-geodata:79724cbf5dcd2b260ac0d60e58135123d527ff4d2e1dc709f6da47fa8f4ee71f"."nation" LIMIT 100; ``` we should still be able to parse the query and know it references [splitgraph/election-geodata](https://www.splitgraph.com/splitgraph/election-geodata/-/console) despite the query having a syntax error. This makes syntax error recovery a must-have for our parser. ### sql-parser from sql-language-server [sql-parser](https://github.com/joe-re/sql-language-server/tree/release/packages/sql-parser) is a JavaScript parser implemented using [Peggy](https://peggyjs.org/) (a JavaScript parser generator). It is part of the [sql-language-server](https://github.com/joe-re/sql-language-server). Lack of syntax error recovery disqualifies this library. It also did not support using schemas in table names (e.g. `"splitgraph/election-geodata"."nation"` was considered a syntax error, but `"splitgraph/election-geodata"` was not). ### tree-sitter [tree-sitter](https://tree-sitter.github.io/tree-sitter/) is a parser generator. The generated parsers include syntax error recovery. When there is a syntax error, only a few AST nodes get marked as `ERROR`, but the rest of the code is parsed like normal. It also supports incremental parsing. This means doing a re-parse of the code after editing it is more efficient than parsing from scratch if only we provide tree-sitter the previous AST and the description of the modified range of code. Both of these qualities make tree-sitter well-suited for code editors. In fact, it is used in [neovim](https://neovim.io/doc/user/treesitter.html), [Atom](https://neovim.io/doc/user/treesitter.html), [Emacs](https://lists.gnu.org/archive/html/emacs-devel/2022-11/msg01443.html), and [Helix](https://helix-editor.com/), to name a few. Tree-sitter also powers basic IDE operations in web versions of VSCode (like ) thanks to [the vscode-anycode extension](https://github.com/microsoft/vscode-anycode). It also powers parsing of bash in [the bash-language-server](https://github.com/bash-lsp/bash-language-server/blob/f2c7447929bd0ab20f37ec5a44719430aa111d14/server/src/analyser.ts#L74). See [Introduction to tree-sitter](https://teknologiumum.com/posts/introductory-to-treesitter) for a more detailed description of what tree-sitter can do. Tree-sitter has bindings in many languages. The ones relevant to us are: - [web-tree-sitter](https://github.com/tree-sitter/tree-sitter/tree/master/lib/binding_web) for WASM, - [node-tree-sitter](https://github.com/tree-sitter/node-tree-sitter) for Node.js. As for the grammar, [tree-sitter-sql](https://github.com/DerekStride/tree-sitter-sql/) is a well-maintained SQL grammar used in Neovim. In our testing, it successfully parsed the pgSQL we threw at it, and the parts it stumbled on were fixed in just a handful of days. All of the above led us to decide tree-sitter is the right choice for parsing pgSQL in the Console. ## Extracting referenced tables from the query Tree-sitter parses the query into an AST. [The corpus tests of the grammar](https://github.com/DerekStride/tree-sitter-sql/blob/main/test/corpus/select.txt) show the stringified AST node types. Now the challenge becomes extracting the referenced tables from that AST. Neovim's `:InspectTree` command is extremely useful at understanding the AST while interactively editing code. ![Neovim with the source query in the left window and the parsed AST in the right window. The `relation` AST node is selected in the AST window and the table reference is highlighted in the query.](/static-v2/images/blog/parsing-pgsql-with-tree-sitter/tree-sitter-inspect-tree-parsed-ast.png) Here we can also see the AST parsed from a query that has a syntax error. ![Neovim with the source query in the left window and the parsed AST in the right window. There is a syntax error in the query, but the parsed AST still contains a `relation`.](/static-v2/images/blog/parsing-pgsql-with-tree-sitter/tree-sitter-inspect-tree-error-recovery.png) Tree-sitter also supports [declaratively querying the AST](https://tree-sitter.github.io/tree-sitter/using-parsers#pattern-matching-with-queries) using queries written as [S-expressions](https://en.wikipedia.org/wiki/S-expression). It takes away the burden of walking the AST and looking for subtrees that match a certain shape. We ended up with the following query to capture the referenced tables: ```txt ( relation ( ( object_reference schema: (identifier) name: (identifier) ) @reference ) ) ``` ![Neovim with the source query in the left window, the parsed AST in the right-top window, and the tree-sitter query playground in the right-bottom. The matched `relation` AST node and source code is highlighted.](/static-v2/images/blog/parsing-pgsql-with-tree-sitter/tree-sitter-playground-relation-query.png) This query ended up capturing the table reference we care about. ### Extracting parts of a table reference Tree-sitter gives us back the table reference as a string like `"splitgraph/election-geodata:79724cbf5dcd2b260ac0d60e58135123d527ff4d2e1dc709f6da47fa8f4ee71f"."nation"`. Now it is our job to extract the namespace, repository name, image tag, and the table name from this reference. This felt like a good job for a regular expression. We ended up with the following one and wrote a bunch of test cases to make sure it also tolerates errors (e.g. a missing table name at the end when the user is still typing it): ```ts const tableReferenceRegExp = /^"((?[^/]+)?)(\/((?[^":]+)?)(:((?[^"]+)?))?"?(\."?((?[^"]+)?)"?)?)?$/; ``` It uses [named capturing groups](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Regular_expressions/Named_capturing_group) to make extracting the reference parts easier. ## Result Tying these pieces together, the Splitgraph Console query editor now supports displaying referenced tables in the sidebar as a tree. It updates nearly instantly. We added a debounce to avoid updating the UI so often. ![Splitgraph Console query editor with referenced tables shown in the sidebar.](/static-v2/images/blog/parsing-pgsql-with-tree-sitter/splitgraph-console-with-referenced-tables.png) We found that the tree-sitter parsing process usually takes less than 1ms on a laptop. Using 6x CPU throttling in Chrome still leads to a usable UI.

## Check it out Boost your SQL writing experience with live query introspection. Try it now
--- ## Bonus: supabase/postgres_lsp discussion As we were working on integrating tree-sitter in the Splitgraph Console, Supabase was working on the [postgres_lsp](https://github.com/supabase/postgres_lsp), a language server for PostgreSQL. Creating a language server involves much more work than just the parser. It can provide diagnostics, autocomplete, semantic highlighting, code actions, "Go to definition", and [many other features](https://microsoft.github.io/language-server-protocol/specifications/lsp/3.17/specification/#languageFeatures). The parser is still at the core of a language server. Omitting error recovery from the parser used in a language server can lead to frustrating experience for the users. For example, with semantic highlighting, the user will have a jarring experience if the query stops being highlighted each other keystroke due to intermittent parsing errors. Autocomplete also is problematic to get working when suggestions are only available when the query is valid. Most of the time the user will request suggestions for a half-written query, which, most likely, is not a valid query yet. If the server does not implement syntax error recovery during parsing, it will keep yielding empty or wrong suggestions. TypeScript server (`tsserver`) which is used in the TypeScript Language Server, has advanced syntax error recovery which offers stellar TypeScript authoring experience. Syntax error recovery is heavily integrated into the parser, for example: - [nodes are annotated when surrounding nodes have errors](https://github.com/microsoft/TypeScript/blob/b4cd9d8fdd1a3a9a8324069a7a6f4336538aa688/src/compiler/parser.ts#L1578), - [missing nodes are created when there are errors in the AST](https://github.com/microsoft/TypeScript/blob/b4cd9d8fdd1a3a9a8324069a7a6f4336538aa688/src/compiler/parser.ts#L2582), - [parsing functions are aware whether the parser is in "error recovery" mode](https://github.com/microsoft/TypeScript/blob/b4cd9d8fdd1a3a9a8324069a7a6f4336538aa688/src/compiler/parser.ts#L2785) and adjust their behavior. At the time of writing this article (2023-08-09), postgres_lsp employs some measures to handle syntax errors returned by [pg_query.rs](https://github.com/pganalyze/pg_query.rs) ([source](https://github.com/supabase/postgres_lsp/blob/1250f5ed14a0e86b2b7fa581214284c67b960621/crates/parser/src/statement.rs#L123)). Their LSP is still at a very early stage and only supports semantic highlighting (and keeps crashing quite often), which makes it hard to assess. We are very interested to see if using a parser with no syntax error recovery as a base will be a viable solution. That said, we are extremely excited that there is development in this space.

Splitgraph has been acquired by EDB! Read the blog post.

pgsql

Parsing pgSQL with tree-sitter in WASM

Product

Support

Company

Community

Splitgraph