Work on SQLite 4 Has Concluded
Richard Hipp (via Hacker News):
Lessons learned from SQLite4 have been folded into SQLite3 which continues to be actively maintained and developed. This repository exists as an historical record. There are no plans at this time to resume development of SQLite4.
SQLite4 stores all content, from all tables and all indices, in a single keyspace. This contrasts with SQLite3 that required a separate keyspace for each table and each index. The SQLite4 storage also differs from SQLite3 in that it requires the storage engine to sort keys is lexicographical order, whereas SQLite3 uses a very complex comparison function to determine the record storage order.
[…]
The default built-in storage engine is a log-structured merge database.
[…]
SQLite3 allows one to declare any column or columns of a table to be the primary key. But internally, SQLite3 simply treats that PRIMARY KEY as a UNIQUE constraint. The actual key used for storage in SQLite is the rowid associated with each row.
SQLite4, on the other hand, actually uses the declared PRIMARY KEY of a table (or, more precisely, an encoding of the PRIMARY KEY value) as the key into the storage engine. SQLite4 tables do not normally have a rowid (unless the table has no PRIMARY KEY in which case a rowid is created to be the implicit primary key.) That means that content is stored on disk in PRIMARY KEY order. It also means that records can be located in the main table using just a single search on the PRIMARY KEY fields.
The LSM embedded database software stores data in three distinct data structures[…]
I’ve had the chance to hear Richard Hipp talk about SQLite yesterday! He mentioned that the LSM tree storage engine is available as an extension to sqlite3. More specifically, he mentioned that he didn’t really get the performance improvements he had hoped for, for insertion-heavy use cases.
I think part of this is because of a fundamental limitation of sqlite that it’s an embedded database that has to persist data on disk at all times: The design of LSM trees works well with databases with a resident in-memory component because it’s an approximation of just dumping every new thing you see at the end of an unordered in-memory array. This is as opposed to a data structure like a b-tree where you have to find exactly where to put the data first, and then put it there. This finding bit means you’re doing a lot of random access in memory, which is thrashing all of your caches (CPU / disk etc). LSM trees avoid this thrashing by just dumping stuff at the end of an array. However this means you have to scan that array to do lookups (as opposed to something easier like binary search). Then as your array gets big, you merge and flush it down to a lower “layer” of the lsm tree which is slightly bigger and sorted. And when that one fills, you flush further. And these merge-flushes are nice big sequential writes so that’s nice too.
Anyway, with SQLite, the highest layer of your LSM tree would probably (this is conjecture) have to be on disk because of the way that there is no server component, versus in an in-memory system it’d probably be in your L2/L3 cache or at least your main memory. So this could be one reason why that model didn’t work out as well for them.
Previously: SQLite 4.
See also: Richard Hipp on the Changelog podcast.
