Earlier quoted context omitted.
Isn’t Lucene already a household name?
Not sure I understand your point. Can you clarify some?
Lucene uses roaring bitmaps for filters.
Bitmap Indexes in Go: Search Speed (2019)
31–40 of 40 posts
Re: Bitmap Indexes in Go: Search Speed (2019)
#32Earlier quoted context omitted.
Isn’t Lucene already a household name?
Lucene is fast, but probably can't handle analytical type questions on massive amounts of data as fast as a pure binary index can. I could be wrong about that though. I do know Solr has it because Lucene does...
Elasticsearch (another household name) is built on Lucene too, so I wouldn’t count it out.
Re: Bitmap Indexes in Go: Search Speed (2019)
#33Earlier quoted context omitted.
Not sure I understand your point. Can you clarify some?
Lucene uses roaring bitmaps for filters.
Sure, I completely get it. However, does that mean bitmaps have been fully explored? For example, OLAP is only growing as a market as the need for realtime analysis on the most fresh data. I mean, we never going to have 'less' data nor are we ever going to seek results 'slower'. Where I am going with this, utilizing technologies like bitmaps in OLAP services is an area I believe will see continued growth. While Lucene is a known commodity, I think we can agree it hasn't solved the sector, right?
Re: Bitmap Indexes in Go: Search Speed (2019)
#34Earlier quoted context omitted.
This is neat! Curious what type of use case you use ducks for most often? Also...what tradeoffs are keeping you from implementing bitmaps in ducks?
As far as the bitmaps holdup, well. Let's see. The slowest step in ducks right now is combining the results of a multi-index query. Suppose I get 1000 objects matching one attribute and another 1000 objects from another, I've now got to intersect those two sets. Right now I'm using sets, or in some cases, sorted lists that act as sets [1]. But intuitively, a bitwise "and" ought to be faster, due to SIMD etc. It's rea…
> Suppose I get 1000 objects matching one attribute and another 1000 objects from another, I've now got to intersect those two sets. Right now I'm using sets, or in some cases, sorted lists that act as sets [1]. But intuitively, a bitwise "and" ought to be faster, due to SIMD etc.
I worked on this exact problem today.
This is probably super obvious and I bet you're already doing something similar (or smarter still), but I'm excited about it so I'm telling you anyway.
I was doing the naive O(m log n) algorithm where you fetch one set of items and then test them each against the other index one by one (both implemented as B-trees).
I got an enormous speedup[1] after I realized that you can get a discount on index look-ups by testing a sorted list of multiple items in the same tree traversal operation. Not only does each item tested allow you to reduce the search scope, you can often omit repeating several of the calculations closer to the root.
[1] Eventually 10x, but that's in part due to naively parallelizing the workload. The single threaded approach was still something like 4-5x compared to the original approach. 20k ops/s for thousands of items tested against a 800 Mb index.
Re: Bitmap Indexes in Go: Search Speed (2019)
#35I'm not sure I follow what it is they're benchmarking (although I struggle reading text that has too many images so I may be confused as to what they're even doing). I'd expect the bottleneck in a database index to be your disk or RAM access patterns. It seems very counterintuitive to see a real-world speed-up from SIMD if that is the case. The fact that they're seeing one in the benchmark would suggest maybe the ben…
They're benchmarking the bitmap operations like AND,OR etc. These operations benefit a lot from vectorization.
Re: Bitmap Indexes in Go: Search Speed (2019)
#36Re: Bitmap Indexes in Go: Search Speed (2019)
#37A bit off-topic but is there some website/directory where I can learn about modern data structures or unknown/less popular data structures?
Excellent question, although it can be interpreted a few ways. I'm by no means an expert, but here are a couple that I've taken a look at -- if you have more detail around whether you're thinking about storage structures (i.e. LSM trees vs. B-trees) or actual data types (string, int, etc), let me know and I'm happy to share more: https://medium.com/@shivendrasingh410/modern-data-structures... and https://www.interviewcake.com/data-structures-reference
Re: Bitmap Indexes in Go: Search Speed (2019)
#38Earlier quoted context omitted.
As northern Portuguese I beg to differ. :)
Ha! Now i gotta know your favorite northern Portuguese recipes/dishes/restaurants, et al.
You can start with Ensopado de Borrego, slowly cooked in black pots like in the Beiras regions, or to stay with fish, Bacalhau à Minhota, from the Minho region.
Re: Bitmap Indexes in Go: Search Speed (2019)
#39Lucene (and therefore Elasticsearch and Solar) uses bitmaps for its filter cache.
https://www.elastic.co/blog/frame-of-reference-and-roaring-b...
ClickHouse has some bitmap functions as well though not for indices.
https://clickhouse.com/docs/en/sql-reference/functions/bitma...
I don't think they're unknown to most db developers, just not the best fit for a common query loads. You can scan through a bitmap really fast yes, but you can also read a list of document IDs from a BTree very quickly for any specific value.
Would like to see some benchmarks of this database for comparison.
Re: Bitmap Indexes in Go: Search Speed (2019)
#40Earlier quoted context omitted.
As far as the bitmaps holdup, well. Let's see. The slowest step in ducks right now is combining the results of a multi-index query. Suppose I get 1000 objects matching one attribute and another 1000 objects from another, I've now got to intersect those two sets. Right now I'm using sets, or in some cases, sorted lists that act as sets [1]. But intuitively, a bitwise "and" ought to be faster, due to SIMD etc. It's rea…
> Suppose I get 1000 objects matching one attribute and another 1000 objects from another, I've now got to intersect those two sets. Right now I'm using sets, or in some cases, sorted lists that act as sets [1]. But intuitively, a bitwise "and" ought to be faster, due to SIMD etc. I worked on this exact problem today. This is probably super obvious and I bet you're already doing something similar (or smarter still),…
Wow, congrats on the speedup! Breakthroughs like that feel really good.