Goal: Pass all 4259065 tests in sqllogictest in 1 week

There are likely many ways of doing these things, but here is my vague recollection from the time when I worked on a C++ in-memory database. We used tree transformations for query planner/optimizer. The evaluator was implemented as a virtual interface that had a lot of complexity, but on most basic level it took some parameters and returned rows of data.

Optimizer/query planner worked by parsing the query as a tree of operations and then finding tree transformations which are equivalent. Most basically this involved swapping table join orders and trading between materializing and streaming operators(^0). Costing was based on histograms data histograms which essentially enabled estimating how many rows each node in the query tree is expected to return. Generally you want to reduce the number of rows you are materializing ASAP. This generally means joining tables with fewest rows first, because then you can efficiently scan larger tables. Default strategy for joining large tables was to scan smaller one and build a map of the values and then scan the other one checking the map for each record. An alternative strategy is to build a bloom filter instead of the map, but that is only more efficient if the cross-section of the join is small.

Virtual execute evaluate interface enabled a lot of custom execution strategies for selecting from row/column/external db based tables, sorting data, and tons of join strategies.

Note 0: The constraint with streaming operators is that you can't fully sort the data before next step is executed. This prohibits execution strategies such as efficient joins which require all data to be sorted.

> I would have liked to have learned more about how the query planner and evaluator work!

If you want to know how sqlite does that, it has good docs about it, particularly https://sqlite.org/opcode.html

Another thing I wonder is if Zig's C interop is good enough to simply reuse Lemon. Basically

- on the input side, write a Tokenizer in Zig and feed that into the generated state machine in C

- on the output side, consume Lemon's C data structures / function calls directly in Zig. This is probably the hard part as the grammar and semantic actions are very intertwined

That would be a cool demo, although honestly maybe not even less work

> I would have liked to have learned more about how the query planner and evaluator work! There was almost nothing about that? Just the tests magically moving from 0% to 95%.

At the veeeery bottom:

> Detailed writeup to follow probably in a week or two.

I bet they wouldn't. They're well aware their complier often runs code inside if(false) blocks (in certain positions) and they just don't see this as important. Moving fast is more important. (Where exactly they're moving to is not quite clear.)

This is kind of an unhealthy attitude?

@jamii seems super talented, but his bio says "in the past I've built database engines, query planners, compilers, developer tools and interfaces for [a...] myriad [of] consulting and personal research projects.", along with his repo's being related to SQL parers, or literal text-editors working purely on string manipulation. He is also sponsored to spent 100% of his time doing exactly this.

What I mean that he is almost definitely a 10x dev at writing SQL parsers. But ask him to write a shader that renders a neat waterbed material and he'd be likely a 0.8x dev? The overlap between experience and context is key.

It’s amusing that people even question the existence of 10x developers.

What fraction of devs could even complete this, let alone in merely 10x the time?

> are actually 10x (or more)

To me, the more likely explanation is that this guy is an excellent developer, working on a problem he was suited to, and that's about all you can say. He came up with good strategies and insights here, and worked hard, and did a lot of other stuff right. But the idea of a generically 10x developer is a cartoonish oversimplification of how the world works.

10x developers exist, but their prevalence is greatly overstated. Also, churning out code at 10x doesn't make one a 10x developer (this could even hamper everyone else).

I also propose that moniker be banned from being self-applied, and is in fact, a smell test: if you encounter a colleague calling themselves a 10x developer, start interviewing immediately. No good will come out of that.

Of course it's impressive but this isn't the sort of work the average dev ends up doing day to day. We spend our time digging into dependencies (this had zero) both internal and external, interfacing with stakeholders and looking up business logic for a change. All those async tasks ultimately add up to significant headwinds even for the best "10x" dev.

I think the most important thing is "wanting to be faster/10x" (from the author's personal blog BTW) https://www.scattered-thoughts.net/writing/moving-faster/

Also, it's good if language doesn't stand in your way.

The input is 9139 lines long, each anomaly probably occurs dozens of times.

It's possible the files can't be edited within this project. I had a similar experience writing a code parsing engine. Sometimes it's best documented as code debt and the rewrite can be done at a later time.

Most likely: https://github.com/boyter/scc

Here's a new relevant post for anyone looking:

"Processing 40 TB of code from ~10M projects with a server and Go for $100 (2019)"

<https://news.ycombinator.com/item?id=33072846>

I'm interested as well.

He also used a compiler, and a standard library, and a computer.

The first dependency is a "dependency", but in the same way that an RFC you have to read with your eyes is a dependency. Except in this case, the dependency is a definition, in formal language (extended-backus-naur form, a.k.a. "e-bnf"), of the SQL language, as defined in ISO/IEC 9075:2016[0] (the 2016 version of the SQL language specification). They then use this language definition as the input to a program which generates parsers (called a parser-generator[1]), so that they can quickly get to where they have a library which they can use to parse/validate/inspect the SQL being given to them.

Copying the BFN "from an external source" is a smart move, since it means they don't have to do lots of busy work slowly reading and transcribing the specification; someone's already done that step, so why would anyone expect the author to waste time?

Using a parser generator is also a smart move since they exist already and are used all over the place (nobody hand-writes parsers for large languages; that's just a needless source of tedium and bugs). The code that's spit out of the parser generator is novel; that's newly created code which isn't taken from someone else's Github/other repo.

Ultimately, I don't see how any of what the author's done constitutes "[relying] on a dependency" given that they're not using anyone elses Zig source code in their compiled binary, they're writing lots of code for themselves to use, just very quickly, and with powerful tools.

[0] - https://en.wikipedia.org/wiki/SQL:2016

[1] - https://en.wikipedia.org/wiki/Compiler-compiler