3 ms·

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

by 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
> 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 https://sqlite.org/opcode.html
- 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
chubot 4y ago
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
Izkata 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%. At the veeeery bottom: > Detailed writeup to follow probably in a week or two.

by chubot 4y ago

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

> 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 https://sqlite.org/opcode.html

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

chubot 4y ago

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

Izkata 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%. At the veeeery bottom: > Detailed writeup to follow probably in a week or two.