12 ms·
SQLite Internals: Pages and B-trees
- bob1029 4y ago> Simplicity leads to reliability and I don't know of a more reliable database than SQLite. 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.
- eatonphil 4y agoSee also: https://tailscale.com/blog/an-unlikely-database-migration/ https://tailscale.com/blog/an-unlikely-database-migration/, and https://tailscale.com/blog/database-for-2022/ https://tailscale.com/blog/database-for-2022/.
- dymk 4y agoJSON file (or any file you directly write to) is simple, but has few of the guarantees SQLite gives you with regards to persistence. SQLite abstracts away all of that for you by handling the fancy platform-specific I/O stuff under the hood. 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.
- fikama 4y agoCould you elaborate more on those things abstracted by SQLite? or point to further reading - You got me interested
- Lex-2008 4y agoNot OP, but I remember reading an interesting article about issues that simple write() might face: https://danluu.com/deconstruct-files/ https://danluu.com/deconstruct-files/ 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 https://sqlite.org/atomiccommit.html
- benbjohnson 4y agoYeah, I like JSON on disk too. There's some "gotchas" to avoid to make it safe though like atomic renaming or fsyncing the file and its parent directory. But as long as you avoid those and don't have a lot of data then JSON-on-disk works great.
- vlovich123 4y agoImplied is “as simple as possible but no simpler”. We used JSON on disk at one job BUT. 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)
- anonymouse008 4y agoAt what point does one “need” to move to Postgres / MySQL? It feels like much of DBA is all style points - not necessarily objective.
- zdkl 4y agoIt becomes necessary at some (low) value of concurrent write usage basically. Or if you want to lean on logic built into one of the "proper" RDBMS (GIS, granular access managment, ...).
- masklinn 4y ago> It becomes necessary at some (low) value of concurrent write usage basically. Much less so since the introduction of WAL mode 12 years ago, tho.
- barking_biscuit 4y agoI often see the discussed, but I've not seen any benchmarks testing throughput of concurrent writes in SQLite compared to Postgres, so it's hard to know exactly how far WAL mode make it scale before it's simply the wrong tool for the job. I'm quite curious to know, so at some point I'll get around to doing my own comparison. If you are able to give some indication then that would be very handy. I also think it can be made to scale much further if you have a Multi-Tenant architecture where you essentially do a database per tenant, though that has it's drawbacks along other dimensions (namely schema changes). At some point it's going to come down to disk throughput.
- schwartzworld 4y agoJSON is a pretty poor storage format though, isn't it? I use it for the wordle clone I made, but the code would have been much simpler with SQL statements. And that was without any kind of complicated relational data https://github.com/schwartzworld/schwardle https://github.com/schwartzworld/schwardle
- conradev 4y agoThe funny thing is that SQLite is faster for storing JSON blobs than the file system is: https://www.sqlite.org/fasterthanfs.html https://www.sqlite.org/fasterthanfs.html 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!
- jck 4y agoIt looks like sqlite is not much faster than fs on Linux. 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.
- samatman 4y agoIt's on write that using SQLite really shines. 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.
- yndoendo 4y agoOne of the projects I worked on was an embedded system running on 200MHz with 8MB RAM and micro SD for storage, single data channel. SQLite was chosen because of the power to preform report calculations in SQL and is perfect for configuration storage in simple Key / Value relation, like Firefox about:config. SQLite is my go-to database for application configuration and even non-enterprise web applications.
- CJefferson 4y agoWe did have a big system that used JSON file on disk. The problem is over time we ended up with files with half a JSON, and needed a "cleanup" pass. Except of course the cleanup might find a file in the process of being written, and life slowly got more and more complicated.
- zimpenfish 4y agoWorked at a place that used on-disk XML as their database with multiple (10s of) writers. Started off fragile, ended up hideously complex and fragile. Unfortunately it was originally written by one of the powers that be and his word held sway over every technical decision, good or disastrous.
- outworlder 4y ago> something as crazy as full-blown SQLite. The sqlite library is tiny. Often smaller than some JSON parsers!
- eatonphil 4y agoI cannot imagine such a json parser. You can parse json in only hundreds of lines of code.
- sgbeal 4y ago> 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 ;).
- didgetmaster 4y agoI wrote a new, general-purpose data management system that was originally designed to compete with file systems for storing large amounts of unstructured data (my background is in disk utilities like PartitionMagic and Drive Image). It can be used to convert 100M+ files (photos, documents, videos, etc.) into data objects and attach searchable, contextual meta-data tags to them. 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 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 https://www.youtube.com/channel/UC-L1oTcH0ocMXShifCt4JQQ
- slaymaker1907 4y agoFor reliability, SQLite probably still wins. Even if you write the JSON all at once, what happens when the power goes out at that instant?
- c_hub1125 4y ago
- freecodyx 4y agoIt’s always good for this kind of articles, to refer to source code. Provide links to the source code responsible of some of the implementation details
- eatonphil 4y agoYeah that would be awesome! I'd rephrase your comment as a suggestion rather than a demand though personally. :)
- benbjohnson 4y agoThat's a good idea. There's a careful balance though since once you start talking about specific functions in SQLite then the post becomes very low-level and starts to become less accessible. I'll try to integrate that more in the future though.
- eatonphil 4y agoYeah maybe it would force you to get too close to the code, I don't know SQLite well enough. 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-world-of-postgresql-wire-compatibility.html https://datastation.multiprocess.io/blog/2022-02-08-the-worl... [1] https://notes.eatonphil.com/parser-generators-vs-handwritten-parsers-survey-2021.html https://notes.eatonphil.com/parser-generators-vs-handwritten...
- mandeepj 4y ago> https://github.com/sqlite/sqlite/blob/master/src/btreeInt.h https://github.com/sqlite/sqlite/blob/master/src/btreeInt.h 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
- upupandup 4y agoA bit off topic but fly related: - 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
- mrkurt 4y agocommunity.fly.io is the best place to ask about this. We don't support tcp port ranges yet. We will someday: https://community.fly.io/t/new-feature-every-public-port-now-allowed-for-tcp-services-this-means-http-too/3624 https://community.fly.io/t/new-feature-every-public-port-now...
- nathell 4y agoI dream of a SQLite-like embeddable database engine based on Datomic’s data model and queryable with Datalog. Written in something like C, Rust, or Zig. I’m toying around with the idea of hacking something up, but it’ll likely stay in the dream realm until I have Heaps of Free Time on My Hands (tm). Looking into SQLite’s innards is a great source of inspiration. Thanks for this post.
- kebman 4y agoYour dream sounds very nice.
- packetlost 4y agoI've been doing something very similar, but based on extendible hashing algorithms and LSM trees. I've come to the conclusion that a DAG of constraints, triggers and validations on a flat KV + entity model is probably the ideal data structure for 99% of projects I've worked on. You can get the benefits of the Datomic-like history by... skipping compaction and including a TX instant next to all record/assertions. I've found SQLite, Postgres, the LSM papers, Bitcask, and many other papers to be very helpful in terms of inspiration. 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.
- ftdyuio9p0iugy 4y agoI've had some append-only tables in Postgres and only recently realised that Postgres' system columns (https://www.postgresql.org/docs/14/ddl-system-columns.html https://www.postgresql.org/docs/14/ddl-system-columns.html) already effectively enabled some Datomic-like structure for such append-only tables! Specifically the xmin column allows me to identify the rows to treat atomically as a unit, and to ignore if I'm querying for a historical view.
- packetlost 4y agoYou could probably do it with BRIN indexes similar to how TimescaleDB handles their time-series hypertables
- Linda703 4y ago[dead]
- Rochus 4y agoInteresting article. When I implemented a no-sql database using the sqlite backend for https://github.com/rochus-keller/DoorScope https://github.com/rochus-keller/DoorScope and https://github.com/rochus-keller/CrossLine https://github.com/rochus-keller/CrossLine 15 years ago there was little literature about it (actually also the referenced article is rather light on the pages and b-tree implementation, but e.g. section 9 of https://www.amazon.com/Definitive-Guide-SQLite-Experts-Source/dp/1430232250 https://www.amazon.com/Definitive-Guide-SQLite-Experts-Sourc... was helpful). There was no lmdb or leveldb yet; though there was bekreley db and I did prototypes with it, but the sqlite backend turned out to be much leaner and faster for the task at hand.
- guessmyname 4y agoI love this. 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 :-) [1] https://litestream.io https://litestream.io [2] https://fly.io/blog/all-in-on-sqlite-litestream/ https://fly.io/blog/all-in-on-sqlite-litestream/ [3] https://tailscale.com/blog/database-for-2022/ https://tailscale.com/blog/database-for-2022/
- outworlder 4y ago> went as far as to mock my engineering choices 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!".
- ok_dad 4y agoIt’s amazing how otherwise competent engineers will look down on technology that so many use all around the world when generally their contribution to society is a few buggy Python classes in some internal codebase.
- switchbak 4y agoAre they competent, or have they only written a few buggy classes? Your strawman needs work :) 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.
- CoastalCoder 4y agoA bit of a tangent, but the Corecursive podcast has a really interesting interview with the creator of SQLite: [0] [0] https://corecursive.com/066-sqlite-with-richard-hipp/ https://corecursive.com/066-sqlite-with-richard-hipp/
- anewpersonality 4y agoHow much of SQLite is D. Richard Hipp versus companies that are contributing to the code?
- azornathogron 4y agoI can't directly answer your question because I don't know, but I will note that the SQLite Copyright page states > 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 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.
- benbjohnson 4y agoI talked with the SQLite team about a year or two ago and IIRC there were four people working on it (including Dr. Hipp). I believe they were all full time but I didn't ask.
- under-Peter 4y agoFor people who enjoy this article I recommend reading the two-parter “How does SQLite work?” [1] [2] by Julia Evans. It too is an exploration into the inner workings but diving deeper into code. And for those interested in more details on b-trees, there’s “The Ubiquitous B-Tree” by Douglas Cramer which I enjoyed a lot. [1] https://jvns.ca/blog/2014/09/27/how-does-sqlite-work-part-1-pages/ 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-btrees/ https://jvns.ca/blog/2014/10/02/how-does-sqlite-work-part-2-... [3] http://carlosproal.com/ir/papers/p121-comer.pdf http://carlosproal.com/ir/papers/p121-comer.pdf
- alberth 4y agoOff topic: does it bother anyone else when author By Line and Date Published is displayed at the very end of the blog/article as opposed to the start/top? 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.
- zasdffaa 4y agoA date published anywhere at all is fortunate.
- hinkley 4y agoIf it's accurate. Went searching for something the other day, Google listed is as being written the middle of May. I figured that would contain pretty recent and relevant info. Nope. The actual article was written in 2012, when the tech in question barely existed.
- justin66 4y agoThere are so many "evergreen" articles in the world which do not even include a post date that it's hard to be annoyed about this.
- LAC-Tech 4y agoSQLite is 21 years old, and for me it just keeps getting better and better. More performant, more relevant features, all while being just as easy to embed and administer.
- thundergolfer 4y agoYou can get hands on with this at codecrafters.io. They have a ‘do it from scratch’ challenge that takes you from the .dbinfo command to implementing a full table scan with a WHERE clause. I got up to implementing a basic SELECT over multiple columns.
- ericls 4y agoGood read. I wonder how the underlying physical disk or file systems handle the writes or updates
- c_hub1125 4y agoSQLite is a great choice as an in-memory database or when Postgres is clearly an overkill, e.g. storing some configs. I'm using it myself 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.
- c_hub1125 4y ago
- jerryjerryjerry 4y agoIt looks like SQLite is more popular in China than other regions: https://ossinsight.io/analyze/sqlite/sqlite https://ossinsight.io/analyze/sqlite/sqlite
- naniwaduni 4y agoThis map looks like a surprisingly good proxy for GDP, aside from China being really high (mostly attributed to users somehow associated with three Chinese companies?)
- jerryjerryjerry 4y agoGood catch! Actually I was thinking the popularity of SQLite somehow relates to the adoption rate of mobile devices where majority of these devices embeds SQLite to manage data like pictures.
- ernie24 4y agoYou should be careful what kind of links you post in your articles. Once I've clicked on /r/eatsandwiches I was too distracted to read the rest of the blog post.