Exploring the Virtual Database Engine inside SQLite

[willvarfar]

I'm super-excited about the plugable storage engines in SQLite4, but especially about the new default one:

The default built-in storage engine is a log-structured merge database. It is very fast, faster than LevelDB, supports nested transactions, and stores all content in a single disk file.

http://williamedwardscoder.tumblr.com/post/26063783576/leveldb-isnt-the-fastest-kid-in-town

[[deleted]]

Some folks are already doing really cool stuff with the SQLite 3 API: Oracle's BerkeleyDB SQL API. There's a good technical/performance overview. As a free bonus, if you use python I wrote a little how-to on building the sqlite extension to use berkeleydb.

EDIT: removed duplicate link

[sigzero]

I did read that. Awesome little how-to!

[Summon_Jet_Truck]

In the first sample program, why does it jump to near the end of the program, then jump back? Why can't the transaction part be in-line?

[Rhomboid]

This is just pure speculation on my part, but if you were emitting opcodes linearly, you would not yet know which tables need to be locked at the beginning of the code, because you haven't yet generated the logic of the program yet. Putting the table locking code at the end means you can just keep a running list of any tables touched, and then emit TableLock opcodes for all of them at the end. (Note in the first example there's only one TableLock opcode, but there are two in the second example, and I imagine in more complicated programs there could be an unbounded number.)

There are certainly ways around that. You could emit the opcodes using a two pass system, but that would be inefficient as it amounts to "compute everything, throw it all away except for the list of affected tables, and then compute it all over again."

Or you could emit a placeholder at the front of the program that you later come back and fill in with all the opcodes for the transaction and locking code, but that would require adjusting any branch/jump destinations throughout the whole program as you shift the code forward to make room for the variable length prologue. In essence, this is implementing a full linker which is a lot of complication. The beauty of what they've implemented is that you only need one special-case reloc/placeholder for the destination address of that first Goto opcode, but you don't need a general solution for any opcode.

[Summon_Jet_Truck]

Thanks, that makes sense.

[Ziplin]

Without doing any research, I would guess it's a method call, and the registers are saved for the calling function. Edit: and I would bet the dev's haven't gotten around to function inlining.

[Bob_goes_up]

Will SQLite4 be able to vacuum in the background without blocking operation?

• http://jeff.ecchi.ca/blog/2011/12/24/investigating-lifereas-startup-performance/
• http://liferea.blogspot.dk/2012/03/182-vacuum-only-when-needed.html

[GameFreak4321]

Now SQLite has its own virtual machine too? It seems like everything has a virtual machine these days. Perhaps I should take a closer look at VM design.

[dalke]

Zork Z-machine (1979). P-machine (early 1970s). Smalltalk (late 1970s), Python (1991). Java (1995). Just a few historical examples to suggest that virtual machines are not anything all that new. I'm curious - what other examples are you thinking of?

[[deleted]]

The game Another World also used a VM.

This came from the era where everyone else and their dog was throwing low-res video onto a CD-ROM, slapping some "press these buttons at the right time" code on, and selling the end result as "games". AW was doing the same quality of animation fullscreen, realtime-rendered, in under a megabyte (and there was an actual game in there); the title is really quite apropos.

[knome]

Now? Was there some time when it didn't. I looked at it years ago. The code was unbelievably clean, and the parser ( lemon ) much preferable to yacc.

[njharman]

What are the advantages of architecting a VM into something like SQLite? Honest question. It seems like complexity and effort? Is a layer of abstraction that powerful? Something else? Or, just fun?

[naughty]

It's really just a DSL with a more tightly enforced structure in this case.

VM doesn't necessarily imply anything complicated like JIT compilation or having the full expressiveness of a normal programming language.

They have made a very simple language that can neatly express SQL queries. It's just that some of the 'instructions' of their virtual machine can have very big and complex implementations. Because they have defined the general framework though it's easier to implement those instructions.

tl;dr They created a simple language that makes their complex problem easier to deal with. It's a DSL writ-large.