cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Alex Liu (JIRA)" <>
Subject [jira] [Commented] (CASSANDRA-6048) Add the ability to use multiple indexes in a single query
Date Fri, 18 Oct 2013 18:10:47 GMT


Alex Liu commented on CASSANDRA-6048:

A good summary of different index scans in PostgresSQL.

h4. Index scan vs Bitmap Index Scan vs Merge join

h5. Index Scan 
reads the index in alternation, bouncing between table and index, row at a time. 
    Performance gain when reading a few rows from a big table. It goes to the index, finds
the rows
    Only method of accessing a table the can return rows in sorted order - useful in combination
with LIMIT.
    Disadvantage: Causes random I/O against the base table. Read a row from the index, then
a row from the table, and so on.

h5. Bitmap Index Scan 
    scans all index rows before examining base table.
    Can efficiently combine data from multiple indeces. the TID bitmap can handle boolean
ANDs and ORs.
    Handles LIMIT poorly.
    Adjust page cost parameters to use Index scans vs Bitamp scans on queries where it makes
    SMALL INDEXES ARE BETTER. Less columns are better. Avoid multicolumn indexes.

h5. Merge join
Puts both input relations in sorted order (sort or index scan), and match up on equal values
by scanning through the two in parallel.
Only way to handle really big datasets, however merge joins are slower.

My approach is combing Index scan and merge join of indexes which handle limit clause better
and keep the order.
We can use Bitmap Index Scan for none-limit clause query and result sets are not in order.

> Add the ability to use multiple indexes in a single query
> ---------------------------------------------------------
>                 Key: CASSANDRA-6048
>                 URL:
>             Project: Cassandra
>          Issue Type: New Feature
>          Components: Core
>            Reporter: Alex Liu
>            Assignee: Alex Liu
>             Fix For: 2.1
>         Attachments: 6048-1.2-branch.txt, 6048-trunk.txt
> Existing data filtering uses the following algorithm
> {code}
>    1. find best selective predicate based on the smallest mean columns count
>    2. fetch rows for the best selective predicate predicate, then filter the data based
on other predicates left.
> {code}
> So potentially we could improve the performance by
> {code}
>    1.  joining multiple predicates then do the data filtering for other predicates.
>    2.  fine tune the best predicate selection algorithm
> {code}
> For multiple predicate join, it could improve performance if one predicate has many entries
and another predicate has a very few of entries. It means a few index CF read, join the row
keys, fetch rows then filter other predicates
> Another approach is to have index on multiple columns.

This message was sent by Atlassian JIRA

View raw message