Author: jbellis
Date: Tue Nov 3 03:20:43 2009
New Revision: 832287
URL: http://svn.apache.org/viewvc?rev=832287&view=rev
Log:
optimize away unnecessary seeks during range scan
patch by Gary Dusbabek; reviewed by jbellis for CASSANDRA-350
Modified:
incubator/cassandra/trunk/CHANGES.txt
incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SSTableSliceIterator.java
incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java
incubator/cassandra/trunk/test/unit/org/apache/cassandra/db/TableTest.java
Modified: incubator/cassandra/trunk/CHANGES.txt
URL:
http://svn.apache.org/viewvc/incubator/cassandra/trunk/CHANGES.txt?rev=832287&r1=832286&r2=832287&view=diff
==============================================================================
--- incubator/cassandra/trunk/CHANGES.txt (original)
+++ incubator/cassandra/trunk/CHANGES.txt Tue Nov 3 03:20:43 2009
@@ -30,6 +30,8 @@
for normal writes (CASSANDRA-446) and bulk load (CASSANDRA-420)
* Add MemtableFlushAfterMinutes, a global replacement for the old
per-CF FlushPeriodInMinutes setting (CASSANDRA-463)
+ * Datacenter quorum consistency levels (CASSANDRA-492)
+ * optimizations to slice reading (CASSANDRA-350)
0.4.2
Modified:
incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SSTableSliceIterator.java
URL:
http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SSTableSliceIterator.java?rev=832287&r1=832286&r2=832287&view=diff
==============================================================================
---
incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SSTableSliceIterator.java
(original)
+++
incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SSTableSliceIterator.java
Tue Nov 3 03:20:43 2009
@@ -39,13 +39,13 @@
{
private final boolean reversed;
private final byte[] startColumn;
+ private final byte[] finishColumn;
private final AbstractType comparator;
private ColumnGroupReader reader;
- public SSTableSliceIterator(SSTableReader ssTable, String key, byte[]
startColumn, boolean reversed)
+ public SSTableSliceIterator(SSTableReader ssTable, String key, byte[]
startColumn, byte[] finishColumn, boolean reversed)
throws IOException
{
- // TODO push finishColumn down here too, so we can tell when we're
done and optimize away the slice when the index + start/stop shows there's
nothing to scan for
this.reversed = reversed;
/* Morph key into actual key based on the partition type. */
@@ -53,15 +53,27 @@
long position = ssTable.getPosition(decoratedKey);
this.comparator = ssTable.getColumnComparator();
this.startColumn = startColumn;
+ this.finishColumn = finishColumn;
if (position >= 0)
reader = new ColumnGroupReader(ssTable, decoratedKey, position);
}
private boolean isColumnNeeded(IColumn column)
{
- return reversed
- ? startColumn.length == 0 || comparator.compare(column.name(),
startColumn) <= 0
- : comparator.compare(column.name(), startColumn) >= 0;
+ if (startColumn.length == 0 && finishColumn.length == 0)
+ return true;
+ else if (startColumn.length == 0 && !reversed)
+ return comparator.compare(column.name(), finishColumn) <= 0;
+ else if (startColumn.length == 0 && reversed)
+ return comparator.compare(column.name(), finishColumn) >= 0;
+ else if (finishColumn.length == 0 && !reversed)
+ return comparator.compare(column.name(), startColumn) >= 0;
+ else if (finishColumn.length == 0 && reversed)
+ return comparator.compare(column.name(), startColumn) <= 0;
+ else if (!reversed)
+ return comparator.compare(column.name(), startColumn) >= 0 &&
comparator.compare(column.name(), finishColumn) <= 0;
+ else // if reversed
+ return comparator.compare(column.name(), startColumn) <= 0 &&
comparator.compare(column.name(), finishColumn) >= 0;
}
public ColumnFamily getColumnFamily()
@@ -156,15 +168,41 @@
return false;
/* seek to the correct offset to the data, and calculate the data
size */
- IndexHelper.IndexInfo curColPostion = indexes.get(curRangeIndex);
- file.seek(columnStartPosition + curColPostion.offset);
- while (file.getFilePointer() < columnStartPosition +
curColPostion.offset + curColPostion.width)
+ IndexHelper.IndexInfo curColPosition = indexes.get(curRangeIndex);
+
+ /* see if this read is really necessary. */
+ if (reversed)
+ {
+ if ((finishColumn.length > 0 &&
comparator.compare(finishColumn, curColPosition.lastName) > 0) ||
+ (startColumn.length > 0 && comparator.compare(startColumn,
curColPosition.firstName) < 0))
+ return false;
+ }
+ else
+ {
+ if ((startColumn.length > 0 && comparator.compare(startColumn,
curColPosition.lastName) > 0) ||
+ (finishColumn.length > 0 &&
comparator.compare(finishColumn, curColPosition.firstName) < 0))
+ return false;
+ }
+
+ boolean outOfBounds = false;
+
+ file.seek(columnStartPosition + curColPosition.offset);
+ while (file.getFilePointer() < columnStartPosition +
curColPosition.offset + curColPosition.width && !outOfBounds)
{
IColumn column =
emptyColumnFamily.getColumnSerializer().deserialize(file);
if (reversed)
blockColumns.addFirst(column);
else
blockColumns.addLast(column);
+
+ /* see if we can stop seeking. */
+ if (!reversed && finishColumn.length > 0)
+ outOfBounds = comparator.compare(column.name(),
finishColumn) >= 0;
+ else if (reversed && startColumn.length > 0)
+ outOfBounds = comparator.compare(column.name(),
startColumn) >= 0;
+
+ if (outOfBounds)
+ break;
}
if (reversed)
Modified:
incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java
URL:
http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java?rev=832287&r1=832286&r2=832287&view=diff
==============================================================================
---
incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java
(original)
+++
incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java
Tue Nov 3 03:20:43 2009
@@ -61,7 +61,7 @@
public ColumnIterator getSSTableColumnIterator(SSTableReader sstable)
throws IOException
{
- return new SSTableSliceIterator(sstable, key, start, reversed);
+ return new SSTableSliceIterator(sstable, key, start, finish, reversed);
}
public SuperColumn filterSuperColumn(SuperColumn superColumn, int gcBefore)
Modified:
incubator/cassandra/trunk/test/unit/org/apache/cassandra/db/TableTest.java
URL:
http://svn.apache.org/viewvc/incubator/cassandra/trunk/test/unit/org/apache/cassandra/db/TableTest.java?rev=832287&r1=832286&r2=832287&view=diff
==============================================================================
--- incubator/cassandra/trunk/test/unit/org/apache/cassandra/db/TableTest.java
(original)
+++ incubator/cassandra/trunk/test/unit/org/apache/cassandra/db/TableTest.java
Tue Nov 3 03:20:43 2009
@@ -18,9 +18,12 @@
package org.apache.cassandra.db;
+import java.text.DecimalFormat;
+import java.text.NumberFormat;
import java.util.*;
import java.io.IOException;
+import org.apache.cassandra.config.DatabaseDescriptor;
import org.apache.commons.lang.StringUtils;
import org.apache.commons.lang.ArrayUtils;
import org.junit.Test;
@@ -170,6 +173,65 @@
validateGetSliceNoMatch(table);
}
+ @Test
+ public void testGetSliceWithCutoff() throws Throwable
+ {
+ // tests slicing against data from one row in a memtable and then
flushed to an sstable
+ final Table table = Table.open("Keyspace1");
+ final ColumnFamilyStore cfStore =
table.getColumnFamilyStore("Standard1");
+ final String ROW = "row4";
+ final NumberFormat fmt = new DecimalFormat("000");
+
+ RowMutation rm = new RowMutation("Keyspace1", ROW);
+ ColumnFamily cf = ColumnFamily.create("Keyspace1", "Standard1");
+ // at this rate, we're getting 78-79 cos/block, assuming the blocks
are set to be about 4k.
+ // so if we go to 300, we'll get at least 4 blocks, which is plenty
for testing.
+ for (int i = 0; i < 300; i++)
+ cf.addColumn(column("col" + fmt.format(i),
"omg!thisisthevalue!"+i, 1L));
+ rm.add(cf);
+ rm.apply();
+
+ Runner verify = new Runner()
+ {
+ public void run() throws Exception
+ {
+ ColumnFamily cf;
+
+ // blocks are partitioned like this: 000-097, 098-193,
194-289, 290-299, assuming a 4k column index size.
+ assert DatabaseDescriptor.getColumnIndexSize() == 4096 :
"Unexpected column index size, block boundaries won't be where tests expect
them.";
+
+ // test forward, spanning a segment.
+ cf = cfStore.getColumnFamily(ROW, new QueryPath("Standard1"),
"col096".getBytes(), "col099".getBytes(), false, 4);
+ assertColumns(cf, "col096", "col097", "col098", "col099");
+
+ // test reversed, spanning a segment.
+ cf = cfStore.getColumnFamily(ROW, new QueryPath("Standard1"),
"col099".getBytes(), "col096".getBytes(), true, 4);
+ assertColumns(cf, "col096", "col097", "col098", "col099");
+
+ // test forward, within a segment.
+ cf = cfStore.getColumnFamily(ROW, new QueryPath("Standard1"),
"col100".getBytes(), "col103".getBytes(), false, 4);
+ assertColumns(cf, "col100", "col101", "col102", "col103");
+
+ // test reversed, within a segment.
+ cf = cfStore.getColumnFamily(ROW, new QueryPath("Standard1"),
"col103".getBytes(), "col100".getBytes(), true, 4);
+ assertColumns(cf, "col100", "col101", "col102", "col103");
+
+ // test forward from beginning, spanning a segment.
+ String[] strCols = new String[100]; // col000-col099
+ for (int i = 0; i < 100; i++)
+ strCols[i] = "col" + fmt.format(i);
+ cf = cfStore.getColumnFamily(ROW, new QueryPath("Standard1"),
"".getBytes(), "col099".getBytes(), false, 100);
+ assertColumns(cf, strCols);
+
+ // test reversed, from end, spanning a segment.
+ cf = cfStore.getColumnFamily(ROW, new QueryPath("Standard1"),
"".getBytes(), "col288".getBytes(), true, 12);
+ assertColumns(cf, "col288", "col289", "col290", "col291",
"col292", "col293", "col294", "col295", "col296", "col297", "col298", "col299");
+ }
+ };
+
+ reTest(table.getColumnFamilyStore("Standard1"), verify);
+ }
+
private void validateGetSliceNoMatch(Table table) throws IOException
{
ColumnFamilyStore cfStore = table.getColumnFamilyStore("Standard2");
