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

61–70 of 127 posts

Re: How bloom filters made SQLite 10x faster

#61

Post by Scene_Cast2 »

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…

It's also a problem in machine learning. Your data might be mangled due to a bug but the NN will still extract something useful out of it. Or, on the flip side, if you make a change to the data and things do break (learning stops converging), you never really know if it's the architecture or the data that's the issue.

Re: How bloom filters made SQLite 10x faster

#62

Post by thaumasiotes »

agilob wrote: post #45
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.

Why do you want a UUID index? Use an integer index and have the UUID in another column.

Re: How bloom filters made SQLite 10x faster

#63

Post by sethammons »

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

We 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

Re: How bloom filters made SQLite 10x faster

#64

Post by kanak »

eru wrote: post #34
nsteel wrote: post #17

Earlier quoted context omitted.

Maybe 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

You can convert static data structures like these into dynamic ones with about a logarithmic slowdown. So it might still be worthwhile. (You could also combine a static filter with a dynamic bloom filter in front. A bit like generational garbage collection.)

For others interested in this idea, look up "Bentley-Saxe transformation". These lecture notes are very readable: https://jeffe.cs.illinois.edu/teaching/datastructures/notes/... .

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

Re: How bloom filters made SQLite 10x faster

#65

Post by dymk »

thaumasiotes wrote: post #62
agilob wrote: post #45

Earlier quoted context omitted.

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.

Why do you want a UUID index? Use an integer index and have the UUID in another column.

Because if you want to refer to things by a UUID, now you have two indexes

Re: How bloom filters made SQLite 10x faster

#66

Post by scotty79 »

bawolff wrote: post #47
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…

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

Re: How bloom filters made SQLite 10x faster

#67

Post by LudwigNagasena »

metadat wrote: post #41
ramraj07 wrote: post #37

Earlier quoted context omitted.

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

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

I guess the person is asking how much a slowdown did the whole query receive.

Re: How bloom filters made SQLite 10x faster

#68

Post by leourbina »

dymk wrote: post #65
thaumasiotes wrote: post #62

Earlier quoted context omitted.

Why do you want a UUID index? Use an integer index and have the UUID in another column.

Because if you want to refer to things by a UUID, now you have two indexes

UUIDs are very wasteful [1]. For most use cases you can replace them with much shorter strings and still have very low chances of collisions [2]

[1] https://henvic.dev/posts/uuid/

[2] https://alex7kom.github.io/nano-nanoid-cc/

Re: How bloom filters made SQLite 10x faster

#70

Post by PittleyDunkin »

leourbina wrote: post #68
dymk wrote: post #65

Earlier quoted context omitted.

Because if you want to refer to things by a UUID, now you have two indexes

UUIDs are very wasteful [1]. For most use cases you can replace them with much shorter strings and still have very low chances of collisions [2] [1] https://henvic.dev/posts/uuid/ [2] https://alex7kom.github.io/nano-nanoid-cc/

Sure, at cost of increased complexity of access. Sometimes the waste is worth the simplicity.
Post reply on HN