11 ms·

Goal: Pass all 4259065 tests in sqllogictest in 1 week

288 points by luu 4y ago

kris-s 4y ago
What a cool project, I bet they learned a ton doing this.
ok_dad 4y ago
What's the `scc` tool I see used there?
- shadycuz 4y ago
  I'm interested as well.
- lifthrasiir 4y ago
  Most likely: https://github.com/boyter/scc https://github.com/boyter/scc
  - okasaki 4y ago
    7 ways of installing it, but no deb or rpm. Is this the wonderful future of FOSS where developers don't bother working with distribution maintainers anymore?
    - duped 4y ago
      This has been the norm for awhile. No one wants to work with distro maintainers because their model is incompatible with how people build and distribute their software. You either get a curl sh, a tarball, or a wrapper around either of those that pretends to be a .deb or .rpm.
    - mperham 4y ago
      I've distributed a lot of software and DEB/RPM has to be the worst. I'd suggest those distros improve on their developer ergonomics if they want to stay relevant. 100% of my customers use Docker images these days as it is much much easier to use.
      - okasaki 4y ago
        I guess that's for web stuff? You wouldn't distribute 'cloc' and similar in a docker image. One hopes.
        ok_dad 4y ago
        I will refer you to the first tool I thought to Google with "docker image for X": https://hub.docker.com/r/stedolan/jq https://hub.docker.com/r/stedolan/jq Yes, it's despicable.
        okasaki 4y ago
        10M+ pulls >:O https://www.youtube.com/watch?v=umDr0mPuyQc https://www.youtube.com/watch?v=umDr0mPuyQc
        ArchOversight 4y ago
        It's the easiest way to distribute software in a way that is controlled by the author of the software and where the author can reasonably control all of the dependencies installed. This way you are providing a one-stop shop that can easily be run. I have all kinds of tools that are docker containers because its simpler to not have to worry about all kinds of library mismatches or locations of shared libraries, and instead ship a minimal docker container instead.
    - ok_dad 4y ago
      Someday someone will make a hyper-package-managers to be able to manage their packages installed via the thousands of package-managers out there today. Then, several other hyper-package-managers will be developed to cover the cases the first didn't cover. Then comes the hyper-hyper-package-managers...
    - dec0dedab0de 4y ago
      Hasn't it always been rare for developers to maintain distro specific packages? That's why distro's have package maintainers, they also modify the layout and default configurations and whatnot to be consistent with the rest of the distro.
      - rcxdude 4y ago
        Yeah, Official debs/rpms are a thing but often completely independent of any distribution's packaging efforts (and they often have very different priorities).
    - pushedx 4y ago
      Go binaries are statically-linked, and this tool doesn’t require any configuration files or other additional files. Binaries are provided on the Releases page, so all you need to do is download one, put it in /usr/local/bin, and it’s essentially guaranteed to work. To upgrade, you download the new release and overwrite it. There’s an argument to be made for not having the version information available for dependency resolution (for scc as a dependency) available in your package manager, but you have to admit that it’s easy enough to install. GitHub doesn’t even mind if you `wget && chmod` from their CDN URL.
- ok_dad 4y ago
  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 https://news.ycombinator.com/item?id=33072846>
