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

101–110 of 127 posts

Re: How bloom filters made SQLite 10x faster

#101

Post by eru »

kanak wrote: post #64
eru wrote: post #34

Earlier quoted context omitted.

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

Thanks! I got my intro to this topic from Okasaki's Purely Functional Data Structures.

Re: How bloom filters made SQLite 10x faster

#102

Post by sgarland »

scotty79 wrote: post #66
bawolff wrote: post #47

Earlier quoted context omitted.

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.

Then your table schema was likely sub-optimal.

Re: How bloom filters made SQLite 10x faster

#103

Post by scotty79 »

sgarland wrote: post #102
scotty79 wrote: post #66

Earlier quoted context omitted.

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.

Then your table schema was likely sub-optimal.

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

Re: How bloom filters made SQLite 10x faster

#104

Post by avinassh »

kwillets wrote: post #78

The 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 filte…

hey could you let me know which part you found confusing specifically, so that I can rephrase it? Thanks!

Re: How bloom filters made SQLite 10x faster

#105

Post by IgorPartola »

jeremyvisser wrote: post #97
IgorPartola wrote: post #94

Earlier quoted context omitted.

Even if you are running it all on the same machine, a separate worker queue process and a web server process cannot share an SQLite database file. And it’s not that it’s best practice. It is because sometimes you legitimately do need separate processes. Imagine you have a web UI for a service that transcodes video. You aren’t running transcodes on the same CPU cores as your web requests. And chances are you need a lo…

> Even if you are running it all on the same machine, a separate worker queue process and a web server process cannot share an SQLite database file. Excuse me? The only way you would be able to come to this conclusion is if you did no reading whatsoever and never tried it. This “confidently wrong” attitude really needs to stop.

If you read the relevant docs you will see how this is implemented and maybe realize that locking your entire database for a write transaction isn’t something that works for a whole lot of cases. Of course multiple readers are allowed, but multiple writers even to different tables still contend for the same lock (that doesn’t work on all file systems). There isn’t table-level locking, let alone row level locking.

Re: How bloom filters made SQLite 10x faster

#106

Post by IgorPartola »

sgarland wrote: post #99
IgorPartola wrote: post #94

Earlier quoted context omitted.

Even if you are running it all on the same machine, a separate worker queue process and a web server process cannot share an SQLite database file. And it’s not that it’s best practice. It is because sometimes you legitimately do need separate processes. Imagine you have a web UI for a service that transcodes video. You aren’t running transcodes on the same CPU cores as your web requests. And chances are you need a lo…

> Even if you are running it all on the same machine, a separate worker queue process and a web server process cannot share an SQLite database file. From SQLite’s FAQ page, yes they can [0]. Two processes cannot simultaneously write to it, but they can both have it open, and read. With a modicum of tuning and application error handling, you can quite easily have multiple processes writing. > …you really need to start…

Correct. You cannot have concurrent writers even to two independent tables. That page also clearly states the limitations of even this global lock system. I should have been more precise with my language in that while it’s possible it functionally can get to being useless pretty quickly.

SQLite is a wonderful database engine. But it isn’t the end all be all and no it doesn’t scale in the same way as something like Postgres. You cannot stretch it but you hit diminishing returns fairly quickly.

Re: How bloom filters made SQLite 10x faster

#107

Post by bogdan-lab »

The 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?

Re: How bloom filters made SQLite 10x faster

#108

Post by simonw »

jedberg wrote: post #44

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…

Did 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?

Re: How bloom filters made SQLite 10x faster

#109

Post by kwillets »

avinassh wrote: post #104
kwillets wrote: post #78

The 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 filte…

hey could you let me know which part you found confusing specifically, so that I can rephrase it? Thanks!

The animation, pseudocode, and join order discussion all imply that the cartesian product is being generated.

Re: How bloom filters made SQLite 10x faster

#110

Post by mythz »

joshlemer wrote: post #83
mythz wrote: post #38

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

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

Not 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.
Post reply on HN