cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Corentin Chary (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CASSANDRA-12915) SASI: Index intersection can be very inefficient
Date Tue, 06 Dec 2016 17:08:58 GMT

    [ https://issues.apache.org/jira/browse/CASSANDRA-12915?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15726079#comment-15726079
] 

Corentin Chary commented on CASSANDRA-12915:
--------------------------------------------

{code}
CREATE KEYSPACE test WITH replication = {'class': 'SimpleStrategy', 'replication_factor':
'1'}  AND durable_writes = true;

CREATE TABLE test.test (
    r text PRIMARY KEY,
    a text,
    b text,
    c text,
    data text
) WITH bloom_filter_fp_chance = 0.01
    AND caching = {'keys': 'ALL', 'rows_per_partition': 'NONE'}
    AND comment = ''
    AND compaction = {'class': 'org.apache.cassandra.db.compaction.SizeTieredCompactionStrategy',
'max_threshold': '32', 'min_threshold': '4'}
    AND compression = {'chunk_length_in_kb': '64', 'class': 'org.apache.cassandra.io.compress.LZ4Compressor'}
    AND crc_check_chance = 1.0
    AND dclocal_read_repair_chance = 0.1
    AND default_time_to_live = 0
    AND gc_grace_seconds = 864000
    AND max_index_interval = 2048
    AND memtable_flush_period_in_ms = 0
    AND min_index_interval = 128
    AND read_repair_chance = 0.0
    AND speculative_retry = '99PERCENTILE';
CREATE CUSTOM INDEX test_a_idx ON test.test (a) USING 'org.apache.cassandra.index.sasi.SASIIndex'
WITH OPTIONS = {'analyzer_class': 'org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer',
'case_sensitive': 'true'};
CREATE CUSTOM INDEX test_c_idx ON test.test (c) USING 'org.apache.cassandra.index.sasi.SASIIndex'
WITH OPTIONS = {'analyzer_class': 'org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer',
'case_sensitive': 'true'};
CREATE CUSTOM INDEX test_b_idx ON test.test (b) USING 'org.apache.cassandra.index.sasi.SASIIndex'
WITH OPTIONS = {'analyzer_class': 'org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer',
'case_sensitive': 'true'};
{code}

{code}
$ cat > generate.py
import sys
import random

def main(args):
    n = int(args[1])

    for i in xrange(n):
        a = '0'
        b = i % 10
        c = i % (n / 10) + random.randint(0, 10)
        print ("%d,%s,%d,%d,%d" % (i, a, b, c, i))

if __name__ == '__main__':
    main(sys.argv)
$ python generate.py 2000000 > test.csv
{code}


{code}
COPY test.test FROM 'test.csv'  WITH MAXBATCHSIZE = 100 AND MAXATTEMPTS = 10 AND MAXINSERTERRORS
= 999999;
SELECT * FROM test.test WHERE a = '0' AND c = '44859' ALLOW FILTERING;
{code}

3.X - with logs but without optimisations - 20ms (according to tracing)

