incubator-connectors-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kwri...@apache.org
Subject svn commit: r1204771 - in /incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore: Index.java IndexAccessor.java IndexNodeColumnKey.java IndexNodeEqualsKey.java IndexNodeParentKey.java
Date Tue, 22 Nov 2011 01:06:42 GMT
Author: kwright
Date: Tue Nov 22 01:06:41 2011
New Revision: 1204771

URL: http://svn.apache.org/viewvc?rev=1204771&view=rev
Log:
Revamp index code to be amenable to rebalancing.

Added:
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeColumnKey.java
  (with props)
Modified:
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/Index.java
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexAccessor.java
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeEqualsKey.java
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeParentKey.java

Modified: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/Index.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/Index.java?rev=1204771&r1=1204770&r2=1204771&view=diff
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/Index.java
(original)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/Index.java
Tue Nov 22 01:06:41 2011
@@ -23,6 +23,32 @@ import org.apache.warthog.interfaces.*;
 import org.apache.warthog.common.*;
 
 /** This is the standard implementation of WHIndex.
+*
+* The index structure has a one-to-one correspondence with the rows
+* in the underlying table.  Since there is such a correspondence, we make
+* use of the rowID for each table row as a "nodeID".  This reduces the number
+* of keys/values we need to track for an index.
+*
+* The index has the following overall structure:
+* (a) An (optional) root node reference, as decribed by a root key, which points to
+*   either nothing or the root node for the first index column;
+* (b) A set of nodes for the first index column organized in a btree;
+* (c) A reference from each node representing the first index column which
+*   functions as the root pointer for a btree based on the second index column, etc.
+*
+* Each btree node has a lesser child node reference, a greater child node reference,
+* and an "equals" child node reference.  All of these relationships refer to comparisons
+* of the current column value for the row represented by the node.  There are also rules
+* for what is legal in any given context within each btree.  Specifically, nodes that 
+* exist in the "equals" chain cannot have greater or lesser children, only "equals"
+* children.
+*
+* For each node reference, there's also a back reference, which allows you to walk back
+* up the tree.  This is unique since every index node can have only one reference to it.
+*
+* In the future, a "maximum depth" value will also be associated with every node, so as
+* to allow automatic rebalancing of each btree.
+*
 */
 public class Index implements WHIndex
 {
@@ -115,72 +141,71 @@ public class Index implements WHIndex
   protected void addNodeInto(long rowID, WHKey parentKey)
     throws WHException
   {
+    for (int columnIndex = 0 ; columnIndex < columnNames.length ; columnIndex++ )
+    {
+      // Place a node into a specific tree as indicated by the column number.
+      // This will either wind up in an equals chain (in which case, a link to the column
child will already exist),
+      // or it will wind up as a new primary node (in which case, the link to the column
child will need to be created).
+      
+      WHKey columnKey = placeIntoBtree(rowID,parentKey,columnIndex);
+
+      // Create the column link, if it needs creating
+      if (columnIndex + 1 < columnNames.length && columnKey == null)
+        parentKey = new IndexNodeColumnKey(indexName,rowID,columnNames[columnIndex]);
+      else
+        parentKey = columnKey;
+    }
+  }
+  
+  /** Method to place a new node into a specific tree for a column.
+  */
+  protected WHKey placeIntoBtree(long rowID, WHKey parentKey, int columnIndex)
+    throws WHException
+  {
+    // Get the current column
+    String columnName = columnNames[columnIndex];
+    WHComparator comparator = comparators[columnIndex];
+    // Read the value we're going to be inserting
+    WHValue insertValue = table.getValue(rowID,columnName);
     // Keep going until we've found the insertion point
-    WHValue[] newRowIndexValues = null;
     while (true)
     {
       // Pick up the current node from the parent
       long currentRowID = readIndexParentChild(parentKey);
       if (currentRowID == -1L)
       {
-        // Our new node is the root node; set the root node accordingly
-        setIndexParentChild(parentKey,rowID);
-        return;
+        // Set the node in place
+        setIndexParentChild(parentKey,columnName,rowID);
+        return new IndexNodeColumnKey(indexName,currentRowID,columnName);
       }
 
-      // If we haven't yet, read the new node's (the one being inserted) column values
-      if (newRowIndexValues == null)
-      {
-        newRowIndexValues = new WHValue[columnNames.length];
-        for (int i = 0 ; i < newRowIndexValues.length ; i++)
-        {
-          newRowIndexValues[i] = table.getValue(rowID,columnNames[i]);
-        }
-      }
+      // Read the value at this node
+      WHValue currentValue = table.getValue(currentRowID,columnName);
       
-      // Loop through the index columns
-      boolean newNodeFound = false;
-      for (int i = 0 ; i < columnNames.length; i++)
-      {
-        String currentColumn = columnNames[i];
-        // Get the value from the row, so we can fire the comparator
-        WHValue currentValue = table.getValue(currentRowID,currentColumn);
-        int comparatorResult = comparators[i].compare(currentValue,newRowIndexValues[i]);
-        // Based on the result, decide which way to go
-        long nextRowID;
-        switch (comparatorResult)
-        {
-        case WHComparator.RESULT_LESS:
-          // Descend the lesser tree for this column.
-          parentKey = new IndexNodeLesserKey(indexName,currentRowID,currentColumn);
-          newNodeFound = true;
-          break;
-        case WHComparator.RESULT_GREATER:
-          // Descend the greater tree for this column.
-          parentKey = new IndexNodeGreaterKey(indexName,currentRowID,currentColumn);
-          newNodeFound = true;
-          break;
-        case WHComparator.RESULT_EQUALS:
-          // Go on to the next column...
-          break;
-        default:
-          throw new WHException("Comparator returned illegal result");
-        }
-        if (newNodeFound)
-          break;
-        // Go on to next column
-      }
+      // Perform the comparison
+      int comparatorResult = comparator.compare(currentValue,insertValue);
       
-      // We've either found an exact match, or the node has been changed and we have to start
over.
-      if (newNodeFound)
+      // Based on the result, decide which way to go
+      switch (comparatorResult)
+      {
+      case WHComparator.RESULT_LESS:
+        // Descend the lesser tree for this column.
+        parentKey = new IndexNodeLesserKey(indexName,currentRowID,columnName);
         continue;
+      case WHComparator.RESULT_GREATER:
+        // Descend the greater tree for this column.
+        parentKey = new IndexNodeGreaterKey(indexName,currentRowID,columnName);
+        continue;
+      case WHComparator.RESULT_EQUALS:
+        // Insert here!  into the chain if need be...
+        break;
+      default:
+        throw new WHException("Comparator returned illegal result");
+      }
       
-      // Equals result.  We found a node which is identical to the one we are adding.
-      if (unique)
+      if (unique && columnIndex +1 == columnNames.length)
       {
-        // This is a problem; we can't add more than one identical row to this index.  Treat
it as a deadlock
-        // exception for now.  We might want to create a new exception type that is a derivative
-        // of WHDeadlockException for this case, however.
+        // Unique constraint violation
         throw new WHDeadlockException();
       }
       
@@ -188,21 +213,21 @@ public class Index implements WHIndex
       // We insert the new node at the beginning of the chain so we don't have to scan it,
obviously...
       
       // First, get the old ref, if there is one.
-      long currentEqualsRowID = readIndexNodeEqualsNode(currentRowID);
+      long currentEqualsRowID = readIndexNodeEqualsNode(currentRowID,columnName);
       
       // Move the old pointer to the new position
       if (currentEqualsRowID != -1L)
       {
         // Delete the old one
-        deleteIndexNodeEqualsNode(currentRowID);
+        deleteIndexNodeEqualsNode(currentRowID,columnName);
         // Move the pointer to the child of the node we just created
-        setIndexNodeEqualsNode(rowID,currentEqualsRowID);
+        setIndexNodeEqualsNode(rowID,columnName,currentEqualsRowID);
       }
       
       // Now, set the new ref.
-      setIndexNodeEqualsNode(currentRowID,rowID);
+      setIndexNodeEqualsNode(currentRowID,columnName,rowID);
       
-      return;
+      return new IndexNodeEqualsKey(indexName,currentRowID,columnName);
     }
   }
   
