Open Source SQL Parsers

https://tokern.io/blog/open-source-sql-parsers/

by EntICOnc • 4 years ago

125 102 4 years ago

eatonphil4• 4 years ago

I wrote a similar post recently and not all the libraries overlap interestingly. My post includes sample code for each library and evaluates a few various complexity SELECT queries for correctness.

I may have to write a second post now to include some from this one that I missed!

https://datastation.multiprocess.io/blog/2022-04-11-sql-pars...

1egg0myegg0• 4 years ago

Since DuckDB is so portable, it can be a good choice for adding a SQL parser to a new system. Have a look here for an example that uses the parser separately from the execution engine: https://github.com/duckdb/duckdb/blob/master/examples/standa...

eatonphil4• 4 years ago

Duckdb itself uses a variation of pganalyze's library-ification of postgres's parser so this seems a little indirect.

That said, I've heard the duckdb folks have improved on the postgres parser a bit.

tehlike9• 4 years ago

Not related to parsers, but i find sql syntax so backwards.

Listing columns first Then table Then join Then filter Then group bys Then limit

The order of operations are out of whack and makes pipeline ing a little hard.

I found this to be closer to LINQ way

https://github.com/prql/prql

I hope in near future databases will come with better query languages...

minxomat• 4 years ago

KQL is a more LINQy language.

tehlike9• 4 years ago

Looks interesting.

nickcox• 4 years ago

The order of operations are out of whack and makes pipeline ing a little hard

It makes it really hard to offer good autocompletions too.

tfigment• 4 years ago

This comes up for me in autocompleting editors. Have to start with "select * from table t;" then go back and then remove * and t.<ctrl-space> to get the hints to populate and then continue with joins which may require going back to select. Update and delete at least start with tables and joins.

userbinator2• 4 years ago

It was probably influenced by COBOL, i.e. designed to read like English.

manigandham• 4 years ago

In fact, SQL (structured query language) was originally called SEQUEL (structured English query language).

ErwinSmout18• 4 years ago

It was probably also influenced by Codd's own preference for the data language in calculus-based style (Codd's roots as a mathematician are to "blame" here), as opposed to algebra-based (the style typically preferred by developers).

technion3• 4 years ago

This feels a lot like why Kusto was invented. It's very close to SQL, but written the other way around with the table name first, then the 'where', and finally the columns.

https://docs.microsoft.com/en-us/azure/data-explorer/kusto/q...

tehlike9• 4 years ago

Correct looks like it's trying to be the linq of sql. Looks good. MSFT really knows how to make programming tools...

zmxz3• 4 years ago

In my case it's the opposite - SQL is perfectly readable and fits my mental model while the project you linked feels awkward and hard to read.

However, it's good to have options, I wonder if prql will get traction. It would be great if it did.

7952• 4 years ago

A lot of the time people's mental model will be derived from the language though.

vkazanov2• 4 years ago

...and there's more to sql trouble than just troublesome syntax, typical for languages of its generation!

1. Sql is non-modular

2. Non-orthogonal

3. Its parroting of the (beautiful) relational data model is... opinionated at best.

The standard is unreadable and not really implementable, one always has to resort to implementation docs.

Realistically there are no alternatives, but... sql is no good.

rzmmm• 4 years ago

What do you think about using SQL views and functions to make composable, modular SQL code?

ErwinSmout18• 4 years ago

Imagine you need to write a query to answer "what are the cities with more than 4000 inhabitants".

What more natural could there be than to write this as (old 1992 correlated query style)

SELECT cityName FROM Cities C WHERE ((SELECT COUNT() FROM Inhabitants I WHERE I.cityName = C.cityName) > 4000)

Agreed ???

YOU CAN'T DO THIS IN SQL [standard version] !!! You must write

SELECT cityName FROM Cities C WHERE (4000 < (SELECT COUNT() FROM Inhabitants I WHERE I.cityName = C.cityName))

This makes SQL about the only language in the world that allows you to write "a<b" in certain places but forbids you to write "b>a" in those very same places. Some professional piece of language design.

