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

71–80 of 127 posts

Re: How bloom filters made SQLite 10x faster

#71

Post by liontwist »

miunau wrote: post #43
liontwist wrote: post #25

Earlier quoted context omitted.

You want to configure it so it has a timeout. Take turns. That’s how locks work. The only difference between SQLite and Postgres write locking is the granularity.

It's not a trivial difference like you suggest.

I agree It’s not a trivial difference in implementation and the concurrent write performance is probably a lot worse.

But it’s talked about as if it’s a categorical limitation, the app will fail if there is concurrency. But it’s just a question of how much time will be spent locking.

A website with a 16 process pool for handling requests will be fine.

Re: How bloom filters made SQLite 10x faster

#72

Post by jschafer »

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.

I do not know if it is still the case, but the last time I looked into the source code SQLite did hash all strings to the exact same value.

So the bloom filter optimization does not work there.

It had to do with the different ways strings can be compared with collating functions, as strings may be equal even if they have different bytes: https://sqlite.org/forum/forumpost/0846211821

Re: How bloom filters made SQLite 10x faster

#73

Post by NDizzle »

I like to think it's more than a nit to pick, but does anyone else absolutely despise the way the sql is written in the example? Join table1, table2, table3, table4... then the "on" logic in the where clause, without explicitly defining which columns belong to which table? Completely unsupportable and wastes so much time years from now. Please don't write sql like that, everyone.

Re: How bloom filters made SQLite 10x faster

#74

Post by jschafer »

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?

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

Re: How bloom filters made SQLite 10x faster

#75

Post by [deleted] »

immibis wrote: post #7
DaveMcMartin wrote: post #5

SQLite is getting better and better. I am using it in production for a bunch of websites and never got a problem.

It should be fine for read-only data. If you want to write, be aware that only one process can write at a time, and if you forget to set busy_timeout at the start of the connection, it defaults to zero milliseconds and you'll get an error if another process has locked the database for writing while you try to read or write it. Client-server databases tend to handle concurrent writers better.

[deleted]

Re: How bloom filters made SQLite 10x faster

#76

Post by QuadrupleA »

Small aside based on some comments here -

People frequently bring up write concurrency issues in SQLite, with the implied idea that if two physical people are using your app at once they'll get errors. But of course it's concurrency at a transaction level, vastly different - if your writes take 1ms (in SQLite they might even be faster), you can support 1,000 writes per second. And if your users are generating a write click every 5 seconds (a very engaged user base, in most apps more users are readers) you can support 5,000 simultaneous physical people before you need to start worrying about scaling, replication, and distributed shenanigans.

If only 5% of those users are writers and the rest are readers / lurkers, you can support 100,000 users simultaneously.

I suspect close to 99% of distributed app architectures are premature optimizations for a scale the company will never reach.

Re: How bloom filters made SQLite 10x faster

#77

Post by FpUser »

remram wrote: post #32
DaveMcMartin wrote: post #5

SQLite is getting better and better. I am using it in production for a bunch of websites and never got a problem.

If you never got a problem then how is it getting better?

Packs more features and improvements over the time. One can read it to see that it gets better

Re: How bloom filters made SQLite 10x faster

#78

Post by kwillets »

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 filter does not reduce the cardinality of the join, it simply replaces each B-tree probe and filter with a Bloom probe on a pre-filtered key set.

This technique is well-known; the paper cites several examples, and Bloom filter pushdown is common to many commercial systems.

Re: How bloom filters made SQLite 10x faster

#79

Post by cogman10 »

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/

Call me crazy, but I'm simply splitting my UUID into the higher and lower bits and indexing off that.

IE

    CREATE TABLE foo(
        id_ms    UNSIGNED BIG INT NOT NULL,
        id_ls    UNSIGNED BIG INT NOT NULL,
        PRIMARY KEY (id_ms, id_ls)
    ) WITHOUT ROWID;
That works well with UUIDv7 and is just storing 128bits rather than a full string. In most languages it's pretty trivial to turn 2 longs into a UUID and vice versa.

Re: How bloom filters made SQLite 10x faster

#80

Post by emseetech »

immibis wrote: post #54
kevingadd wrote: post #19

Earlier quoted context omitted.

Depending on the amount of write throughput you need and whether you care about latency, "concurrent writes" aren't necessarily a problem either. You can just shove them into a queue and then have a single thread pull stuff out of the queue and push it into SQLite. That still scales, up to a point.

No, because your readers are still blocked by writers and still randomly fail if you forgot to set busy_timeout, which is something at least one person didn't they had to do until they read this comment.

| readers are still blocked by writers

We're all using WAL mode these days, right?

Post reply on HN