@@ -211,48 +236,54 @@ public class Index implements WHIndex
   protected void deleteRow(long rowID)
     throws WHException
   {
-    // The strategy for deletion is to use the back pointers to locate everything we need
and then locally adjust the
-    // tree.
+    // The deletion algorithm must remove N keys, one per column.  We start with the key
for
+    // column N-1, and work back to column 0.
+    // 
+    // Each remove basically occurs independently within its own btree.  In each btree, if
+    // the node has an equals child, that child is promoted and takes on the greater and
lesser children
+    // of the node that is going away.  If there is no equals child, then we promote either
the lesser or
+    // the greater child, and if there are none of those we just remove the node and do nothing
else.
+    //
+    // As part of promoting the lesser or greater child, the other child (if it exists) will
be inserted
+    // into the btree and will be carried to the bottom and linked in.
     
-    // Find its parent
-    WHKey parentKey = readIndexNodeParentKey(rowID);
+    for (int i = columnNames.length ; i > 0 ; i--)
+    {
+      removeFromBtree(rowID,i-1);
+    }
+  }
+  
+  /** Remove a row for a specific column from the corresponding btree.
+  */
+  protected void removeFromBtree(long rowID, int columnIndex)
+    throws WHException
+  {
+    String columnName = columnNames[columnIndex];
     
-    // There are a number of standard situations we look for which maintain the invariant,
before we
-    // resort to more expensive operations.  These are listed below.
-    //
-    // (1) If there's an equals child, promote it to the current position, also moving all
the greater/lesser links.
-    // (2) If there are no greater/lesser links and no equals children, just delete the parent
ref.
-    //
-    // The full algorithm, and the most expensive, is as follows:
-    //
-    // (a) Look through the greater/lesser links in column order.  The first link that's
found is the one that needs to be promoted.
-    // (b) We KNOW there's no equals chain for the node being deleted, but there could be
lower-priority greater/lesser links.  Each
-    //   of these child nodes must be inserted into the node that is being promoted as if
it were a new node.
+    // Build the index node's parent key
+    WHKey parentKey = readIndexNodeParentKey(rowID,columnName);
     
     // Look for an 'equals' child
-    long equalsChild = readIndexNodeEqualsNode(rowID);
+    long equalsChild = readIndexNodeEqualsNode(rowID,columnName);
     if (equalsChild != -1L)
     {
-      // Case (1) (as described above).  Promote the child.
-      deleteIndexNodeEqualsNode(rowID);
-      deleteIndexParentChild(parentKey);
-      setIndexParentChild(parentKey,equalsChild);
+      // Case (1) (as described above).  Promote the child.  We know the child has
+      // no greater/lesser children.
+      deleteIndexNodeEqualsNode(rowID,columnName);
+      deleteIndexParentChild(parentKey,columnName);
+      setIndexParentChild(parentKey,columnName,equalsChild);
       // Now, transfer the delete node's lesser/greater children to the equalsChild.
-      for (int i = 0 ; i < columnNames.length ; i++)
+      long lesserChild = readIndexNodeLesserNode(rowID,columnName);
+      if (lesserChild != -1L)
       {
-        String currentColumn = columnNames[i];
-        long lesserChild = readIndexNodeLesserNode(rowID,currentColumn);
-        if (lesserChild != -1L)
-        {
-          deleteIndexNodeLesserNode(rowID,currentColumn);
-          setIndexNodeLesserNode(equalsChild,currentColumn,lesserChild);
-        }
-        long greaterChild = readIndexNodeGreaterNode(rowID,currentColumn);
-        if (greaterChild != -1L)
-        {
-          deleteIndexNodeGreaterNode(rowID,currentColumn);
-          setIndexNodeGreaterNode(equalsChild,currentColumn,greaterChild);
-        }
+        deleteIndexNodeLesserNode(rowID,columnName);
+        setIndexNodeLesserNode(equalsChild,columnName,lesserChild);
+      }
+      long greaterChild = readIndexNodeGreaterNode(rowID,columnName);
+      if (greaterChild != -1L)
+      {
+        deleteIndexNodeGreaterNode(rowID,columnName);
+        setIndexNodeGreaterNode(equalsChild,columnName,greaterChild);
       }
       return;
     }
@@ -263,53 +294,45 @@ public class Index implements WHIndex
     // arbitrary.  Someday we'll choose to promote the deeper side perhaps...
     
     // First, unhook the whole tree from the parent.
-    deleteIndexParentChild(parentKey);
+    deleteIndexParentChild(parentKey,columnName);
     
     // Now look for a promotion candidate to hook in in its place.
     long promotionCandidate = -1L;
-    for (int i = 0 ; i < columnNames.length ; i++)
+    if (promotionCandidate == -1L)
     {
-      String currentColumn = columnNames[i];
-      promotionCandidate = readIndexNodeLesserNode(rowID,currentColumn);
+      promotionCandidate = readIndexNodeLesserNode(rowID,columnName);
       if (promotionCandidate != -1L)
-      {
         // We found our promotion candidate!
-        deleteIndexNodeLesserNode(rowID,currentColumn);
-        break;
-      }
-      promotionCandidate = readIndexNodeGreaterNode(rowID,currentColumn);
+        deleteIndexNodeLesserNode(rowID,columnName);
+    }
+    if (promotionCandidate == -1L)
+    {
+      promotionCandidate = readIndexNodeGreaterNode(rowID,columnName);
       if (promotionCandidate != -1L)
-      {
         // Candidate found
-        deleteIndexNodeGreaterNode(rowID,currentColumn);
-        break;
-      }
+        deleteIndexNodeGreaterNode(rowID,columnName);
     }
     
     if (promotionCandidate != -1L)
     {
       // Hook in the promotion candidate as child of the parent.
-      setIndexParentChild(parentKey,promotionCandidate);
+      setIndexParentChild(parentKey,columnName,promotionCandidate);
       // Transfer the remaining lesser/greater children into the promotionCandidate node
-      for (int i = 0 ; i < columnNames.length ; i++)
+      long lesserChild = readIndexNodeLesserNode(rowID,columnName);
+      if (lesserChild != -1L)
+      {
+        // Peel it away from the deleteNodeID
+        deleteIndexNodeLesserNode(rowID,columnName);
+        // Now insert this node into promotionCandidate via parentKey
+        placeIntoBtree(lesserChild,parentKey,columnIndex);
+      }
+      long greaterChild = readIndexNodeGreaterNode(rowID,columnName);
+      if (greaterChild != -1L)
       {
-        String currentColumn = columnNames[i];
-        long lesserChild = readIndexNodeLesserNode(rowID,currentColumn);
-        if (lesserChild != -1L)
-        {
-          // Peel it away from the deleteNodeID
-          deleteIndexNodeLesserNode(rowID,currentColumn);
-          // Now insert this node into promotionCandidate via parentKey
-          addNodeInto(lesserChild,parentKey);
-        }
-        long greaterChild = readIndexNodeGreaterNode(rowID,currentColumn);
-        if (greaterChild != -1L)
-        {
-          // Delete the reference from the deletion node
-          deleteIndexNodeGreaterNode(rowID,currentColumn);
-          // Now insert this node into promotionCandidate via parentKey
-          addNodeInto(greaterChild,parentKey);
-        }
+        // Delete the reference from the deletion node
+        deleteIndexNodeGreaterNode(rowID,columnName);
+        // Now insert this node into promotionCandidate via parentKey
+        placeIntoBtree(greaterChild,parentKey,columnIndex);
       }
     }
   }
