You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by "Corentin Chary (JIRA)" <ji...@apache.org> on 2016/11/24 16:08:58 UTC
[jira] [Comment Edited] (CASSANDRA-12915) SASI: Index intersection
can be very inefficient
[ https://issues.apache.org/jira/browse/CASSANDRA-12915?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15693630#comment-15693630 ]
Corentin Chary edited comment on CASSANDRA-12915 at 11/24/16 4:08 PM:
----------------------------------------------------------------------
Updated the patch on https://github.com/apache/cassandra/pull/85
I still haven't restored the behavior for the primary that filters on min/max rather than e. I'll do that once we agree more on what to do.
This version uses the blockCount to guess the cardinality. It doesn't work well because it depends a lot of the value, but it is better than nothing (no regressions). Having the real count/estimate would make it perform way better.
This version already saves one search that would have generated ~1M results and two iterations on this set of 1M results.
Example query:
{code}
SELECT name, parent, component_2 from biggraphite_metadata.metrics WHERE component_3 = '__END__' AND parent LIKE 'criteo.%' AND component_0 = 'criteo' LIMIT 500 ALLOW FILTERING;
{code}
Example log:
TRACE [ReadStage-2] 2016-11-24 16:55:50,190 QueryController.java:284 - Expressions: [Expression{name: component_0, op: EQ, lower: (criteo, true), upper: (criteo, true), exclusions: []}, Expression{name: parent, op: PREFIX, lower: (criteo, true), upper: (criteo, true), exclusions: []}, Expression{name: component_3, op: EQ, lower: (__END__, true), upper: (__END__, true), exclusions: []}], Op: AND
TRACE [ReadStage-2] 2016-11-24 16:55:50,190 QueryController.java:301 - Final view: {Expression{name: component_3, op: EQ, lower: (__END__, true), upper: (__END__, true), exclusions: []}=[SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big)], Expression{name: parent, op: PREFIX, lower: (criteo, true), upper: (criteo, true), exclusions: []}=[SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big)], Expression{name: component_0, op: EQ, lower: (criteo, true), upper: (criteo, true), exclusions: []}=[SSTableIndex(column: component_0, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big), SSTableIndex(column: component_0, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: component_0, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: component_0, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big), SSTableIndex(column: component_0, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big)]}
TRACE [ReadStage-2] 2016-11-24 16:55:50,190 QueryController.java:268 - Estimated row count for Expression{name: component_3, op: EQ, lower: (__END__, true), upper: (__END__, true), exclusions: []}: 5
TRACE [ReadStage-2] 2016-11-24 16:55:50,190 QueryController.java:268 - Estimated row count for Expression{name: parent, op: PREFIX, lower: (criteo, true), upper: (criteo, true), exclusions: []}: 19
TRACE [ReadStage-2] 2016-11-24 16:55:50,190 QueryController.java:268 - Estimated row count for Expression{name: component_0, op: EQ, lower: (criteo, true), upper: (criteo, true), exclusions: []}: 0
TRACE [ReadStage-2] 2016-11-24 16:55:50,190 QueryController.java:156 - Searching (Expression{name: parent, op: PREFIX, lower: (criteo, true), upper: (criteo, true), exclusions: []},[SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big)])
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:160 - Found 622248 tokens
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:176 - (Expression{name: parent, op: PREFIX, lower: (criteo, true), upper: (criteo, true), exclusions: []},[SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big)]) LIMIT 500 622248
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:156 - Searching (Expression{name: component_3, op: EQ, lower: (__END__, true), upper: (__END__, true), exclusions: []},[SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big)])
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:160 - Found 225 tokens
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:176 - (Expression{name: component_3, op: EQ, lower: (__END__, true), upper: (__END__, true), exclusions: []},[SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big)]) LIMIT 500 225
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:179 - We found less than 500 tokens. Stopping.
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:199 - count: 622248, ratio: 3.6159216E-4, threshold: 500
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:202 - Skipping
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:199 - count: 225, ratio: 1.0, threshold: 500
was (Author: iksaif):
Updated the patch on https://github.com/apache/cassandra/pull/85
I still haven't restored the behavior for the primary that filters on min/max rather than e. I'll do that once we agree more on what to do.
This version uses the blockCount to guess the cardinality. It doesn't work well because it depends a lot of the value, but it is better than nothing (no regressions). Having the real count/estimate would make it perform way better.
This version already saves one search that would have generated ~1M results and two iterations on this set of 1M results.
Example query:
SELECT name, parent, component_2 from biggraphite_metadata.metrics WHERE component_3 = '__END__' AND parent LIKE 'criteo.%' AND component_0 = 'criteo' LIMIT 500 ALLOW FILTERING;
Example log:
TRACE [ReadStage-2] 2016-11-24 16:55:50,190 QueryController.java:284 - Expressions: [Expression{name: component_0, op: EQ, lower: (criteo, true), upper: (criteo, true), exclusions: []}, Expression{name: parent, op: PREFIX, lower: (criteo, true), upper: (criteo, true), exclusions: []}, Expression{name: component_3, op: EQ, lower: (__END__, true), upper: (__END__, true), exclusions: []}], Op: AND
TRACE [ReadStage-2] 2016-11-24 16:55:50,190 QueryController.java:301 - Final view: {Expression{name: component_3, op: EQ, lower: (__END__, true), upper: (__END__, true), exclusions: []}=[SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big)], Expression{name: parent, op: PREFIX, lower: (criteo, true), upper: (criteo, true), exclusions: []}=[SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big)], Expression{name: component_0, op: EQ, lower: (criteo, true), upper: (criteo, true), exclusions: []}=[SSTableIndex(column: component_0, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big), SSTableIndex(column: component_0, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: component_0, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: component_0, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big), SSTableIndex(column: component_0, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big)]}
TRACE [ReadStage-2] 2016-11-24 16:55:50,190 QueryController.java:268 - Estimated row count for Expression{name: component_3, op: EQ, lower: (__END__, true), upper: (__END__, true), exclusions: []}: 5
TRACE [ReadStage-2] 2016-11-24 16:55:50,190 QueryController.java:268 - Estimated row count for Expression{name: parent, op: PREFIX, lower: (criteo, true), upper: (criteo, true), exclusions: []}: 19
TRACE [ReadStage-2] 2016-11-24 16:55:50,190 QueryController.java:268 - Estimated row count for Expression{name: component_0, op: EQ, lower: (criteo, true), upper: (criteo, true), exclusions: []}: 0
TRACE [ReadStage-2] 2016-11-24 16:55:50,190 QueryController.java:156 - Searching (Expression{name: parent, op: PREFIX, lower: (criteo, true), upper: (criteo, true), exclusions: []},[SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big)])
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:160 - Found 622248 tokens
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:176 - (Expression{name: parent, op: PREFIX, lower: (criteo, true), upper: (criteo, true), exclusions: []},[SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big), SSTableIndex(column: parent, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big)]) LIMIT 500 622248
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:156 - Searching (Expression{name: component_3, op: EQ, lower: (__END__, true), upper: (__END__, true), exclusions: []},[SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big)])
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:160 - Found 225 tokens
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:176 - (Expression{name: component_3, op: EQ, lower: (__END__, true), upper: (__END__, true), exclusions: []},[SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-46-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-44-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-32-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-45-big), SSTableIndex(column: component_3, SSTable: /home/cchary/dev/cassandra/data/data/biggraphite_metadata/metrics-bc4c0170afe811e6b283ef585b20e369/mc-47-big)]) LIMIT 500 225
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:179 - We found less than 500 tokens. Stopping.
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:199 - count: 622248, ratio: 3.6159216E-4, threshold: 500
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:202 - Skipping
TRACE [ReadStage-2] 2016-11-24 16:55:50,272 QueryController.java:199 - count: 225, ratio: 1.0, threshold: 500
> 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)