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

31–40 of 127 posts

Re: How bloom filters made SQLite 10x faster

#31

Post by bob1029 »

liontwist wrote: post #26
bob1029 wrote: post #23

Earlier quoted context omitted.

SQLite really isn't meant to be used exactly like a hosted solution. I don't know who is advocating for this. 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.

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

Re: How bloom filters made SQLite 10x faster

#33

Post by tehjoker »

nsteel wrote: post #17
datadeft wrote: post #13

Next should be this -> https://x.com/lemire/status/1869752213402157131 What a progress we have with these. Amazing times.

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

It's also not clear that a better filter will result in a substantial improvement for SQLite. If the improvement is on the order of a tens or hundreds of nanoseconds per a query, that's nothing compared to hitting disk.

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.

Re: How bloom filters made SQLite 10x faster

#34

Post by eru »

nsteel wrote: post #17
datadeft wrote: post #13

Next should be this -> https://x.com/lemire/status/1869752213402157131 What a progress we have with these. Amazing times.

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

Re: How bloom filters made SQLite 10x faster

#36

Post by eru »

PartiallyTyped wrote: post #16
bawolff wrote: post #12

Earlier quoted context omitted.

Well yes, heurstics for query planning is a very well researched field

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

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

Re: How bloom filters made SQLite 10x faster

#37

Post by ramraj07 »

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?

Re: How bloom filters made SQLite 10x faster

#38

Post by mythz »

Thanks 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

[2] https://www.sqlite.org/rsync.html

Re: How bloom filters made SQLite 10x faster

#39

Post by scotty79 »

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

Re: How bloom filters made SQLite 10x faster

#40

Post by devoutsalsa »

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?

90%?
Post reply on HN