Hacker News Reader

Comment by kiwicopple | Hacker News Reader

(i'm on the supabase team)

this is an update from the launch here:

https://news.ycombinator.com/item?id=37020610

The focus for the past few months has been getting the Parser right. It has been a lot of work. I'll ping Philipp and get him to join the discussion if there are any questions

We'd also love more contributors, if this sort of thing is up your alley

View on HN

> ...getting the Parser right. It has been a lot of work.

True.

I have an ANTLR4 grammar for SQL. Am noob. Getting things "correct" was some effort. I have the quixotic goal of accepting multiple dialects. It's a lot of time referencing docs, playing with SQL fiddles, and learning how other grammars work.

Now working on performance. Just as tough for noob me. TIL That means removing any potential ambiquities at runtime. ANTLR4's ALL(*) algorithm does some runtime magic whenever the happy path fails. Which tanks performance. Great for making "good enough" grammars. Not so great for chewing thru a corpus of tests.

SQLite has a terrific test suite. Including generated 'random' machine queries. My naive grammar took > 1000ms on these monsters, when it worked. After a few, it'd just ABEND with out of memory errors. Whoops!

By removing ambiquities, those monsters now take < 100ms. I really shouldn't make any claims until all the tests pass. (I'm still trying to figure out if I can handle both T-SQL style bracketed [names] and Postgres style name[index] array references, in the same grammar, without symmantic predicates.)

Any way. This experience has piqued my interest in PEG. I'm worried my LL(k) grammar is too brittle. Making it hard to for any one to maintain and adapt. As you well know, for sure. (For a taste of this challenge, peek at some of the other available ANTLR SQL grammars.) Oh well; that's a concern for later.

I'm looking forward to checking out Supabase's grammar. I'll share mine (Show HN) when I think it's good enough.

that's a huge task to take upon, looking forward to go through it! compared to you, we have gone the "easy" way and use the actual parser from the Postgres server. so no grammar definition and the like. our work was mainly around adapting libpg_query (which is build to parse executable SQL) for our use case.

> use the actual parser from the Postgres server. so no grammar definition and the like.

Doesn't Postgres use Lex/Yacc to describe the grammar?

It actually uses Flex/Bison, and does take advantage of the extended features they provide.

Thanks for the correction. But either way, doesn't this mean that a formal lexicon/grammar are available for the language server to draw upon?

If we're all being postgres-specific, isn't there presumably a grammar somewhere in postgres's code that is used to parse the query SQL? Wouldn't you all want to use that same file as a source so it's 100% identical to what Postgres is actually doing?

Genuine question. But maybe the tooling is incompatible.

Also, have you looked at Azure Data Studio? I'm wondering how much you can reuse from the work they did.

Not necessarily. It might be a recursive descent parser (to generate better error messages).

Yacc, I believe.

https://www.postgresql.org/docs/7.1/parser-stage.html

I'll check out Azure Data Studio, thank you.

For a bunch of reasons, probably all bad, I decided to roll my own, using ANTLR.

Being just a simple bear, LALR (yacc, bison) is beyond me.

With ANTLR4 the parse tree can be pretty close to the desired abstract syntax tree. Which is very nice.

Also, ANTLR4 has automagic left-recursion, so grammars can be very similar to the (reference) EBNF.

Lastly, ANTLR4 allows grammar inheritance. My hope is to have a subgrammar for each dialect which extends the one amazing core supergrammar. Looking at all the example SQL grammars, they're all pretty different, so it's not immediately clear how to generalize. Which is a bummer.

Where is the SQLite test suite, please? I'd be very interested.

There are already SQL grammars, check https://github.com/antlr/grammars-v4 specifically in here I think https://github.com/antlr/grammars-v4/tree/master/sql I contributed to one of them, and I wrote my own for some personal work. Be warned, it's very involved, very complex and MSSQL is rather ill-defined.

Names bracket identifiers) in SQL are bloody awful. Sometimes square brackets are even compulsory, and why you can usually replace [...] with the SQL standard "..." , not always! Trust me, it gets worse.

