[jira] [Commented] (CASSANDRA-8414) Avoid loops over array backed iterators that call iter.remove()

["Benedict (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/CASSANDRA-8414?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14233485#comment-14233485 ] 

Benedict commented on CASSANDRA-8414:
-------------------------------------

I've edited the title because it's not quite that compaction is O(n^2), but that certain operations within a partition are. It's also not limited to just that specific method. The best solution is probably to introduce a special deletion iterator on which a call to remove() simply sets a corresponding bit to 1; once we exhaust the iterator we commit the deletes in one pass.

> Avoid loops over array backed iterators that call iter.remove()
> ---------------------------------------------------------------
>
>                 Key: CASSANDRA-8414
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-8414
>             Project: Cassandra
>          Issue Type: Bug
>          Components: Core
>            Reporter: Richard Low
>
> I noticed from sampling that sometimes compaction spends almost all of its time in iter.remove() in ColumnFamilyStore.removeDeletedStandard. It turns out that the cf object is using ArrayBackedSortedColumns, so deletes are from an ArrayList. If the majority of your columns are GCable tombstones then this is O(n^2). The data structure should be changed or a copy made to avoid this.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)