@@ -338,31 +361,74 @@ public class Index implements WHIndex
   protected void remove()
     throws WHException
   {
-    deleteSubtree(new IndexRootKey(indexName));
+    deleteBtree(new IndexRootKey(indexName),0);
   }
   
-  /** Delete a subtree described by a WHKey */
-  protected void deleteSubtree(WHKey key)
+  /** Delete a single btree with specified column index.
+  */
+  protected void deleteBtree(WHKey key, int indexColumn)
     throws WHException
   {
+    if (indexColumn == columnNames.length)
+      return;
+
+    // For this btree, start with the root
     long child = readIndexParentChild(key);
+    // If there's no root, we are done
     if (child == -1L)
       return;
+    
     // Delete the child.
+    String columnName = columnNames[indexColumn];
     // First, unlink from the parent.
-    deleteIndexParentChild(key);
+    deleteIndexParentChild(key,columnName);
     // Recursively clean up all child links.
-    deleteSubtree(new IndexNodeEqualsKey(indexName,child));
-    for (int i = 0 ; i < columnNames.length ; i++)
-    {
-      String currentColumn = columnNames[i];
-      deleteSubtree(new IndexNodeLesserKey(indexName,child,currentColumn));
-      deleteSubtree(new IndexNodeGreaterKey(indexName,child,currentColumn));
-    }
+    deleteBtree(new IndexNodeEqualsKey(indexName,child,columnName),indexColumn);
+    deleteBtree(new IndexNodeLesserKey(indexName,child,columnName),indexColumn);
+    deleteBtree(new IndexNodeGreaterKey(indexName,child,columnName),indexColumn);
+    // Move on to next column
+    deleteBtree(new IndexNodeColumnKey(indexName,child,columnName),indexColumn+1);
   }
   
   // Protected methods
 
