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

151–160 of 231 posts

Re: Why SQLite Uses Bytecode

#151

Post by mfoc »

bryancoxwell wrote: post #77
userbinator wrote: post #8

The problem of rendering a tree-of-objects as a table is sufficiently difficult that nobody does it, as far as I know. Hence, no tree-of-objects database engine provides the level of detail in their "EXPLAIN" output that SQLite provides. I believe Microsoft SQL Server uses an object tree internally, and yet its query plan output is a table: https://learn.microsoft.com/en-us/sql/t-sql/statements/set-s...

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?

Quote from the article:

"A tree-of-objects representation is more difficult to publish in a human-readable form. The objects that comprise the tree tend to all be very different, and thus it is tricky to come up with a consistent and simple table representation with which to display the objects. Any any such table representation that you do come up with would almost certainly have more than six columns, probably many more. The problem of rendering a tree-of-objects as a table is sufficiently difficult that nobody does it"

To further elaborate on this important point.

There is an 'impedance mismatch' (conceptual difficulty mapping between the two logic models) between the tree abstract data type and the table abstract data type. Specifically, there are four key differences between the simple table data structure and the more complex tree data structure that makes mapping between them a non-trivial operation.

Hierarchical: A table has a flat representation; a tree has a hierarchical representation.

Order: The order of the rows in a table typically do not matter (they may have a unique rowid). The order of branches (nodes) and leaves in a tree is important, and the ordering itself in an encoding of valuable information.

Semi-structured: A table has a fixed structure (rows multiplied by columns). A tree has a flexible structure - an arbitrary combination of branches (internal nodes) and leaves (terminal nodes). Semi-structured data has a structure that may not necessarily be known in advance, the tree has irregular and variable formation; the tree may have branches with missing or supplementary nodes.

Meta-data: The information describing the meaning of the data in a table is typically stored separately from the table - consequently a schema is often mandatory. A schema is optional for a tree abstract data type.

As an aside, I have been visiting hacker news almost daily since 2010. This is my first comment on hacker news. I want to say thank you to the community for the many valuable insights over this years.

Re: Why SQLite Uses Bytecode

#152

Post by xymostech »

pdubroy wrote: post #139

I think most people associate bytecode VMs / interpreters with general-purpose programming languages, but it's a surprisingly useful concept in other contexts. Sometimes bytecode VMs appear in unexpected places! A few that I'm aware of: - eBPF, an extension mechanism in the Linux kernel - DWARF expression language, with interpreters in debuggers like GDB and LLDB - The RAR file format includes a bytecode encoding for…

The original TeX Fonts stored their metrics in TFM (short for TeX font metrics) files, which contains a bytecode interpreter for calculating ligatures and kerning between characters. I learned about that when I tried reading the files myself.

From what I can tell, modern fonts using OpenType just have tables to accomplish something similar now, in the form of the GSUB and GPOS tables?

Documentation for the TFM format here: https://tug.org/TUGboat/Articles/tb02-1/tb02fuchstfm.pdf (search for lig/kern)

Re: Why SQLite Uses Bytecode

#153

Post by samatman »

adontz wrote: post #45

Looks like SQLite could benefit from copy-and-patch JIT compiler.

