3 ms·

> It sounds like they were using an expression tree and changed it to something like truth tables, which are essentially "flat" expression representations that

> It sounds like they were using an expression tree and changed it to something like truth tables, which are essentially "flat" expression representations that can support any boolean expression. I don't think that's an accurate description - it's more that we converted the tree representation (which still exists at parse/plan time) into an opcode/bytecode representation, evaluated by a mini-VM. Obviously that VM is quite specialized, and not general purpose (and currently it's afaik no internally turing complete, due to the lack of backward jumps, but that's just a question of the program generator, rather than the VM itself). The VM uses computed goto based dispatch if available (even though on modern x86 hardware the benefits aren't as large as on older HW).

atombender 8y ago
Makes sense, thanks. I thought maybe this was a smaller change where you just used a different layout/representation of the tree that allowed faster, more cache-friendly evaluation, but you've actually gone much further with this VM, which is fascinating given that it opens up the possibility of JITing queries. My day job involves working on a query engine that faces some of the same design challenges, so I find this stuff very interesting.
- anarazel 8y ago
  > but you've actually gone much further with this VM, which is fascinating given that it opens up the possibility of JITing queries. That's why I did it, and why that's the first part in PG 11 that got JITed ;) > My day job involves working on a query engine that faces some of the same design challenges, so I find this stuff very interesting. FWIW, part of the design decisions I made for this stuff in PG were made to a significant part because it had to be adaptable incrementally without breaking too many idiosyncrasies (although there were some, in another commit, around multiple set-returning-functions in the SELECT list). I'd definitely do some things differently if I were to design more on a green field.

atombender 8y ago

Makes sense, thanks. I thought maybe this was a smaller change where you just used a different layout/representation of the tree that allowed faster, more cache-friendly evaluation, but you've actually gone much further with this VM, which is fascinating given that it opens up the possibility of JITing queries. My day job involves working on a query engine that faces some of the same design challenges, so I find this stuff very interesting.

anarazel 8y ago
> but you've actually gone much further with this VM, which is fascinating given that it opens up the possibility of JITing queries. That's why I did it, and why that's the first part in PG 11 that got JITed ;) > My day job involves working on a query engine that faces some of the same design challenges, so I find this stuff very interesting. FWIW, part of the design decisions I made for this stuff in PG were made to a significant part because it had to be adaptable incrementally without breaking too many idiosyncrasies (although there were some, in another commit, around multiple set-returning-functions in the SELECT list). I'd definitely do some things differently if I were to design more on a green field.