+  /** Get next column's root node for an index node.
+  * This link is necessary in order to allow each tree to rebalance independently.
+  */
+  protected long readIndexNodeColumnNode(long rowID, String columnName)
+    throws WHException
+  {
+    LongValue outRowID = (LongValue)ts.get(new IndexNodeColumnKey(indexName,rowID,columnName));
+    if (outRowID == null)
+      return -1L;
+    return outRowID.getValue();
+  }
+  
+  /** Set next column's root node for an index node.
+  */
+  protected void setIndexNodeColumnNode(long rowID, String columnName, long refRowID)
+    throws WHException
+  {
+    IndexNodeColumnKey key = new IndexNodeColumnKey(indexName,rowID,columnName);
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,refRowID,columnName);
+    ts.put(key,new LongValue(refRowID));
+    ts.put(parentKey,key);
+  }
+
+  /** Delete the column root-node child reference for an index node.  Presumes that the reference
exists.
+  */
+  protected void deleteIndexNodeColumnNode(long rowID, String columnName)
+    throws WHException
+  {
+    IndexNodeColumnKey key = new IndexNodeColumnKey(indexName,rowID,columnName);
+    LongValue childReference = (LongValue)ts.get(key);
+    if (childReference == null)
+      throw new WHDeadlockException();
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,childReference.getValue(),columnName);
+    ts.put(key,null);
+    ts.put(parentKey,null);
+  }
+  
   /** Get the lesser child reference for an index node.
   */
   protected long readIndexNodeLesserNode(long rowID, String columnName)
@@ -380,7 +446,7 @@ public class Index implements WHIndex
     throws WHException
   {
     IndexNodeLesserKey key = new IndexNodeLesserKey(indexName,rowID,columnName);
-    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,refRowID);
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,refRowID,columnName);
     ts.put(key,new LongValue(refRowID));
     ts.put(parentKey,key);
   }
