[
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)
