Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bitmap Indexes in Go: Search Speed (2019)

habr.com

Post reply on HN
Print view View original

21–30 of 40 posts

Re: Bitmap Indexes in Go: Search Speed (2019)

#21

Post by todd8 »

This is an interesting article, and I'll probably take a look at the go language profiling capabilities and built-in machine independent assembler.

The idea of using bitmaps for retrieval on multiple indexes isn't new. Not surprisingly Knuth has a good discussion of the technique [Knuth], it was explained very well with a nice illustration of using notched recipe cards that is worth taking a peek at.

-- straying off topic below this line --

One surprising note, Calvin N. Mooers invented zatocoding in 1947. This technique used the notched cards for information retrieval and cited by Knuth under the subsection superimposed coding. Calvin N. Mooers went on to invent the "Reactive Typewriter" in the 1960s. This was an visionary implementation of how users might interact with computers using a terminal device (like a teletype). Mooers' Reactive Typewriter was programmed using a language he invented named TRAC.

TRAC is a macro based language. It, like the roughly contemporaneous GPM of Christopher Strachey (1965), is a Turing complete language based on macros that can define other macros, etc. I learned about TRAC in the mid 1970s from Ted Nelson's book Computer Lib/Dream Machines [Nelson]. It was one of three languages featured in that book. A fun little book, Etudes for Programmers, which I bought in 1978 inspired me to implement a version of TRAC. It's a nice exercise.

Many years later (I believe it was 1991), during an Open Software Foundation meeting in Cambridge, Massachusetts, I got to meet Mooers in person, he was sitting in the front row during a presentation, and I got to speak with him briefly afterwards.

By the way, Christopher Strachey wrote the first paper on the concept of time-sharing in 1959 and in the 1970's with Dana Scott is credited with coming up with the important development in the theory of programming languages known as Denotational Semantics.

[Knuth] Donald Knuth. (1973).The Art of Computer Programming, Vol 3/Sorting and Searching. Section 6.5, Retrieval on Secondary Keys. Addison-Wesley.

[Nelson] Theodor H Nelson. (1974). Computer lib : you can and must understand computers now. ISBN 0893470023. OCLC 11182412. https://en.wikipedia.org/wiki/Computer_Lib/Dream_Machines

[Strachey] https://en.wikipedia.org/wiki/Christopher_Strachey#cite_note...

[Wetherell] Charles Wetherell, Etudes for Programmers, Prentice Hall, 1977, https://www.amazon.com/Etudes-Programmers-Charles-Wetherell/...

Re: Bitmap Indexes in Go: Search Speed (2019)

#22

Post by maycotte »

todd8 wrote: post #21

This is an interesting article, and I'll probably take a look at the go language profiling capabilities and built-in machine independent assembler. The idea of using bitmaps for retrieval on multiple indexes isn't new. Not surprisingly Knuth has a good discussion of the technique [Knuth], it was explained very well with a nice illustration of using notched recipe cards that is worth taking a peek at. -- straying off…

Love that! Early categorical/bitmap storage using notches...punched or not punched!

Re: Bitmap Indexes in Go: Search Speed (2019)

#23

Post by kordlessagain »

eurasiantiger wrote: post #12
JAA1337 wrote: post #8

Earlier quoted context omitted.

I think it's fair to say that the use cases for bitmaps have not yet been fully explored. I believe their use in areas of analytics and OLAP/RTOLAP will continue to grow as the desire to infer and target demo's across households increases.

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

Re: Bitmap Indexes in Go: Search Speed (2019)

#24

Post by skingkong »

manimino wrote: post #15

Writing an object indexer is a fun project. My Python indexer, ducks [1], went through a lot of the same development stages, such as supporting only exact-value matches at first. I tried binning too, but ultimately using a BTree was simpler and performed well enough (500ns for a log-n tree traversal, vs 50ns hash). Still looking for a way to apply bitmap indexing in ducks; it would surely speed up multi-index queries…

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?

Re: Bitmap Indexes in Go: Search Speed (2019)

#26

Post by JAA1337 »

mrjn wrote: post #25

Wonder how this compares to Sroar [1] [1]: https://dgraph.io/blog/post/serialized-roaring-bitmaps-golan...

Thank you for sharing this. As someone who is working to learn more about bitmaps, id like to ask how you came across this? Is there a specific community or other that you follow? Thanks!

Re: Bitmap Indexes in Go: Search Speed (2019)

#27

Post by manimino »

skingkong wrote: post #24
manimino wrote: post #15

Writing an object indexer is a fun project. My Python indexer, ducks [1], went through a lot of the same development stages, such as supporting only exact-value matches at first. I tried binning too, but ultimately using a BTree was simpler and performed well enough (500ns for a log-n tree traversal, vs 50ns hash). Still looking for a way to apply bitmap indexing in ducks; it would surely speed up multi-index queries…

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?

Ducks, the story:

I was using Python in-memory vector search engine called Annoy [1] to do semantic search on various kinds of data. It worked great for finding "similar" objects. Story A has similar text to story B, image A looks like image B, etc.

So Annoy solved the hard part. But doing basic metadata lookups was surprisingly hard in Python. How do I get all images matching some criteria (say, size range, or tags)? I'd have to serialize them all into a DB, and use a DB index. Databases are great, but they add code bloat and overhead; I'm usually working Jupyter notebooks and I like keeping as few external dependencies as possible.

So I wrote ducks as a quick, convenient way to index anything.

There's lots of other usage patterns of course, it's very generic. It makes a great Wordle / crossword solver too. "Find me words where the first letter is A and the fifth letter is L" is very fast in ducks.

Indexing is just one of those things you always need. Python didn't have a good way to do it, and now it does!

Source code's here if you're curious: https://github.com/manimino/ducks

[1] Annoy: https://github.com/spotify/annoy

Re: Bitmap Indexes in Go: Search Speed (2019)

#28

Post by manimino »

skingkong wrote: post #24
manimino wrote: post #15

Writing an object indexer is a fun project. My Python indexer, ducks [1], went through a lot of the same development stages, such as supporting only exact-value matches at first. I tried binning too, but ultimately using a BTree was simpler and performed well enough (500ns for a log-n tree traversal, vs 50ns hash). Still looking for a way to apply bitmap indexing in ducks; it would surely speed up multi-index queries…

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 really just a matter of thinking about how to write it. This video was quite helpful as it mentioned that Postgres uses a similar approach, so probably I'll have a look at their implementation first and take inspiration from there.

[1] https://ducks.readthedocs.io/en/latest/how_it_works.html#sor...

Re: Bitmap Indexes in Go: Search Speed (2019)

#30

Post by skingkong »

manimino wrote: post #27
skingkong wrote: post #24

Earlier 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?

Ducks, the story: I was using Python in-memory vector search engine called Annoy [1] to do semantic search on various kinds of data. It worked great for finding "similar" objects. Story A has similar text to story B, image A looks like image B, etc. So Annoy solved the hard part. But doing basic metadata lookups was surprisingly hard in Python. How do I get all images matching some criteria (say, size range, or tags)…

Huh, that's really cool and makes a lot of sense. Thanks for sharing more about it
Post reply on HN