Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How bloom filters made SQLite 10x faster

avi.im

Post reply on HN
Print view View original

41–50 of 127 posts

Re: How bloom filters made SQLite 10x faster

#41

Post by metadat »

ramraj07 wrote: post #37
jschafer wrote: post #22

Note 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 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 t…

How much of a slowdown did you estimate this bug caused?

It actually would have performed faster, but the false positive rate drastically increased.

Re: How bloom filters made SQLite 10x faster

#42

Post by liontwist »

bob1029 wrote: post #31
liontwist wrote: post #26

Earlier quoted context omitted.

Sharing between processes? Absolutely. Machines? No. For example, LAMP stack applications could swap the M for SQlite (and I think it would have been better historically if they did).

Sharing between processes isn't impossible but this where you get all of your performance caveats. 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 ser…

> but this where you get all of your performance caveats.

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.

Re: How bloom filters made SQLite 10x faster

#43

Post by miunau »

liontwist wrote: post #25
gwervc wrote: post #21

Earlier quoted context omitted.

No, it's indeed a very real problem. I ran into with a very small service.

You want to configure it so it has a timeout. Take turns. That’s how locks work. The only difference between SQLite and Postgres write locking is the granularity.

It's not a trivial difference like you suggest.

Re: How bloom filters made SQLite 10x faster

#44

Post by jedberg »

Bloom 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.

Re: How bloom filters made SQLite 10x faster

#45

Post by agilob »

jschafer wrote: post #22

Note 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 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 t…

On top of that I don't think it's fair to say it's 10x faster when it btree was tested only on integer index primary key column. Benchmarks with that bold statements should include short string (1-16 chars maybe) and UUID indexes at least.

Re: How bloom filters made SQLite 10x faster

#46

Post by agilob »

remram wrote: post #32
DaveMcMartin wrote: post #5

SQLite is getting better and better. I am using it in production for a bunch of websites and never got a problem.

If you never got a problem then how is it getting better?

What if we didn't know we had a problem? And now it's "ooooh it's better now".

Re: How bloom filters made SQLite 10x faster

#47

Post by bawolff »

scotty79 wrote: post #39

> SQLite does Nested Loop join 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.

If 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.

Re: How bloom filters made SQLite 10x faster

#48

Post by bawolff »

bob1029 wrote: post #31
liontwist wrote: post #26

Earlier quoted context omitted.

Sharing between processes? Absolutely. Machines? No. For example, LAMP stack applications could swap the M for SQlite (and I think it would have been better historically if they did).

Sharing between processes isn't impossible but this where you get all of your performance caveats. 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 ser…

I don't see why performance would be significantly different between multiple threads using same sqlite db vs multiple processes on same machine. Can you explain more what you mean?

Re: How bloom filters made SQLite 10x faster

#49

Post by mahmoodz98 »

What 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

Re: How bloom filters made SQLite 10x faster

#50

Post by tacone »

mahmoodz98 wrote: post #49

What 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

You 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.

Post reply on HN