svn commit: r802950 - in /incubator/cassandra/trunk/src/java/org/apache/cassandra: db/filter/SSTableNamesIterator.java utils/BloomFilter.java

[jb...@apache.org]

Author: jbellis
Date: Mon Aug 10 22:52:08 2009
New Revision: 802950

URL: http://svn.apache.org/viewvc?rev=802950&view=rev
Log:
check column-level bloom filter during name-based slicing.
patch by jbellis; reviewed by Jun Rao for CASSANDRA-325

Modified:
    incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SSTableNamesIterator.java
    incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/BloomFilter.java

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SSTableNamesIterator.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SSTableNamesIterator.java?rev=802950&r1=802949&r2=802950&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SSTableNamesIterator.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/db/filter/SSTableNamesIterator.java Mon Aug 10 22:52:08 2009
@@ -8,6 +8,7 @@
 import org.apache.cassandra.db.marshal.AbstractType;
 import org.apache.cassandra.io.*;
 import org.apache.cassandra.config.DatabaseDescriptor;
+import org.apache.cassandra.utils.BloomFilter;
 
 public class SSTableNamesIterator extends SimpleAbstractColumnIterator
 {
@@ -15,10 +16,10 @@
     private Iterator<IColumn> iter;
     public final SortedSet<byte[]> columns;
 
-    public SSTableNamesIterator(String filename, String key, String cfName, SortedSet<byte[]> columns) throws IOException
+    public SSTableNamesIterator(String filename, String key, String cfName, SortedSet<byte[]> columnNames) throws IOException
     {
-        assert columns != null;
-        this.columns = columns;
+        assert columnNames != null;
+        this.columns = columnNames;
         SSTableReader ssTable = SSTableReader.open(filename);
 
         String decoratedKey = ssTable.getPartitioner().decorateKey(key);
@@ -31,13 +32,24 @@
         {
             file.seek(position);
 
-            /* note the position where the key starts */
             String keyInDisk = file.readUTF();
             assert keyInDisk.equals(decoratedKey) : keyInDisk;
             file.readInt(); // data size
 
             /* Read the bloom filter summarizing the columns */
-            IndexHelper.defreezeBloomFilter(file);
+            BloomFilter bf = IndexHelper.defreezeBloomFilter(file);
+            List<byte[]> filteredColumnNames = new ArrayList<byte[]>(columnNames.size());
+            for (byte[] name : columnNames)
+            {
+                if (bf.isPresent(name))
+                {
+                    filteredColumnNames.add(name);
+                }
+            }
+            if (filteredColumnNames.isEmpty())
+            {
+                return;
+            }
 
             List<IndexHelper.IndexInfo> indexList = IndexHelper.deserializeIndex(file);
 
@@ -47,7 +59,7 @@
             /* get the various column ranges we have to read */
             AbstractType comparator = DatabaseDescriptor.getComparator(SSTable.parseTableName(filename), cfName);
             SortedSet<IndexHelper.IndexInfo> ranges = new TreeSet<IndexHelper.IndexInfo>(IndexHelper.getComparator(comparator));
-            for (byte[] name : columns)
+            for (byte[] name : filteredColumnNames)
             {
                 int index = IndexHelper.indexFor(name, indexList, comparator, false);
                 if (index == indexList.size())
@@ -68,7 +80,8 @@
                 while (file.getFilePointer() < columnBegin + indexInfo.offset + indexInfo.width)
                 {
                     final IColumn column = cf.getColumnSerializer().deserialize(file);
-                    if (columns.contains(column.name()))
+                    // we check vs the original Set, not the filtered List, for efficiency
+                    if (columnNames.contains(column.name()))
                     {
                         cf.addColumn(column);
                     }

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/BloomFilter.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/BloomFilter.java?rev=802950&r1=802949&r2=802950&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/BloomFilter.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/utils/BloomFilter.java Mon Aug 10 22:52:08 2009
@@ -85,6 +85,18 @@
         return true;
     }
 
+    public boolean isPresent(byte[] key)
+    {
+        for (int bucketIndex : getHashBuckets(key))
+        {
+            if (!filter_.get(bucketIndex))
+            {
+                return false;
+            }
+        }
+        return true;
+    }
+
     /*
      @param key -- value whose hash is used to fill
      the filter_.