I think this is unlikely for SQLite (other comments cover why it probably wouldn't happen even if it were likely to benefit), but I happened to have the copy and patch paper open in a tab, so I'll take the opportunity to share it here.

https://sillycross.github.io/assets/copy-and-patch.pdf

It has great potential for many applications, if not this particular one.

Re: Why SQLite Uses Bytecode

#154

Post by Sesse__ »

hn_throwaway_99 wrote: post #5
runlaszlorun wrote: post #3

Earlier quoted context omitted.

SQLite is the first one I’ve looked at the internals of. Do others walk an AST of the query instead?

FTA: > Tree-Of-Objects → The input SQL is translated in a tree of objects that represent the processing to be done. The SQL is executed by walking this tree. This is the technique used by MySQL and PostgreSQL.

Note that this only holds true for fairly recent MySQL (MySQL 8.x, not including the oldest 8.0.x releases). 5.7 and older, and by extension MariaDB, instead models pretty much everything as a large fixed-function recursive function that calls itself for each new table in the join, plus some function pointers for handling of GROUP BY and such.

TBH, when it comes to query execution (A JOIN B JOIN C GROUP BY …), I think the difference between SQLite's bytecode and a tree of iterators (the classical Volcano executor) is fairly small in practice; they are quite interchangeable in terms of what they can do, and similar when it comes to performance. The difference between bytecode and tree structure is much larger when it comes to evaluation of individual expressions (a + b * cos(c)), especially since that involves much more of a type system; that is more obviously in the “bytecode is the way to go” camp to me.

Re: Why SQLite Uses Bytecode

#155

Post by lupusreal »

infecto wrote: post #99
jonp888 wrote: post #59

Earlier quoted context omitted.

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.

I'm amazed people like yourself care so much about it to write a post like this. Doesn't your brain have something better to think about beyond artificial outrage?

"I'm surprised people use $WHATEVER because nobody uses it" usually means "I don't like $WHATEVER and wish you would stop using it."

I see this frequently directed towards reddit and twitter.

Re: Why SQLite Uses Bytecode

#156

Post by immibis »

zarathustreal wrote: post #88
jonp888 wrote: post #59

Earlier quoted context omitted.

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.

[flagged]

I stopped using Twitter because "Space Man" banned most of one political side. Maybe if you didn't notice that, you're in a bubble?

Re: Why SQLite Uses Bytecode

#157

Post by galaxyLogic »

fancyfredbot wrote: post #79
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.

For simple functions which are not called repeatedly you have to invert this list - interpreted code is fastest and compiling the code is slowest. The complied code would still be faster if you excluded the compilation time. It's just that the overhead of compiling it is sometimes higher than the benefit.

I wonder in actual business scenarios isn't the SQL fully known before an app goes into production? So couldn't it make sense to compile it all the way down?

There are situations where the analyst enters SQL into the computer interactively. But in those cases the overhead of compiling does not really matter since this is infrequently done, and there is only a single user asking for the operation of running the SQL.

Re: Why SQLite Uses Bytecode

#158

Post by Sesse__ »

anon291 wrote: post #20
chrisaycock wrote: post #2

SQLite's design docs were the first time I had seen a database use a virtual machine instead of walking a tree. I later noticed VMs in libraries, embedded DSLs, and other applications outside of large general-purpose programming languages. That really drove home for me that VMs could be anywhere and were often a useful step in handling a user's expressions.

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…

> Also, most SQL plans are trees (Until you get to WITH RECURSIVE).

WITH RECURSIVE can also generally be implemented tree-style, you just loop a bunch in one of the iterators.

There are some databases, like Umbra, which can have DAG query plans for the benefit of more efficient groupjoin (GROUP BY pushed down into a join). IIRC some of the unnesting patterns can also benefit from non-tree plans.

Re: Why SQLite Uses Bytecode

#159

Post by Sesse__ »

MrBuddyCasino wrote: post #19

I was surprised the text didn’t mention one major difference between the byte code approach vs AST: coupling. When your database engine runs in-process, there is no possibility of the server and the client library having diverging versions. But this is common with traditional databases. Once you bake in the execution steps („how to execute“) instead of describing the query via AST („what to execute“), an important pa…

> Not an issue for sqlite, potentially disastrous for mysql.

MySQL _completely_ switched execution paradigm through the course of a couple of 8.0.x sub-releases, generally without anyone noticing.

Re: Why SQLite Uses Bytecode

#160

Post by wolf550e »

SQLite wrote: post #96
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.

Performance analysis indicates that SQLite spends very little time doing bytecode decoding and dispatch. Most CPU cycles are consumed in walking B-Trees, doing value comparisons, and decoding records - all of which happens in compiled C code. Bytecode dispatch is using less than 3% of the total CPU time, according to my measurements. So at least in the case of SQLite, compiling all the way down to machine code might…

It is possible to construct a worst case scenario for bytecode execution, for example very complex expressions in the WHERE and/or SELECT clauses that compute values, and a query plan that performs a full table scan over a table with say 100 million rows that is cached in RAM (or maybe use generate_series, whatever works best).

Computing the expressions should dominate execution time, right?

Then, to compare against the best possible case, we can write a custom C program that uses sqlite internals to perform the same task (full scan of the table, extract values from row) and does not use the bytecode VM and computes the complex expressions in regular C code (e.g. a function that accepts floats and returns a float or whatever).

Then comparing the two implementations will tell us how much faster sqlite can be if it had a "perfect" JIT.

Post reply on HN