(Disclaimer : I don't know how matters are in SQL:2016 wrt to this issue, but it drove a former IBM employee who was at the time a member of the SQL standards committee to (a) start work on TTM and (b) leave IBM as soon as he could.)

ako• 4 years ago

Nice example of: always begin with the end in mind - first specify what data you want to see and then specify where it should come from.

I think it helps you focus on the outcome required, and makes you more efficient deciding how to implement it.

I use the same approach for methods in normal code: first decide on the signature of the method, and potentially a unit test to test it, and then think about the implementation.

tehlike9• 4 years ago

I like to think of data transformation a chaining problem. Linq lambda syntax is kind of like that.

db.Table.where(x=> x.name == 'abc').skip(10).take(20).groupBy()

This is really hard in sql especially with temporary tables and nesting you need to do as soon as you need to do things a little out of order...

Etc

cryptonector6• 4 years ago

I don't mind SQL, really, but I would prefer a query construction API that has the full power of SQL (and more even). At the very least such a thing would not have a SQL injection problem, but also could be used to generate ASTs.

  Query q = db.from("foo").join("bar").using("id")
    .select("id","foothing","barthing");

However, the moment you want any non-trivial SQL expression, such an API becomes unwieldy. And yet the need for non-trivial SQL expressions in queries can't be avoided, nor can it be left to the host language.

Also, I'd really like a SQL mode where no literal constants are allowed, as a mechanism to force the use of query parameters and prevent SQL injection.

tehlike9• 4 years ago

Linq in c# fixes that.

ErwinSmout18• 4 years ago

That "the API becomes unwieldy" is in fact inevitable. In order to support .where(<boolean expression>) as well as .select(<any expression>, ascolname) you need a way to pass a parameter of type something-like-expression to the .where() and .select() methods, and lambdas or at least something like them appear to be the right way to do that (e.g. .where((foothing) -> (foothing<0)), but languages offer no means to "introspect into the lambda" which is what is needed to translate it into SQL.

Plus (assume my .where() example was Java), the host language compiler is never going to find a way to cope with the declaration of the 'input' of the 'lambda', *precisely* because [the definitions of] those things are outside the scope of what the host language compiler knows about. So you need a way to do something like "import my-db-definition;" And then you need to put machinery in place to verify at runtime that the definitions as they are for the db, are still the same (or compatible) with the definitions that the program was compiled with. Etc. etc. etc.

tehlike9• 4 years ago

Some discussion on prql https://news.ycombinator.com/item?id=30060784#30062329

anitil6• 4 years ago

I'd be interested to hear people's use cases for parsing SQL. The link talks about exploring sql history, but has anyone else got some interesting uses?

A couple of times where I've needed to parse SQL I would typically write a module for sqlite3 and get it to do the parsing for me. But annoyingly I can't remember _why_ I did this or what I was trying to achieve.

eatonphil4• 4 years ago

Building a SQL IDE and want to do introspection on queries. Building a SQL frontend for some API or CLI. Building a SQL-aware proxy. Just a few ideas. :)

achanda358• 4 years ago

Some more: SQL linter, alternate DB implementations (Cockroach DB, TiDB etc), SQL optimisers

anitil6• 4 years ago

Interesting. Out of interest, what would an SQL-aware proxy give you? On-the-fly rewrites? Automatic caching?

cgio• 4 years ago

Harvesting lineage information could be a good use case.

crorella5• 4 years ago

Yes! you can then put a UI on top of that and answer stuff like "who will get affected by my change on this table?" or.. "there is a bug in my pipeline and now I need to notify downstream consumers"

anitil6• 4 years ago

This would be so useful to me right now. So often I'm flying blind making edits and just praying I don't ruin someone else's day

lmwnshn6• 4 years ago

In Andy Pavlo's current seminar class 15-799 [0], everyone parsed SQL to extract which columns were being accessed in a workload's queries. This was used to build an automatic index tuning tool.

[0] https://15799.courses.cs.cmu.edu/spring2022/project1.html

crorella5• 4 years ago

haha, we did just that in my company, but aimed at distributed tables (like HDFS) for their partition and bucketing schemata.

dmfay• 4 years ago

I'm using a tree-sitter grammar^1, which category the OP doesn't mention, to index database object references in data access code and process schema migrations^2. The idea is early detection of potentially-dangerous database changes that modify or drop tables/views still used elsewhere, across the entire organization's code. It's already saved my bacon a few times.

^1 specifically https://github.com/DerekStride/tree-sitter-sql , but there are a few others around too

^2 https://ectomigo.com

i_s3• 4 years ago

At my work, we often parse and rewrite a query before handing it off to SQL Server, because there are a lot of cases where Microsoft misses obvious optimizations. Sometimes there are also optimizations we can do because of things we know at compile time, but don't fit in the type system of SQL. The impact varies all the way from just shaving off 10% of the execution time, to changing some queries from timing out in a web request to executing in a few hundred milliseconds.

A few examples:

- Inlining scalar function calls (less impactful now with Sql Server 2019)

- Removing joins from a query when we know it won't impact the number of records

- Deepening where conditions against derived tables

- Killing "branches" of union queries when they can be determined to not matter statically

Yes, we could write the queries that way in the first place, but it would make them harder to compose, more verbose, and harder for the programmer to communicate intent. Not to mention, often the user can impact what the query will be, making it less feasible.

lmwnshn6• 4 years ago

less impactful now with Sql Server 2019

Could I ask what your process is for detecting whether a rewrite rule is still useful in subsequent versions of the DBMS? Do you read the release notes and test things out manually, or do you have an automated A/B test thing going on?

Additionally, have you ever had a rewrite rule change from being beneficial to being detrimental after upgrading versions? If so, how did you detect that?

Thanks!

Edit: Also, what considerations do you have for rewrite rule order? Do you find that it makes a significant difference in practice?

zasdffaa8• 4 years ago

Hmm? This doesn't make much sense. MSSQL does these already I think (except the first)

- Inlining scalar function calls (less impactful now with Sql Server 2019)

write them as table valued funcs and it'll inline them for you (ugly but it works and is easy)

- Removing joins from a query when we know it won't impact the number of records

That's just tree pruning. It does that

- Deepening where conditions against derived tables

If I understand you that's predicate pushdown. MSSQL does it well.

- Killing "branches" of union queries when they can be determined to not matter statically

Not sure what you mean. Can you give an example?

crorella5• 4 years ago

We created a custom purpose parser to get some interesting facts about the SQL statements running in our warehouse, a couple of millions of queries per day. With that information, we created a tool that finds the best partition and bucketing schema for each table, based on how the query patterns of downstream pipelines access them.

Since some of the tables are multi-petabyte with thousand of downstream consumers, the savings have been in the millions of USD, because of CPU savings mostly, but also there is the benefit of improved wall time and data arriving much earlier to dashboards and reports.

lmwnshn6• 4 years ago

Would you be able to provide examples of interesting facts, and is this tool (or anything similar) open-source or described publicly? Thanks!

newusertoday• 4 years ago

auto generating api for frontend and backend that uses sql query and metadata.

password4321• 4 years ago

Yes! Crossing the boundary between code + DB allows things like showing "this url could read/write these table columns", down to "hover over data to see the source" levels. This can track what has been accessed in the past year vs. no longer used, etc.

You can also reverse engineer missing foreign key relationships by parsing all of an apps' stored procedures (for relationship diagrams, etc.). Or just what external entities are referenced from "other" databases to get an idea of minimal schemas needed for automated testing.

matteote• 4 years ago

I use ANTLR4 and its rewriter to translate between two similar SQL dialects, for migration purposes.

technion3• 4 years ago

I'm still waiting for a very simple proxy where I can write rules like "DELETE statements must come with a WHERE".

orangepanda• 4 years ago

Oh this doesnt need a condition, let me just WHERE 1=1

gunnarmorling• 4 years ago

For Debezium (a change data capture solution) we parse SQL for some of the connectors in order to keep track of the schema of captured tables as DDL statements are executed.

Events we receive e.g. from MySQL aren't fully self-descriptive, you need to know the schema they adhere to in order to interpret them. As table schemas can change over time and as -- due to the async nature of streaming the transaction log -- we may receive change events produced from before a table's schema was changed, we cannot simply query the current table schema. Parsing incoming DDL events is the only way for keeping the connector's view on the schema in sync.

pbowyer• 4 years ago

A couple of years ago I inherited an old, badly written web app doing up to 800 queries per page. It was slow and hammering the server.

Being read-heavy the app was an ideal candidate for output caching. But - there were no hooks in the admin code to add cache invalidation. And I wasn't going to crawl through 10s of thousands of badly written lines and add cache invalidation calls manually, because I would miss some.

So I hooked into the database layer, parsed the SQL queries and extracted the table names. The read-heavy pages on the frontend were tagged in the cache with the names of the tables they read data from. In the backend, I'd collect the table names in all the write SQL queries and then clear the cache that was tagged with these table names.

Working at the table level rather than row level it cleared more data than was needed, but it was simple and effective.

It worked really well but never went into production - in the end we forced a rewrite of the app. One day I'd like to revisit the idea.

anitil6• 4 years ago

That is a fantastic use case! I'd have never have thought of doing this

madebyherzblut• 4 years ago

Slightly off-topic, but I appreciate any pointers: In a project, I want to offer an SQL interface for data analysts similar to Stripe Sigma[1]. The tricky thing is not to parse the query but to map the public schema to the private schema, add authorization, and distribute the query across data stores. So, I am looking for a customizable query parser, planner, and execution engine.

I briefly looked into Apache Calcite and DataFusion[2], but I am unsure if I am on the right track. If someone has any ideas about where to look, please let me know.

[1] https://stripe.com/en-gb/sigma [2] https://github.com/apache/arrow-datafusion

zasdffaa8• 4 years ago

So, I am looking for a customizable query parser, planner, and execution engine

That looks like an entire DB engine, isn't it?

map the public schema to the private schema

sounds like view.

It seems like a pretty major project as you describe it.

haliax• 4 years ago

For a similar use case, I’ve been considering a combination of s3 exports of db views (mapping private schema to public) + lakeformation governed tables (which allow table, row, and cell level security via iam) + redshift or athena for querying + sts/cognito for authorization to give logged in users a temporary access key id and secret access key. Admittedly an AWS heavy setup, but in my use case that’s an advantage :)