samsquire 4y ago
I handrolled a very very basic SQL parser in my toy database hash-db https://GitHub.com/samsquire/hash-db https://GitHub.com/samsquire/hash-db It's distributed dynamodb style keyvalue, SQL and Cypher graph database. I feel if you want to get a project moving forward for something as large as a database, you can get something rudimentary working and extend the parser when you need those features. SQL wise it supports Joins and where's and rudimentary full text search It uses rockset's converged indexes for ease of query generation. If you're interested in queries then you should read this blog post. https://rockset.com/blog/converged-indexing-the-secret-sauce-behind-rocksets-fast-queries/ https://rockset.com/blog/converged-indexing-the-secret-sauce... The database is partly multimodel with document storage and SQL and graph Cypher querying but I am yet to get all the models to be mutually queryable. The document storage is queryable by SQL but graphs aren't queryable by SQL or as a document.
iLoveOncall 4y ago
No dependencies but the very first step relies on a dependency? It's not because you copy-paste it that it's not a dependency...
- eatonphil 4y ago
  He also used a compiler, and a standard library, and a computer.
  - iLoveOncall 4y ago
    There's a bit of a difference between taking away the only truly hard part of the project and using the standard library.
    - eatonphil 4y ago
      The SQL grammar is already defined. He didn't invent SQL. He had to take the grammar from somewhere. You wanted him to handwrite it copied from the ANSI SQL paper? Or to just think up all the possible grammars and ignore the real paper? How would that be different or better than this?
      - remram 4y ago
        [[edit: NO HE DIDN'T!]] If you missed it, the author does more than reuse the grammar, he used a parser generator, which I think is what iLoveOncall is reacting to. Personally I do agree that, when writing a language interpreter and claiming "no dependency", grabbing an existing parser is a bit of a cheat. Just like grabbing an existing bytecode VM, garbage collector, just-in-time engine, ... would be. It doesn't make the endeavor less interesting or less formidable, but it doesn't really fit "no dependencies" any more.
        eatonphil 4y ago
        > If you missed it, the author does more than reuse the grammar, he used a parser generator, which I think is what iLoveOncall is reacting to. Huh? He wrote the parser generator. https://github.com/jamii/hytradboi-jam-2022/tree/main/lib/sql https://github.com/jamii/hytradboi-jam-2022/tree/main/lib/sq...
spullara 4y ago
So does anyone else agree that there are actually 10x (or more) developers? This is a pretty good example of how one works.
- stocknoob 4y ago
  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?
  - viraptor 4y ago
    The fraction of devs that regularly deal with databases and parsing. There are no 10x devs. There are devs with long experience in a specific category. The 10x idea is kind of stupid in terms of companies looking for them - it just means "we want people successfully trained somewhere else".
    - subroutine 4y ago
      I agree there are probably no 10x devs. This person took 7 days to (almost) complete this task (which they cherry picked for their self), suggesting the average 1x dev with experience in this domain would take 70 days. I think it would be more reasonable to call someone a 3 -sigma dev (someone 3 standard deviations above the mean. These would exist because that's how stats work)
      - rcxdude 4y ago
        It's worth pointing out that in the origin of the "10x developer" term, it's relative to the worst performing devs, not the average. Also, you're not guaranteed to have an example 3 standard deviations above the mean. It strongly depends on your distribution and sample size.
        subroutine 4y ago
        I think the prevailing current definition is wrt. the average dev. The worst dev could be arbitrarily bad (suggesting the average dev could also be 10x). You're right about the sufficient sample size.
apetresc 4y ago
> So parsing the bnf is kind of a mess, but I only have to parse this one bnf and not bnfs in general so I just mashed in a bunch of special cases. Surely at that point it would've been a lot cleaner and more practical to just edit the one file you need to parse, to remove the weird line breaks, etc., rather than building special cases into your parser to work around those lines? What am I missing?
- Forge36 4y ago
  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.
- ruuda 4y ago
  The input is 9139 lines long, each anomaly probably occurs dozens of times.
  - cheeze 4y ago
    My strat for something like this is often to 'massage' it with basic unix commands, and then feed sane input into the program. Not always the best way, but usuaully the easiest thing that works for me.
mdaniel 4y ago
> I lost a lot of time in the morning to segfaults in the zig compiler. (https://github.com/jamii/hytradboi-jam-2022#day-4 https://github.com/jamii/hytradboi-jam-2022#day-4) I bet the zig project would be interested in the sha of the tree that blows up their compiler
- puffoflogic 4y ago
  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.)
  - an_ko 4y ago
    > their complier often runs code inside if(false) blocks (in certain positions) Do you have an example? Sounds like a catastrophic edge case.
    - dwohnitmok 4y ago
      If parent is referring to what I think she/he is referring to, then it's something like this: https://github.com/ziglang/zig/issues/6768 https://github.com/ziglang/zig/issues/6768. Keep in mind this is only to do with comptime not runtime. So not ideal, but not catastrophic in the sense of "my program evaluated the wrong conditional branch at runtime!"
      - Aeolun 4y ago
        It still kind of generates a bunch of undefined behavior if parts of your code disappear from the build where they shouldn’t.
    - puffoflogic 4y ago
      Here are some examples of "obvious" miscompilations like this: https://github.com/ziglang/zig/issues/10349 https://github.com/ziglang/zig/issues/10349 https://github.com/ziglang/zig/issues/9810 https://github.com/ziglang/zig/issues/9810 https://github.com/ziglang/zig/issues/8952 https://github.com/ziglang/zig/issues/8952 https://github.com/ziglang/zig/issues/4491 https://github.com/ziglang/zig/issues/4491 https://github.com/ziglang/zig/issues/5230 https://github.com/ziglang/zig/issues/5230 https://github.com/ziglang/zig/issues/6444 https://github.com/ziglang/zig/issues/6444 https://github.com/ziglang/zig/issues/7097 https://github.com/ziglang/zig/issues/7097 https://github.com/ziglang/zig/issues/3882 https://github.com/ziglang/zig/issues/3882
bsima 4y ago
And I would have done it too, if it weren’t for that meddling parser
chubot 4y ago
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%. e.g. What table and value representation was used? FWIW I suspect using a LALR(1) parser in Zig on the sqlite grammar would have saved some time and gotten past the parsing headache. The sqllogictest comes directly from sqlite, so it seems like the parsing problem is mostly "port from C to Zig" (which are very similar metalanguages, or I guess meta- meta- languages in this case :) ) Lemon is apparently a mini-yacc, just for sqlite's grammar, and is about 7K lines of C code, with no deps: https://sqlite.org/src/doc/trunk/doc/lemon.html https://sqlite.org/src/doc/trunk/doc/lemon.html
- TrainedMonkey 4y ago
  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.
- throwaway81523 4y ago
yesimahuman 4y ago
When I saw they were building their own parser I wondered why not use something like antlr? There are a lot of antlr grammars for SQL dialects. But then this is zig and I don’t know if there’s a zig antlr runtime yet.
funstuff007 4y ago
It would have been more amazing to see how many tests GPT-3 could pass.
jfkw 4y ago
I couldn't figure out what software is being developed to pass the sqllogittest suite here. Will this be a SQLite-like database or SQL parser implemented Zig?

288 points by luu 4y ago

kris-s 4y ago

What a cool project, I bet they learned a ton doing this.

ok_dad 4y ago

What's the `scc` tool I see used there?

shadycuz 4y ago
I'm interested as well.
lifthrasiir 4y ago
Most likely: https://github.com/boyter/scc https://github.com/boyter/scc
- okasaki 4y ago
  7 ways of installing it, but no deb or rpm. Is this the wonderful future of FOSS where developers don't bother working with distribution maintainers anymore?
  - duped 4y ago
    This has been the norm for awhile. No one wants to work with distro maintainers because their model is incompatible with how people build and distribute their software. You either get a curl sh, a tarball, or a wrapper around either of those that pretends to be a .deb or .rpm.
  - mperham 4y ago
    I've distributed a lot of software and DEB/RPM has to be the worst. I'd suggest those distros improve on their developer ergonomics if they want to stay relevant. 100% of my customers use Docker images these days as it is much much easier to use.
    - okasaki 4y ago
      I guess that's for web stuff? You wouldn't distribute 'cloc' and similar in a docker image. One hopes.
      - ok_dad 4y ago
        I will refer you to the first tool I thought to Google with "docker image for X": https://hub.docker.com/r/stedolan/jq https://hub.docker.com/r/stedolan/jq Yes, it's despicable.
        okasaki 4y ago
        10M+ pulls >:O https://www.youtube.com/watch?v=umDr0mPuyQc https://www.youtube.com/watch?v=umDr0mPuyQc
      - ArchOversight 4y ago
        It's the easiest way to distribute software in a way that is controlled by the author of the software and where the author can reasonably control all of the dependencies installed. This way you are providing a one-stop shop that can easily be run. I have all kinds of tools that are docker containers because its simpler to not have to worry about all kinds of library mismatches or locations of shared libraries, and instead ship a minimal docker container instead.
  - ok_dad 4y ago
    Someday someone will make a hyper-package-managers to be able to manage their packages installed via the thousands of package-managers out there today. Then, several other hyper-package-managers will be developed to cover the cases the first didn't cover. Then comes the hyper-hyper-package-managers...
  - dec0dedab0de 4y ago
    Hasn't it always been rare for developers to maintain distro specific packages? That's why distro's have package maintainers, they also modify the layout and default configurations and whatnot to be consistent with the rest of the distro.
    - rcxdude 4y ago
      Yeah, Official debs/rpms are a thing but often completely independent of any distribution's packaging efforts (and they often have very different priorities).
  - pushedx 4y ago
    Go binaries are statically-linked, and this tool doesn’t require any configuration files or other additional files. Binaries are provided on the Releases page, so all you need to do is download one, put it in /usr/local/bin, and it’s essentially guaranteed to work. To upgrade, you download the new release and overwrite it. There’s an argument to be made for not having the version information available for dependency resolution (for scc as a dependency) available in your package manager, but you have to admit that it’s easy enough to install. GitHub doesn’t even mind if you `wget && chmod` from their CDN URL.
ok_dad 4y ago
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 https://news.ycombinator.com/item?id=33072846>

samsquire 4y ago

I handrolled a very very basic SQL parser in my toy database hash-db https://GitHub.com/samsquire/hash-db https://GitHub.com/samsquire/hash-db It's distributed dynamodb style keyvalue, SQL and Cypher graph database. I feel if you want to get a project moving forward for something as large as a database, you can get something rudimentary working and extend the parser when you need those features. SQL wise it supports Joins and where's and rudimentary full text search It uses rockset's converged indexes for ease of query generation. If you're interested in queries then you should read this blog post. https://rockset.com/blog/converged-indexing-the-secret-sauce-behind-rocksets-fast-queries/ https://rockset.com/blog/converged-indexing-the-secret-sauce... The database is partly multimodel with document storage and SQL and graph Cypher querying but I am yet to get all the models to be mutually queryable. The document storage is queryable by SQL but graphs aren't queryable by SQL or as a document.

iLoveOncall 4y ago

No dependencies but the very first step relies on a dependency? It's not because you copy-paste it that it's not a dependency...

eatonphil 4y ago
He also used a compiler, and a standard library, and a computer.
- iLoveOncall 4y ago
  There's a bit of a difference between taking away the only truly hard part of the project and using the standard library.
  - eatonphil 4y ago
    The SQL grammar is already defined. He didn't invent SQL. He had to take the grammar from somewhere. You wanted him to handwrite it copied from the ANSI SQL paper? Or to just think up all the possible grammars and ignore the real paper? How would that be different or better than this?
    - remram 4y ago
      [[edit: NO HE DIDN'T!]] If you missed it, the author does more than reuse the grammar, he used a parser generator, which I think is what iLoveOncall is reacting to. Personally I do agree that, when writing a language interpreter and claiming "no dependency", grabbing an existing parser is a bit of a cheat. Just like grabbing an existing bytecode VM, garbage collector, just-in-time engine, ... would be. It doesn't make the endeavor less interesting or less formidable, but it doesn't really fit "no dependencies" any more.
      - eatonphil 4y ago
        > If you missed it, the author does more than reuse the grammar, he used a parser generator, which I think is what iLoveOncall is reacting to. Huh? He wrote the parser generator. https://github.com/jamii/hytradboi-jam-2022/tree/main/lib/sql https://github.com/jamii/hytradboi-jam-2022/tree/main/lib/sq...

spullara 4y ago

So does anyone else agree that there are actually 10x (or more) developers? This is a pretty good example of how one works.

stocknoob 4y ago
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?
- viraptor 4y ago
  The fraction of devs that regularly deal with databases and parsing. There are no 10x devs. There are devs with long experience in a specific category. The 10x idea is kind of stupid in terms of companies looking for them - it just means "we want people successfully trained somewhere else".
  - subroutine 4y ago
    I agree there are probably no 10x devs. This person took 7 days to (almost) complete this task (which they cherry picked for their self), suggesting the average 1x dev with experience in this domain would take 70 days. I think it would be more reasonable to call someone a 3 -sigma dev (someone 3 standard deviations above the mean. These would exist because that's how stats work)
    - rcxdude 4y ago
      It's worth pointing out that in the origin of the "10x developer" term, it's relative to the worst performing devs, not the average. Also, you're not guaranteed to have an example 3 standard deviations above the mean. It strongly depends on your distribution and sample size.
      - subroutine 4y ago
        I think the prevailing current definition is wrt. the average dev. The worst dev could be arbitrarily bad (suggesting the average dev could also be 10x). You're right about the sufficient sample size.

apetresc 4y ago

> So parsing the bnf is kind of a mess, but I only have to parse this one bnf and not bnfs in general so I just mashed in a bunch of special cases. Surely at that point it would've been a lot cleaner and more practical to just edit the one file you need to parse, to remove the weird line breaks, etc., rather than building special cases into your parser to work around those lines? What am I missing?

Forge36 4y ago
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.
ruuda 4y ago
The input is 9139 lines long, each anomaly probably occurs dozens of times.
- cheeze 4y ago
  My strat for something like this is often to 'massage' it with basic unix commands, and then feed sane input into the program. Not always the best way, but usuaully the easiest thing that works for me.

mdaniel 4y ago

> I lost a lot of time in the morning to segfaults in the zig compiler. (https://github.com/jamii/hytradboi-jam-2022#day-4 https://github.com/jamii/hytradboi-jam-2022#day-4) I bet the zig project would be interested in the sha of the tree that blows up their compiler

puffoflogic 4y ago
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.)
- an_ko 4y ago
  > their complier often runs code inside if(false) blocks (in certain positions) Do you have an example? Sounds like a catastrophic edge case.
  - dwohnitmok 4y ago
    If parent is referring to what I think she/he is referring to, then it's something like this: https://github.com/ziglang/zig/issues/6768 https://github.com/ziglang/zig/issues/6768. Keep in mind this is only to do with comptime not runtime. So not ideal, but not catastrophic in the sense of "my program evaluated the wrong conditional branch at runtime!"
    - Aeolun 4y ago
      It still kind of generates a bunch of undefined behavior if parts of your code disappear from the build where they shouldn’t.
  - puffoflogic 4y ago
    Here are some examples of "obvious" miscompilations like this: https://github.com/ziglang/zig/issues/10349 https://github.com/ziglang/zig/issues/10349 https://github.com/ziglang/zig/issues/9810 https://github.com/ziglang/zig/issues/9810 https://github.com/ziglang/zig/issues/8952 https://github.com/ziglang/zig/issues/8952 https://github.com/ziglang/zig/issues/4491 https://github.com/ziglang/zig/issues/4491 https://github.com/ziglang/zig/issues/5230 https://github.com/ziglang/zig/issues/5230 https://github.com/ziglang/zig/issues/6444 https://github.com/ziglang/zig/issues/6444 https://github.com/ziglang/zig/issues/7097 https://github.com/ziglang/zig/issues/7097 https://github.com/ziglang/zig/issues/3882 https://github.com/ziglang/zig/issues/3882

bsima 4y ago

And I would have done it too, if it weren’t for that meddling parser

chubot 4y ago

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%. e.g. What table and value representation was used? FWIW I suspect using a LALR(1) parser in Zig on the sqlite grammar would have saved some time and gotten past the parsing headache. The sqllogictest comes directly from sqlite, so it seems like the parsing problem is mostly "port from C to Zig" (which are very similar metalanguages, or I guess meta- meta- languages in this case :) ) Lemon is apparently a mini-yacc, just for sqlite's grammar, and is about 7K lines of C code, with no deps: https://sqlite.org/src/doc/trunk/doc/lemon.html https://sqlite.org/src/doc/trunk/doc/lemon.html

TrainedMonkey 4y ago
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.
throwaway81523 4y ago

yesimahuman 4y ago

When I saw they were building their own parser I wondered why not use something like antlr? There are a lot of antlr grammars for SQL dialects. But then this is zig and I don’t know if there’s a zig antlr runtime yet.

funstuff007 4y ago

It would have been more amazing to see how many tests GPT-3 could pass.

jfkw 4y ago

I couldn't figure out what software is being developed to pass the sqllogittest suite here. Will this be a SQLite-like database or SQL parser implemented Zig?