49 points | 5d ago | Discuss on Hacker News | Back to Radar
This project started about three years ago as a small piece of a proxy project (ramaproxy.org): on every request we pick a random upstream proxy that matches a handful of flags and a country or city. The data barely changes, the queries happen constantly. Scanning a Vec got slow, and SQLite felt like a lot of database for "give me a random row with these flags".
VennDB is a Rust library: you add a derive macro to a struct, and it generates a database type and a query builder for it. Bools become bitmasks, filter values become sets of rows, and a query is the intersection of those sets. It can pick a random match without finding all of them first.
It is mostly a bitmap index, generated from your struct so you don't have to write and maintain it yourself. It is also narrow on purpose: append-only and in-memory, with no updates or deletes. As such it is not really a database in the traditional sense of the word, but as I was not sure how to name it differently given it does fulfill a niche subset of usecases that I would otherwise use an (in-memory) database for it seemed fitting.
We just released 0.7, which rewrote the engine. In the README compares it with a hand-written roaring bitmap index, SQLite and a plain Vec. roaring gets close on some queries. We're not database experts, so if the benchmarks look unfair or there's prior art we missed, I'd like to hear it.
That explanation makes complete sense, because with this in mind, I can compare it to Apache Druid which does the same thing for data spilled onto S3.
Since this is immutable, you only had to solve "naming things", since the caches didn't need to be invalidated.
Druid is technically mutable, since it lets you mutate whole segments & then cache these bitmasks without having the original data in memory.
But if your dataset is already in memory, this is a neat implementation of an index and it should be faster than Roaring since you can skip the extra translation to the row-id that requires.
Druid uses Roaring - https://dl.acm.org/doi/10.1145/2938503.2938515
I'm still surprised there aren't more implementations out there, because it's a very useful class in application programming. For example, gameplay tags in unreal engine are queries in this class [0], and Intel ships a library using them for binary message parsing. It can also be done almost completely in SIMD, which is the route my shitty library takes. If you add recursion on top, you get queries that can express regular languages / monadic datalog.
My library quickly bottlenecked on memory bandwidth though. It doesn't seem like you're ordering joins by selectivity or a bitmap index to avoid reading unnecessary memory, so is this a direction you plan to explore more in the future?
[0] https://dev.epicgames.com/documentation/unreal-engine/using-...
Many years later while trying to figure out how we could best filter on our upstream proxies based on request and user requirements, and after having read a book of a fellow belgian about proc macros, did it come to me that this might actually work, and it did. That said, if you compare the first version of this lib vs what it is now it is still same in spirit but has gotten much better by now.
Thanks for the search term though :) Could you share your C++ library and the queries that hit the bandwidth limit? Your memory-bandwidth question got me to try this, and we just released the result in 0.7.1. VennDB already used bitmap indexes and could start from a selective filter. The change was to intersect dense indexes a block at a time, so if the first two filters empty a block, we can skip the remaining reads for it.
On an M4 Max with 8.4M rows, eight independent filters went from 184 to 158 µs. When the first two ruled out seven out of eight regions, it went from 183 to 78 µs. Those timings cover building the query through reading the first match. I’d be curious to see your C++ library. What did the queries look like when you hit the bandwidth limit?
Comments are loaded live from Hacker News and are not stored by Mid or Real.