Merge branch 'cassandra-2.1' into trunk
Conflicts:
src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/284d3f7f
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/284d3f7f
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/284d3f7f
Branch: refs/heads/trunk
Commit: 284d3f7fe0210acfdc9b242c2987124eda5a9c66
Parents: c7fb27a 9881ea6
Author: Aleksey Yeschenko <[email protected]>
Authored: Mon May 5 22:58:58 2014 +0300
Committer: Aleksey Yeschenko <[email protected]>
Committed: Mon May 5 22:58:58 2014 +0300
----------------------------------------------------------------------
CHANGES.txt | 1 +
.../cassandra/db/ArrayBackedSortedColumns.java | 254 +++++++++++--------
.../apache/cassandra/db/AtomicBTreeColumns.java | 76 +++++-
.../cassandra/db/CollationController.java | 46 ++--
.../org/apache/cassandra/db/ColumnFamily.java | 17 +-
.../apache/cassandra/db/ColumnFamilyStore.java | 5 +-
.../apache/cassandra/db/RowIteratorFactory.java | 19 +-
.../apache/cassandra/db/filter/ColumnSlice.java | 146 -----------
.../cassandra/db/filter/ExtendedFilter.java | 4 +-
.../cassandra/db/filter/IDiskAtomFilter.java | 4 +-
.../cassandra/db/filter/NamesQueryFilter.java | 39 +--
.../apache/cassandra/db/filter/QueryFilter.java | 56 ++--
.../cassandra/db/filter/SliceQueryFilter.java | 24 +-
.../cassandra/service/RowDataResolver.java | 11 +-
.../apache/cassandra/utils/MergeIterator.java | 25 +-
.../org/apache/cassandra/utils/btree/BTree.java | 12 +-
.../apache/cassandra/utils/btree/BTreeSet.java | 8 +-
.../apache/cassandra/utils/btree/Cursor.java | 8 +-
18 files changed, 360 insertions(+), 395 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/284d3f7f/CHANGES.txt
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/284d3f7f/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
----------------------------------------------------------------------
diff --cc src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
index 5cd51d8,f5624d2..ef2c2c6
--- a/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
+++ b/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
@@@ -435,77 -445,25 +446,78 @@@ public class ArrayBackedSortedColumns e
public Iterator<Cell> reverseIterator(ColumnSlice[] slices)
{
maybeSortCells();
- return new SlicesIterator(Arrays.asList(cells).subList(0, size),
getComparator(), slices, !reversed);
+ return slices.length == 1
+ ? slice(slices[0], !reversed, null)
+ : new SlicesIterator(slices, !reversed);
}
+ public SearchIterator<CellName, Cell> searchIterator()
+ {
+ maybeSortCells();
+
+ return new SearchIterator<CellName, Cell>()
+ {
+ // the first index that we could find the next key at, i.e. one
larger
+ // than the last key's location
+ private int i = 0;
+
+ // We assume a uniform distribution of keys,
+ // so we keep track of how many keys were skipped to satisfy last
lookup, and only look at twice that
+ // many keys for next lookup initially, extending to whole range
only if we couldn't find it in that subrange
+ private int range = size / 2;
+
+ public boolean hasNext()
+ {
+ return i < size;
+ }
+
+ public Cell next(CellName name)
+ {
+ if (!isSorted || !hasNext())
+ throw new IllegalStateException();
+
+ // optimize for runs of sequential matches, as in
CollationController
+ // checking to see if we've found the desired cells yet
(CASSANDRA-6933)
+ int c = metadata.comparator.compare(name, cells[i].name());
+ if (c <= 0)
+ return c < 0 ? null : cells[i++];
+
+ // use range to manually force a better bsearch "pivot" by
breaking it into two calls:
+ // first for i..i+range, then i+range..size if necessary.
+ //
https://issues.apache.org/jira/browse/CASSANDRA-6933?focusedCommentId=13958264&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-13958264
+ int limit = Math.min(size, i + range);
+ int i2 = binarySearch(i + 1, limit, name,
internalComparator());
+ if (-1 - i2 == limit)
+ i2 = binarySearch(limit, size, name,
internalComparator());
+ // i2 can't be zero since we already checked cells[i] above
+ if (i2 > 0)
+ {
+ range = i2 - i;
+ i = i2 + 1;
+ return cells[i2];
+ }
+ i2 = -1 - i2;
+ range = i2 - i;
+ i = i2;
+ return null;
+ }
+ };
+ }
+
- private static class SlicesIterator extends AbstractIterator<Cell>
+ private class SlicesIterator extends AbstractIterator<Cell>
{
- private final List<Cell> cells;
private final ColumnSlice[] slices;
- private final Comparator<Composite> comparator;
+ private final boolean invert;
private int idx = 0;
- private int previousSliceEnd = 0;
+ private int previousSliceEnd;
private Iterator<Cell> currentSlice;
- public SlicesIterator(List<Cell> cells, CellNameType comparator,
ColumnSlice[] slices, boolean reversed)
+ public SlicesIterator(ColumnSlice[] slices, boolean invert)
{
- this.cells = reversed ? Lists.reverse(cells) : cells;
this.slices = slices;
- this.comparator = reversed ? comparator.reverseComparator() :
comparator;
+ this.invert = invert;
+ previousSliceEnd = invert ? size : 0;
}
protected Cell computeNext()
http://git-wip-us.apache.org/repos/asf/cassandra/blob/284d3f7f/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
----------------------------------------------------------------------
diff --cc src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
index a6a245f,27eb46d..4eb4940
--- a/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
+++ b/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
@@@ -33,12 -34,8 +34,10 @@@ import org.apache.cassandra.config.CFMe
import org.apache.cassandra.db.composites.CellName;
import org.apache.cassandra.db.composites.Composite;
import org.apache.cassandra.db.filter.ColumnSlice;
- import org.apache.cassandra.db.index.SecondaryIndexManager;
import org.apache.cassandra.utils.ObjectSizes;
+import org.apache.cassandra.utils.SearchIterator;
import org.apache.cassandra.utils.btree.BTree;
+import org.apache.cassandra.utils.btree.BTreeSearchIterator;
- import org.apache.cassandra.utils.btree.BTreeSet;
import org.apache.cassandra.utils.btree.UpdateFunction;
import org.apache.cassandra.utils.concurrent.OpOrder;
import org.apache.cassandra.utils.memory.MemtableAllocator;
http://git-wip-us.apache.org/repos/asf/cassandra/blob/284d3f7f/src/java/org/apache/cassandra/db/CollationController.java
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/284d3f7f/src/java/org/apache/cassandra/db/ColumnFamily.java
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/284d3f7f/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java
----------------------------------------------------------------------
diff --cc src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java
index 19faeb7,0e0643f..3471e6a
--- a/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java
+++ b/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java
@@@ -185,33 -191,21 +192,23 @@@ public class NamesQueryFilter implement
{
private final ColumnFamily cf;
private final DecoratedKey key;
- private final Iterator<CellName> iter;
+ private final Iterator<CellName> names;
+ private final SearchIterator<CellName, Cell> cells;
- public ByNameColumnIterator(Iterator<CellName> names, ColumnFamily
cf, DecoratedKey key)
- public ByNameColumnIterator(Iterator<CellName> iter, DecoratedKey
key, ColumnFamily cf)
++ public ByNameColumnIterator(Iterator<CellName> names, DecoratedKey
key, ColumnFamily cf)
{
- this.iter = iter;
+ this.names = names;
this.cf = cf;
this.key = key;
+ this.cells = cf.searchIterator();
}
- public ColumnFamily getColumnFamily()
- {
- return cf;
- }
-
- public DecoratedKey getKey()
- {
- return key;
- }
-
protected OnDiskAtom computeNext()
{
- while (iter.hasNext())
+ while (names.hasNext() && cells.hasNext())
{
- CellName current = iter.next();
- Cell cell = cf.getColumn(current);
+ CellName current = names.next();
+ Cell cell = cells.next(current);
if (cell != null)
return cell;
}
@@@ -244,7 -248,7 +251,7 @@@
public NamesQueryFilter deserialize(DataInput in, int version) throws
IOException
{
int size = in.readInt();
-- SortedSet<CellName> columns = new TreeSet<CellName>(type);
++ SortedSet<CellName> columns = new TreeSet<>(type);
ISerializer<CellName> serializer = type.cellSerializer();
for (int i = 0; i < size; ++i)
columns.add(serializer.deserialize(in));
@@@ -267,7 -271,7 +274,7 @@@
public Iterator<RangeTombstone> getRangeTombstoneIterator(final
ColumnFamily source)
{
if (!source.deletionInfo().hasRanges())
-- return Iterators.<RangeTombstone>emptyIterator();
++ return Iterators.emptyIterator();
return new AbstractIterator<RangeTombstone>()
{
http://git-wip-us.apache.org/repos/asf/cassandra/blob/284d3f7f/src/java/org/apache/cassandra/service/RowDataResolver.java
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/284d3f7f/src/java/org/apache/cassandra/utils/btree/Cursor.java
----------------------------------------------------------------------
diff --cc src/java/org/apache/cassandra/utils/btree/Cursor.java
index 132a776,02e047a..6814d26
--- a/src/java/org/apache/cassandra/utils/btree/Cursor.java
+++ b/src/java/org/apache/cassandra/utils/btree/Cursor.java
@@@ -91,9 -91,9 +91,9 @@@ public final class Cursor<K, V extends
_reset(btree, comparator, lowerBound, inclusiveLowerBound,
upperBound, inclusiveUpperBound, forwards);
}
- private void _reset(Object[] btree, Comparator<V> comparator, Object
lowerBound, boolean inclusiveLowerBound, Object upperBound, boolean
inclusiveUpperBound, boolean forwards)
+ private void _reset(Object[] btree, Comparator<K> comparator, Object
lowerBound, boolean inclusiveLowerBound, Object upperBound, boolean
inclusiveUpperBound, boolean forwards)
{
- ensureDepth(btree);
+ init(btree);
if (lowerBound == null)
lowerBound = NEGATIVE_INFINITY;
if (upperBound == null)
