4 ms·

Thanks, definitely a good resource Though I do think it's illumating to see the smallest, slowest code that implements the spec Similar to the "500 lines or l

by chubot 4y ago

Thanks, definitely a good resource Though I do think it's illumating to see the smallest, slowest code that implements the spec Similar to the "500 lines or less" book, or say a TCP/IP implementation in Python I cloned it, and it's ~3600 lines, which is very interesting. I didn't think you could implement anything that passes 95% of an sqlite test suite in that much code, as sqlite itself is at least 200K lines IIRC. It has a ton of features built up over 20 years. Sure you save a lot by not having a disk pager, efficient data structures, and so forth, but still that's pretty small, and parsing/tokenizing is over 1000 lines of it.

mytherin 4y ago
That specific SQLite test suite (one of four [1]) has loads of generated SQL queries, and a long tail of more varied hand-written tests. That 95% of the test suite will be mostly generated queries that follow the same basic pattern of joins and projections with basic arithmetic and comparisons. See for example [2] and [3]. The generated tests are not designed to test a wide breadth of features of the SQL language, and passing them with a simple engine is very doable. A lot of the value of these tests is that the sheer volume of queries tends to find obscure problems in optimizers that would not easily surface otherwise. That is of course not a problem in a simple engine that does not have an optimizer. [1] https://www.sqlite.org/testing.html#test_harnesses https://www.sqlite.org/testing.html#test_harnesses [2] https://github.com/gregrahn/sqllogictest/blob/master/test/random/groupby/slt_good_13.test https://github.com/gregrahn/sqllogictest/blob/master/test/ra... [3] https://raw.githubusercontent.com/gregrahn/sqllogictest/master/test/random/select/slt_good_102.test https://raw.githubusercontent.com/gregrahn/sqllogictest/mast...
- chubot 4y ago
  Ah OK that makes sense, because I can't see any way you'd fit builtin functions like string matching/transformation in ~3600 minus ~1000 lines, and I think a bunch of those are part of the SQL standard. The numbers could be misleading because the 5% of failing tests could be a large part or most of the core language (window functions?), while the 95% are some combinatorial tests that happen to take the exact same code path in an unoptimized engine i.e. with 4.2 million tests for 2600 lines, it seems like you're going to have a lot of duplicate coverage, even accounting for state space explosion

by chubot 4y ago

mytherin 4y ago

That specific SQLite test suite (one of four [1]) has loads of generated SQL queries, and a long tail of more varied hand-written tests. That 95% of the test suite will be mostly generated queries that follow the same basic pattern of joins and projections with basic arithmetic and comparisons. See for example [2] and [3]. The generated tests are not designed to test a wide breadth of features of the SQL language, and passing them with a simple engine is very doable. A lot of the value of these tests is that the sheer volume of queries tends to find obscure problems in optimizers that would not easily surface otherwise. That is of course not a problem in a simple engine that does not have an optimizer. [1] https://www.sqlite.org/testing.html#test_harnesses https://www.sqlite.org/testing.html#test_harnesses [2] https://github.com/gregrahn/sqllogictest/blob/master/test/random/groupby/slt_good_13.test https://github.com/gregrahn/sqllogictest/blob/master/test/ra... [3] https://raw.githubusercontent.com/gregrahn/sqllogictest/master/test/random/select/slt_good_102.test https://raw.githubusercontent.com/gregrahn/sqllogictest/mast...

chubot 4y ago
Ah OK that makes sense, because I can't see any way you'd fit builtin functions like string matching/transformation in ~3600 minus ~1000 lines, and I think a bunch of those are part of the SQL standard. The numbers could be misleading because the 5% of failing tests could be a large part or most of the core language (window functions?), while the 95% are some combinatorial tests that happen to take the exact same code path in an unoptimized engine i.e. with 4.2 million tests for 2600 lines, it seems like you're going to have a lot of duplicate coverage, even accounting for state space explosion