4 ms·

Here's an absolutely crazy idea that I had the other day... Since Zig has comptime, couldn't a Zig reimplementation of SQLite use comptime for compile-time quer

by jhgb 4y ago

Here's an absolutely crazy idea that I had the other day... Since Zig has comptime, couldn't a Zig reimplementation of SQLite use comptime for compile-time query compilation? Including generating native code for fixed queries? So far I haven't been able to come up with any counterargument for why this wouldn't work.

apavlo 4y ago
> couldn't a Zig reimplementation of SQLite use comptime for compile-time query compilation? Including generating native code for fixed queries? SQLite already compiles queries into opcodes and then uses its own VM to interpret them. You would have to reimplement the internal VM.
- jhgb 4y ago
  I'm aware of that, but these elementary operations have some definitions in code. Even just calling them in a fixed sequence (as opposed to dispatching at runtime one opcode at a time) would be something optimizable for a sufficiently smart compiler. However, given a good-enough design of the whole system, straight code generation from the query plan shouldn't be a problem either (and at that point, the Zig compiler should be able to do even more work with the generated query code). I mean, any reimplementation would presumably use Zig features heavily anyway -- otherwise you could just link with the C code.
pvg 4y ago
The counter-argument is interpreting the query is not what takes up the time in executing a typical RDBMS query. Imagine a db is just a key-value store, the query is some keys and the db just spits out whatever it found in a giant hashtable. That's not going to get faster if you 'compile' the query. It's not going to get much faster if your db is a more realistic three hashtables, two big arrays and a partridge in a b-tree.
- jhgb 4y ago
  It might not be worth for everything, but extremely simple queries on extremely simple schemas would not be the goal here.
cryptonector 4y ago
You lose at "reimplementation of SQLite".
- jhgb 4y ago
  Possibly, but then again, if one's aim is to replace C with Zig in the future perhaps completely, because SQLite became de-facto standard file format for many applications (see OGC GeoPackage for example), you might need some implementation of SQLite for that. If a file format is going to stick for decades, you'll definitely get other implementations of that file format sooner or later in environments that can't or don't want to use C.
  - noodledoodletwo 4y ago
    What environment cannot run C?
    - jhgb 4y ago
      Well, for instance, famously, any multiple-stack machines will have a hard time trying to run C because C assumes a single hardware stack. Although I imagine that currently, in most cases, you'll want to avoid C for software reasons, rather than hardware reasons (for example, you're required to deploy pure Java code, or pure C# code, or want to avoid any unsafe code in Rust, things like that).
      - cryptonector 4y ago
        > C assumes a single hardware stack No, it doesn't. C does not even assume a stack. A platform where function call frames are allocated on the heap would not be incompatible with C. You could say that some C code assumes a stack, but that's pretty exceptional. > Although I imagine that currently, in most cases, you'll want to avoid C for software reasons, Yes. > rather than hardware reasons Hard to imagine hardware on which C could not run. Maybe a JVM chip, but even then, you could compile C to bytecode.
deleted 4y ago
[deleted]
AndyKelley 4y ago
Similar idea: https://andrewkelley.me/post/string-matching-comptime-perfect-hashing-zig.html https://andrewkelley.me/post/string-matching-comptime-perfec...

by jhgb 4y ago

apavlo 4y ago

> couldn't a Zig reimplementation of SQLite use comptime for compile-time query compilation? Including generating native code for fixed queries? SQLite already compiles queries into opcodes and then uses its own VM to interpret them. You would have to reimplement the internal VM.

jhgb 4y ago
I'm aware of that, but these elementary operations have some definitions in code. Even just calling them in a fixed sequence (as opposed to dispatching at runtime one opcode at a time) would be something optimizable for a sufficiently smart compiler. However, given a good-enough design of the whole system, straight code generation from the query plan shouldn't be a problem either (and at that point, the Zig compiler should be able to do even more work with the generated query code). I mean, any reimplementation would presumably use Zig features heavily anyway -- otherwise you could just link with the C code.

pvg 4y ago

The counter-argument is interpreting the query is not what takes up the time in executing a typical RDBMS query. Imagine a db is just a key-value store, the query is some keys and the db just spits out whatever it found in a giant hashtable. That's not going to get faster if you 'compile' the query. It's not going to get much faster if your db is a more realistic three hashtables, two big arrays and a partridge in a b-tree.

jhgb 4y ago
It might not be worth for everything, but extremely simple queries on extremely simple schemas would not be the goal here.

cryptonector 4y ago

You lose at "reimplementation of SQLite".

jhgb 4y ago
Possibly, but then again, if one's aim is to replace C with Zig in the future perhaps completely, because SQLite became de-facto standard file format for many applications (see OGC GeoPackage for example), you might need some implementation of SQLite for that. If a file format is going to stick for decades, you'll definitely get other implementations of that file format sooner or later in environments that can't or don't want to use C.
- noodledoodletwo 4y ago
  What environment cannot run C?
  - jhgb 4y ago
    Well, for instance, famously, any multiple-stack machines will have a hard time trying to run C because C assumes a single hardware stack. Although I imagine that currently, in most cases, you'll want to avoid C for software reasons, rather than hardware reasons (for example, you're required to deploy pure Java code, or pure C# code, or want to avoid any unsafe code in Rust, things like that).
    - cryptonector 4y ago
      > C assumes a single hardware stack No, it doesn't. C does not even assume a stack. A platform where function call frames are allocated on the heap would not be incompatible with C. You could say that some C code assumes a stack, but that's pretty exceptional. > Although I imagine that currently, in most cases, you'll want to avoid C for software reasons, Yes. > rather than hardware reasons Hard to imagine hardware on which C could not run. Maybe a JVM chip, but even then, you could compile C to bytecode.

deleted 4y ago

[deleted]

AndyKelley 4y ago

Similar idea: https://andrewkelley.me/post/string-matching-comptime-perfect-hashing-zig.html https://andrewkelley.me/post/string-matching-comptime-perfec...