I don't find antlr grammars to be brittle, and while they can lose in performance (by how much I don't know, perhaps quite considerably) they are very easy to maintain and I am very fortunate to have antlr to work with.

Edit: unless you are very familiar with the SQL and also a masochist, please don't try and write your own grammar. For someone with my background it was very time-consuming, without that background it will be a nightmare. Friendly warning.

> Where is the SQLite test suite

Here's the scrapped tests:

https://github.com/bkiers/sqlite-parser/tree/master/src/test...

I didn't find a scrapper. I was cobbling together my own scrapper when I stumbled onto these files. My scrapper is turrible.

This SQLite grammar is included in grammars-v4. Looks like a copy vs a fork. I don't know why these tests weren't copied too.

> please don't try and write your own grammar

I must be a masochist.

Aside: Ages ago, during an job interview, when asked to talk about some of my prior work, I mentioned my SQL grammar. The self-described "bar raiser" cut me off, dismissed my effort as trivial, because the grammar generator (ANTLR) does all the work. I had no response.

A, thanks for these tests! That will be really useful for my work.

A couple of thoughts: what do you mean by a 'scrapper'? At first I thought you meant scraper, but I don't think it's that. I haven't come across the term before in this context, can you explain please.

I'm a bit concerned about the times reported for your parsing. It's unfortunately well-known that the python output of antlr is agonisingly slow – what is your output language? (I don't think that's your problem, but if it is then switching to Java output will fix this immediately).

Oof. Yes, I meant scraper.

> ...concerned about the times reported

Agreed.

FWIW...

My wall time for this beast (randtest1) is ~55ms.

    SELECT coalesce((select max(11- -19-f-t1.b+a) from t1 where exists(select 1 from t1 where 11-~(d)-c*a*~t1.a-t1.e-t1.e+coalesce((select coalesce((select t1.c from t1 where case (c) when d then e else 11 end=t1.f),t1.d) from t1 where (t1.d)>b), -11) | f+t1.f not in (((c)),b,13))),f) FROM t1 WHERE case when 19+c>=t1.a then t1.c when not case when not exists(select 1 from t1 where +f | b*b*19+19*13-a | case when t1.e not in (t1.f,t1.c,b) then 11 when 17>t1.c then a else e end<>e) then b when 17=t1.e then b else e end<>t1.b then a else d end-t1.b=(13)

Whereas simple statements like these are < 20ms each.

    select ((select 1) union (select 1));

    select a between b and c and d;

I need to add profiling metrics to the build, to (proactively) catch performance regressions.

It's fairly easy for ambiguity to sneak in. Mostly because I'm noob. But also because I'm stubbornly using left-recursion and I'm still navigating ANTLR's magical rule rewriting.

> ...python output of antlr is agonisingly slow

Still just using Java.

Edit: Now I'm curious. I'll try ANTLR's Python runtime asap.

My tool is a language translation widget. Input SQL and output templates (vs something like an ORM).

In the future, I'd like to support dynamic languages (stacks) like Python and nodejs/deno. One, just to be a good citizen ("when in Rome..."). But also to try some half-baked notions for supporting dynamic SQL at runtime. Which isn't (yet?) feasible with a compile-time stack like Java.

Thanks for your interest. I put my email in my HN profile. I can send you updates on my work. And once I get to a "beta" release (usable by other people), I intend to have weekly "office hours" on Zoom (or some such).

Only tangentially related, but if it's of any interest I'm about 90% done with a PEG grammar for the PostgREST query DSL for similar reasons. Happy to share it if it'd be useful.

Do you have a link to the DSL? Curious to learn more

Yep, posted it in response to sibling comment.

it would definitely be interesting. if it's private and can't share a link, my email is in my profile

Sure, still a WIP but it's getting there [1]

[1] https://github.com/superscribe-io/superscribe/blob/developme...

thanks for sharing - we'll check it out

Reply on news.ycombinator.com