32 ms·
How bloom filters made SQLite 10x faster
- deleted 2y ago[deleted]
- dang 2y agoRelated: SQLite: Past, Present, and Future - https://news.ycombinator.com/item?id=32675861 https://news.ycombinator.com/item?id=32675861 - Sept 2022 (143 comments)
- ncruces 2y ago[flagged]
- gpcz 2y agoEven if true, it seems like they're doing a pretty good job on their own.
- jpalawaga 2y agoSQLite is self-described as not open contribution. So yes by their own measure they've made it more difficult to mainline features (and intentionally so).
- steve_gh 2y agoI submitted a bug report on SQLite a year or so back (a simple test case only, not a solution). The folks were super nice, and their patch went into the next release.
- ncruces 2y agoMe too, repeatedly. I've asked questions, reported bugs, asked for enhancements, made suggestions, submitted patches for consideration, and was always welcomed. Even when I'm asking for stuff that doesn't necessarily align with their goals. 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.
- binary132 2y agoOpen contribution isn’t a good in and of itself.
- DaveMcMartin 2y agoSQLite is getting better and better. I am using it in production for a bunch of websites and never got a problem.
- immibis 2y agoIt should be fine for read-only data. If you want to write, be aware that only one process can write at a time, and if you forget to set busy_timeout at the start of the connection, it defaults to zero milliseconds and you'll get an error if another process has locked the database for writing while you try to read or write it. Client-server databases tend to handle concurrent writers better.
- bingaweek 2y ago[flagged]
- y1n0 2y agoI bet your great to work with.
- bawolff 2y agoI think people overstate this. 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.
- kevingadd 2y agoDepending on the amount of write throughput you need and whether you care about latency, "concurrent writes" aren't necessarily a problem either. You can just shove them into a queue and then have a single thread pull stuff out of the queue and push it into SQLite. That still scales, up to a point.
- 2y ago
- PartiallyTyped 2y agoJust a thought, just because a general problem is NPHard doesn't mean that we can't find specific solutions quickly or that a given input is hard to search for. If the downstream effect results in an order of magnitude less work, it makes sense, it's just a tradeoff.
- bawolff 2y agoWell yes, heurstics for query planning is a very well researched field
- PartiallyTyped 2y agoI was more thinking about solving NP hard problems. Modern CPUs are fast, if the benefit is worth it against the downstream task, just do it.
- eru 2y agoMost instances of most NP hard problems are fast and easy to solve in practice. Eg you have to go to quite a bit of effort to construct a knapsack problem that's hard to solve.
- DHRicoF 2y agoWhat complexity class will be the problem of construct only hards to solve knapsack (or others) problems?
- eru 2y agoFor knapsack, you can do that easily in polynomial time. Well, given a few minimal assumptions, like P!=NP; because otherwise there are no hard instances. 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.
- datadeft 2y agoNext should be this -> https://x.com/lemire/status/1869752213402157131 https://x.com/lemire/status/1869752213402157131 What a progress we have with these. Amazing times.
- nsteel 2y agoMaybe not such a great fit for sqlite: > 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
- ComputerGuru 2y agoSame restriction with cuckoo filters. Are there any better than bloom filters without this restriction?
- cb321 2y agoI think you may be confusing the strict immutability of binary fuse with the "degraded" (aka need-to-resize-a-hash-table-once-"full") of https://en.wikipedia.org/wiki/Cuckoo_filter https://en.wikipedia.org/wiki/Cuckoo_filter under high hash table load. 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 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 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 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-coding-with-allowable-errors/ 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.
- jschafer 2y agoNote that the measurements in the paper were made before they fixed a bug where they confused bits and bytes. So SQLite only used 1/8 of the reserved bloom filter space, thus increasing the false positive rate significantly: https://sqlite.org/src/info/56d9bb7aa63043f5 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.
- ramraj07 2y agoHow much of a slowdown did you estimate this bug caused?
- devoutsalsa 2y ago90%?
- metadat 2y agoIt actually would have performed faster, but the false positive rate drastically increased.
- LudwigNagasena 2y agoI guess the person is asking how much a slowdown did the whole query receive.
- jschafer 2y agoSQLite only knows nested loop joins and the bloom filter can just tell us "no need to do a join, there is definitely no matching entry". 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%.
- agilob 2y ago
- mythz 2y agoThanks to its simplicity for development and hosting SQLite has become our first choice for new Apps. We use a number of different ways to workaround its single concurrent writer limitation [1]. Whilst we're currently using Litestream for replication, we're currently evaluating switching to SQLite's native rsync [2]. [1] https://servicestack.net/posts/scalable-sqlite https://servicestack.net/posts/scalable-sqlite [2] https://www.sqlite.org/rsync.html https://www.sqlite.org/rsync.html
- ngrilly 2y agoLitestream replicates continuously. sqlite3_rsync takes a snapshot. How do you plan to use the latter?
- Faaak 2y agoDumb question, but how do you use SQLite on kubernetes? Indeed SQLite doesn't work over NFS (and I guess other remote file shares) so how do you share access to it to other pods?
- moooo99 2y agoWithout an additional layer you will have to be happy with a single vertically scaled instance of your application. If you want to resort to horizontal scaling, you can look into something like LiteFS
- joshlemer 2y agoIs switching to SQLite really making hosting your web apps less of a headache? Most hosting providers make spinning up your standard client-server RDBMSs (MySQL, Postgres) a breeze.
- mythz 2y agoNot having to worry about needing to configure, manage or pay for any additional infrastructure dependencies definitely makes hosting a lot simpler. Using RDS was the only thing keeping us on AWS, by switching to SQLite we're now running all new Apps on Hetzner VMs which costs around ~€0.60/mo to host a .NET + SQLite Docker App.
- scotty79 2y ago> SQLite does Nested Loop join Only that? Never anything better? Really? EDIT: Really. Section titled Joins here https://sqlite.org/optoverview.html 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.
- bawolff 2y agoIf you mean in mysql explain: "Using join buffer (Block Nested Loop)", its not slow because nested loop algorithm is being used, its slow because of the join buffer part, which is an optimization used when its not possible to immediately get the right row of the inner table via an index. 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.
- scotty79 2y agoFair enough, most of my memories about building fast, complex queries come from my Postgres times. 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.
- sgarland 2y agoThen your table schema was likely sub-optimal.
- scotty79 2y agoIt was long time ago. The schema was basically one table with a lot of fields and records and multiple small tables with way fewer records. Query in question resulted in small number of rows (because of LIMIT clause). 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.
- jedberg 2y agoBloom filters are great, I wish more people knew about them. The most important part about a bloom filter: 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.
- simonw 2y agoDid you maintain a single bloom filter for each user listing the comment IDs they had voted on across the whole site, or was it one bloom filter per user per thread?
- jedberg 2y agoI honestly don't remember for sure, but I believe it was one row per comment with a list of everyone who voted on it. So you could quickly get the answer to "did user X vote on comment Y?" 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.
- jart 2y agoThat's wonderful. Can you help me understand why every single button click on Reddit has an 800ms user visible latency gap? Reddit has always been this way, ever since its very beginning. Its latency has always been so slow compared to Hacker News. Why can't Reddit go snappy like HN? Is Python just really really slow compared to LISP? Why didn't your bloom filter improve user visible latency?
- mahmoodz98 2y agoWhat happens if the table is one with a big number of deletes? The Bloom filter false positive rate will keep increasing as time goes on. 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
- tacone 2y agoYou might reset the single position (which would invalidate all matching items) which is better than recalculating everything or mass invalidation. My guess though is that many use cases are likely data stores that don't experience deletes at all.
- schobi 2y agoThe article says "at the start of the join operation the bits will be set in the bloom filter". So maybe this is built for every query? Would be needed anyway if there is a where clause for the joined table.
- sethammons 2y agoWe do rotating filters for that. Items are added to the current and next bloom filters, and we stop serving from one, serving from the next, delete the former, and start the next filter. Another option is a cuckoo filter; it is like a bloom but allows deletion
- shayansm1 2y agohttps://llimllib.github.io/bloomfilter-tutorial/ https://llimllib.github.io/bloomfilter-tutorial/ for understanding how bloom filters work
- klaussilveira 2y agoIf anyone is interested, here are multiple membership filter implementations: https://github.com/FastFilter/fastfilter_cpp/ https://github.com/FastFilter/fastfilter_cpp/
- NDizzle 2y agoI like to think it's more than a nit to pick, but does anyone else absolutely despise the way the sql is written in the example? Join table1, table2, table3, table4... then the "on" logic in the where clause, without explicitly defining which columns belong to which table? Completely unsupportable and wastes so much time years from now. Please don't write sql like that, everyone.
- somat 2y ago"update ... from ..." still uses that syntax and it throws me for a loop every time. I have to stop and think about it while convincing myself it is doing the same thing as "join on". https://www.postgresql.org/docs/16/sql-update.html https://www.postgresql.org/docs/16/sql-update.html
- QuadrupleA 2y agoSmall aside based on some comments here - 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.
- IgorPartola 2y agoThe issue isn’t quite just that. If you are running your app and database on one single server and don’t need to move past that, SQLite is a great solution. But let’s say you have a web server and a worker server or more than one of each. Now you can’t access SQLite from multiple hosts as it doesn’t have a network access model. So your architecture is somewhat limited. You can still utilize it by either putting a network front end on it or setting up an API server in front of it that everything else uses. But at that point you have basically abstracted away SQLite enough that just using Postgres is easier. And with Postgres you get a lot more features that go hand in hand with multiple servers: replication, failover, etc. 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.
- SeenNotHeard 2y agoExactly. As Dr. Hipp writes on the web site, "SQLite does not compete with client/server databases. SQLite competes with fopen()."
- deleted 2y ago[deleted]
- kwillets 2y agoThe description of nested loop join is confusing; it's mainly a single pass through the outer table with one B-tree probe per row to each inner table. 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.
- bogdan-lab 2y agoThe article states that order of join matters because then nest loops differently. But we still go through entire loops everywhere. Where do those numbers in the example come from? If we have 1000, 20 and 200 elements in 3 loops, algorithmically, it does not matter in which order you iterate. Complexity is always 1000×20×200. What am I missing?
- kebsup 2y agoYou don't go through entire loops everywhere because if there isn't a match in the first two tables, you don't have to check the match with the third table. 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.
- bogdan-lab 2y agoAh, I see the numbers in the example are the numbers of matched rows, not a total number of rows... Make sense. I do not work with databases, did not know that you should pay attention to the order here.
- ray_v 2y agoSteve Gibson (grc.com) did a really great job of explaining how cascading bloom filters work in order to efficiently achieve fast certificate revocation lookups in Firefox. It's definitely worth checking out the episode https://twit.tv/posts/tech/cascading-bloom-filters-revolutionizing-web-security https://twit.tv/posts/tech/cascading-bloom-filters-revolutio...