cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Stu Hood (JIRA)" <>
Subject [jira] Updated: (CASSANDRA-1472) Add bitmap secondary indexes
Date Fri, 17 Sep 2010 23:22:33 GMT


Stu Hood updated CASSANDRA-1472:

    Attachment: 1472-v3.tgz

Attaching a third version of the patch. Since the last revision:
* 0001 through 0009 were updated to fix bugs, but didn't experience any significant changes
* Integrated KEYS_BITMAP indexes into ColumnFamilyStore.scan (*0012*, *0013*)
** Added abstract db.secindex.SecondaryIndex, with KeysIndex and KeysBitmapIndex subclasses
*** SecondaryIndex.certainty(expression) returns false if the index can return false positives
*** SecondaryIndex.iterator(bounds, expression) iterates keys matching the index
** KeysBitmapIndex implements the probable key iteration by merging the results from the sstable
bitmap indexes with the results of a brute-force filtering of all memtables (see TODOs)
* Indexes larger than memory are supported (*0010*)
** Bitmap indexes are recreated during usage of SSTableWriter (no change there)
** The 'io.sstable.bitidx.ScratchStack' object implements merging for bitidxs which is very
similar to SSTable compaction, but it occurs synchronously while the SSTableWriter is in use:
### A segment of the index is built in memory, flushed to disk, and added to a stack
### When enough segments of the same size exist, the stack merges them
** Although IO is still mostly sequential, SSTable write performance drops by about 25% per
index added. Haven't looked into bottlenecks here.


TODOs, in order of importance:
* Integrate rebuilding bitidxs into SSTable recovery
* Replace Memtable brute-force filtering with an in-memory index attached to the Memtable
* Improve bin selection


I think this is probably ready for review if anyone has time: incorporating KEYS_BITMAP indexes
into SSTable recovery is probably the last blocker.

> Add bitmap secondary indexes
> ----------------------------
>                 Key: CASSANDRA-1472
>                 URL:
>             Project: Cassandra
>          Issue Type: Improvement
>          Components: Core
>            Reporter: Stu Hood
>             Fix For: 0.7.0
>         Attachments: 1472-v3.tgz
> Bitmap indexes are a very efficient structure for dealing with immutable data. We can
take advantage of the fact that SSTables are immutable by attaching them directly to SSTables
as a new component (supported by CASSANDRA-1471).

This message is automatically generated by JIRA.
You can reply to this email to add a comment to the issue online.

View raw message