compaction: Optimize partition filtering for cleanup compaction
compaction: Optimize partition filtering for cleanup compaction

Realized that the overall complexity of partition filtering in
cleanup is O(N * log(M)), where
	N is # of tokens
	M is # of ranges owned by the node

Assuming N=10,000,000 for a table and M=257, N*log(M) ~= 80,056,245
checks performed during the whole cleanup.

This can be optimized by taking advantage that owned ranges are
both sorted and non wrapping, so an incremental iterator-oriented
checker is introduced to reduce complexity from O(N * log(M)) to
O(N + M) or just O(N).

BEFORE

240MB to 237MB (~98% of original) in 3239ms = 73MB/s. ~950016 total partitions merged to 949943.
719MB to 719MB (~99% of original) in 9649ms = 74MB/s. ~2900608 total partitions merged to 2900576.
1GB to 1GB (~100% of original) in 15231ms = 74MB/s. ~4536960 total partitions merged to 4536852.
1GB to 1GB (~100% of original) in 15244ms = 74MB/s. ~4536960 total partitions merged to 4536840.
1GB to 1GB (~100% of original) in 15263ms = 74MB/s. ~4536832 total partitions merged to 4536783.
1GB to 1GB (~100% of original) in 15216ms = 74MB/s. ~4536832 total partitions merged to 4536812.

AFTER

240MB to 237MB (~98% of original) in 3169ms = 74MB/s. ~950016 total partitions merged to 949943.
719MB to 719MB (~99% of original) in 9444ms = 76MB/s. ~2900608 total partitions merged to 2900576.
1GB to 1GB (~100% of original) in 14882ms = 76MB/s. ~4536960 total partitions merged to 4536852.
1GB to 1GB (~100% of original) in 14918ms = 76MB/s. ~4536960 total partitions merged to 4536840.
1GB to 1GB (~100% of original) in 14919ms = 76MB/s. ~4536832 total partitions merged to 4536783.
1GB to 1GB (~100% of original) in 14894ms = 76MB/s. ~4536832 total partitions merged to 4536812.

Fixes #6807.

test: mode(dev).

Signed-off-by: Raphael S. Carvalho <1e2942cea40e3b4d2162dfcd9e53e41c05a84d22@scylladb.com>
Message-Id: <20210802213159.182393-1-1e2942cea40e3b4d2162dfcd9e53e41c05a84d22@scylladb.com>

scylladb/scylla,scylladb/scylla,scylladb/scylla,scylladb/scylla