How bloom filters made SQLite 10x faster

Re:How bloom filters made SQLite 10x faster by ramraj07 on Sunday December 22, 2024 @11:02PM (#42491649)

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

[ Parent | on HN ]

Re:How bloom filters made SQLite 10x faster by devoutsalsa on Sunday December 22, 2024 @11:44PM (#42491867)

90%?

[ Parent | on HN ]

Re:How bloom filters made SQLite 10x faster by metadat on Monday December 23, 2024 @12:41AM (#42492094)

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

[ Parent | on HN ]

Re:How bloom filters made SQLite 10x faster by LudwigNagasena on Monday December 23, 2024 @09:31AM (#42494620)

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

[ Parent | on HN ]

Re:How bloom filters made SQLite 10x faster by jschafer on Monday December 23, 2024 @10:40AM (#42495160)

SQLite 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%.

[ Parent | on HN ]