RoaringBitmap / RoaringBitmap/CRoaring

Implement Bit-sliced index for CRoaring

Open
#435 7 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C
Stars
1.9k
Forks
334
Avg merge
2d 5h
Merged PRs (30d)
17

Description

There are implements for bit slice index in java and go. Do we need in C/C++?

I think implementing Bit-sliced index for CRoaring include these tasks:

  • support mutable Bit-sliced index in C
  • support RangeBitmap in C
  • A range Index demo for postgres using RangeBitmap in C
  • A mutable bit-sliced index demo for postgres using bit-sliced index in C
  • A range index demo for Apache Parequet file-format in C/C++
  • A mutable bit-sliced index demo for Apache Parequet file-format using Bit-sliced index in C

@lemire we've implemented mutable Bit-sliced index in C and using it for postgres. Due to there are two implements for bit-sliced index, (BSI and RangeBitmap), one is mutable but the performance is poor, the other is immutable ,but the performance is great. Could we make a decision or re-design it ?

cc @ richardstartin

refer to :

  1. https://richardstartin.github.io/posts/range-bitmap-index
  2. https://richardstartin.github.io/posts/range-predicates
  3. https://github.com/RoaringBitmap/RoaringBitmap/tree/master/bsi
  4. https://github.com/lemire/BitSliceIndex/issues/1

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by comparing the existing Java and Go bit-sliced index implementations with the C BSI and RangeBitmap approaches mentioned in the issue. Resolve whether to redesign or choose one approach, then define the scope for mutable indexing and the PostgreSQL and Apache Parquet demos. Done means the selected design and requested integrations are implemented.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, cpp, postgresql
Domain
databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.