Why SQLite Uses Bytecode
sqlite.org
sqlite.org
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.
1. interpreted code
2. compiled then interpreted bytecode
3. compiled machine code
The further up, the simpler.
The further down, the faster.
You can also compile to bytecode (when building), and then compile that bytecode to the machine code (when running). That way, you can take advantage of the exact processor that is running your program.
This is the approach taken by .NET and Java, and I presume most other runtime environments that use bytecode.
Different JIT compilers have different levels of sophistication, being able to dynamically profile code at runtime or otherwise, and the range of applied optimizations of this type may also vary significantly.
Then, AOT imposes a different restrictions in the form of what types of modularity the language/runtime wants to support (Swift ABI vs no AOT ABI in .NET NativeAOT or GraalVM Native Image), what kind of operations modifying type system are allowed, if any, and how the binary is produced.
In more trivial implementations, where JIT does not perform any dynamic recompilation and profile based optimizations, the difference might come down to simply pre-JITing the code, with the same quality of codegen. Or the JIT may be sophisticated by AOT mode might still be a plain pre-JIT which makes dynamic profiling optimizations off-limits (which was historically the case for .NET's ReadyToRun and partially NGEN, IIRC JVM situation was similar up until GrallVM Native Image).
In more advanced implementations, there are many concerns which might be at odds with each other: JIT compilers have to maintain high throughput in order to be productive but may be able to instrument intermediate compilations to gather profile data, AOT compilers, in the absence of static profile data (the general case), have to make a lot more assumptions about the code, but can reason about compiled code statically, assuming such compilation comes with "frozen world" type of packaging (rather than delegating dynamic parts to emulation with interpreter).
And then there are smaller details - JIT may not be able to ever emit pure direct calls for user code where a jump is performed to an immediate encoded in the machine code, because JIT may have to retain the ability to patch and backpatch the callsites, should it need to de/reoptimize. Instead, the function addresses may be stored in the memory, and those locations are encoded instead where calls are emitted in the form of dereference of a function pointer from a static address and then a jump to it.
JIT may also be able to embed the values of static readonly fields as JIT constants in codegen, which .NET does aggressively, but is unable to pre-initialize such values by interpreting static initialization at compile time in such an aggressive way that AOT can (constexpr style).
So in general, a lot of it comes down to offering a different performance profile. A lot of the beliefs in AOT performance stem from the fact lower-level languages rely on it, and the compilers offering it are very advanced (GCC and Clang mainly), which can expend very long compilation times on hundreds of optimization passes JIT compilers cannot. But otherwise, JIT compilers can and do compete, just a lot of modern day advanced implementations are held back by the code that they are used for, in particular in Java land where OpenJDK is really, really good, but happens to be hampered by being targeted by Java and JVM bytecode abstraction, which is not as much of a limitation in C# that can trade blows with C++ and Rust quite confidently the moment the abstraction types match (when all use templates/struct generics for example).
More on AOT and JIT optimizations (in the case of .NET):
- https://devblogs.microsoft.com/dotnet/performance-improvemen...
- https://migeel.sk/blog/2023/11/22/top-3-whole-program-optimi...
If someone has similar authoritative content on what GraalVM Native Image does - please post it.
In fact, JIT can perform slightly better once the program reaches "steady state" because it can target the exact processor running and also perform the dynamic profile-guided optimization, which may or may not yield meaningful improvements in real life.
Nick Chapsas did some benchmarking of .NET AOT vs JIT, if you are interested:
For example, Java/JVM compiles bytecode AOT and compiles machine code JIT.
Edit: It's worth clarifying that the entire codebase does not run like that, not even the entire plan tree - just the scans and tight vectorized aggregation/join loops on the columns/data ranges that happen to be held in RAM in a columnar format.
Is this just the same as "interpret the query plan" or am I missing something?
So this is not bytecode interpretation, it's native machine code executed directly on CPU whenever the SQL exec engine decides to jump there. This is different from, say Apache Impala that compiles new LLVM machine code for each query execution for the query's scanning tight loops.
Edit: I guess why I see this as not just not regular bytecode interpretation (I don't actually know that much about it in general), is that these building blocks can include various loops (and can do their thing on entire vectors of data), so looks like they can push quite a bit of complexity into the machine code sections, before returning back to the normal interpreted AST/opcode land.
You might call those interpreter operations.
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.
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.
You would hope, but no that's not reality. In reality most of the people "writing SQL" in a business scenario don't even know SQL, they're using an ORM like Hibernate, SQLAlchemy, or similar which is dynamically generating queries that likely subtly change every time the application on top changes.
In situations where you have a limited number of queries and these are used repeatedly then some kind of cache for the complied code will be able to amortise the cost of compilation.
I certainly agree that a situation where an analyst enters SQL manually is a weird niche and not common. However most applications can dynamically construct queries on behalf of users and so getting a good hit rate on your cache of precompiled queries isn't a certainty.
On the other hand, query plan may depend on the specific parameters - the engine may produce a different plan for a query for users with deleted=true (index scan) and for deleted=false (99% of users are not deleted, not worth it to use index).
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.
Edit: PRG->RPG.
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 arithmetic, etc.
To be fair, RPG has been continuously updated and the version I’ve seen has Java integration.
It’s somewhat amusing that a single developer using Python can run circles around entire teams of RPG programmers. Technology marches on. :)
> 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.
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.
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.
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.
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.
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.)
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.
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.
... 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 discussing "micro ops fusion" a decade ago I think).
Getting on par with GCC/Clang with your own JIT is pretty hefty.
[1] https://twitter.com/gorilla0513/status/1784623660193677762
And they are all barely breathing.
The community density is low (because of the split), the discovery sucks (because of decentralization and no algo to suggest content), the culture is homogeneous (I encounter people mostly from one political side) and the publication of limited quality.
You can't start new communities from old users. Communities are built by the young, they are the ones with the creativity, motivation and free time to do it.
That's why twitter, made mostly by young people from 20 years ago, still got the inertia of it, are is more interesting and active.
And that's why tik tok and roblox are full of life. I'm sure the kids are also elsewhere, where we are not looking, creating the communities of tomorrow.
In sports, for instance, if you are talented and 15 there are pipelines into established and pro sports that make sense to follow. If you are 30 and missed your chance for that you can still be a pioneer in an emerging “extreme” sport.
A lot of young people seem to think creativity is 99% asking for permission and 1% “just do it”, it takes some experience before people realize it is really the other way around.
I see this frequently directed towards reddit and twitter.
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...
The estimated/actual execution plan feature in SQL Server Management Studio was changed to use XML in SQL Server 2005. The SQL Server team are only adding new information to the XML representation, not the text representation.
The name "estimated" execution plan is a bit misleading. If you executed the statement(s) with the current indexes and statistics, that's how it would be executed. I think the "estimated" part of the name is because the number of rows returned from each node, and the execution time of each node, is an estimate.
Assuming that the indexes and statistics don't change, you should expect the "actual" execution plan to have the same shape. It will just be annotated with the number of rows that were actually retrieved as well as the estimated numbers. SQL Server doesn't re-plan if it turns out the number of rows was greater (or fewer) than expected.
As a SQLite and SQL Server user, I find that I would like something more detailed from SQLite than EXPLAIN QUERY PLAN (which just tells you the join order), but less detailed than the bytecode. Particularly I want to know why it chose that join order or to use that index.
I second your longing for something more detailed than explain query plan in Sqlite though.
In fact I complained about it here and some sqlite developer pointed me to these resources:
https://news.ycombinator.com/item?id=30405275
I've never actually tried yet. Queries are still too fast to do all that:)
"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.
What I want to do is represent my tree-structure as a table in a relational database and then be able to efficiently get the tree structure back by transforming the table-representation back into a tree.
Further I would like to do that in plain standard SQL. This must be a common problem, any documented solutions out there?
Great question - you have touched on the key difference between a labeling scheme and an encoding scheme for tree data structures.
As mentioned previously, the tree is an abstract data type, that is to say, a conceptual model that defines the nodes in a tree, and their relationships.
To be able to evaluate a expression that processes a tree, one needs a labeling scheme. The purpose of a labeling scheme is to assign unique labels to each node in the tree and these labels must facilitate node ordering, and often (but not always) a labeling scheme will permit the reconstruction of the tree structure.
However, no labeling scheme captures the node type, names or the content stored at the nodes. For that we need an encoding scheme. An encoding scheme is constructed upon a labeling scheme and augments it with the information necessary to fully represent the tree in a table-like data structure. In answer to your question, it also permits the full transformation from the table representation to the original tree structure.
Thus, it sounds like what you are looking for is an encoding scheme.
There are many different labeling schemes out there for tree structure data, and virtually all of them can be augmented with additional information to construct a complete encoding scheme. Concerning documented solutions - I have not been active in this space for a number of years, so off the bat - I don't have a recommended documented solution to point you too.
But to help, I will put a link to my PhD thesis [1] which gives a more in-depth understanding of labeling schemes and encoding schemes for tree structured data with an example of a simple implementation of an encoding scheme enabling the full transformation from the table representation to the original tree structure (pages 5-9) and a survey of the advantages and disadvantages of existing labeling schemes concerning their usefulness to be part of an encoding scheme you could use in your solution (see chapter 2)
Caveat 1: My thesis was written in the context of updating dynamic (XML) trees but it addresses the transformation between tree and table data structures.
Caveat 2: The thesis was written 11 years ago, but every now and then I have kept in touch with the latest developments in the area, and to my knowledge, there have been no major developments since.
I hope it helps.
select
-- count(*)
a.mandt, b.rldnr, a.bukrs, a.gjahr, a.belnr, b.docln, a.buzei
-- *
from BSEG as a
innerjoin ACDOCA as b
on b.rclnt = a.mandt
and b.rbukrs = a.bukrs
and b.gjahr = a.gjahr
and b.belnr = a.belnr
where a.mandt = '715'
and b.rldnr = '0L'
and b.docln = '000001'
and a.buzei = '001'
and a.gjahr = '2018'
--and a.gjahr = '2017'
--and a.gjahr = '2019'
--order by a.mandt, b.rldnr, a.bukrs, a.gjahr, a.belnr, b.docln, a.buzei
limit 200;
for a human readable view of this you can look e.g. here https://docsfortec.com/sap/S4/tables/ACDOCA
Did they start out with German table names and decide to give new tables English names at some point?
explain select * from xy join uv on (x = u and u > 0) where u < 2;
Project
├─ columns: [xy.x:2!null, xy.y:3, uv.u:0!null, uv.v:1]
└─ LookupJoin
├─ IndexedTableAccess(uv)
│ ├─ index: [uv.u]
│ ├─ static: [{(0, 2)}]
│ ├─ colSet: (3,4)
│ ├─ tableId: 2
│ └─ Table
│ ├─ name: uv
│ └─ columns: [u v]
└─ IndexedTableAccess(xy)
├─ index: [xy.x]
├─ keys: [uv.u:0!null]
├─ colSet: (1,2)
├─ tableId: 1
└─ Table
├─ name: xy
└─ columns: [x y]- be able to put the projection in a varable and reuse it (and I think orm people might love it)
- have a quick way to forward the the non-aggregated fields of projection to a group by (maybe with the aforementionned variables)
- Does this[1] solve the group by wish?
- Depending on what you mean by projection, maybe this[2] or this[3]?
[1] https://duckdb.org/docs/api/python/relational_api#aggregatee...
[2] https://duckdb.org/docs/api/python/relational_api#projectexp...
[3] https://duckdb.org/docs/api/python/expression#column-express...
Maybe SQLite could have a similar mechanism, but the cache stays on disk or an external memory cache.
I think we already kind of have that already; one can prepare a query/statement and then use it multiple times. Regex engines also do that, except that in the case of SQlite one can bind different parameter values.
Programmers worried about SQL lexing/parsing times can compile their most used queries once for all at programmer startup. Plus, one can sometimes break a query with annoyingly variable parts into smaller queries glued with SQLite API calls.
That's exactly how those "prepared statements" work in SQLite - you get a handle to a piece of bytecode, and you can call it with different parameters.
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.
My usual problems are:
1) Running queries manually, where SQL is much more friendly than writing bytecode by hand. 2) Running queries using a clueless ORM that has no idea how to optimize them, so leaving this job to the database makes sense.
I believe the actually rare problem is "writing hyper-optimized complex queries tailored to the current state of the database", where bytecode would help. But that is a very unusual usecase.
Maybe there are shops that use databases very differently from me, but it makes sense that SQL is optimized for the common use case.
And since db internals are very different, it's hard to make a single bytecode standard that makes sense to use across different databases. You can probably write something specialized for sqlite or postgres, but since nobody did, probably it's not as useful for other people too.
Optimization isn’t the goal here, this quote misrepresents the idea. In the spirit of dismissal through all these years, btw, some people just don‘t get it and think it’s for better performance. It is, but for better performance of a developer, not that of a database. The goal is to have a set of languages above that bytecode that would help with usual programming bookkeeping and with expressing queries in an algorithmic way because that’s how you designed it. SQL lacks DX ergonomics, it’s just a language from the clueless epoch.
I recall a previous discussion about the SQLite bytecode and potential alternatives, where the main idea was that, if SQLite had gone the other way, you could have a much more general engine, where you could achieve something like DuckDB itself just as a set of extensions.
Reading the draft, it doesn't seem that extensibility of SQLite was a main factor in deciding. Maybe this trade-off also covers extensions somehow, which would be nice to see in the final document.
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.
So, if a query caused a full table scan or similar against the table, it's an error, regardless of the actual content.
A lot of "typical" backend code would then simply require you to make the right indices you need to support your queries, and the query planner would be forced to use those indices in all situations.
2) You can already sort of do what you say; that "higher level imperative language" is available simply by breaking your query up into smaller chunks.
At least in MS-SQL (which is what I know), simply do
declare @tmp1 as table (...)
insert into @tmp1 ...
declare @tmp2 as table (...)
insert into @tmp2 ... from @tmp1 join ...
3) That said, I think SQL is a wonderful idea, I am also super-productive in implementing business logic in it; but it is a horrible language; the learning curve is so much higher than it needs to be and so many silly pitfalls. So fully support pushes for better languages.
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.
The precursors to sql rdbms, and the war over competing concepts, were also quite thought provoking.
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 custom data transformation
More here: https://dubroy.com/blog/bytecode-vms-in-surprising-places/
Ultima IV used one to animate sprites on it's title screen map. For the next version of XU4 I implemented three bytecode interpreters to script the entire title sequence. There's a high level presentation interpreter, a GPU rendering interpreter, and one for the Ultima IV bytecode.
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)
[1] https://developer.apple.com/fonts/TrueType-Reference-Manual/...
https://en.wikipedia.org/wiki/Interpreter_pattern
https://gameprogrammingpatterns.com/bytecode.html
https://wiki.c2.com/?InterpreterPattern
I first read about it from the "Design Patterns" book, which I would recommend to everyone.
Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.
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.)
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.
That has its own problems though - using an AST as a shared source of truth for your JIT compilers is cumbersome for implementing stuff like OSR. But from a perf standpoint, it’s probably fine.
Also - say you want to optimize just for startup time, like if the code you’re running has minimal looping or reexecution. Then AST is better because you skip a step before first execution.
> 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.
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.
It was really big in gaming, Zork, Sierra games, LucasArts games, and even a few more "action" games like Flashback were all designed around VMs to make porting somewhat sane. Running the byte code is usually not the performance bottleneck in these cases but drawing stuff to the screen is, and the VM had to handle that.
https://en.wikipedia.org/wiki/Burroughs_Large_Systems
It used an almost memory safe systems language, ESPOL, zero Assembly, all CPU capabilities are exposed via intrisics, one of the first recoded uses of unsafe code blocks, there was tagging and capabilities support, the CPUs were microcoded. All of this in 1961, a decade before C came to be.
ESPOL was quickly replaced by NEWP, although there are very little data when it happened, probly a couple of years later.
Nowadays it is still sold by Unisys under the guise of being a mainframe system for those that value security above all, as ClearPath MCP, and you can get NEWP manual.
https://www.unisys.com/solutions/enterprise-computing/clearp...
https://public.support.unisys.com/aseries/docs/ClearPath-MCP...
Another example, all the Xerox PARC workstations, which loaded the respective interpreter (Smalltalk, Interlisp, Mesa, Mesa/Cedar) into the CPU as first step during the boot process.
Is Intel microcode able to be changed by anyone? I understand that even CPUs get field updates nowadays.
I don't know a whole lot about microarchitecture, but from my understanding, it's not possible to modify microcode's actual uOps in software, it's the translation from assembly to microcode that's being patched in updates.
David Parnas talks a lot about this as a way to reliable modularisation: https://two-wrongs.com/deliberate-abstraction.html
When looked at this way, a VM makes the most sense actually because a pointer-heavy tree implementation is just terrible for caching and is super wasteful. Also, most SQL plans are trees (Until you get to WITH RECURSIVE).
I'm working on a CEP in C right now and a stack-based bytecode is simply the most 'obvious' way to represent a tree when you don't want to have to deal with lots of memory allocations. Just pre-allocate a buffer large enough and increment and go.
Either way, try taking something like the following and printing an expression tree like the one below
LITERAL 2
LITERAL 3
LITERAL 4
MUL
PLUS
Plus
Mul
3
4
2
Now, try writing ops to manipulate and rewrite it. It's actually really a fun way to represent trees.
> "Remember: The VDBE opcodes are not part of the interface definition for SQLite. The number of opcodes and their names and meanings change from one release of SQLite to the next." https://www.sqlite.org/opcode.html#the_opcodes
For anyone interested in understanding how a register-based VM operates I highly recommend:
A No-Frills Introduction to Lua 5.1 VM Instructions by Kein-Hong Man. https://www.mcours.net/cours/pdf/hasclic3/hasssclic818.pdf
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.
https://casadevall.pro/articles/2020/11/compiling-word-for-w...
"Originally code-named “EP” (for “Electronic Paper”), Multiplan was written to use a very clever p-code compiler system created by Richard Brodie. This p-code system, which was also used later by Microsoft Word, allowed Microsoft to target Multiplan to a huge number of different 8-bit and 16-bit computer systems. (Charles Simonyi once estimated that Multiplan was available for 100 platforms.)"
"Microsoft has introduced a code compression technology in its C/C++ Development System for Windows version 7.0 (C/C++ 7.0) called p-code (short for packed code) that provides programmers with a flexible and easy-to-implement solution for minimizing an application's memory requirements. In most cases, p-code can reduce the size of an executable file by about 40 percent. For example, the Windows Project Manager version 1.0 (resource files not included) shrinks from 932K (C/C ++ 7.0 with size optimizations turned on) to 556K when p-code is employed."
"Until now, p-code has been a proprietary technology developed by the applications group at Microsoft and used on a variety of internal projects. The retail releases of Microsoft Excel, Word, PowerPoint�, and other applications employ this technology to provide extensive breadth of functionality without consuming inordinate amounts of memory."Similarly, the TI-99/4 series of computers had a cumbersome way of accessing memory, because most of the RAM in the machine was exclusively controlled by the video chip and could only be accessed by poking a few registers. So the designers implemented a bytecode VM in ROM called GPL (Graphics Programming Language) that would make accesses to this video RAM seem like straightforward RAM accesses. TI encouraged the use of GPL to develop games and other applications for the system. Unfortunately, the fact that it was interpreted by the CPU, plus the fact that the CPU could only access video-chip memory during the horizontal and vertical retrace intervals, made GPL execution very slow. And since the machine's in-ROM BASIC interpreter was written in GPL, you now know why BASIC programs on the TI-99/4 and /4A crept along at the most leisurely of paces.
So VMs were definitely a thing used to make certain kinds of tradeoffs, even way back in the 8-bit days when systems had mere kilobytes of memory. Who knows how many might be lurking in a modern system!
I think it's a special case of the fact that finite state machines are everywhere you look.
[1] https://stratos.seas.harvard.edu/files/MonetDebull2012.pdf
[2] https://www.researchgate.net/publication/220538804_Database_...
I have once tried benchmarking it by writing a tiny VM interpreter and a corresponding threaded one with direct jumps in Zig (which can force inline a call, so I could do efficient direct jumps) and I have - to me surprisingly- found that the naive while-switch loop was faster, even though the resulting assembly of the second approach seemed right.
I wasn’t sure if I saw it only due to my tiny language and dumb example program, or if it’s something deeper. E.g. the JVM does use direct threaded code for their interpreter.
A tree based evaluator has to do something like -
for (int i = 0; i < df.size(); i++) {
// switch on expression type (column, binary operator, unary operator etc)
// switch on expression operator type (add, subtract, equals etc)
// switch on column type (int, long, float etc)
// actual evaluation
}
for (int i = 0; i < df.size(); i++) {
result[i] = df.getLong(column1Index, i) + df.getLong(column2Index, i)) == df.getLong(column3Index, i)
}The main benefit of bytecodes is then cache friendliness, by removing all of those unpredictable loads and stores to obtain the expression details (opcode, arguments, etc.). All of those are inlined into the bytecode array which is already in cache.
It’s not?
I don't have personal experience on it, but I've read that in practice it's not worth the effort—at least not yet. Apparently there are some issues with it and it barely speeds up queries (except perhaps certain ones?). I imagine this could be in big part because LLVM is not really a good fit for JIT where you want to spend very little time to do the compilation itself.
1. start interpreting the code once it has been parsed, and start jitting a function being called;
2. generate naive bytecode for the function that generates native code equivalents of the run actions of the AST (including some fast-path code for simple cases such as adding two 32-bit integers, and falling back to function calls to perform the add on more complex types);
3. generate more optimal code for sequences of instructions in the background, such as entire for/while loops, then patch in calls to those fast-path versions when ready.
That way you can start running the code immediately after parsing it, and can switch to the faster versions when they are ready if the code takes longer to run in the slower version.
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 part of the execution logic now lives in the driver.
I suspect this complicates version upgrades and bugfixes, because the database is less self-contained.
Not an issue for sqlite, potentially disastrous for mysql.
I don't believe *any* SQL client library actually tries to parse e.g. PostgreSQL itself at any point of processing. You can read what the PostgreSQL protocol does here: https://www.postgresql.org/docs/current/protocol-flow.html#P...
> potentially disastrous for mysql
This is completely incorrect. The MySQL client side isn't responsible for execution steps and this isn't part of its wire protocol at all.
With prepared statements, the server parses the statement and gives the client back a handle, which is basically just a unique identifier that the client can use to invoke the prepared statement.
MySQL _completely_ switched execution paradigm through the course of a couple of 8.0.x sub-releases, generally without anyone noticing.
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
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
Those actions would typically allocate and build (partial) ASTs, but you can do anything with them. You can for example directly evaluate the subexpression if your grammar is simple enough. Likewise bytecodes can be generated on the fly; the only concern here is a backward reference, which has to be patched after the whole expression block gets generated, but otherwise you don't have to build any tree-like structure here. (Most practical parsers only need a stack to function.)
E.g. pseudo-Yacc rules for compiling the while loop in a C-like notation.
while_loop : WHILE '(' expr ')' statement
{
let back = get_label();
let fwd = get_label();
let expr = $3; // code for expr recursively generated
let stmt = $5; // code for statement, recursively generated
$$ = make_code(stmt.reg(),
`$back:\n`
`${expr.code()}\n`
`BF ${expr.reg}, $fwd\n` // branch if false
`${stmt.code()}\n`
`JMP $back\n`
`$fwd:\n`)
}
;
The while statement produces no value, so we just borrow the statement's .reg() as a dummy in the call to make_code; our rule is that every code fragment has an output register, whether it produces a value or not.
When the LALR(1) parser reduces this while loop rule to the while_loop grammar symbol, the expr and statements have already been processed; so the rule action has ready access to the code objects for them. We just synthesize a new code object. We grab a pair of labels that we need for the forward and back jump.
I'm assuming we have a vaguely JS-like programming language being used for the grammar rule actions, in which we have template strings with interpolation, and adjacent strings get merged into one. The bytecode assembly is line oriented, so we have \n breaks.
One possible kind of expression is a simple integer constant, INTEGER:
expr : INTEGER
{
let reg = allocate_reg();
let val = $1
$$ = make_code(reg,
`LOAD $reg, #$val\n`)
}
statement : '{' '}'
{
$$ = make_code(R0, // dedicated zero register
""); // no-code solution
}
LOAD R1, #1\n ; output register is R1
L0:\n ; back label
LOAD R1, #1\n ; code for expr
BF R1, L1\n ; branch if false to L1
; no code came from empty statement
JMP L0 ; back branch
L1:\n ; fwd labelThe key restriction is that you must be able to generate the bytecode in a single pass over the source code. For example, the compilation of a function at the top of the file must not depend on declarations further down the file.
E.g. imagine you're in a leaf production for some simple grammar for an operator that can only take integers, w/all error handling ignored:
parse_fooexpr() {
left = parse_int
emit_int(left)
expect_token(FOO_OP)
right = parse_int
emit_int(right)
emit_foo_op()
}
Wirth's compilers usually didn't use an AST, and his book on compiler construction contains a thorough walkthrough on generating code as you parse, if you want to see it explained in a lot more detail and w/tricks to generate better code than the most naive approaches will.
The difficulty with this approach comes when you want to apply optimisations or where it's inconvenient to generate the code in parse-order because the language tries to smart about what feels better to write, but you can get pretty far with this method.
https://compilers.iecc.com/crenshaw/
Chapter 2 and 3, expression parsing, should give you the idea. Instead of building the AST, you build code. So you're cutting out the middle man (AST).
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.
The downside -- especially for dynamic languages like JavaScript -- is that you need to keep all of the type checks and fast-paths in the code, resulting in larger code blocks. With more type analysis you could group fast-path instructions together (e.g. within a while or for loop) but that takes time, which is typically why a JIT engine uses multiple passes -- generate the slower machine code first, then improve the fast-path blocks for code that is long running.
Huh? A bytecode interpreter still ends up branching based on the decoded value of the byte codes. The VM bytecodes are not directly executed by the CPU (at least not usually, Jazelle and some older P-code stuff being rare exceptions).
This is what it looks like for the example being discussed ("a massive switch statement"): https://github.com/sqlite/sqlite/blob/b11daa50f9ea11c332bb59...
Perhaps confusing bytecode generation and interpretation with JIT? JIT is often paired with a bytecode but neither is dependent on the other.
But yes, if you are interpreting the intermediate VM bytecode you will still have a switch or dispatch branch when evaluating each instruction.
"The bytecode generated by SQLite is usually smaller than the corresponding AST coming out of the parser. During initial processing of SQL text (during the call to sqlite3_prepare() and similar) both the AST and the bytecode exist in memory at the same time and so more memory is used then. But that is a transient state. The AST is quickly discarded and its memory recycled [...]"
> 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, but it is sufficiently difficult that I have never seen it actually done.
I don't think it's too difficult. You can avoid stack unwinding by just not using the native stack in the first place and using an explicit stack. This is one step towards a bytecode VM though, as you're virtualizing the stack. Definitely easier in bytecode though as it already makes all of that state explicit.
For the article overall, isn't it a bit trivial to see that a bytecode interpreter must be faster and more compact? Write out the expression tree to an array as an in-order traversal and this is basically an executable bytecode. It will be more compact because you no longer need hidden malloc/object headers and pointers for subexpressions (they're preceding indices!), and it will be faster because it's basically all in cache, so no cache misses from pointer chasing.
I can't imagine a situation in which the tree would ever be faster for execution, in general. At best, the overhead might be just too small to care about. We use trees in compilers because we need to perform incremental rewrites. This is trivial with trees but can get expensive when expanding and contracting arrays. Execution doesn't need to perform rewrites though, it needs linear, cache-friendly access patterns.
However, the article does make a good point that the query plan may be tuned on the fly during execution, eg. the small rewrites I mentioned above occurring while executing. I'm not fully convinced this couldn't be done in bytecode though.
Since all of this (byte coding) (AST) is done by almost many programming languages I ever explored (Python,Ruby, lua, ...). It would have been awesome, if they were easily parse-able I guess.
Most of the ORM implementations are very error prone to those design decisions. (Especially SQL databases).
I've seen some cool graphical visualisation tools for postgres http://tatiyants.com/postgres-query-plan-visualization/
I often miss having the cardinality and the amount of bytes read for each part of the query like Oracle query plans provide.
Or is everyone really that happy with SQLite query plans?
It also would be quite a challenge given their long-term-support statement (https://www.sqlite.org/lts.html):
“Cross-platform Code → SQLite runs on any platform with an 8-bit byte, two's complement 32-bit and 64-bit integers, and a C compiler. It is actively tested on all currently popular CPUs and operating systems. The extreme portability of the SQLite code and file format will help it remain viable on future platforms.”
https://sillycross.github.io/assets/copy-and-patch.pdf
It has great potential for many applications, if not this particular one.