Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why SQLite Uses Bytecode

sqlite.org

Post reply on HN
Print view View original

51–60 of 231 posts

Re: Why SQLite Uses Bytecode

#51

Post by bch »

Scaevolus wrote: post #27
anon291 wrote: post #20

Earlier quoted context omitted.

Stack-based VMs, like SQLite's (I think), ARE trees. A stack based VM's bytecode (without DUP and POP) is just the post-order depth-first traversal of the corresponding expression tree. With DUP you have a connected acyclic DAG. With POP you have an acyclic DAG with one or more components. With loops you have a full graph. When looked at this way, a VM makes the most sense actually because a pointer-heavy tree implem…

SQLite's VM is register-based, not stack-based.

It’s been both - was stack, converted to register[0][1].

[0] https://www.sqlite.org/vdbe.html

[1] https://www.sqlite.org/src/info/051ec01f2799e095

Re: Why SQLite Uses Bytecode

#52

Post by kccqzy »

megadal wrote: post #28
lifthrasiir wrote: post #23

Earlier quoted context omitted.

You don't need one, Lua is another example where no AST is ever generated. In some sense the resulting bytecode closely corresponds to the AST that would have been generated though.

Genuinely asking as parsing without an AST is something I've never seen explained: How do you go from source code to bytecode without an AST? Isn't the bytecode just a flattened representation of an AST obtained by some sort of tree traversal? This seems to imply an AST is involved in the generation of the bytecode

Another way to think about this is to imagine you are working in a lazy-by-default language like Haskell. The code might seem to build up an AST and then evaluate it, but (disregarding parse errors) the AST is never materialized in memory at once: the tree might only have one level, with its children represented by thunks that continue to parse more of the source code. (If you are unfamiliar with Haskell laziness, imagine that the so-called tree has children that are functions to produce the next level of the tree.) Of course you will need a carefully designed bytecode in order to generate bytecode from AST where the children is not yet known.

Re: Why SQLite Uses Bytecode

#53

Post by DeathArrow »

paulddraper wrote: post #34
wolf550e wrote: post #29

The page is the result of this exchange on Twitter: https://twitter.com/gorilla0513/status/1784756577465200740 I was surprised to receive a reply from you, the author. Thank you :) Since I'm a novice with both compilers and databases, could you tell me what the advantages and disadvantages are of using a VM with SQLite? https://twitter.com/DRichardHipp/status/1784783482788413491 It is difficult to summarize the advan…

There are three approaches: 1. interpreted code 2. compiled then interpreted bytecode 3. compiled machine code The further up, the simpler. The further down, the faster.

There is also JIT bytecode.

Re: Why SQLite Uses Bytecode

#54

Post by tanelpoder »

paulddraper wrote: post #34
wolf550e wrote: post #29

The page is the result of this exchange on Twitter: https://twitter.com/gorilla0513/status/1784756577465200740 I was surprised to receive a reply from you, the author. Thank you :) Since I'm a novice with both compilers and databases, could you tell me what the advantages and disadvantages are of using a VM with SQLite? https://twitter.com/DRichardHipp/status/1784783482788413491 It is difficult to summarize the advan…

There are three approaches: 1. interpreted code 2. compiled then interpreted bytecode 3. compiled machine code The further up, the simpler. The further down, the faster.

4. lots of small building blocks of static machine code precompiled/shipped with DB software binary, later iterated & looped through based on the query plan the optimizer came up with. Oracle does this with their columnar/vector/SIMD processing In-Memory Database option (it's not like LLVM as it doesn't compile/link/rearrange the existing binary building blocks, just jumps & loops through the existing ones in the required order)

Edit: It's worth clarifying that the entire codebase does not run like that, not even the entire plan tree - just the scans and tight vectorized aggregation/join loops on the columns/data ranges that happen to be held in RAM in a columnar format.

Re: Why SQLite Uses Bytecode

#56

Post by jiehong »

SQLite EXPLAIN plan is indeed represented as a table, but I don’t find it necessarily that much easier to read and understand.

I often miss having the cardinality and the amount of bytes read for each part of the query like Oracle query plans provide.

Or is everyone really that happy with SQLite query plans?

Re: Why SQLite Uses Bytecode

#57

Post by bvrmn »

jiehong wrote: post #56

SQLite EXPLAIN plan is indeed represented as a table, but I don’t find it necessarily that much easier to read and understand. I often miss having the cardinality and the amount of bytes read for each part of the query like Oracle query plans provide. Or is everyone really that happy with SQLite query plans?

There is EXPLAIN QUERY PLAN which outputs usual high level plan description. But there is no easily reached disk/cache usage stats.

Re: Why SQLite Uses Bytecode

#59

Post by jonp888 »

coolandsmartrr wrote: post #46
wolf550e wrote: post #29

The page is the result of this exchange on Twitter: https://twitter.com/gorilla0513/status/1784756577465200740 I was surprised to receive a reply from you, the author. Thank you :) Since I'm a novice with both compilers and databases, could you tell me what the advantages and disadvantages are of using a VM with SQLite? https://twitter.com/DRichardHipp/status/1784783482788413491 It is difficult to summarize the advan…

I am amazed that the author (D Richard Hipp) made an effort to find and respond to a tweet that was (1) not directed/"@tted" at him or (2) written in his native language of English (original tweet is in Japanese[1]). [1] https://twitter.com/gorilla0513/status/1784623660193677762

Side note, but I'm amazed that anyone that is not a journalist or a politician still actively uses X/twitter. Everyone I used to follow has stopped.

Re: Why SQLite Uses Bytecode

#60

Post by manx »

I'm wondering if one could write this bytecode directly (or with a higher level imperative language) instead of SQL. Often, the programmer knows exactly which index lookups need to happen in a loop, while it seems like a burden to express that in SQL. This might also be an opportunity to create a different type safe dsl for database access.
Post reply on HN