cryptonector6• 4 years ago

Here's a few:

  - syntax highlighting
  - algebraic manipulations
  - optimization analysis of queries seen
  - analysis of equivalence of queries
  - query rewriting (for style, performance, etc.)
  - RDBMS portability layer (implement a common
    subset of SQL, port queries to different
    engines; see previous item)

I can probably think of more.

userbinator2• 4 years ago

Much like with other things, recursive-descent is probably the best way to write a SQL parser as it's easy to debug, modify, and extend. There's some great hyperlinked grammars at https://ronsavage.github.io/SQL/ for those who want to try writing one.

Also, is it just me or does the text of this article have an almost SEO-spam-like "texture" to it? It reads very unnaturally.

lmwnshn6• 4 years ago

On the other hand, you're probably writing your SQL parser to parse SQL queries that are being fed into some DBMS. I found pg_query's argument convincing: "Our conclusion: The only way to correctly parse all valid SQL queries that PostgreSQL understands, now and in the future, is to use PostgreSQL itself." [0]

[0] https://pganalyze.com/blog/parse-postgresql-queries-in-ruby

bogomipz• 4 years ago

"Parsing SQL queries provides superpowers for monitoring data health"

Can someone say how this works exactly? What does parsing offer that things like logs and other metrics don't in terms of monitoring?

