Chandrasekhar Thumuluru created CASSANDRA-15397:
---------------------------------------------------
Summary: IntervalTree performance comparison with Linear Walk and
Binary Search based Elimination.
Key: CASSANDRA-15397
URL: https://issues.apache.org/jira/browse/CASSANDRA-15397
Project: Cassandra
Issue Type: Improvement
Reporter: Chandrasekhar Thumuluru
Attachments: 99p_10000_SSTable_with_5000_Searches.png,
99p_15000_SSTable_with_5000_Searches.png,
99p_20000_SSTable_with_5000_Searches.png,
99p_25000_SSTable_with_5000_Searches.png,
99p_30000_SSTable_with_5000_Searches.png,
99p_5000_SSTable_with_5000_Searches.png
Cassandra uses IntervalTrees to identify the SSTables that overlap with search
interval. In Cassandra, IntervalTrees are not mutated. They are recreated each
time a mutation is required. This can be an issue during repairs. In fact we
noticed such issues during repair.
Since lists are cache friendly compared to linked lists and trees, I decided to
compare the search performance with:
* Linear Walk.
* Elimination using Binary Search (idea is to eliminate intervals using start
and end points of search interval).
Based on the tests I ran, I noticed Binary Search based elimination almost
always performs similar to IntervalTree performance or out performs
IntervalTree based search.
I ran the tests using random intervals to build the tree/lists and another
randomly generated search interval with 5000 iterations. I'm attaching all the
relevant graphs.
PS: For the purpose of test, I simplified the IntervalTree code by making it
non-generic and removing the data portion of the interval.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
