You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@cassandra.apache.org by Shaun Cutts <sh...@cuttshome.net> on 2011/02/05 17:48:19 UTC
order of index expressions
Hello,
I'm wondering if cassandra is sensitive to the order of index expressions in (pycassa call) get_indexed_slices?
If I have several column indexes available, will it attempt to optimize the order?
Thanks,
-- Shaun
Re: order of index expressions
Posted by Shaun Cutts <sh...@cuttshome.net>.
Jonathan,
Thanks for your thoughts....
> On Sun, Feb 6, 2011 at 11:03 AM, Shaun Cutts <sh...@cuttshome.net> wrote:
>> What I think you should be doing is the following: open iterators on the matching keys for each of the indexes; the inside loop would pick an iterator at random, and pull a match from it. This would assure that the expected number of entries examined is a small multiple (# of other indexes) of the index with the most "precision".
>
> Isn't this a bad approximation of performing an intersection by
> iterating through each index results (which, since they return in
> sorted order, can be done without horrible memory cost)?
I don't think so, unless I'm not understanding you. The point is... suppose you have 1M matches on the key for one index, and 1 in the other (for a row among the 1M matching the first), and you have no information about which is which. If you arbitrarily pick one to go first at random, you loop 500K times on average.
If you do what I'm suggesting you loop 2 times on average -- a big difference :). This is "breadth first search" but the breadth is just the number of indexes... if there are really thousands of indexes you could bound to the X most likely, but in that case getting the order right for optimal depth-first is quite unlikely, whereas since this is an "AND", for even modest X you lower your chances of a "wrong" choice exponentially.
Also, is the amount of memory for a "cursor" in an index really that large compared with the memory that you use for query specification in any case? Your current method does assume it has random access to the query.
I do think its a flaw that something which can be done in constant time actually takes time which could be proportional to the number of rows, just by picking the wrong index.
> I'm not opposed to doing that. But I have no idea how to guess when
> that is better than the current inner-loop method.
What I'm proposing is always at most a constant times number of iterations worse (ok -- # of times proportional to the number of indexes used), vs something that could be arbitrarily much worse. But you could adapt the current heuristic to tune the probabilities, so that the worse case will be asymptotically the same as current.... but the average case will be much better.
>
>> I know you have a new type of index in the works... but it doesn't look like "trunk" has any modifications for "scan", and presumably the strategy I just mentioned is pretty general (not depending on histograms, etc). Does it sound like a good idea?
>
> I think you're thinking of
> https://issues.apache.org/jira/browse/CASSANDRA-1472, and my
> understanding is that the bitmap approach basically does what you want
> only faster.
>
I'll have to study it. As far as I know what I'm proposing is orthogonal to histogram methods that don't actually keep stats on the joins (which is a lot of stats to keep), and even in this case it can be used to optimize "lower resolution" statistics to the partial experience from sampling the current query.
It does introduce extra overhead for small queries, of course, so if you had histograms that guaranteed that the query was going to be very small for a particular index then it would be best to put that first without fiddling. However, typically you have exact info for only the common keys, not the rare ones.
-- Shaun
> --
> Jonathan Ellis
> Project Chair, Apache Cassandra
> co-founder of DataStax, the source for professional Cassandra support
> http://www.datastax.com
Re: order of index expressions
Posted by Jonathan Ellis <jb...@gmail.com>.
On Sun, Feb 6, 2011 at 11:03 AM, Shaun Cutts <sh...@cuttshome.net> wrote:
> What I think you should be doing is the following: open iterators on the matching keys for each of the indexes; the inside loop would pick an iterator at random, and pull a match from it. This would assure that the expected number of entries examined is a small multiple (# of other indexes) of the index with the most "precision".
Isn't this a bad approximation of performing an intersection by
iterating through each index results (which, since they return in
sorted order, can be done without horrible memory cost)?
I'm not opposed to doing that. But I have no idea how to guess when
that is better than the current inner-loop method.
> I know you have a new type of index in the works... but it doesn't look like "trunk" has any modifications for "scan", and presumably the strategy I just mentioned is pretty general (not depending on histograms, etc). Does it sound like a good idea?
I think you're thinking of
https://issues.apache.org/jira/browse/CASSANDRA-1472, and my
understanding is that the bitmap approach basically does what you want
only faster.
--
Jonathan Ellis
Project Chair, Apache Cassandra
co-founder of DataStax, the source for professional Cassandra support
http://www.datastax.com
Re: order of index expressions
Posted by Shaun Cutts <sh...@cuttshome.net>.
Ok,
So I understand now. You choose the index with the smallest number of matches per key on the average. Unfortunately this doesn't work out so well for me. I am doing a query in the "edges" columnfamily of a graph database, which should return edges with source and target labels equal to given values.
I have about 30M edges, and the target labels have on the average more matching rows. Unfortunately in the given case there are 2 matches on target label, and about 100K on the source label, and I have 5000 similar queries to perform for the overall task.
What I think you should be doing is the following: open iterators on the matching keys for each of the indexes; the inside loop would pick an iterator at random, and pull a match from it. This would assure that the expected number of entries examined is a small multiple (# of other indexes) of the index with the most "precision".
Then (if you want) you can optimize using overall statistics to adjust the initial probabilities if you want. But as you process the query you should mix these initial probabilities with probabilities proportional to the actual fraction of overall matches generated by a given index. (I guess you can control the speed of mixing using the standard deviations on the initial key counts if you want).
I know you have a new type of index in the works... but it doesn't look like "trunk" has any modifications for "scan", and presumably the strategy I just mentioned is pretty general (not depending on histograms, etc). Does it sound like a good idea?
-- Shaun
On Feb 6, 2011, at 12:15 AM, Jonathan Ellis wrote:
> ColumnFamilyStore.scan
>
> On Sat, Feb 5, 2011 at 10:32 PM, Shaun Cutts <sh...@cuttshome.net> wrote:
>> Thanks for the response!
>>
>> So.. I *may* have a bug to report (at least I can generate radically different response times based on expression order with a multiply indexed columnfamily), but first I'll have to upgrade to a stable version (currently I have 7.0rc2 installed).
>>
>> I was also wondering where the code that does this is... is it in
>>
>> java.org.apache.cassandra.db.columniterator.IndexedSliceReader?
>>
>>
>> Thanks,
>>
>> -- Shaun
>>
>> On Feb 5, 2011, at 2:39 PM, Jonathan Ellis wrote:
>>
>>> On Sat, Feb 5, 2011 at 8:48 AM, Shaun Cutts <sh...@cuttshome.net> wrote:
>>>> Hello,
>>>> I'm wondering if cassandra is sensitive to the order of index expressions in
>>>> (pycassa call) get_indexed_slices?
>>>
>>> No.
>>>
>>>> If I have several column indexes available, will it attempt to optimize the
>>>> order?
>>>
>>> Yes.
>>>
>>> --
>>> Jonathan Ellis
>>> Project Chair, Apache Cassandra
>>> co-founder of DataStax, the source for professional Cassandra support
>>> http://www.datastax.com
>>
>>
>
>
>
> --
> Jonathan Ellis
> Project Chair, Apache Cassandra
> co-founder of DataStax, the source for professional Cassandra support
> http://www.datastax.com
Re: order of index expressions
Posted by Jonathan Ellis <jb...@gmail.com>.
ColumnFamilyStore.scan
On Sat, Feb 5, 2011 at 10:32 PM, Shaun Cutts <sh...@cuttshome.net> wrote:
> Thanks for the response!
>
> So.. I *may* have a bug to report (at least I can generate radically different response times based on expression order with a multiply indexed columnfamily), but first I'll have to upgrade to a stable version (currently I have 7.0rc2 installed).
>
> I was also wondering where the code that does this is... is it in
>
> java.org.apache.cassandra.db.columniterator.IndexedSliceReader?
>
>
> Thanks,
>
> -- Shaun
>
> On Feb 5, 2011, at 2:39 PM, Jonathan Ellis wrote:
>
>> On Sat, Feb 5, 2011 at 8:48 AM, Shaun Cutts <sh...@cuttshome.net> wrote:
>>> Hello,
>>> I'm wondering if cassandra is sensitive to the order of index expressions in
>>> (pycassa call) get_indexed_slices?
>>
>> No.
>>
>>> If I have several column indexes available, will it attempt to optimize the
>>> order?
>>
>> Yes.
>>
>> --
>> Jonathan Ellis
>> Project Chair, Apache Cassandra
>> co-founder of DataStax, the source for professional Cassandra support
>> http://www.datastax.com
>
>
--
Jonathan Ellis
Project Chair, Apache Cassandra
co-founder of DataStax, the source for professional Cassandra support
http://www.datastax.com
Re: order of index expressions
Posted by Shaun Cutts <sh...@cuttshome.net>.
Thanks for the response!
So.. I *may* have a bug to report (at least I can generate radically different response times based on expression order with a multiply indexed columnfamily), but first I'll have to upgrade to a stable version (currently I have 7.0rc2 installed).
I was also wondering where the code that does this is... is it in
java.org.apache.cassandra.db.columniterator.IndexedSliceReader?
Thanks,
-- Shaun
On Feb 5, 2011, at 2:39 PM, Jonathan Ellis wrote:
> On Sat, Feb 5, 2011 at 8:48 AM, Shaun Cutts <sh...@cuttshome.net> wrote:
>> Hello,
>> I'm wondering if cassandra is sensitive to the order of index expressions in
>> (pycassa call) get_indexed_slices?
>
> No.
>
>> If I have several column indexes available, will it attempt to optimize the
>> order?
>
> Yes.
>
> --
> Jonathan Ellis
> Project Chair, Apache Cassandra
> co-founder of DataStax, the source for professional Cassandra support
> http://www.datastax.com
Re: order of index expressions
Posted by buddhasystem <po...@bnl.gov>.
Jonathan,
what's the implementation of that? I.e. is is a product of indexes or nested
loops?
Thanks,
Maxim
--
View this message in context: http://cassandra-user-incubator-apache-org.3065146.n2.nabble.com/order-of-index-expressions-tp5995909p5996488.html
Sent from the cassandra-user@incubator.apache.org mailing list archive at Nabble.com.
Re: order of index expressions
Posted by Jonathan Ellis <jb...@gmail.com>.
On Sat, Feb 5, 2011 at 8:48 AM, Shaun Cutts <sh...@cuttshome.net> wrote:
> Hello,
> I'm wondering if cassandra is sensitive to the order of index expressions in
> (pycassa call) get_indexed_slices?
No.
> If I have several column indexes available, will it attempt to optimize the
> order?
Yes.
--
Jonathan Ellis
Project Chair, Apache Cassandra
co-founder of DataStax, the source for professional Cassandra support
http://www.datastax.com