throwaway858• 4 years ago

There is also a Haskell port of the original PostgreSQL parser, implemented using megaparsec, which makes it highly flexible and hackable: https://github.com/nikita-volkov/hasql-th#implementation

cm2187• 4 years ago

I believe antlr has grammars for other sql syntaxes (sqlite, tsql, etc): https://github.com/antlr/grammars-v4/tree/master/sql

m-novikov• 4 years ago

There are also multiple ongoing projects attempting to implement incremental parsers(1, 2, 3) e.g. for tree-sitter. To make editing SQL code more convenient.

[1] https://github.com/m-novikov/tree-sitter-sql

[2] https://github.com/DerekStride/tree-sitter-sql

[3] https://github.com/Snowflake-Labs/lezer-snowsql

conaclos• 4 years ago

SQL is a mess. It is difficult to find a parser that fulfills your needs.

A month ago, I needed a parser to parse SQLite schemas. SQLite has some edge case and I needed a lossless parsing to detect these edge cases.

I finally wrote my own parser [1] to fullfill my needs and to have some fun. This is for a POC project.

[1] https://github.com/coast-team/sqlschm

cryptonector6• 4 years ago

If I needed to parse SQLite3 schemas, I might just fork the Lemon grammar for SQLite3 from SQLite3 and make it produce an AST.

Open Source SQL Parsers

Related Stories