[
https://issues.apache.org/jira/browse/CASSANDRA-5677?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13699261#comment-13699261
]
Jonathan Ellis commented on CASSANDRA-5677:
-------------------------------------------
Why would we want to retain the Centered implementation?
> Performance improvements of RangeTombstones/IntervalTree
> --------------------------------------------------------
>
> Key: CASSANDRA-5677
> URL: https://issues.apache.org/jira/browse/CASSANDRA-5677
> Project: Cassandra
> Issue Type: Improvement
> Affects Versions: 1.2.0
> Reporter: Fabien Rousseau
> Priority: Minor
> Attachments: 5677-new-IntervalTree-implementation.patch
>
>
> Using massively range tombstones leads to bad response time (ie 100-500
> ranges tombstones per row).
> After investigation, it seems that the culprit is how the DeletionInfo are
> merged. Each time a RangeTombstone is added into the DeletionInfo, the whole
> IntervalTree is rebuilt (thus, if you have 100 tombstones in one row, then
> 100 instances of IntervalTree are created, the first one having one interval,
> the second one 2 intervals,... the 100th one : 100 intervals...)
> It seems that once the IntervalTree is built, it is not possible to add a new
> Interval. Idea is to change the implementation of the IntervalTree by another
> one which support "insert interval".
> Attached is a proposed patch which :
> - renames the IntervalTree implementation to IntervalTreeCentered (the
> renaming is inspired from : http://en.wikipedia.org/wiki/Interval_tree)
> - adds a new implementation IntervalTreeAvl (which is described here :
> http://en.wikipedia.org/wiki/Interval_tree#Augmented_tree and here :
> http://en.wikipedia.org/wiki/AVL_tree )
> - adds a new interface IIntervalTree to abstract the implementation
> - adds a new configuration option (interval_tree_provider) which allows to
> choose between the two implementations (defaults to previous
> IntervalTreeCentered)
> - updates IntervalTreeTest unit tests to test both implementations
> - creates a mini benchmark between the two implementations (tree creation,
> point lookup, interval lookup)
> - creates a mini benchmark between the two implementations when merging
> DeletionInfo (which shows a big performance improvement when using 500
> tombstones for a row)
> This patch applies for 1.2 branch...
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
