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

111–120 of 127 posts

Re: How bloom filters made SQLite 10x faster

#111

Post by thesz »

somat wrote: post #81
PartiallyTyped wrote: post #10

Just a thought, just because a general problem is NPHard doesn't mean that we can't find specific solutions quickly or that a given input is hard to search for. If the downstream effect results in an order of magnitude less work, it makes sense, it's just a tradeoff.

The one I liked was the postgres genetic optimizer. https://www.postgresql.org/docs/17/geqo-pg-intro.html The theory being an exhaustive search of all possible query plans is np-hard and would take too long, so you do a limited, iterative, best fit search. My understanding is it never worked super great and would only be used if your query exceeded some high level of complexity. I distinctly remember it being removed…

As you mentioned machine learning, a useful way to implement inference in language models is to use a beam search: https://en.wikipedia.org/wiki/Beam_search

Beam search approximates NP-hard solutions (make wider beam, have better approximation), is very old and it is used in SQLite query planner: https://www.sqlite.org/queryplanner-ng.html

Re: How bloom filters made SQLite 10x faster

#112

Post by kebsup »

bogdan-lab wrote: post #107

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?

You don't go through entire loops everywhere because if there isn't a match in the first two tables, you don't have to check the match with the third table.

It's better to check A x C before A x B if you know that A x C has less matching rows, because the final loop will be shorter.

Re: How bloom filters made SQLite 10x faster

#113

Post by jart »

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…

That's wonderful. Can you help me understand why every single button click on Reddit has an 800ms user visible latency gap? Reddit has always been this way, ever since its very beginning. Its latency has always been so slow compared to Hacker News. Why can't Reddit go snappy like HN? Is Python just really really slow compared to LISP? Why didn't your bloom filter improve user visible latency?

Re: How bloom filters made SQLite 10x faster

#114

Post by jedberg »

simonw wrote: post #108
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?

I honestly don't remember for sure, but I believe it was one row per comment with a list of everyone who voted on it. So you could quickly get the answer to "did user X vote on comment Y?"

And of course the answer from a bloom filter was either "no" or "probably yes?", which was good enough to then do an actual lookup of that person's vote on that comment.

Re: How bloom filters made SQLite 10x faster

#115

Post by jedberg »

jart wrote: post #113
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…

That's wonderful. Can you help me understand why every single button click on Reddit has an 800ms user visible latency gap? Reddit has always been this way, ever since its very beginning. Its latency has always been so slow compared to Hacker News. Why can't Reddit go snappy like HN? Is Python just really really slow compared to LISP? Why didn't your bloom filter improve user visible latency?

I can't tell if you're trolling or serious. If you're serious, I think the problem may be on your end, because I don't see that latency, and when I worked there, we didn't see that latency either.

My average latency on reddit is about 150ms, most of that network transit time. Some calls are slow, yes, but on average site wide when I worked there is was about 300ms (yes we measured it).

> Is Python just really really slow compared to LISP?

Now I'm almost certain you're trolling. Reddit was originally written in LISP. It was rewritten to Python for a massive speedup. Then we rewrote parts of it in C for another speedup. And now I'm pretty sure they have Rust and Golang too.

Also, I'm pretty sure HN isn't in Arc anymore.

Re: How bloom filters made SQLite 10x faster

#116

Post by [deleted] »

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…

[deleted]

Re: How bloom filters made SQLite 10x faster

#117

Post by jart »

jedberg wrote: post #115
jart wrote: post #113

Earlier quoted context omitted.

That's wonderful. Can you help me understand why every single button click on Reddit has an 800ms user visible latency gap? Reddit has always been this way, ever since its very beginning. Its latency has always been so slow compared to Hacker News. Why can't Reddit go snappy like HN? Is Python just really really slow compared to LISP? Why didn't your bloom filter improve user visible latency?

I can't tell if you're trolling or serious. If you're serious, I think the problem may be on your end, because I don't see that latency, and when I worked there, we didn't see that latency either. My average latency on reddit is about 150ms, most of that network transit time. Some calls are slow, yes, but on average site wide when I worked there is was about 300ms (yes we measured it). > Is Python just really really…

I am serious. If you're not logged in then reddit pages will take 150ms to respond if you exclude the snooserv ?rdt=xxxx redirect (which makes it take 200ms total).

    master jart@luna:~/cosmo$ time curl --tcp-fastopen -L 'https://www.reddit.com/r/torties/comments/1hldi83/i_adopted_two_girls/' 2>/dev/null | head -c1 >/dev/null
    real    0m0.203s
    user    0m0.016s
    sys     0m0.006s
But if you're logged in as "jart" and use that chrome inspect feature to "copy as curl command" and run it on the shell, then the above URL takes 800ms to respond. Pretty much every page on Reddit takes 800ms+ to send back the first byte of content. Yes I use old reddit mode. I imagine the same problem afflicts all your long time loyal fans who uses Reddit while logged in. FWIW my ping to reddit.com is 4.5ms.

Re: How bloom filters made SQLite 10x faster

#118

Post by jedberg »

jart wrote: post #117
jedberg wrote: post #115

Earlier quoted context omitted.

I can't tell if you're trolling or serious. If you're serious, I think the problem may be on your end, because I don't see that latency, and when I worked there, we didn't see that latency either. My average latency on reddit is about 150ms, most of that network transit time. Some calls are slow, yes, but on average site wide when I worked there is was about 300ms (yes we measured it). > Is Python just really really…

I am serious. If you're not logged in then reddit pages will take 150ms to respond if you exclude the snooserv ?rdt=xxxx redirect (which makes it take 200ms total). master jart@luna:~/cosmo$ time curl --tcp-fastopen -L 'https://www.reddit.com/r/torties/comments/1hldi83/i_adopted_two_girls/' 2>/dev/null | head -c1 >/dev/null real 0m0.203s user 0m0.016s sys 0m0.006s But if you're logged in as "jart" and use that chrome…

Something is broken in your profile then. I also use old reddit and most pages load within 150ms for me.

Re: How bloom filters made SQLite 10x faster

#119

Post by jart »

jedberg wrote: post #118
jart wrote: post #117

Earlier quoted context omitted.

I am serious. If you're not logged in then reddit pages will take 150ms to respond if you exclude the snooserv ?rdt=xxxx redirect (which makes it take 200ms total). master jart@luna:~/cosmo$ time curl --tcp-fastopen -L 'https://www.reddit.com/r/torties/comments/1hldi83/i_adopted_two_girls/' 2>/dev/null | head -c1 >/dev/null real 0m0.203s user 0m0.016s sys 0m0.006s But if you're logged in as "jart" and use that chrome…

Something is broken in your profile then. I also use old reddit and most pages load within 150ms for me.

Any idea how I get unbroken?

Re: How bloom filters made SQLite 10x faster

#120

Post by jedberg »

jart wrote: post #119
jedberg wrote: post #118

Earlier quoted context omitted.

Something is broken in your profile then. I also use old reddit and most pages load within 150ms for me.

Any idea how I get unbroken?

You could contact them but honestly that probably wouldn't work very well. Things that might help: switch your settings from old reddit to new reddit, use new reddit to load a few pages, and then switch back. Also try using "newest" reddit at https://sh.reddit.com.
Post reply on HN