How bloom filters made SQLite 10x faster
avi.im
avi.im
https://sqlite.org/src/info/56d9bb7aa63043f5
I found and reported the bug because I wanted to know how the bloom filters work in SQLite for my uni seminar paper. Still wondering if one can find those kind of bugs with test cases.
If it has a false positive all the time (the worst case) then the performance is the same as before the bloom filter optimization was implemented (besides the small bloom filter overhead).
As the bloom filter size in SQLite directly depends on the table size I estimated a false positive rate of 63.2% due to this bug, while it could have been just 11.75%.
IE
CREATE TABLE foo(
id_ms UNSIGNED BIG INT NOT NULL,
id_ls UNSIGNED BIG INT NOT NULL,
PRIMARY KEY (id_ms, id_ls)
) WITHOUT ROWID;
You could define the table as WITHOUT ROWID [1], but as docs point out, the average row size shouldn’t exceed 200 bytes for the default 4 KiB page size. Since a UUID in text form is at best 32 chars, that doesn’t leave much for the rest of the columns.
So the bloom filter optimization does not work there.
It had to do with the different ways strings can be compared with collating functions, as strings may be equal even if they have different bytes: https://sqlite.org/forum/forumpost/0846211821
People frequently bring up write concurrency issues in SQLite, with the implied idea that if two physical people are using your app at once they'll get errors. But of course it's concurrency at a transaction level, vastly different - if your writes take 1ms (in SQLite they might even be faster), you can support 1,000 writes per second. And if your users are generating a write click every 5 seconds (a very engaged user base, in most apps more users are readers) you can support 5,000 simultaneous physical people before you need to start worrying about scaling, replication, and distributed shenanigans.
If only 5% of those users are writers and the rest are readers / lurkers, you can support 100,000 users simultaneously.
I suspect close to 99% of distributed app architectures are premature optimizations for a scale the company will never reach.
I am a huge fan of SQLite but its best use case is a local database for a local application. You can use it for a client-server setup in some special circumstances but in my mind you’d need a compelling reason to do that rather than using the standard solution of something like Postgres.
I guess my point is, a single cloud VM with the (web) app server and a SQLite database will take you VERY far these days in terms of performance and concurrent users. The web server becomes your client-server layer, which can possibly eliminate the need for a separate client-server interface on the database end. Of course each app is different, but it's worth taking a hard look at whether you need that additional server & network connection (i.e. a bunch of app servers sharing the same database, that can't be done with an API). It's good to delete any part or process that you can.
Cloud vendor developer-marketing and resume-driven-development has pushed the industry into ever more complicated distributed infrastructures, but I suspect the needs of 99% of businesses could be handled much more simply, with vertical scaling if needed (larger VM class) before diving into kubernetes, clustering, load balancing, lambda, microservices, replication, etc.
And it’s not that it’s best practice. It is because sometimes you legitimately do need separate processes. Imagine you have a web UI for a service that transcodes video. You aren’t running transcodes on the same CPU cores as your web requests. And chances are you need a lot more power for the worker side than the web side.
For toy projects you can get away with almost any setup. For a project where people are paying money for a service you really need to start engineering your infrastructure because you have actual trade offs.
Excuse me? The only way you would be able to come to this conclusion is if you did no reading whatsoever and never tried it.
This “confidently wrong” attitude really needs to stop.
From SQLite’s FAQ page, yes they can [0]. Two processes cannot simultaneously write to it, but they can both have it open, and read. With a modicum of tuning and application error handling, you can quite easily have multiple processes writing.
> …you really need to start engineering your infrastructure because you have actual trade offs.
Step one is fully understanding the abilities and limitations of available tooling.
SQLite is a wonderful database engine. But it isn’t the end all be all and no it doesn’t scale in the same way as something like Postgres. You cannot stretch it but you hit diminishing returns fairly quickly.
SQLite: Past, Present, and Future - https://news.ycombinator.com/item?id=32675861 - Sept 2022 (143 comments)
They will never have a false negative (and only sometimes a false positive).
We used this to vastly improve render times for comments pages on reddit. We used two tricks. The first was to store the time of your last vote as a first class property on your user object. If you loaded a comments page for a link that was submitted after your last vote, we knew that you couldn't have voted on any of those comments.
But if you had voted afterwards, we had to look up every single comment on the page to see if you had voted on it (we couldn't only do the comments made before your last vote because we didn't know the creation time until after we looked up the comment, and it was faster to just look up the vote).
But with a bloom filter, we could very quickly look up all the comments and get back a list of all the ones you voted on (with a couple of false positives in there). Then we could go to the cache and see if your actual vote was there (and if it was an upvote or a downvote). It was only after a failed cache hit did we have to actually go to the database.
But that bloom filter saved us from doing sometimes 1000s of cache lookups.
And of course the answer from a bloom filter was either "no" or "probably yes?", which was good enough to then do an actual lookup of that person's vote on that comment.
My average latency on reddit is about 150ms, most of that network transit time. Some calls are slow, yes, but on average site wide when I worked there is was about 300ms (yes we measured it).
> Is Python just really really slow compared to LISP?
Now I'm almost certain you're trolling. Reddit was originally written in LISP. It was rewritten to Python for a massive speedup. Then we rewrote parts of it in C for another speedup. And now I'm pretty sure they have Rust and Golang too.
Also, I'm pretty sure HN isn't in Arc anymore.
master jart@luna:~/cosmo$ time curl --tcp-fastopen -L 'https://www.reddit.com/r/torties/comments/1hldi83/i_adopted_two_girls/' 2>/dev/null | head -c1 >/dev/null
real 0m0.203s
user 0m0.016s
sys 0m0.006s
The linked paper is clearer:
"However, the inner loops in the join are typically accelerated with existing primary key indexes or temporary indexes built on the fly."
"Note that SQLite probes the part table index for every tuple in the lineorder table."
The Bloom filter does not reduce the cardinality of the join, it simply replaces each B-tree probe and filter with a Bloom probe on a pre-filtered key set.
This technique is well-known; the paper cites several examples, and Bloom filter pushdown is common to many commercial systems.
If you’re using one of the hosting providers or managed services that just give you a DB to use and you don’t have to think about administering it, it’s a pretty relaxed experience.
Even if you self-host, running a container with the DB of your choice usually isn’t that much more difficult than just having an SQLite DB for your app, at that point it’s probably more about the features which each solution provides.
Personally, I have some stuff running on MariaDB, PostgreSQL and SQLite and I’ve almost never had any problems with either. Then again, I’ve never gotten to a scale with personal stuff where the specifics of that choice would matter much.
Eg you have to go to quite a bit of effort to construct a knapsack problem that's hard to solve.
First, you start with an NP problem where virtually all instances are expected to be hard, like finding the pre-image to a given sha256 hash digest. Second, you sample a random instance in O(n). Third and last, you reduce this problem from the original sha256 inversion to knapsack. You can do this in polynomial time, because knapsack is NP complete.
Note for the pedantic: inverting sha256 is certainly in NP, but it's not expected to be NP complete.
Second note for the pedantic: because sha256's digest has a specific fixed size, you can technically solve any problems around it in constant time with a big lookup table. So you should replace sha256 in my example with any other problem that's expected to be hard on average.
https://www.postgresql.org/docs/17/geqo-pg-intro.html
The theory being an exhaustive search of all possible query plans is np-hard and would take too long, so you do a limited, iterative, best fit search.
My understanding is it never worked super great and would only be used if your query exceeded some high level of complexity. I distinctly remember it being removed at some point, but I see it mentioned in current docs, so I am probably wrong about that.
Anyway I wonder if, with some of the new advances in machine learning, it would be worth revisiting this approach to optimization.
Beam search approximates NP-hard solutions (make wider beam, have better approximation), is very old and it is used in SQLite query planner: https://www.sqlite.org/queryplanner-ng.html
What am I missing?
It's better to check A x C before A x B if you know that A x C has less matching rows, because the final loop will be shorter.
Yes, the sqlite concurrency model is a bad choice if you have a high degree of concurrent writes. However for many applications that simply isn't true. When it comes to websites i think people significantly overestimate the amount of concurrent writes.
We're all using WAL mode these days, right?
The only difference between SQLite and Postgres write locking is the granularity.
But it’s talked about as if it’s a categorical limitation, the app will fail if there is concurrency. But it’s just a question of how much time will be spent locking.
A website with a 16 process pool for handling requests will be fine.
Even if you don’t use message passing to use one thread to perform all updates/writes, it still performs very solidly for many use cases.
If you are sharing your database between processes or machines, you are probably doing "the fancy new SQLite thing" wrong.
If you need to share information contained in a SQLite database with other processes or machines, you can write application-level code to handle this concern.
For example, LAMP stack applications could swap the M for SQlite (and I think it would have been better historically if they did).
I think it is a bit unfair to argue against SQLite on performance grounds but then not explore ways to utilize instances of it within a single process scope where it is most effective.
Sharing a single SQLite connection across all threads within a process is where you get the best performance outcomes. Everything is serialized within the SQLite provider - assuming you are using a mainstream build. So, if your storage subsystem is fast (NVMe & friends), you will achieve very good outcomes. Any utilization model that requires a file open/close operation every time you want to touch the data is a complete non-starter by comparison. The "unit of work" paradigm that hosted providers recommend is catastrophic for performance with SQLite.
One option for the "I absolutely must share this SQLite instance with 30+ services" scenario is to simply wrap it with a REST API or similar.
You mean the one where it locks on write? It’s totally fine, if you wrote any cross process code yourself it’s probably going to do similar locking.
The only point I’m disagreeing about is the blanket statement “your SQLite website won’t work if it has concurrent writers”. It will.
https://www.sqlite.org/lockingv3.html
In the single process access model, you can connect exactly once and remain in a reserved lock state the entire time.
There are advantages and disadvantages to using WAL instead of a rollback journal. Advantages include:
WAL is significantly faster in most scenarios.
WAL provides more concurrency as readers do not block writers and a writer does not block readers. Reading and writing can proceed concurrently.
Disk I/O operations tends to be more sequential using WAL.
WAL uses many fewer fsync() operations and is thus less vulnerable to problems on systems where the fsync() system call is broken.*To me the concept of SQLite in these scenarios, without the WAL, is just nuts.
What a progress we have with these. Amazing times.
> One of the challenges with binary fuse filters, is that they are immutable once populated, so data cannot be added incrementally, and they consume a significant amount of memory during the populate process
In any event, to address your question, most of the time people truncate to some round number of bytes (8, 16, 32, 64 bits, really) because this is very cheap, but it’s actually barely more expensive to truncate to any smaller than 64 number of bits with masks & shifts. Doing so with a back-to-back array of such truncated b-bit numbers (https://github.com/c-blake/adix/blob/master/adix/sequint.nim) structured as a regular hash table (such as robin hood linear probing (https://github.com/c-blake/adix/blob/master/adix/bltab.nim) where a hit or miss will likely only induce a nearly guaranteed single cache line miss up to ~90..95+% utilization) lets you make a filter with many fewer CPU cache misses (~10X fewer, but everything always depends on where you land in the parameter space) than a Bloom filter at a small 2..4X cost in more space.
There are some example numbers and a “calculus analysis” at the bottom of https://github.com/c-blake/adix/blob/master/tests/bl.nim, but it’s all only a few hundred lines of Nim and you could re-do a test in your favorite ProgLang. This table does eventually "fill up" like Cuckoo or any fixed malloc'd arena at which point people usually double/whatever to make more space resulting in a linear amortized cost growing up from zero. I would just call this a b-bit hash existence filter or maybe b-filter or bit-level filter if you want to get brief.
FWIW, I believe this was even understood by the aboriginal paper by Bloom in his 1970 CACM article (https://cacm.acm.org/research/space-time-trade-offs-in-hash-...) based upon his footnote2, though I think he was referring less to a CPU cache and more to "loading a whole word of memory at a time" like the 36-bit word IBM mainframes of the day, though these are similar mathematically (just think of a 64B cache-line as a 512-bit aligned word). Somehow it got lost in the teaching of Bloom filters.
To speculate on that "somehow", once you have a new dimension (accuracy in space-time-accuracy here), it is easy/natural to only consider "projections", but such oversimplifications can lead one astray. E.g., most people I know optimize for space only to indirectly optimize for time, but most discussion on this topic is about space-accuracy.
Edit: I guess you could get really efficient at detecting things not in the database, but the soon as you get a single false or true positive the process runs into the equivalent of a screeching halt if you need to actually check if it's there.
(You could also combine a static filter with a dynamic bloom filter in front. A bit like generational garbage collection.)
A recent paper trying to systematically apply the idea to databases "Towards Systematic Index Dynamization" ( https://bpb-us-e1.wpmucdn.com/sites.psu.edu/dist/b/123163/fi... )
https://twit.tv/posts/tech/cascading-bloom-filters-revolutio...
One way to address this is to recalculate it every n deletes, but this sounds similar to AUTOVACUUM issues in PostgreSQL and might result in unexpected drops in performance
My guess though is that many use cases are likely data stores that don't experience deletes at all.
So maybe this is built for every query? Would be needed anyway if there is a where clause for the joined table.
Another option is a cuckoo filter; it is like a bloom but allows deletion
Only that? Never anything better? Really?
EDIT: Really.
Section titled Joins here https://sqlite.org/optoverview.html
states:
"SQLite implements joins as nested loops."
That's quite shocking.
While doing MySQL and Postgres when nested loop showed up in EXPLAIN in almost all cases I knew I botched my query and/or indexes.
As far as i know (might be wrong,im not really familiar with mysql internals), mysql (like sqlite) generally uses nested loop joins all the time. The EXPLAIN just only says something in the join buffer case. When using a simple nested loop join, EXPLAIN does not mention the fact that it is using that algorithm.
Though I remember one instance where while using MySQL in a web app it turned out that N+1 was faster than doing a JOIN.
It was faster to get rows from big table and then run few additional queries to get data for found rows from smaller ones than join everything together in one query. Maybe the nested loop buffer was culprit or whatever. Maybe I ran into edge case of query planner MySQL had 20 years ago. Who knows.
OTOH, I've requested clarification (just some basic documentation really) on the “open contribution” fork of SQLite… and they never documented their own code.
And I'm sorry, I know sarcasm isn't the way here, and is impolite, but that was exactly the point.
Less than a week ago we had a whole thread where, again, we discussed the impossibility of improving SQLite from the outside because it's not “open contribution.”
Well, this is just a great example of much larger feature that was developed in collaboration with them.