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

201–210 of 231 posts

Re: Why SQLite Uses Bytecode

#201

Post by JonChesterfield »

FridgeSeal wrote: post #86
tanelpoder wrote: post #54

Earlier quoted context omitted.

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 req…

That’s a really cool idea! Is there any writeups or articles about this in more detail?

It's called a template JIT. You get to remove the interpreter control flow overhead but tend to end up with a lot of register shuffling at the boundaries. Simpler than doing things properly, usually faster than a bytecode interpreter.

Re: Why SQLite Uses Bytecode

#202

Post by [deleted] »

AtlasBarfed wrote: post #121
paulddraper wrote: post #34

Earlier quoted context omitted.

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.

optimizing runtimes (usually bytecode) can beat statically compiled code, because they can profile the code over time, like the JVM. ... which isn't going to close the cold startup execution gap, which all the benchmarks/lies/benchmarks will measure, but it is a legitimate thing. I believe Intel CPUs actually sort of are #2. All your x86 is converted to microcode ops, sometimes optimized on the fly (I remember Intel…

[deleted]

Re: Why SQLite Uses Bytecode

#203

Post by JonChesterfield »

manx wrote: post #60

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.

Definitely yes. Databases and compilers have a lot in common. This bytecode is exactly equivalent to a compiler IR. It's called out as such in the OP where the decoupling between front end and backend is noted. Therefore you can construct the bytecode from outside of the database and feed it to the backend (may require patching sqlite to make the entry points accessible).

By analogy, this is really easy in LLVM. You can write the IR you want in a text file and feed it back into the infrastructure. This is used a lot in testing and debugging LLVM. It's much harder in GCC for reasons that never made much sense to me.

There's probably a parser for the format of the EXPLAIN text dump in sqlite somewhere intended for modifying the debug output then feeding it back into the engine. Maybe not documented, but I expect it works fine in practice.

Re: Why SQLite Uses Bytecode

#204

Post by JonChesterfield »

asvitkine wrote: post #133
manx wrote: post #60

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.

The main downside is now you're making the bytecode an API which means all future changes need to be backwards compatible.

You can do an automatic upgrade thing, where you recognise old formats and upgrade them on the fly. Possibly with a window on it where at sufficient age people need to run their elderly code through multiple upgrade cycles.

Or you can declare it an unstable interface and it's on the user to deal with it changing over time.

Or you can just leave it accessible without excessive work, but not document it, and then it's very obviously on the external tool to deal with the impedance matching.

Re: Why SQLite Uses Bytecode

#205

Post by masklinn »

kayodelycaon wrote: post #145
lqet wrote: post #106

Earlier quoted context omitted.

> I was advocating for it for decades, but everyone dismisses it with “you don’t know better than rdbms”. That’s almost a religion. Which is simply not true. Query optimization is done heuristically, for the simple reason that you usually need to run the query to get the information required for "perfect" optimization. If the RDBMS really knew better, it wouldn't offer query hints.

Postgres doesn't offer query hints. ;)

And that's regularly a problem, and why e.g. Amazon offers Query Plan Management, and there are extensions around hinting or fixing query plans.

Re: Why SQLite Uses Bytecode

#206

Post by iainmerrick »

pizlonator wrote: post #134

That’s awesome, I didn’t know SQLite had a bytecode. Based on my experience writing interpreters, I know that bytecode is faster to interpret. (Source: I wrote JavaScriptCore’s interpreter and it’s optimizing JITs. I’ve also worked on other language implementations. I’ve seen the AST vs bytecode thing play out more than once.)

Maybe I'm missing something, but the bytecode approach seems really obviously better, just from a memory usage and locality point of view. Scanning an array of bytes or words is obviously going to be faster than traversing a tree of pointers.

So I'd be surprised to find a serious language implementation using a pure AST in its interpreter, without at the very least flattening it to an array!

Edit to add: of course there are some cases where you might actually want the AST approach, as the Sqlite doc is careful to point out. But not very many.

Re: Why SQLite Uses Bytecode

#207

Post by iainmerrick »

naasking wrote: post #175

On incrementally running bytecode: > This is more difficult to achieve in a tree-of-objects design. When the prepared statement is a tree-of-objects, execution is normally accomplished by walking the tree. To pause the statement in the middle of a computation means unwinding the stack back up to the caller, all the while saving enough state to resume evaluation where it last left off. This is not impossible to do, bu…

I think the article is just trying to be scrupulously fair by listing all possible disadvantages as well as advantages. But I agree with you, the bytecode approach seems obviously better.

Re: Why SQLite Uses Bytecode

#208

Post by lmz »

blacklion wrote: post #125
wglb wrote: post #120

Earlier quoted context omitted.

I'm curious. Would you have a pointer to the documentation of PRG language?

Oooops, it is IBM RPG, not PRG! My bad! There are some links in Wikipedia. I never used it, but only read big thread about SQL vs RPG on Russian-speaking forum, and there was a ton of examples from person who works with IBM i platform in some big bank. Basic operations look like SQLite bytecodes: open table, move cursor after record with key value "X", get some fields, update some field, plus loops, if's, basic arith…

That kind of manipulation isn't limited to RPG. I believe dBase and descendants also work similarly with manual cursor manipulation.

Re: Why SQLite Uses Bytecode

#209

Post by tucnak »

IsTom wrote: post #80
bryancoxwell wrote: post #77

Earlier quoted context omitted.

I don’t doubt the author, but what is it that makes rendering a tree of objects to a table a difficult problem? Is that not what browsers do when they render a table element?

At least they're hard to display on a terminal. Reading EXPLAIN ANALYZE diagrams from psql does not spark joy.

It does in something like DataGrip. Honestly, I can't imagine using Postgres without it these days.

Re: Why SQLite Uses Bytecode

#210

Post by TeMPOraL »

wruza wrote: post #81
manx wrote: post #60

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.

I was advocating for it for decades, but everyone dismisses it with “you don’t know better than rdbms”. That’s almost a religion. Despite the fact that most of the tables most people have are never any big (except for a few oltps that you ought to leave to specific sql server wizards anyway) and you usually do have the idea how it should work. SQL is a cool solution for a set of problems that has a very non-zero xor…

I'm wondering the opposite - could RDBMS know better than programmer how to structure the program? The other day I had this realization, that if I squint, quite a lot of code I see and write could be seen as database tables, prepared statements, and specialized indexes. In particular, every time I use an associative table (or several) to speed up access to data along particular dimension (like X/Y coordinates in the world of a videogame), that's equivalent to making an index in SQL.
Post reply on HN