{code}
TRACE [ReadStage-2] 2016-12-06 17:58:08,743 QueryPlan.java:60 - Analyzing org.apache.cassandra.config.CFMetaData@450c6f26[cfId=04e98180-bbb7-11e6-9680-cf420076f59b,ksName=test,cfName=test,flags=[COMPOUND],params=TableParams{comment=,
read_repair_chance=0.0, dclocal_read_repair_chance=0.1, bloom_filter_fp_chance=0.01, crc_check_chance=1.0,
gc_grace_seconds=864000, default_time_to_live=0, memtable_flush_period_in_ms=0, min_index_interval=128,
max_index_interval=2048, speculative_retry=99PERCENTILE, caching={'keys' : 'ALL', 'rows_per_partition'
: 'NONE'}, compaction=CompactionParams{class=org.apache.cassandra.db.compaction.SizeTieredCompactionStrategy,
options={max_threshold=32, min_threshold=4}}, compression=org.apache.cassandra.schema.CompressionParams@8f72cea3,
extensions={}, cdc=false},comparator=comparator(),partitionColumns=[[] | [a b c data]],partitionKeyColumns=[r],clusteringColumns=[],keyValidator=org.apache.cassandra.db.marshal.UTF8Type,columnMetadata=[a,
r, b, c, data],droppedColumns={},triggers=[],indexes=[org.apache.cassandra.schema.IndexMetadata@78b5523d[id=2e3c652f-e00c-3bd3-b2e9-90de1c170900,name=test_a_idx,kind=CUSTOM,options={analyzer_class=org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer,
case_sensitive=true, class_name=org.apache.cassandra.index.sasi.SASIIndex, target=a}], org.apache.cassandra.schema.IndexMetadata@4e4f20d2[id=6b00489b-7010-396e-9348-9f32f5167f88,name=test_b_idx,kind=CUSTOM,options={analyzer_class=org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer,
case_sensitive=true, class_name=org.apache.cassandra.index.sasi.SASIIndex, target=b}], org.apache.cassandra.schema.IndexMetadata@681c0362[id=45fcb286-b87a-3d18-a04b-b899a9880c91,name=test_c_idx,kind=CUSTOM,options={analyzer_class=org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer,
case_sensitive=true, class_name=org.apache.cassandra.index.sasi.SASIIndex, target=c}]]] [a
= 0, c = 44859]
TRACE [ReadStage-2] 2016-12-06 17:58:08,744 QueryController.java:289 - Expressions: [Expression{name:
c, op: EQ, lower: (44859, true), upper: (44859, true), exclusions: []}, Expression{name: a,
op: EQ, lower: (0, true), upper: (0, true), exclusions: []}], Op: AND
TRACE [ReadStage-2] 2016-12-06 17:58:08,745 QueryController.java:321 - Final view: {Expression{name:
a, op: EQ, lower: (0, true), upper: (0, true), exclusions: []}=[SSTableIndex(column: a, SSTable:
/home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-40-big), SSTableIndex(column:
a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-34-big),
SSTableIndex(column: a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-39-big)],
Expression{name: c, op: EQ, lower: (44859, true), upper: (44859, true), exclusions: []}=[SSTableIndex(column:
c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-39-big),
SSTableIndex(column: c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-40-big),
SSTableIndex(column: c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-34-big)]}
TRACE [ReadStage-2] 2016-12-06 17:58:08,745 QueryController.java:270 - Estimated row count
for Expression{name: a, op: EQ, lower: (0, true), upper: (0, true), exclusions: []}: 3
TRACE [ReadStage-2] 2016-12-06 17:58:08,745 QueryController.java:270 - Estimated row count
for Expression{name: c, op: EQ, lower: (44859, true), upper: (44859, true), exclusions: []}:
1559
TRACE [ReadStage-2] 2016-12-06 17:58:08,745 QueryController.java:157 - Searching (Expression{name:
c, op: EQ, lower: (44859, true), upper: (44859, true), exclusions: []},[SSTableIndex(column:
c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-39-big),
SSTableIndex(column: c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-40-big),
SSTableIndex(column: c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-34-big)])
TRACE [ReadStage-2] 2016-12-06 17:58:08,746 QueryController.java:161 - Found 13 tokens
TRACE [ReadStage-2] 2016-12-06 17:58:08,746 QueryController.java:177 - (Expression{name: c,
op: EQ, lower: (44859, true), upper: (44859, true), exclusions: []},[SSTableIndex(column:
c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-39-big),
SSTableIndex(column: c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-40-big),
SSTableIndex(column: c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-34-big)])
LIMIT 100 13
TRACE [ReadStage-2] 2016-12-06 17:58:08,746 QueryController.java:157 - Searching (Expression{name:
a, op: EQ, lower: (0, true), upper: (0, true), exclusions: []},[SSTableIndex(column: a, SSTable:
/home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-40-big), SSTableIndex(column:
a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-34-big),
SSTableIndex(column: a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-39-big)])
TRACE [ReadStage-2] 2016-12-06 17:58:08,747 QueryController.java:161 - Found 2000000 tokens
TRACE [ReadStage-2] 2016-12-06 17:58:08,747 QueryController.java:177 - (Expression{name: a,
op: EQ, lower: (0, true), upper: (0, true), exclusions: []},[SSTableIndex(column: a, SSTable:
/home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-40-big), SSTableIndex(column:
a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-34-big),
SSTableIndex(column: a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-39-big)])
LIMIT 100 2000000
TRACE [ReadStage-2] 2016-12-06 17:58:08,747 QueryController.java:201 - count: 13, ratio: 1.0,
threshold: 100
TRACE [ReadStage-2] 2016-12-06 17:58:08,747 QueryController.java:201 - count: 2000000, ratio:
6.5E-6, threshold: 100
TRACE [ReadStage-2] 2016-12-06 17:58:08,747 QueryPlan.java:65 - done
{code}

3.X - with logs and optimisations - 5ms (according to tracing)

We can see that it skips the search on other indexes as soon as it finds enough tokens. Even
without with optimisation it would have discarded the results from 'a' because it returns
way more
results than the filter on 'c'.