@@ -394,7 +460,7 @@ public class Index implements WHIndex
     LongValue childReference = (LongValue)ts.get(key);
     if (childReference == null)
       throw new WHDeadlockException();
-    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,childReference.getValue());
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,childReference.getValue(),columnName);
     ts.put(key,null);
     ts.put(parentKey,null);
   }
@@ -416,7 +482,7 @@ public class Index implements WHIndex
     throws WHException
   {
     IndexNodeGreaterKey key = new IndexNodeGreaterKey(indexName,rowID,columnName);
-    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,refRowID);
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,refRowID,columnName);
     ts.put(key,new LongValue(refRowID));
     ts.put(parentKey,key);
   }
@@ -430,17 +496,17 @@ public class Index implements WHIndex
     LongValue childReference = (LongValue)ts.get(key);
     if (childReference == null)
       throw new WHDeadlockException();
-    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,childReference.getValue());
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,childReference.getValue(),columnName);
     ts.put(key,null);
     ts.put(parentKey,null);
   }
   
   /** Get the equals child reference for an index node.
   */
-  protected long readIndexNodeEqualsNode(long rowID)
+  protected long readIndexNodeEqualsNode(long rowID, String columnName)
     throws WHException
   {
-    LongValue outRowID = (LongValue)ts.get(new IndexNodeEqualsKey(indexName,rowID));
+    LongValue outRowID = (LongValue)ts.get(new IndexNodeEqualsKey(indexName,rowID,columnName));
     if (outRowID == null)
       return -1L;
     return outRowID.getValue();
@@ -448,35 +514,35 @@ public class Index implements WHIndex
   
   /** Set the equals child reference for an index node.  Presumes that a reference doesn't
yet exist.
   */
-  protected void setIndexNodeEqualsNode(long rowID, long refRowID)
+  protected void setIndexNodeEqualsNode(long rowID, String columnName, long refRowID)
     throws WHException
   {
-    IndexNodeEqualsKey key = new IndexNodeEqualsKey(indexName,rowID);
-    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,refRowID);
+    IndexNodeEqualsKey key = new IndexNodeEqualsKey(indexName,rowID,columnName);
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,refRowID,columnName);
     ts.put(key,new LongValue(refRowID));
     ts.put(parentKey,key);
   }
 
   /** Delete the equals child reference for an index node.  Presumes that the reference exists.
   */
-  protected void deleteIndexNodeEqualsNode(long rowID)
+  protected void deleteIndexNodeEqualsNode(long rowID, String columnName)
     throws WHException
   {
-    IndexNodeEqualsKey key = new IndexNodeEqualsKey(indexName,rowID);
+    IndexNodeEqualsKey key = new IndexNodeEqualsKey(indexName,rowID,columnName);
     LongValue childReference = (LongValue)ts.get(key);
     if (childReference == null)
       throw new WHDeadlockException();
-    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,childReference.getValue());
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,childReference.getValue(),columnName);
     ts.put(key,null);
     ts.put(parentKey,null);
   }
 
   /** Get the parent reference for an index node.
   */
-  protected WHKey readIndexNodeParentKey(long rowID)
+  protected WHKey readIndexNodeParentKey(long rowID, String columnName)
     throws WHException
   {
-    WHKey rval = (WHKey)ts.get(new IndexNodeParentKey(indexName,rowID));
+    WHKey rval = (WHKey)ts.get(new IndexNodeParentKey(indexName,rowID,columnName));
     if (rval == null)
       throw new WHDeadlockException();
     return rval;
@@ -495,16 +561,16 @@ public class Index implements WHIndex
   
   /** Set an index parent's child node.  Presumes this child is not set yet.
   */
-  protected void setIndexParentChild(WHKey parentKey, long rowID)
+  protected void setIndexParentChild(WHKey parentKey, String columnName, long rowID)
     throws WHException
   {
     ts.put(parentKey,new LongValue(rowID));
-    ts.put(new IndexNodeParentKey(indexName,rowID),parentKey);
+    ts.put(new IndexNodeParentKey(indexName,rowID,columnName),parentKey);
   }
   
   /** Remove an index parent's child node reference.  Presumes that this child exists.
   */
-  protected void deleteIndexParentChild(WHKey parentKey)
+  protected void deleteIndexParentChild(WHKey parentKey, String columnName)
     throws WHException
   {
     // Get the existing child
@@ -512,7 +578,7 @@ public class Index implements WHIndex
     if (childNodeRef == null)
       throw new WHDeadlockException();
     ts.put(parentKey,null);
-    ts.put(new IndexNodeParentKey(indexName,childNodeRef.getValue()),null);
+    ts.put(new IndexNodeParentKey(indexName,childNodeRef.getValue(),columnName),null);
   }
   
   /** Get the root pointer for an index.
@@ -528,25 +594,25 @@ public class Index implements WHIndex
   
   /** Set the root pointer for an index.  Presumes the root pointer does not currently exist.
   */
-  protected void setIndexRootNode(long rootRowID)
+  protected void setIndexRootNode(long rootRowID, String columnName)
     throws WHException
   {
     IndexRootKey key = new IndexRootKey(indexName);
-    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,rootRowID);
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,rootRowID,columnName);
     ts.put(key,new LongValue(rootRowID));
     ts.put(parentKey,key);
   }
 
   /** Delete the root node reference for an index.  Presumes that the reference exists.
   */
