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 provide a performance boost 3% or less. That's not very much, considering the size, complexity, and portability costs involved.
A key point to keep in mind is that SQLite bytecodes tend to be very high-level (create a B-Tree cursor, position a B-Tree cursor, extract a specific column from a record, etc). You might have had prior experience with bytecode that is lower level (add two numbers, move a value from one memory location to another, jump if the result is non-zero, etc). The ratio of bytecode overhead to actual work done is much higher with low-level bytecode. SQLite also does these kinds of low-level bytecodes, but most of its time is spent inside of high-level bytecodes, where the bytecode overhead is negligible compared to the amount of work being done.
Part of the benefit of compiling bytecode (or anything) is specializing code to the context (types, values, etc) in which it appears. While I don't doubt your analysis, it could be the case that compiled C code in question is full of branches that can be folded away when specialized to the context of the query, such as the structure of the rows, the type and values of columns, etc.
Basically all of what you are saying about high-level bytecodes applies to dynamic languages, too. But they benefit highly from specializing each bytecode given static and dynamic context, and shortcutting dataflow through local variables.
There's usually a cost to shuttling data between bytecodes too. When two are fused together the second can lift the data from wherever the first wanted to leave it, as opposed to routing through a fixed location. Might be what you mean by shortcutting dataflow?
Also doing control flow in bytecode is usually slower than doing it in the native code.
I wonder if the context in which the instructions occur is sufficiently finite in sqlite for ahead of specialisation of the bytecode to be better. That is, the program you're operating on isn't known until JIT time, but the bytecode implementations are. SQL should correspond to an unusually specific set of operations relative to a general purpose language implementation.
The compiler will notice some values are constant when working with the bytecode. It can know ahead of time which arguments correspond to folding branches within the bytecode instructions and specialise correspondingly. If that works, you've emitted a sequence of calls into opcodes which are less branchy than they would otherwise be, at which point the opcode implementations start to look like basic blocks and a template JIT to machine code beckons.
> Most CPU cycles are consumed in walking B-Trees, doing value comparisons, and decoding records
Emphasis added. This is because of SQLite3's varint encoding method for numbers. Performance-wise it was probably a mistake, though it's a form of compression, which might have paid off in terms of space.
(I seem to remember seeing something, possibly by you, about this before.)
I wonder if it would be possible to replace the varint encoding... Yes, it'd be a compatibility break in that older SQLite3s couldn't open newer DBs.
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 arithmetic, etc.
Well, having programmed RPG professionally, there is no question that a python programmer would clock any RPG programmer. RPG is a terrible way to program.
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.
> A key point to keep in mind is that SQLite bytecodes tend to be very high-level
That's right. "Bytecode" is a spectrum. SQLite's bytecode is higher-level than e.g. WASM, JVM, Python, etc. (Notably, because the original source code is higher-level.)
A while back was musing if it was possible to come up with something resembling the instruction set for a CPU for an abstract relational-engine. Is this basically what SQLite is doing with bytecodes?
I think yes, essentially. Bytecode running on a software interpreter is the same thing as machine code running on a silicon interpreter. Probably slower, probably a different ISA, but very much the same idea.
The OP suggests the sqlite bytecode also has arithmetic & control flow in it which you might want to exclude in other settings. There's a parallel with cisc vs risc instruction sets here, and to calls into a compiler runtime vs expanding instructions into larger numbers of more primitive ones in place.
@rkrzr there's a circular definition in your "no" - if "CPU" means "an interpreter that executes instructions simpler than SQL" then this is indeed not an instruction set. If "CPU" means "interpreter of a given ISA" then it could be. The virtual machine in the sqlite codebase is the definition of the CPU for this instruction set. Unless you want to define CPU as exclusive of software implementations of interpreters.
> Bytecode dispatch is using less than 3% of the total CPU time, according to my measurements
> compiling all the way down to machine code might provide a performance boost 3% or less
This logic doesn't seem sound? Because the application now spends 3% on bytecode dispatch doesn't tell us anything about how long it would instead spend on e.g. interpreting SQL.
Unfortunately you can’t do performance analysis this way but I think the overall point that it’s a fraction probably still stands as you’d expect the I/O work to dominate.
The reason you can’t do the analysis the way that you explicitly stated (which fairly is what was implied) is that when you lower the code to machine code you typically get rid of branches in the execution path. Since branches slow down execution by a disproportionate amount vs how long they themselves take, it’s easy to get a >3% boost getting rid of code paths that seem like there’s only 3% of room.
What the author also failed to mention is that they’ve gone on many optimization hunts eeking out less than a percent here or there to get a cumulative boost, so 3% isn’t anything to sneeze at.
That being said, the broader point which is valid is that the maintenance isn’t worth the performance profile that SQLite targets not to mention that JITs open up an attack vector for security exploits. So the cost vs benefit is squarely in the interpreted side for now.
Edit: Forgot to mention that performance tuning a JIT to work well is also hard - for small queries you’ll spend more time compiling the byte code than you would just executing. That’s why all the big JS engines do a tiered approach where each tier optimizes a bit more.
Holy smokes, that's the coolest thing I've found out about recently.
I'm trying to wrap my head around where this sits within the OS. Is it a layer "on top" of everything? Or does it sit "underneath" the higher level os functionality?
Apologies if that doesn't make any sense, it looks to be a really cool tool and I'll be investigating it regardless.
About 10% overall (9.96% to be precise), according to server logs over the previous 10 days.
Robots hit dynamic content at about twice the rate as humans: 14.12% versus 7.8%. About 34% of traffic is from robots, from what I can tell (though to be
fair, many robots these days work hard to disguise themselves has human, so
the actual percentage of robot traffic is likely much higher.)
That is inaccurate. Ginko's statement is closer to truth.
I was inspired to write SQLite while working with Informix on DDG-79 and I saw how useful an embedded database would be in some situations, compared to a client/server solution. So I went off and wrote SQLite on my own, while the development contract was on hiatus. There was never a request for SQLite or anything like it coming from the the navy (or more precisely, Bath Iron Works) as they were both very happy with Informix on the ship and Oracle on land and had zero desire for anything new or different. The development team I worked on ended up using SQLite some for prototyping and testing on that project, but it was never deployed to the ship, as far as I know.
So yes, the whole point of SQLite was to build a database that operated as a library linked into the application, rather than as a separate server, as ginko postulates. Design issues on a single system within DDG-79 (Automated Common Diagrams) were the inspiration for that idea, but to say that SQLite was designed for DDG-79 is not true. There was never a request for SQLite coming from the navy or the ship designers. Indeed, there is was a lot of pushback against SQLite. SQLite was just a crazy idea coming from a rogue developer who happened to be working on one of the many on-board systems at that time.
I've always wondered why sqlite came along, but adoption of msql (Matt Dillons' similar database stack) didn't catch on .. did you have any opportunity to review the existing database tools that were available at the time, and if so - what did you find?
I realize this question is a bit archaic so if there's not really any good answers, no worries - but as I was using Matt's msql in the 2000's in the same way that I now use sqlite, its something I often wonder whenever I set up a new sqlite.db ...
One example: Fossil (https://fossil-scm.org), the version control system used by SQLite itself. Fossil is Git-like in its underlying design but has a different interface. Fossil stores a complete source code repository as an SQLite database, rather than a pile-of-files as Git does. Storing content this way gives Fossil UI advantages over Git, such as the ability to easily find decedents of a check-in, and the ability to assign the same tag to multiple check-ins (ex: tagging every release with the "release" tag.)
Yeah - I'm very much about maintaining an immutable record. That is why, back in 2006, I started designing Fossil to control SQLite, instead of just switching to Git.
I think that proper version control should be immutable. If history is changeable, what's the point in having history at all? It ceases to be "history" and becomes just a fable or hagiography.
Mistakes happen, and it is important to be able to correct them, which Fossil does do. In many ways Fossil's mistake-correction logic is far better than Git's. If you make a check-in to the wrong branch, you can move it after the fact in Fossil. If you check-in with the wrong user-id, or a with a goofy check-in comment, you can edit those too. Was your system clock wonky when you did the commit, resulting in a bad timestamp on the check-in, that too can be fixed. I say "edit" - really you are not modifying the original check-in at all. The original check-in is immutable. But Fossil supports the ability to add correction records (tags) on top of check-ins. The original history is preserved and you can always drill down to find out exactly what happened. But for routine day-to-day usage, only the corrected values are shown on displays and reports. So it is like being able to change history, except that you are left with an audit trail.
This is how accounting and legal systems work. You never erase - you only add corrections.
Which is fine for someone to have as a perspective, I just think that philosophy is far too limiting for a universal VC system and misses the point of what many people use VC for.
It's not so much "the people who are designing Fossil are bad at designing it" as much as it is "I disagree with their starting premises and their goals for the thing they're building." If someone comes to me and asks why they would want to use Git over Fossil, the primary thing I would point at is:
> This is how accounting and legal systems work. You never erase - you only add corrections.
I just personally think that can be in many situations an unhelpful way to think about what a VC is at a fundamental level; I don't think a VC is inherently an accountability system or a legal system, and I think that having that rigidity can get in the way of certain workflows. Again, opinion me, I know you're quite happy with Fossil for SQLite, and that's great and I'm sure it works great. It's not like it's bad to have opinionated tools, I just think that it gets in the way of treating Fossil as something I would recommend as a general Git replacement for everyone.
It comes down to: is the ability to rewrite "history" (which is not even really history at all in Git, it's just a collection of ordered changes) a feature or a problem? Fossil thinks it's a problem, I think it's a feature. Fossil looks at repository history like a historical record, I look at repository "history" as purely an organizational tool for checkpointing/documentation.
> I just personally think that can be in many situations an unhelpful way to think about what a VC is at a fundamental level;
The Devil's Advocate in me feels compelled to point out that git is (to the very best of my fallible knowledge) the _only_ SCM in history to permit rewriting of history. Certainly SVN, CVS, and their predecessors did not get it all wrong by not enabling editing of history?
Admittedly, rebase/squashing/etc. is _necessary_ for a Linux-kernel-scale project, but 99.99+% of software projects are, in terms of the number of contributors/contributions, so far removed from that scale as to not even register on that scale.
Other version control systems don’t give you tools to manage your work while it is being prepared and reviewed, before it is committed to the shared repository. That is when much of the rewriting happens.
> The Devil's Advocate in me feels compelled to point out that git is the _only_ SCM in history to permit rewriting of history. Certainly SVN, CVS, and their predecessors did not get it all wrong by not enabling editing of history?
There are a lot of reasons I don't use SVN and CVS, but correct, their branch model is one of them. I do think that Git's restructuring of how commits and branches work and the flexibility around them is one of the reasons its better than older VC systems.
I'm not sure how strict those older VCs actually were, I'm less familiar with them than I am with Git/Fossil, but... yeah I have no problem saying that if they were doing fully immutable history they were wrong to do so (or maybe "wrong" isn't the best term to use, more that it would be an attribute that I think would make them less useful to a lot of developers).
> 99.99+% of software projects are, in terms of the number of contributors/contributions, so far removed from that scale as to not even register on that scale.
I would disagree with this, I think rebasing/squashing is just a really useful tool, even for smaller projects. It's sort of a difficult debate to have because it's mostly going to come down to opinion. What does necessary mean in a smaller project, VC itself is not strictly necessary for many smaller projects.
SQLite gets by fine with Fossil, the developer prefers having an immutable history. But I'm not sure what to say other than that I use rebasing a lot. Different projects have different development styles.
Last time I used SVN I rebased all the time, no problem. I was using a git-to-svn bridge though. My point is, people will rewrite history on their own computer whether you want them to or not. Git is the only VCS that doesn't fight against that fact.
> I think that proper version control should be immutable. If history is changeable, what's the point in having history at all? It ceases to be "history" and becomes just a fable or hagiography.
Many git users agree, including the kernel from memory. By that I mean there is often some git tree (maybe called "production", "main" or "master") were "fast roll forward" is the only style of commit accepted. Ie, on that tree, you can't change history. But when you're using git to built a commit to that tree, you are allowed (and in the kernel's case expected), to clean the history up, removing all your mistakes and experiments, so the people following the main branch don't have to wade through all that crap.
So the difference is git allows it to be a policy setting, whereas I take it Fossil forces it to be turtles all the way down.
History is only immutable once it's committed to Fossil, and anything not committed is lost forever. This may sound banally obvious, but I think it's fundamentally the problem with Fossil's approach. With git I essentially commit my entire undo/redo stack. I end up discarding most of that later, while with Fossil I would never have committed those intermediate versions in the first place.
Without history rewriting, the rewriting simply takes place before committing instead of after.
I use fossil as my daily driver VCS and I feel like it doesn't go far enough in it's ability to non-destructively amend history. The canonical justification for git-style rewriting is taking all the commits that make up some feature and smashing them down into one "implemented feature X" commit which, as far as I know (?), does not have an analogue in Fossil. Even something like forgetting to add a file to a commit requires an additional commit (and shows up as such on the timeline) with a silly "forgot to include file foo in commit whatever" comment.
Ideally there'd be some kind of "virtual commit" capable of (visually) bundling up a range of commits, with its own message and tags; maybe these could be nested so that you could have a hierarchical view of the timeline: initially you see "release X, release Y" but then you can expand any of those to "implemented feature A, B" which can be further expanded into the actual commits.
Note that there have been no breaking changes since the file format was designed in 2004. The changes shows in the version history above have all be one of (1) typo fixes, (2) clarifications, or (3) filling in the "reserved for future extensions" bits with descriptions of those extensions as they occurred.
No - because nobody has provided a reproducible test case to show an actual performance regression. If we can't reproduce it, then how are we suppose to fix it?
It does do exactly that. If you visit https://sqlite.org/src/stat, the "Schema Version" line tells you exactly what version of the database schema that the repository is using. The SQLite repository uses the very latest Fossil schema, which you can see from the "stat" page has not changed in 8.5 years.
So at least in the case of SQLite, compiling all the way down to machine code might provide a performance boost 3% or less. That's not very much, considering the size, complexity, and portability costs involved.
A key point to keep in mind is that SQLite bytecodes tend to be very high-level (create a B-Tree cursor, position a B-Tree cursor, extract a specific column from a record, etc). You might have had prior experience with bytecode that is lower level (add two numbers, move a value from one memory location to another, jump if the result is non-zero, etc). The ratio of bytecode overhead to actual work done is much higher with low-level bytecode. SQLite also does these kinds of low-level bytecodes, but most of its time is spent inside of high-level bytecodes, where the bytecode overhead is negligible compared to the amount of work being done.