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

21–30 of 231 posts

Re: Why SQLite Uses Bytecode

#21

Post by surfingdino »

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.

Doesn't MS Word internally run a Forth-like VM? I remember reading an article by someone who decompiled an early MS-DOS version of Word only to discover that there was a VM inside.

Re: Why SQLite Uses Bytecode

#22

Post by megadal »

Perhaps my understanding is off, but I am pretty sure parsing and translating SQL into bytecode still involves an AST.

Just that query processing itself is done from the bytecode (produced presumably from an AST or something similar) rather than directly from the AST itself.

If I'm right I can't really see how this performs better unless you're excluding the parsing step from benchmarks

Re: Why SQLite Uses Bytecode

#23

Post by lifthrasiir »

megadal wrote: post #22

Perhaps my understanding is off, but I am pretty sure parsing and translating SQL into bytecode still involves an AST. Just that query processing itself is done from the bytecode (produced presumably from an AST or something similar) rather than directly from the AST itself. If I'm right I can't really see how this performs better unless you're excluding the parsing step from benchmarks

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.

Re: Why SQLite Uses Bytecode

#24

Post by miloignis »

megadal wrote: post #22

Perhaps my understanding is off, but I am pretty sure parsing and translating SQL into bytecode still involves an AST. Just that query processing itself is done from the bytecode (produced presumably from an AST or something similar) rather than directly from the AST itself. If I'm right I can't really see how this performs better unless you're excluding the parsing step from benchmarks

An AST being generated as an intermediate step is mentioned in the article, at least in passing in section 2.4.

The reason bytecode is generally faster (not just for SQL, but in most interpreted languages you may use (Python, etc)) is that walking the AST is relatively expensive and doesn't treat caches nicely. Bytecode is generally located next to each other in memory, and you can make the bytecode fetch/dispatch pretty tight, relative to indirect function calls on an object in an AST.

Re: Why SQLite Uses Bytecode

#25

Post by runlaszlorun »

bane wrote: post #13
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.

VMs really can be. They have a long history in code portability. In the old days it really wasn't uncommon to use an approach centered around some interpretable byte code running in a vm, where the reusable vm was all that needed porting to different architectures and operating systems. This all happened well before Java. It was really big in gaming, Zork, Sierra games, LucasArts games, and even a few more "action" g…

And Pascal p-code! Not the first, I’ve heard, but I believe it’s close to being the first.

Re: Why SQLite Uses Bytecode

#26

Post by tadfisher »

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…

Do clients typically communicate with the server in some AST representation instead of, well, SQL? I'd be surprised if that much parsing/planning happens on the client.

Re: Why SQLite Uses Bytecode

#27

Post by Scaevolus »

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…

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

Re: Why SQLite Uses Bytecode

#28

Post by megadal »

lifthrasiir wrote: post #23
megadal wrote: post #22

Perhaps my understanding is off, but I am pretty sure parsing and translating SQL into bytecode still involves an AST. Just that query processing itself is done from the bytecode (produced presumably from an AST or something similar) rather than directly from the AST itself. If I'm right I can't really see how this performs better unless you're excluding the parsing step from benchmarks

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

Re: Why SQLite Uses Bytecode

#29

Post by wolf550e »

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 advantages and disadvantages of byte-code versus AST for SQL in a tweet. I need to write a new page on this topic for the SQLite documentation. Please remind me if something does not appear in about a week.

Re: Why SQLite Uses Bytecode

#30

Post by MrBuddyCasino »

tadfisher wrote: post #26
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…

Do clients typically communicate with the server in some AST representation instead of, well, SQL? I'd be surprised if that much parsing/planning happens on the client.

Since prepared statements are created by the driver, I was assuming this was the case - but I might be completely wrong here.
Post reply on HN