-  protected void deleteIndexRootNode()
+  protected void deleteIndexRootNode(String columnName)
     throws WHException
   {
     IndexRootKey key = new IndexRootKey(indexName);
     LongValue childReference = (LongValue)ts.get(key);
     if (childReference == null)
       throw new WHDeadlockException();
-    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,childReference.getValue());
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,childReference.getValue(),columnName);
     ts.put(key,null);
     ts.put(parentKey,null);
   }

Modified: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexAccessor.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexAccessor.java?rev=1204771&r1=1204770&r2=1204771&view=diff
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexAccessor.java
(original)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexAccessor.java
Tue Nov 22 01:06:41 2011
@@ -59,7 +59,7 @@ public class IndexAccessor implements WH
     this.indexCriteria = indexCriteria;
     long rootRowID = index.readIndexRootNode();
     if (rootRowID != -1L)
-      queue.pushNeedsAnalysis(rootRowID);
+      queue.pushNeedsAnalysis(rootRowID,0);
   }
     
   /** Are there any more rows?
@@ -103,10 +103,11 @@ public class IndexAccessor implements WH
       if (node.getAction() == ACTION_CHASE_EQUALS)
       {
         // We can skip all analysis, and just chase the equals chain.
-        long rowID = node.getRowID();
-        queue.pushNeedsDereference(rowID);
+        long chaseRowID = node.getRowID();
+        // Push the rowID, then chase the equals chain.
+        queue.pushNeedsDereference(chaseRowID);
         // Now find the next node in the equals chain.
-        long nextEqualsNode = index.readIndexNodeEqualsNode(rowID);
+        long nextEqualsNode = index.readIndexNodeEqualsNode(chaseRowID,indexColumns[indexColumns.length-1]);
         if (nextEqualsNode != -1L)
         {
           // Because it's equals chain, we know that it is unnecessary to evaluate its fields,
so note that when
@@ -117,6 +118,9 @@ public class IndexAccessor implements WH
       }
       
       // This node needs analysis.
+      int columnIndex = node.getColumnIndex();
+      long rowID = node.getRowID();
+      
       // Evaluate the node, pushing its descendents, and make a decision whether to
       // use the row or not.
       
@@ -124,67 +128,46 @@ public class IndexAccessor implements WH
       // We can only add at the beginning of the queue, so we must be careful to push
       // nodes in backwards order!!
       
-      handleColumn(node.getRowID(),0);
-      
-      // Back around until we have a node, or until we hit the end
-    }
-  }
-  
-  /** Handle a single column with the correct ordering of nodes on the queue.
-  */
-  protected void handleColumn(long rowID, int columnIndex)
-    throws WHException
-  {
-    if (columnIndex == indexColumns.length)
-    {
-      // We hit the end, which means we've got a match.
-      queue.pushNeedsDereference(rowID);
-      // Now find the next node in the equals chain.
-      long nextEqualsNode = index.readIndexNodeEqualsNode(rowID);
-      if (nextEqualsNode != -1L)
+      // Evaluate this column
+      String currentColumn = indexColumns[columnIndex];
+      // Get the column value
+      WHValue columnValue = index.getTable().getValue(rowID,currentColumn);
+
+      // Do the assessment, if there are index criteria for this column
+      int criteria;
+      if (indexCriteria != null && indexCriteria[columnIndex] != null)
+        criteria = indexCriteria[columnIndex].evaluateValue(columnValue,comparators[columnIndex]);
+      else
+        criteria = IndexCriteria.SIGNAL_LESSER | IndexCriteria.SIGNAL_GREATER | IndexCriteria.SIGNAL_EQUALS;
+
+      // Remember, we want to push greater values first, then lesser.
+      if ((criteria & IndexCriteria.SIGNAL_GREATER) != 0)
       {
-        // Because it's equals chain, we know that it is unnecessary to evaluate its fields,
so note that when
-        // we queue it.
-        queue.pushChaseEquals(nextEqualsNode);
+        // Dereference the greater child for this column and push that node for analysis
+        long childRowID = index.readIndexNodeGreaterNode(rowID,indexColumns[columnIndex]);
+        if (childRowID != -1L)
+          queue.pushNeedsAnalysis(childRowID,columnIndex);
+      }
+      // Do the equals children next
+      if ((criteria & IndexCriteria.SIGNAL_EQUALS) != 0)
+      {
+        // We want to continue on to the next column, or if we're at the end, we take the
+        // row ID. 
+        if (columnIndex + 1 == indexColumns.length)
+          queue.pushChaseEquals(rowID);
+        else
+          queue.pushNeedsAnalysis(index.readIndexNodeColumnNode(rowID,indexColumns[columnIndex]),columnIndex+1);
+      }
+      if ((criteria & IndexCriteria.SIGNAL_LESSER) != 0)
+      {
+        // Dereference the lesser child for this column and push that node for analysis
+        long childRowID = index.readIndexNodeLesserNode(rowID,indexColumns[columnIndex]);
+        if (childRowID != -1L)
+          queue.pushNeedsAnalysis(childRowID,columnIndex);
       }
-      return;
-    }
-    
-    // Evaluate this column
-    String currentColumn = indexColumns[columnIndex];
-    // Get the column value
-    WHValue columnValue = index.getTable().getValue(rowID,currentColumn);
-
-    // Do the assessment, if there are index criteria for this column
-    int criteria;
-    if (indexCriteria != null && indexCriteria[columnIndex] != null)
-      criteria = indexCriteria[columnIndex].evaluateValue(columnValue,comparators[columnIndex]);
-    else
-      criteria = IndexCriteria.SIGNAL_LESSER | IndexCriteria.SIGNAL_GREATER | IndexCriteria.SIGNAL_EQUALS;
-        
-    // Remember, we want to push greater values first, then lesser.
-    if ((criteria & IndexCriteria.SIGNAL_GREATER) != 0)
-    {
-      // Dereference the greater child for this column and push that node for analysis
-      long childRowID = index.readIndexNodeGreaterNode(rowID,currentColumn);
-      if (childRowID != -1L)
-        queue.pushNeedsAnalysis(childRowID);
-    }
-    if ((criteria & IndexCriteria.SIGNAL_EQUALS) != 0)
-    {
-      // We want to continue on to the next column, or if we're at the end, we take the
-      // row ID. 
-      handleColumn(rowID,columnIndex+1);
-    }
-    if ((criteria & IndexCriteria.SIGNAL_LESSER) != 0)
-    {
-      // Dereference the lesser child for this column and push that node for analysis
-      long childRowID = index.readIndexNodeLesserNode(rowID,currentColumn);
-      if (childRowID != -1L)
-        queue.pushNeedsAnalysis(childRowID);
     }
   }
