[
https://issues.apache.org/jira/browse/CASSANDRA-12915?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15898877#comment-15898877
]
Alex Petrov commented on CASSANDRA-12915:
-----------------------------------------
Sure, what I'm saying is that behaviour is unnecessary to fix the problem that
we have. SASI Range iterators are taking the shortest range.
For example, if we have records like
|| a || b || c ||
| 1 | 1 | 1 |
| 2 | 2 | 1 |
| 3 | 3 | 1 |
And {{b}} and {{c}} are SASI-indexed, and we want to run the query {{WHERE b =
2 AND c = 1}}, we will get 2 iterators, one with {{2}} (for the column {{b}})
and the second one with {{1,2,3}} (for the column {{c}}). Now, SASI will take
the shortest range ({{b}}) and start iterating by "rewinding" the {{c}}
iterator to the token {{2}}. If there's no item for the token, intersection
will be empty.
Now, moving closer to the problem. If we had just imbalanced iterators (one
returning 100 results and the other just 1), SASI would be able to efficiently
intersect ranges and hit the storage to retrieve just a single row. In the case
with __empty__ results from one of the iterators, the one you're fixing, we
were simply using a single iterator, and had to hit the storage a 100 times
(assuming the other iterator returns 100 results). Now, with what I propose, we
will hit is 0 times. Same with your approach, although with a lot of complex
logic that I can not justify, so I have asked you to clarify. The trick was
simply to "replace" that [null
check|https://github.com/ifesdjeen/cassandra/commit/78b1ff630536b0f48787ced74a66d702d13637ba#diff-25d7f486e2818c56d6b01aa952d459f3L146]
with an actual iterator, to let the intersection know there's a second part,
and it's empty. I thought it was already discussed in [this
comment|https://issues.apache.org/jira/browse/CASSANDRA-12915?focusedCommentId=15728412&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-15728412]
but I'm happy to re-iterate:
bq. The way RangeIterator work and how it's optimised, we're
[picking|https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/index/sasi/utils/RangeIntersectionIterator.java#L234-L237]
the "shortest" token tree and start skipping the second token tree based on
the results retrieved from the first one. So one of the indexes will be
iterated anyways. The second index (since it's larger) might have to
fetch/load roughly 10 blocks (since they might be located far from one another
on disk), but it never has to fetch all 2M items. It'll iterate only as many
items as the smallest index has. For example, two index queries would skip
through (left is which index is used, right is index of the item within the
token tree):
and
bq. Moreover, RangeIterator already has [different optimisation
strategies|https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/index/sasi/utils/RangeIntersectionIterator.java#L76-L78]
based on differences in cardinality. I'd say that current benchmark shows that
the query is slightly slower (since we have to go through around twice as much
data on disk). But given the numbers at hand the difference that is small and
it's sub-millisecond, this optimisation seems not to pay the complexity that it
brings.
That's one of the ideas behind SASI, pretty much: to be able to efficiently
merge, iterate and skip iterators.
Looks like we're mostly on the same page. I've ran large-scale tests with a
variant of the patch I've posted (160+GB of data), and it works exactly as
expected. Now, I want to simplify the patch and make sure we do not add the
code we do not need.
So there's no need to add additional logic to hide empty ranges, it's already
handled.
> SASI: Index intersection with an empty range really inefficient
> ---------------------------------------------------------------
>
> Key: CASSANDRA-12915
> URL: https://issues.apache.org/jira/browse/CASSANDRA-12915
> Project: Cassandra
> Issue Type: Improvement
> Components: sasi
> Reporter: Corentin Chary
> Assignee: Corentin Chary
> Fix For: 3.11.x, 4.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.15#6346)