{code}
TRACE [ReadStage-2] 2016-12-06 17:39:13,280 QueryController.java:289 - Expressions: [Expression{name:
a, op: EQ, lower: (0, true), upper: (0, true), exclusions: []}, Expression{name: c, op: EQ,
lower: (44859, true), upper: (44859, true), exclusions: []}], Op: AND
TRACE [ReadStage-2] 2016-12-06 17:39:13,280 QueryController.java:321 - Final view: {Expression{name:
a, op: EQ, lower: (0, true), upper: (0, true), exclusions: []}=[SSTableIndex(column: a, SSTable:
/home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-34-big), SSTableIndex(column:
a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-40-big),
SSTableIndex(column: a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-39-big)],
Expression{name: c, op: EQ, lower: (44859, true), upper: (44859, true), exclusions: []}=[SSTableIndex(column:
c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-39-big),
SSTableIndex(column: c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-40-big),
SSTableIndex(column: c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-34-big)]}
TRACE [ReadStage-2] 2016-12-06 17:39:13,280 QueryController.java:270 - Estimated row count
for Expression{name: a, op: EQ, lower: (0, true), upper: (0, true), exclusions: []}: 3
TRACE [ReadStage-2] 2016-12-06 17:39:13,280 QueryController.java:270 - Estimated row count
for Expression{name: c, op: EQ, lower: (44859, true), upper: (44859, true), exclusions: []}:
1559
TRACE [ReadStage-2] 2016-12-06 17:39:13,280 QueryController.java:157 - Searching (Expression{name:
c, op: EQ, lower: (44859, true), upper: (44859, true), exclusions: []},[SSTableIndex(column:
c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-39-big),
SSTableIndex(column: c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-40-big),
SSTableIndex(column: c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-34-big)])
INFO  [ReadStage-2] 2016-12-06 17:39:13,280 TermIterator.java:51 - Search Concurrency Factor
is set to 1 for ReadStage-2
TRACE [ReadStage-2] 2016-12-06 17:39:13,281 QueryController.java:161 - Found 13 tokens
TRACE [ReadStage-2] 2016-12-06 17:39:13,281 QueryController.java:177 - (Expression{name: c,
op: EQ, lower: (44859, true), upper: (44859, true), exclusions: []},[SSTableIndex(column:
c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-39-big),
SSTableIndex(column: c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-40-big),
SSTableIndex(column: c, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-34-big)])
LIMIT 100 13
TRACE [ReadStage-2] 2016-12-06 17:39:13,281 QueryController.java:181 - We found less than
100 tokens. Stopping.
TRACE [ReadStage-2] 2016-12-06 17:39:13,281 QueryController.java:201 - count: 13, ratio: 1.0,
threshold: 100
{code}


That's a 4x improvement with 2M rows.

It gives even better results for the worst case:

{code}
SELECT * FROM test.test WHERE a = '0' AND c = '0' ALLOW FILTERING;
{code}

With the current code:
{code}
ReadTimeout: Error from server: code=1200 [Coordinator node timed out waiting for replica
nodes' responses] message="Operation timed out - received only 0 responses." info={'received_responses':
0, 'required_responses': 1, 'consistency': 'ONE'}
{code}

With the optimisations it takes only a few ms

