SQLite Internals: Pages and B-trees
fly.io
fly.io
I have been a fan of SQLite for years, and it makes me genuinely happy to see other people have the same enthusiasm for the software.
A couple of years ago, during a job search, I came across a couple of companies that I thought were a good match. I went through the interview process with all of them and, due to similarities in the interview process, we ended up talking about the same thing: databases. Oh the horror in the interviewers’ eyes whenever I mentioned SQLite. Experienced software engineers from The New York Times, for example, went as far as to mock my engineering choices in 3 out of 5 interviews, despite the success of the products my team built on top of SQLite.
The experience made me feel awful and I stopped talking about SQLite for a couple of years. Instead, whenever someone asked a question about databases, I would answer with the PostgreSQL equivalent, knowing that the basic features are all the same.
That is why, whenever I see projects like Litestream [1][2] used by excellent products like Tailscale [3], it brings me joy.
A friend of SQLite is a friend of mine :-)
That said, their experience probably reflects my own: using SQLite on a personal project for config or something, loving the simplicity, loving the "ditch all that complexity" hype, then trying it on a more demanding project that according to their mental model it should have excelled at (a central job tracking process), watching it completely faceplant under load (20TPS? Surely it just needs an index or something? Maybe a ramdisk? Err.....), panicking when they realize that perf and monitoring and diagnostics and optimized backends were some of those "bells and whistles that nobody needs," deciding "fine I'll do it myself," throwing far too much time and effort at co-debugging python and C, recompiling SQLite with debug symbols, sprinkling printfs, running profilers, reading the source, and tracking down the issue... only to find that it was a bad default which people had been unsuccessfully begging the maintainers to change for years, which was guaranteed to torpedo perf under a wide variety of common workloads, and which the maintainers had been resisting based entirely on inertia and the misguided idea that this setting was easily discoverable. Yikes.
That's how someone picks up rules of thumb like "SQLite is for preferences, not perf, and definitely not prod."
Now, this experience is a decade stale. SQLite bit me in 2012 and the particular bug was fixed in 2015 IIRC. The people begging to fix the bad default finally won. Time passed, SQLite got better, and now, based on these new stories of SQLite doing well under load, I think it's time to lift my "once bit, twice shy" sanctions regarding perf. I had them in place for a reason, though, and if you had YOLO'd when I had YOLO'd, you would have faceplanted when I faceplanted. I fully defend the use of sanctions like this in general. They are the only tool we have against overenthusiastic marketing.
To be fair, the SQLite site is pretty good, it's the fans that tend to take things too far.
------------------
AMD GPUs (2014): Waiting for GPGPU support from Adobe and Blender that was supposed to be operational (Adobe) or getting there (Blender) but never landed.
AMD GPUs (2016): I burned an entire semester trying to port CUDA code to OpenCL only to run into bug after bug after bug. Lockups, black screens (no framebuffers were supposed to be involved but bugs find a way), leaks, stalls which were difficult to attribute, unscruitable errors leading to abandoned threads with pleading users from years past with no reply. I finally cracked when after a long day of "I swear this should work I have no idea how the changes I make correspond to the bugs I see" I ran my ailing OpenCL code on a weaker NVidia card, and it Just Worked. Not only did it just work, it was 10x faster. Even though the card was like 2 generations older, and I was using OpenCL, which NVidia had every reason to sandbag, but they were still winning at. Oh, and the debugging tools actually worked, too. I was persuaded to sell my red cards, eat the ebay tax, eat the nvidia tax, and buy green from then on. Time has passed since 2016, though. ROCm looks good and AMD has money now, so maybe they can afford to pay people to fix bugs. I want to see someone running Blender and a modern ML framework or two before I retire the sanctions, though. Anyone have fresh intuition here?
Numba CUDA (2018): I spent two weeks working through a succession of problems that I eventually resolved in two days by just using CUDA C++. Numba CUDA only worked with year-stale CUDA, it copied float8s over a float4 array despite having access to triply redundant type specs, the mechanism to pass buffers between kernels always forced copy off GPU, and one more that I forget. I made patches for the first three and gave up on the last one before fixing. Has anyone used it recently? Is it in better shape these days?
ROCm still has lots of rough edges, but we're slowly filing them down. The documentation is a bit patchy too. Overall, though, it's been a steady progression in the right direction.
That's not acceptable.
> Experienced software engineers
Measured in years, probably, not by ability.
I've heard supposedly 'experienced' engineers saying things like "No-one uses Lua in production!".
Some pretty big businesses have been built on the back of PHP. That doesn't make the language any less ridiculous.
This need not imply condesenction to the language users or designers, not as individuals at any rate.
(Facebook's re-invented Hack isn't nearly as bad. It's about the best language they could have made starting from PHP.)
I think that it was excellently written and actually mentioned concrete issues, rather than vague personal dislikes. That is good, because you can revisit those in 10 years or so and see how many of those have been fixed in the actual language.
Someone actually tried to address a few of those: http://maettig.com/2020-09-16-revisiting-a-fractal-of-bad-de...
That's part of why I carefully wrote 'old-style PHP'.
That said, I'd agree that mockery is rarely ever appropriate, and is often undertaken by those without the credentials to do so.
It's also possible that someone is expressing hard won knowledge/battle scars in an unskilful way. And it takes investigation to know the difference.
You don't want to install Postgresql or Oracle on an embedded system nor would you want the extra weight of administering them for a system that has few users.
The SQLite site runs on SQLite and it has considerable traffic.
The forum and source code trees run on sqlite (via the Fossil SCM, authored by sqlite's Richard Hipp). The main sqlite site is static HTML with a tiny sprinking of JS.
MySQL and PostgreSQL can run locally too. I assume you mean that SQLite doesn't provide a network server interface out of the box?
"Doesn't scale" gets thrown around often. Yeah sure, but sometimes it doesn't _have_ to. I've seen large fleets of NoSQL databases (won't name to avoid flamewars) running workloads they are not really optimal for. Or PostgreSQL databases completely bogged down and vertically scaled to ridiculous levels because teams don't bother to optimize their queries.
Query performance is not part of OKRs, but new releases usually are.
It really depends on the kind of problem and the scale, but a good implementation that matches the problem will sing compared to a mediocre implementation on inappropriate yet highly scalable infrastructure. Even if it's supposedly inferior because it's centralized, etc.
Knowing the constraints of the engineering challenge and choosing wisely within that is key. You can sometimes leverage constraints and simplifications in ways that can stack and remove many layers of complexity. Immediate consistency is a huge one, as are transactions.
I avoided relational tech early in my career, when I was really just turned off by examples of poorly tuned implementations, and badly written schemas and queries. Once I finally opened my mind, I was better able to appreciate its role as compared to other DB models.
I think that's a natural maturation as you progress in your career/get more exposure. It's too bad most of us seemsto have to walk the same path though.
Those conversations are my favorite when interviewing candidates because it gives you a view into how their brains work.
I would’ve nerded out about how so many macOS apps use SQLite under the hood because it’s so solid.
SQLite is even used in the Airbus A350 and they signed (approx something like) a 35 year support contact with Airbus for it, I remember hearing in a podcast a long time ago. (Please correct if I’m way wrong here)
I can think of a couple of scenarios where they wouldn’t want to use SQLite, such as high availability database to support their subscription system, or the back-end for their interactive website (which was a mean stack at one point, so not even SQL).
[1] https://jvns.ca/blog/2014/09/27/how-does-sqlite-work-part-1-... [2] https://jvns.ca/blog/2014/10/02/how-does-sqlite-work-part-2-... [3] http://carlosproal.com/ir/papers/p121-comer.pdf
Looking into SQLite’s innards is a great source of inspiration. Thanks for this post.
Edit: I'm prototyping in Python and implementing in Rust with intent to create a C API and embedding a Scheme runtime for "server"-side query and constraint parsing.
The hard part is getting all of that consistent with concurrent writes. Can rows change while you scan? can indexes? How do you check that your write is valid immediately before committing, etc. things like that.
I think SQL makes that pretty hard already, but in a "database-as-a-bag-of-data-structures" mode I think that's going to get even harder.
To have good query optimization, you need to implement, at the very least, some form of dynamic programming, otherwise you will not be able to optimize queries that have more than half a dozen tables in selects. Then you have to implement selection of the best plan or approximation to it, which would make you implement beam search through space of all solutions you generated, and that's simplest case. For guaranteed optimization, you need to implement or utilize pseudoboolean optimization engine.
I am a database engine developer right now. ;)
Either way, using a WCO join combined with a data-structure that allows for efficient range estimate and dynamic variable ordering, completely obliviates the need for query planning.
Yes, of course, having implementation of all that completely obliviates the need for query planning. ;)
I can't help being sarcastic for a moment, sorry.
In my opinion, in your comment above you clearly demonstrated that even avoidance of query planning is hard, using as example (multi)set of triples for which it is possible to realize all indices.
If what you described is simpler than query planning, then query planning is hard.
Building an immutable path compressed radix tree is pretty straightforward and requires around 1-2kloc, and it's easy to keep track of the n-smallest hashes of leaf values, as well as the total count of leafs in the nodes. The sampling done by the min-hashes give you a good indication of two nodes overlap which the jaccard index is just a different name for.
The query engine itself is like 0.5kloc, and is just walking the different radix-trie indices simultaneously. The basic insight of worst case optimal (WCO) joins, is that it's a lot cheaper to join everything at once and treat it as a constraint propagation problem.
A LINQ style query parser takes up another 1-2kloc and is just a bunch of ol' boilerplate.
In total that's about as much code as your average large C++ codebase CMake file.
You could sketch the entire thing on a napkin and build it in a week if you've build something like it before.
Please, excuse my sarcasm again. But, tell me what to do if I didn't built something like this before? What if I built something like equality saturation engine, pseudoboolean optimization using SAT solver and/or beam search? Will it help me somehow?
You estimated code size at 4.5KLOC max. Given that C++ programmer delivers 20-25 debugged lines of code per hour in the long run (IBM's stats), it would take 225 hours of work. Given that PSP/TSP recommends planning for 4 hours-on-task per day, it will take 56 work days. My calculation suggests 2.5 work months to implement all that in the worst case of 4.5KLOC. Even the best case of 2.5KLOC would take a month and a half of work.
Yours' proposition is not a week's project. Not at all, you can't squeeze it that much.
Query planning is hard. Even if you try your best to avoid it.
And we have not even started talking about WHERE, GROUP BY and ORDER BY clauses' optimizations.
[1] shows the use of loop nest optimization combined with beam search. SQLite uses translation of joins into loop nests, and it transforms loop nests into a graph, the path in the graph represents a solution. The [1] shows simplified nesting graph that is linear, and in general it will be quadratic to the number of tables.
[1] https://www.sqlite.org/queryplanner-ng.html
I really like that approach. This is exactly an equality saturation [2] (saturate loop nesting through loop nesting commutativity) with the beam search as a selection phase.
[2] https://rosstate.org/publications/eqsat/
I think that equality saturation with beam search is a week long project if you already have built something like that. The difference? It will work for arbitrary jons.
Of course I am making fun of your statements.
Equality saturation requires quite careful planning and will not work for couple of months, you will keep finding something that fails. Beam search is just as hard. You can encode optimal solution selection problem as a pseudoboolean optimization problem, which is more straightforward than beam search, and [2] shows that Pueblo is no slouch there.
This is not to say that query planning is easy when you do it my way. Query planning is hard. NP-hard, actually. Sometimes you can get away with a simpler less general solution, but it will bite you sooner than you expect.
`WHERE, GROUP BY and ORDER BY` are relatively straightforward to tack on into the variable ordering.
Having written a sat solver would kinda help you, because modern sat solving algorithms are fundamentally very similar to worst case optimal join algorithms.
The query plan produced by combining binary joins is always going to be off by up to an exponential factor when compared to a WCO join. If you're fine throwing all that complexity onto your problem to generate sub-par query plans, be my guest.
There are at least two different types of them, conflict-derived clause learning and variants and stochastic search and variants.
Which one is more similar to WCO join algorithm?
Tseitin transformation prevents exponential expansion in conversion from DNF to CNF.
The fact that paper's algorithm employs disjunctive normal form suggests the use of binary decision diagrams. ROBDDs represent DNFs naturally, for one example. ZDDs represent sets of sets and were relatively successfully used in non-trivial approaches to the SAT solving problem like [1].
[1] https://web.eecs.umich.edu/~imarkov/pubs/book/b002.pdf
Also, the paper you mentioned has this right in abstract: "However, there is still the quest of making the new worst-case optimal join algorithms truly practical in terms of (1) ease of implementation and (2) secondary index efficiency in terms of number of indexes created to answer a query."
WCO is hard to implement and it might be computation-wise prohibitive.
Yet, it's quite interesting, thank you very much.
Citation greatly needed. Why is it so?
See:
https://www.cs.stanford.edu/people/chrismre/papers/paper49.N...
https://justinjaffray.com/a-gentle-ish-introduction-to-worst...
The difference is not exponential, if I may nitpick. It is sublinear in the case of the "triangles example" - WCO would produce O(n^(1.5)), binary join will produce O(n^2), the difference is O(n^(0.5)) or O(sqrt(n)). The difference is big, but not exponential.
Good nitpick, I think you can construct larger rings where the difference becomes larger than one, but I might be wrong. The dynamic variable ordering trick makes a huge difference in practice, especially when skew is in play. (https://arxiv.org/pdf/1310.3314.pdf)
In general you're right, WCO joins are a relatively young field of study and sometimes struggle with large constant factors, but they are maturing quickly and in a limited (triple) setting like the one OP "wished for", a lot more feasible than for the general case.
Thanks for the interesting discussions, looking forward to reading the references you provided in depth!
Edit: I just remembered this paper, which might be of interest to you. They seem to recover WCO bounds in a pairwise setting, by choosing very smart intermediary join representations: http://www.cs.ox.ac.uk/dan.olteanu/papers/co-tr16.pdf
My old idea was to perform planning after some of the work has been done, because remaining statistics can be different. These papers are of great help!
Until the day you load a bunch of new data and it gets skewed, or you delete a bunch of data without shrinking and oops, your join order and method is not efficient anymore.
You can have this today by running XTDB[1] on top of SQLite via JDBC.
> Written in something like C, Rust, or Zig.
And then compiling your application into native executables with GraalVM Native Image[2].
Embeddable, check. Datomic data model and Datalog query, check. Storage written in C, check.
Edit: it's written in Clojure, so JVM. Extra bleh
No longer actively maintained, but maybe a nice starting point for hacking on your dream!
qpdb/mentat [2] seems to be the largest (+131 commits) and most recently modified (May this year) fork of mozilla/mentat.
[0]: https://github.com/mozilla/mentat/network/members - Seriously, how am I supposed to use this? Hundreds of entries, but no counts for stars, contributors, or commits, no details about recent commits. Just click every one?
The obvious issue is that they're fairly deeply embedded in the Clojure(Script) ecosystem.
You can see me prototype here: https://git.sr.ht/~chiefnoah/quark
I think I gave up when trying to implement one-many relationships because the SQL was getting too gnarly.
https://github.com/sqlite/sqlite/blob/master/src/btreeInt.h
The code for the btree functions is here and is a bit over my head TBH with all the locks and permissions and so on but it's a nice example of how to comment code I think:
This reads to me like an accidental slip into the imperative, breaking a sentence in two parts, and not adding a phrase such, "For example,".
In fact, changing the period to a colon would defuse the imperative. It's subtle!
When I do surveys of software I try to provide links to source (mostly just the relevant file or directory) so folks can verify for themselves. For example when looking into the parsers behind Postgres-compatible DBs [0] and parser techniques in a few major language implementations [1]. But both those posts are at a higher-level than what you're doing here.
I'm sure you'll have good reason either way for this series.
[0] https://datastation.multiprocess.io/blog/2022-02-08-the-worl...
[1] https://notes.eatonphil.com/parser-generators-vs-handwritten...
Woah, Ben! I'm so glad the above link was shared above; thanks to the poster as well. There's a very good amount of in-depth knowledge shared via comments and a reference to Donald knuth's book
However, given that so many hosted Postgres solutions exist and that Postgres has so many essential features that SQLite doesn't, there really is no reason to choose a new hosted SQLite over one of the mature hosted Postgres services. Especially typesystem and mvcc come to my mind, but there's much more Postgres offers over SQLite.
I’m not even a journalist / communication person but I do immediately look at those fields to get a quick sense of relevance (is this an old article possibly out-of-date) and authority of author on said topic.
JSON file on disk might be a reasonable competitor here. This scales poorly, but sometimes you don't need to scale up to something as crazy as full-blown SQLite.
I would also say that the second you need any sort of writing or mutating in any sort of production environment SQLite is also simpler than the file system!
Race conditions in file system operations are easy to hit, and files have a lot more moving pieces (directory entries, filenames, file descriptors, advisory locks, permissions, the read/write API, etc) than a simple SQL schema
Whenever I see “full-blown” next to “SQLite” there is usually some sort of misconception. It’s often simpler and more reliable than the next best option!
I've also found that ripgrep performs surprisingly well with folders containing large numbers of text files - this makes raw json on disk more convenient for many simple usecases which don't require complex queries.
Imagining a moderately large JSON object, a lot of them actually, not hard to read or write exactly but they do carry some common references.
SQLite can: only rewrite the changed fields with a query, and transact the update across the objects. The filesystem can do atomic swaps of each file, usually, if nothing goes wrong. SQLite would also be faster in this case, but I'm more motivated by the ACID guarantees.
SQLite does increase complexity in the sense that it's a new dependency. But as far as dependencies go, SQLite has bindings in almost all languages. IMO even for simple usecases, it's worth using it from the start. Refactors are easier down the line than with a bespoke JSON/yaml/flat encoding.
Read only configuration, sure, JSON (etc) file makes sense. The second you start writing to it, probably not.
And here's what SQLite does to ensure that in case of application or computer crash database contains either new or old data, but not their mix or some other garbage: https://sqlite.org/atomiccommit.html
1. We knew what we were doing with respect to fsync+rename to guarantee transactions. I bet you the vast majority of people who go to do that won’t (SQLite abstract you from needing to understand that)
2. We ended up switching to SQLite anyway and that was a painful migration.
Just pick SQLite to manage data and bypass headaches. There’s a huge ecosystem of SQL-based tools that can help you manage your growth too (eg if you need to migrate from SQLite to Postgres or something)
If not, some jobs will benefit from a better perf insurance policy than "I could probably get this into a profiler if I needed to."
Also, if the SQL that's needed in an application is more "enterprise" style, then SQLite isn't there (yet). ;)
- More than one machine needs to read from the database
- More than one machine needs to write to the database
- The database is too large to hold on one machine
Much less so since the introduction of WAL mode 12 years ago, tho.
However much of the lore around writes remains from the “rwlock” mode where writers would block not just other writers but other readers as well.
That would kill your system at very low write throughputs, since it would stop the system entirely for however long it took for the write transaction to complete.
If the system is concurrent-writes-heavy it remains an issue (since they’ll be serialised)
https://stackoverflow.com/questions/35804884/sqlite-concurre... has some pretty interesting numbers in it. Particularly the difference between using WAL mode vs not. The other aspect to consider is that the concurrent writes limitations apply per database file. Presumably having a database file per tenant improves aggregate concurrent write throughput across tenants? Though at the end of the day the raw disk itself will become a bottleneck, and at least the sqlite client library I'm using does state that it can interact with many different database files concurrently, but that it does have limitations to around ~150 database files. Again, depending on the architecture you can queue up writes so they aren't happening concurrently. I'd be very interested to know given all the possible tools/techniques you could throw at it just how far you could truly push it and would that be woefully underpowered for a typical OLTP system, or would it absolutely blow people's minds at how much it could actually handle?
When it comes to SQLite performance claims I tend to see two categories of people that make quite different claims. One tends to be people who used it without knowing its quirks, got terrible performance out of it as a result, and then just wrote it off after that. The other tends to be people who for some reason or other learned the proper incantations required to make it perform at it's maximum throughput and were generally satisfied with its performance. The latter group appear to be people who initially made most of the same mistakes as the former, but simply stuck it out long enough to figure it out like this guy: https://www.youtube.com/watch?v=j7WnQhwBwqA&ab_channel=Xamar...
I'm building an app using SQLite at the moment, but am not quite up to the point in the process where I've got the time to spent swapping it out for Postgres and then benchmarking the two, but I dare say I will, as I have a hard time trusting a lot of the claims people make about SQLite vs Postgres and I'm mainly doing it as a learning exercise.
It works fine for single user applications.
SQLite is my go-to database for application configuration and even non-enterprise web applications.
The sqlite library is tiny. Often smaller than some JSON parsers!
Stripped of all comments, the current "amalgamation" build of sqlite (which is the one most projects use) has 178k lines and 4.7MB of code. If your JSON parsers are anywhere near 1/10th of that size then they're seriously overengineered ;).
The tags I invented were essentially highly-optimized key-value stores that worked really well. I then discovered that these same KV stores could also be used to form relational tables (a columnar store). It could be used to store both highly structured data or the more semi-structured data found in things like Json documents where every value could be an array. Queries were lightning fast and it could perform analytic operations while still performing transactions at a high speed.
My hobby turned into a massive project as I figured out how to import/export CSV, Json, Json lines, XML, etc. files to/from tables easily and quickly. It still has a lot of work to go before it is a 'full-blown' database, but it is now a great tool for cleaning and analyzing some pretty big tables (tested to 2500 columns and 200M rows).
It is in open beta at https://didgets.com/download and there are a bunch of short videos that show some of the things it can do on my youtube channel: https://www.youtube.com/channel/UC-L1oTcH0ocMXShifCt4JQQ
> Contributed Code
> In order to keep SQLite completely free and unencumbered by copyright, the project does not accept patches.
https://www.sqlite.org/copyright.html
I think the number of people who have worked directly on the code for the canonical SQLite distribution is quite small.
I wonder how the underlying physical disk or file systems handle the writes or updates
- How can i forward range of ports instead of generating 1000s of lines? This is a major blocker for me.
edit: not sure why this is being downvoted, I've received no response from fly.io about this and this is the only way to get their attention on this shortcoming. you can't really expect people to write port 100,00 to 50,000 individually thats like 40,000 lines. Fly.io really needs to support port ranges like 10,000-50,000
We don't support tcp port ranges yet. We will someday: https://community.fly.io/t/new-feature-every-public-port-now...