3 ms·

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 filt

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 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 those kind of bugs with test cases.

ramraj07 2y ago
How much of a slowdown did you estimate this bug caused?
- devoutsalsa 2y ago
  90%?
- metadat 2y ago
  It actually would have performed faster, but the false positive rate drastically increased.
  - LudwigNagasena 2y ago
    I guess the person is asking how much a slowdown did the whole query receive.
- jschafer 2y ago
  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%.
agilob 2y ago
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.
- thaumasiotes 2y ago
  Why do you want a UUID index? Use an integer index and have the UUID in another column.
  - dymk 2y ago
    Because if you want to refer to things by a UUID, now you have two indexes
    - leourbina 2y ago
      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/ https://henvic.dev/posts/uuid/ [2] https://alex7kom.github.io/nano-nanoid-cc/ https://alex7kom.github.io/nano-nanoid-cc/
      - PittleyDunkin 2y ago
        Sure, at cost of increased complexity of access. Sometimes the waste is worth the simplicity.
      - cogman10 2y ago
        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.
Scene_Cast2 2y ago
It's also a problem in machine learning. Your data might be mangled due to a bug but the NN will still extract something useful out of it. Or, on the flip side, if you make a change to the data and things do break (learning stops converging), you never really know if it's the architecture or the data that's the issue.

ramraj07 2y ago

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

devoutsalsa 2y ago
90%?
metadat 2y ago
It actually would have performed faster, but the false positive rate drastically increased.
- LudwigNagasena 2y ago
  I guess the person is asking how much a slowdown did the whole query receive.
jschafer 2y ago
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%.

agilob 2y ago

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.

thaumasiotes 2y ago
Why do you want a UUID index? Use an integer index and have the UUID in another column.
- dymk 2y ago
  Because if you want to refer to things by a UUID, now you have two indexes
  - leourbina 2y ago
    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/ https://henvic.dev/posts/uuid/ [2] https://alex7kom.github.io/nano-nanoid-cc/ https://alex7kom.github.io/nano-nanoid-cc/
    - PittleyDunkin 2y ago
      Sure, at cost of increased complexity of access. Sometimes the waste is worth the simplicity.
    - cogman10 2y ago
      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.

Scene_Cast2 2y ago

It's also a problem in machine learning. Your data might be mangled due to a bug but the NN will still extract something useful out of it. Or, on the flip side, if you make a change to the data and things do break (learning stops converging), you never really know if it's the architecture or the data that's the issue.