{code}
TRACE [ReadStage-2] 2016-12-06 18:07:50,945 QueryPlan.java:60 - Analyzing org.apache.cassandra.config.CFMetaData@3b6bbdb0[cfId=04e98180-bbb7-11e6-9680-cf420076f59b,ksName=test,cfName=test,flags=[COMPOUND],params=TableParams{comment=,
read_repair_chance=0.0, dclocal_read_repair_chance=0.1, bloom_filter_fp_chance=0.01, crc_check_chance=1.0,
gc_grace_seconds=864000, default_time_to_live=0, memtable_flush_period_in_ms=0, min_index_interval=128,
max_index_interval=2048, speculative_retry=99PERCENTILE, caching={'keys' : 'ALL', 'rows_per_partition'
: 'NONE'}, compaction=CompactionParams{class=org.apache.cassandra.db.compaction.SizeTieredCompactionStrategy,
options={max_threshold=32, min_threshold=4}}, compression=org.apache.cassandra.schema.CompressionParams@8f72cea3,
extensions={}, cdc=false},comparator=comparator(),partitionColumns=[[] | [a b c data]],partitionKeyColumns=[r],clusteringColumns=[],keyValidator=org.apache.cassandra.db.marshal.UTF8Type,columnMetadata=[a,
r, b, c, data],droppedColumns={},triggers=[],indexes=[org.apache.cassandra.schema.IndexMetadata@33285244[id=2e3c652f-e00c-3bd3-b2e9-90de1c170900,name=test_a_idx,kind=CUSTOM,options={analyzer_class=org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer,
case_sensitive=true, class_name=org.apache.cassandra.index.sasi.SASIIndex, target=a}], org.apache.cassandra.schema.IndexMetadata@4003dd6d[id=6b00489b-7010-396e-9348-9f32f5167f88,name=test_b_idx,kind=CUSTOM,options={analyzer_class=org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer,
case_sensitive=true, class_name=org.apache.cassandra.index.sasi.SASIIndex, target=b}], org.apache.cassandra.schema.IndexMetadata@26e37ee0[id=45fcb286-b87a-3d18-a04b-b899a9880c91,name=test_c_idx,kind=CUSTOM,options={analyzer_class=org.apache.cassandra.index.sasi.analyzer.NonTokenizingAnalyzer,
case_sensitive=true, class_name=org.apache.cassandra.index.sasi.SASIIndex, target=c}]]] [a
= 0, c = 0]
TRACE [ReadStage-2] 2016-12-06 18:07:50,946 QueryController.java:289 - Expressions: [Expression{name:
c, op: EQ, lower: (0, true), upper: (0, true), exclusions: []}, Expression{name: a, op: EQ,
lower: (0, true), upper: (0, true), exclusions: []}], Op: AND
TRACE [ReadStage-2] 2016-12-06 18:07:50,946 QueryController.java:321 - Final view: {Expression{name:
c, op: EQ, lower: (0, true), upper: (0, true), exclusions: []}=[], Expression{name: a, op:
EQ, lower: (0, true), upper: (0, true), exclusions: []}=[SSTableIndex(column: a, SSTable:
/home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-40-big), SSTableIndex(column:
a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-34-big),
SSTableIndex(column: a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-39-big)]}
TRACE [ReadStage-2] 2016-12-06 18:07:50,946 QueryController.java:270 - Estimated row count
for Expression{name: c, op: EQ, lower: (0, true), upper: (0, true), exclusions: []}: 0
TRACE [ReadStage-2] 2016-12-06 18:07:50,947 QueryController.java:270 - Estimated row count
for Expression{name: a, op: EQ, lower: (0, true), upper: (0, true), exclusions: []}: 3
TRACE [ReadStage-2] 2016-12-06 18:07:50,947 QueryController.java:157 - Searching (Expression{name:
a, op: EQ, lower: (0, true), upper: (0, true), exclusions: []},[SSTableIndex(column: a, SSTable:
/home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-40-big), SSTableIndex(column:
a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-34-big),
SSTableIndex(column: a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-39-big)])
TRACE [ReadStage-2] 2016-12-06 18:07:50,947 QueryController.java:161 - Found 2000000 tokens
TRACE [ReadStage-2] 2016-12-06 18:07:50,947 QueryController.java:177 - (Expression{name: a,
op: EQ, lower: (0, true), upper: (0, true), exclusions: []},[SSTableIndex(column: a, SSTable:
/home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-40-big), SSTableIndex(column:
a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-34-big),
SSTableIndex(column: a, SSTable: /home/iksaif/dev/data/data/test/test-04e98180bbb711e69680cf420076f59b/mc-39-big)])
LIMIT 100 2000000
TRACE [ReadStage-2] 2016-12-06 18:07:50,947 QueryController.java:157 - Searching (Expression{name:
c, op: EQ, lower: (0, true), upper: (0, true), exclusions: []},[])
TRACE [ReadStage-2] 2016-12-06 18:07:50,947 QueryController.java:161 - Found 0 tokens
TRACE [ReadStage-2] 2016-12-06 18:07:50,947 QueryController.java:201 - count: 2000000, ratio:
0.0, threshold: 100
TRACE [ReadStage-2] 2016-12-06 18:07:50,947 QueryController.java:204 - Skipping
TRACE [ReadStage-2] 2016-12-06 18:07:50,947 QueryPlan.java:65 - done
{code}

I can try to run it with more rows if necessary. Didn't get the time to write unit tests today,
hopefully tomorrow.


> SASI: Index intersection can be very inefficient
> ------------------------------------------------
>
>                 Key: CASSANDRA-12915
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-12915
>             Project: Cassandra
>          Issue Type: Improvement
>          Components: sasi
>            Reporter: Corentin Chary
>             Fix For: 3.x
>
>
> It looks like RangeIntersectionIterator.java and be pretty inefficient in some cases.
Let's take the following query:
> SELECT data FROM table WHERE index1 = 'foo' AND index2 = 'bar';
> In this case:
> * index1 = 'foo' will match 2 items
> * index2 = 'bar' will match ~300k items
> On my setup, the query will take ~1 sec, most of the time being spent in disk.TokenTree.getTokenAt().
> if I patch RangeIntersectionIterator so that it doesn't try to do the intersection (and
effectively only use 'index1') the query will run in a few tenth of milliseconds.
> I see multiple solutions for that:
> * Add a static thresold to avoid the use of the index for the intersection when we know
it will be slow. Probably when the range size factor is very small and the range size is big.
> * CASSANDRA-10765



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message