-
+  
   // The types of actions we need the engine to understand, which must be signaled in the
queue
   /** Full analysis */
   protected static final int ACTION_FULL_ANALYSIS = 0;
@@ -202,19 +185,19 @@ public class IndexAccessor implements WH
     {
     }
     
-    public void pushNeedsAnalysis(long rowID)
+    public void pushNeedsAnalysis(long rowID, int columnIndex)
     {
-      nodeList.add(new Node(rowID,ACTION_FULL_ANALYSIS));
+      nodeList.add(new Node(rowID,columnIndex,ACTION_FULL_ANALYSIS));
     }
     
     public void pushChaseEquals(long rowID)
     {
-      nodeList.add(new Node(rowID,ACTION_CHASE_EQUALS));
+      nodeList.add(new Node(rowID,-1,ACTION_CHASE_EQUALS));
     }
     
     public void pushNeedsDereference(long rowID)
     {
-      nodeList.add(new Node(rowID,ACTION_DEREFERENCE));
+      nodeList.add(new Node(rowID,-1,ACTION_DEREFERENCE));
     }
     
     public Node pop()
@@ -229,12 +212,14 @@ public class IndexAccessor implements WH
   protected static class Node
   {
     protected long rowID;
+    protected int columnIndex;
     protected int action;
     
     /** Constructor */
-    public Node(long rowID, int action)
+    public Node(long rowID, int columnIndex, int action)
     {
       this.rowID = rowID;
+      this.columnIndex = columnIndex;
       this.action = action;
     }
     
@@ -245,6 +230,13 @@ public class IndexAccessor implements WH
       return rowID;
     }
     
+    /** Get the column index.
+    */
+    public int getColumnIndex()
+    {
+      return columnIndex;
+    }
+    
     /** Get whether this node should be treated as needing dereference or needing analysis.
     */
     public int getAction()

Added: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeColumnKey.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeColumnKey.java?rev=1204771&view=auto
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeColumnKey.java
(added)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeColumnKey.java
Tue Nov 22 01:06:41 2011
@@ -0,0 +1,38 @@
+/* $Id$ */
+
+/**
+* Licensed to the Apache Software Foundation (ASF) under one or more
+* contributor license agreements. See the NOTICE file distributed with
+* this work for additional information regarding copyright ownership.
+* The ASF licenses this file to You under the Apache License, Version 2.0
+* (the "License"); you may not use this file except in compliance with
+* the License. You may obtain a copy of the License at
+*
+* http://www.apache.org/licenses/LICENSE-2.0
+*
+* Unless required by applicable law or agreed to in writing, software
+* distributed under the License is distributed on an "AS IS" BASIS,
+* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+* See the License for the specific language governing permissions and
+* limitations under the License.
+*/
+
+package org.apache.warthog.tablestore;
+
+import org.apache.warthog.interfaces.*;
+import org.apache.warthog.common.*;
+
+/** Index node next column pointer key */
+public class IndexNodeColumnKey extends IndexNodeKey
+{
+  /** Constructor */
+  public IndexNodeColumnKey(String indexName, long rowID, String columnName)
+  {
+    super(indexName,rowID,columnName);
+  }
+    
+  public IndexNodeColumnKey(byte[] data)
+  {
+    super(data);
+  }
+}
\ No newline at end of file

Propchange: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeColumnKey.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeColumnKey.java
------------------------------------------------------------------------------
    svn:keywords = Id

Modified: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeEqualsKey.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeEqualsKey.java?rev=1204771&r1=1204770&r2=1204771&view=diff
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeEqualsKey.java
(original)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeEqualsKey.java
Tue Nov 22 01:06:41 2011
@@ -22,46 +22,17 @@ package org.apache.warthog.tablestore;
 import org.apache.warthog.interfaces.*;
 import org.apache.warthog.common.*;
 
-/** Key for the btree link when all index criteria are the same */
-public class IndexNodeEqualsKey implements WHKey
+/** Index node equals pointer key */
+public class IndexNodeEqualsKey extends IndexNodeKey
 {
-  protected String indexName;
-  protected long rowID;
-    
   /** Constructor */
-  public IndexNodeEqualsKey(String indexName, long rowID)
+  public IndexNodeEqualsKey(String indexName, long rowID, String columnName)
   {
-    this.indexName = indexName;
-    this.rowID = rowID;
+    super(indexName,rowID,columnName);
   }
     
   public IndexNodeEqualsKey(byte[] data)
   {
-    BufferPointer bp = new BufferPointer(data);
-    this.indexName = StringKey.readObject(bp);
-    this.rowID = LongKey.readObject(bp);
-  }
-
-  public byte[] serializeObject()
-  {
-    byte[] rval = new byte[StringKey.sizeObject(indexName)+
-      LongKey.sizeObject()];
-    BufferPointer bp = new BufferPointer(rval);
-    StringKey.writeObject(bp,indexName);
-    LongKey.writeObject(bp,rowID);
-    return rval;
+    super(data);
   }
-    
-  public long getHashCode()
-  {
-    return StringKey.calculateHashCode(indexName) + LongKey.calculateHashCode(rowID);
-  }
-    
-  public boolean isEquals(WHKey o)
-  {
-    IndexNodeEqualsKey key = (IndexNodeEqualsKey)o;
-    return key.indexName.equals(indexName) &&
-      key.rowID == rowID;
-  }
-
-}
+}
\ No newline at end of file

Modified: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeParentKey.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeParentKey.java?rev=1204771&r1=1204770&r2=1204771&view=diff
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeParentKey.java
(original)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeParentKey.java
Tue Nov 22 01:06:41 2011
@@ -24,45 +24,16 @@ import org.apache.warthog.common.*;
 
 /** Key for the btree link to its parent reference (NOT node; WHKey).  This allows
 * us to perform fast in-context deletions. */
-public class IndexNodeParentKey implements WHKey
+public class IndexNodeParentKey extends IndexNodeKey
 {
-  protected String indexName;
-  protected long rowID;
-    
   /** Constructor */
-  public IndexNodeParentKey(String indexName, long rowID)
+  public IndexNodeParentKey(String indexName, long rowID, String columnName)
   {
-    this.indexName = indexName;
-    this.rowID = rowID;
+    super(indexName,rowID,columnName);
   }
     
   public IndexNodeParentKey(byte[] data)
   {
-    BufferPointer bp = new BufferPointer(data);
-    this.indexName = StringKey.readObject(bp);
-    this.rowID = LongKey.readObject(bp);
-  }
-
-  public byte[] serializeObject()
-  {
-    byte[] rval = new byte[StringKey.sizeObject(indexName)+
-      LongKey.sizeObject()];
-    BufferPointer bp = new BufferPointer(rval);
-    StringKey.writeObject(bp,indexName);
-    LongKey.writeObject(bp,rowID);
-    return rval;
+    super(data);
   }
-    
-  public long getHashCode()
-  {
-    return StringKey.calculateHashCode(indexName) + LongKey.calculateHashCode(rowID);
-  }
-    
-  public boolean isEquals(WHKey o)
-  {
-    IndexNodeParentKey key = (IndexNodeParentKey)o;
-    return key.indexName.equals(indexName) &&
-      key.rowID == rowID;
-  }
-
 }



Mime
View raw message