incubator-connectors-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kwri...@apache.org
Subject svn commit: r1204224 - in /incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog: interfaces/ tablestore/
Date Sun, 20 Nov 2011 19:32:58 GMT
Author: kwright
Date: Sun Nov 20 19:32:57 2011
New Revision: 1204224

URL: http://svn.apache.org/viewvc?rev=1204224&view=rev
Log:
Add indexes

Added:
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHRowID.java   (with props)
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexAccessor.java   (with props)
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeEqualsKey.java   (with props)
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeGreaterKey.java   (with props)
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeKey.java   (with props)
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeLesserKey.java   (with props)
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeParentKey.java   (with props)
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeRowRefKey.java   (with props)
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexRootKey.java   (with props)
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexRowNodeRefKey.java   (with props)
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/LongRowID.java   (with props)
Modified:
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHIndex.java
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHTable.java
    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/Table.java
    incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/TableStore.java

Modified: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHIndex.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHIndex.java?rev=1204224&r1=1204223&r2=1204224&view=diff
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHIndex.java (original)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHIndex.java Sun Nov 20 19:32:57 2011
@@ -24,6 +24,11 @@ package org.apache.warthog.interfaces;
 */
 public interface WHIndex
 {
+  /** Get the index name.
+  */
+  public String getName()
+    throws WHException;
+
   /** Get the table the index applies to.
   */
   public WHTable getTable()
@@ -45,16 +50,7 @@ public interface WHIndex
   * criteria must align with the index's columns.  Null values are permitted where
   * no criteria are present.
   */
-  public WHAccessor buildAccessor(IndexCriteria[] criteria);
-  
-  // Below this line are methods that are not meant to be used for general purposes,
-  // which may be moved to implementation classes.
-  
-  /** Get the comparators corresponding to the columns.
-  * Effectively also returns the index order for each of those columns
-  * (as determined by the comparator).
-  */
-  public WHComparator[] getComparators()
+  public WHAccessor buildAccessor(IndexCriteria[] criteria)
     throws WHException;
   
 }

Added: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHRowID.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHRowID.java?rev=1204224&view=auto
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHRowID.java (added)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHRowID.java Sun Nov 20 19:32:57 2011
@@ -0,0 +1,32 @@
+/* $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.interfaces;
+
+/** This interface describes a kind of key or value that is used to describe
+* a table row.  For simple tables, the implementation is likely to be just a 
+* LongValue, but for joins there is likely to be a compound value consisting of
+* individual WHRowID's from each table participating in the join.  The basic
+* idea is that the precise form of a row ID is only known to the relationship
+* from which it came (and in which it will be interpreted).
+*/
+public interface WHRowID extends WHKey
+{
+  // Right at the moment, there's no special methods needed
+}

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

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

Modified: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHTable.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHTable.java?rev=1204224&r1=1204223&r2=1204224&view=diff
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHTable.java (original)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/interfaces/WHTable.java Sun Nov 20 19:32:57 2011
@@ -25,6 +25,11 @@ package org.apache.warthog.interfaces;
 */
 public interface WHTable
 {
+  /** Get the table name.
+  */
+  public String getName()
+    throws WHException;
+
   /** Get the column names.
   */
   public String[] getColumnNames()

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=1204224&r1=1204223&r2=1204224&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 Sun Nov 20 19:32:57 2011
@@ -20,6 +20,7 @@
 package org.apache.warthog.tablestore;
 
 import org.apache.warthog.interfaces.*;
+import org.apache.warthog.common.*;
 
 /** This is the standard implementation of WHIndex.
 */
@@ -29,18 +30,30 @@ public class Index implements WHIndex
   protected Table table;
   protected String indexName;
   protected String[] columnNames;
-  protected String[] comparatorClasses;
+  protected WHComparator[] comparators;
   protected boolean unique;
   
   /** Constructor */
   public Index(TableStore ts, Table table, String indexName, String[] columnNames, String[] comparatorClasses, boolean unique)
+    throws WHException
   {
     this.ts = ts;
     this.table = table;
     this.indexName = indexName;
     this.columnNames = columnNames;
-    this.comparatorClasses = comparatorClasses;
     this.unique = unique;
+    this.comparators = new WHComparator[comparatorClasses.length];
+    try
+    {
+      for (int i = 0 ; i < comparators.length ; i++)
+      {
+        this.comparators[i] = (WHComparator)Class.forName(comparatorClasses[i]).newInstance();
+      }
+    }
+    catch (Exception e)
+    {
+      throw new WHException("Error instantiating comparator class for index '"+indexName+"': "+e.getMessage(),e);
+    }
   }
   
   /** Get the table the index applies to.
@@ -64,46 +77,507 @@ public class Index implements WHIndex
   * no criteria are present.
   */
   public WHAccessor buildAccessor(IndexCriteria[] criteria)
+    throws WHException
   {
-    // MHL
-    return null;
+    return new IndexAccessor(ts,this,criteria);
   }
   
+  /** Get the index name */
+  public String getName()
+    throws WHException
+  {
+    return indexName;
+  }
+
   // Below this line are methods that are not meant to be used for general purposes,
-  // which may be moved to implementation classes.
   
-  /** Get the comparators corresponding to the columns.
-  * Effectively also returns the index order for each of those columns
-  * (as determined by the comparator).
+  /** Get the comparators.
   */
-  public WHComparator[] getComparators()
-    throws WHException
+  protected WHComparator[] getComparators()
   {
-    // MHL
-    return null;
+    return comparators;
   }
   
   /** Add a new row to the index.
+  * The row must already exist in the underlying table.
+  */
+  protected void addNewRow(long rowID)
+    throws WHException
+  {
+    // The algorithm here simply involves finding the right spot and adding a new node at that point.
+    // We should also rebalance the tree at that point, but that's going to be implemented in phase II.
+    
+    // First, create the new node
+    long newNodeID = allocateNextIndexNode();
+    // Set the rowID pointer for the new node, and visa versa.
+    setIndexNodeTableRow(newNodeID,rowID);
+    
+    addNodeInto(newNodeID,new IndexRootKey(indexName),rowID);
+  }
+  
+  /** Method to add a given node into a subtree where we start only with a parent key.
   */
-  public void addNewRow(long rowID)
+  protected void addNodeInto(long newNodeID, WHKey parentKey, long rowID)
     throws WHException
   {
-    // MHL
+    // Keep going until we've found the insertion point
+    WHValue[] newRowIndexValues = null;
+    while (true)
+    {
+      // Pick up the current node from the parent
+      long currentNodeID = readIndexParentChild(parentKey);
+      if (currentNodeID == -1L)
+      {
+        // Our new node is the root node; set the root node accordingly
+        setIndexParentChild(parentKey,newNodeID);
+        return;
+      }
+
+      // 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] = ts.getTableColumnValue(table.getName(),rowID,columnNames[i]);
+        }
+      }
+      
+      // We evaluate against the row described by the current node ID, which means we need to fetch it
+      long nodeRowID = readIndexNodeTableRow(currentNodeID);
+      // 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 = ts.getTableColumnValue(table.getName(),nodeRowID,currentColumn);
+        int comparatorResult = comparators[i].compare(currentValue,newRowIndexValues[i]);
+        // Based on the result, decide which way to go
+        long nextNodeID;
+        switch (comparatorResult)
+        {
+        case WHComparator.RESULT_LESS:
+          // Descend the lesser tree for this column.
+          parentKey = new IndexNodeLesserKey(indexName,currentNodeID,currentColumn);
+          newNodeFound = true;
+          break;
+        case WHComparator.RESULT_GREATER:
+          // Descend the greater tree for this column.
+          parentKey = new IndexNodeGreaterKey(indexName,currentNodeID,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
+      }
+      
+      // We've either found an exact match, or the node has been changed and we have to start over.
+      if (newNodeFound)
+        continue;
+      
+      // Equals result.  We found a node which is identical to the one we are adding.
+      if (unique)
+      {
+        // 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.
+        throw new WHDeadlockException();
+      }
+      
+      // We keep a linked list of identical nodes.  We can insert into that chain at any point.
+      // 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 currentEqualsNode = readIndexNodeEqualsNode(currentNodeID);
+      
+      // Move the old pointer to the new position
+      if (currentEqualsNode != -1L)
+      {
+        // Delete the old one
+        deleteIndexNodeEqualsNode(currentNodeID);
+        // Move the pointer to the child of the node we just created
+        setIndexNodeEqualsNode(newNodeID,currentEqualsNode);
+      }
+      
+      // Now, set the new ref.
+      setIndexNodeEqualsNode(currentNodeID,newNodeID);
+      
+      return;
+    }
   }
   
   /** Remove a row from the index.  The row must currently exist.
   */
-  public void deleteRow(long rowID)
+  protected void deleteRow(long rowID)
     throws WHException
   {
-    // MHL
+    // The strategy for deletion is to use the back pointers to locate everything we need and then locally adjust the
+    // tree.
+    
+    // First, find the nodeID corresponding to the rowID we're deleting
+    long deleteNodeID = readTableRowIndexNode(rowID);
+    // Also find its parent
+    WHKey parentKey = readIndexNodeParentKey(deleteNodeID);
+    
+    // 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.
+    
+    // Look for an 'equals' child
+    long equalsChild = readIndexNodeEqualsNode(deleteNodeID);
+    if (equalsChild != -1L)
+    {
+      // Case (1) (as described above).  Promote the child.
+      deleteIndexNodeEqualsNode(deleteNodeID);
+      deleteIndexParentChild(parentKey);
+      setIndexParentChild(parentKey,equalsChild);
+      // Now, transfer the delete node's lesser/greater children to the equalsChild.
+      for (int i = 0 ; i < columnNames.length ; i++)
+      {
+        String currentColumn = columnNames[i];
+        long lesserChild = readIndexNodeLesserNode(deleteNodeID,currentColumn);
+        if (lesserChild != -1L)
+        {
+          deleteIndexNodeLesserNode(deleteNodeID,currentColumn);
+          setIndexNodeLesserNode(equalsChild,currentColumn,lesserChild);
+        }
+        long greaterChild = readIndexNodeGreaterNode(deleteNodeID,currentColumn);
+        if (greaterChild != -1L)
+        {
+          deleteIndexNodeGreaterNode(deleteNodeID,currentColumn);
+          setIndexNodeGreaterNode(equalsChild,currentColumn,greaterChild);
+        }
+      }
+      // Now remove the index reference to the rowID, and we're done
+      deleteIndexNodeTableRow(deleteNodeID);
+      return;
+    }
+    
+    // No equals chain.  Instead we look for a node to be promoted.
+    
+    // The column priority is fixed and will not change, but the priority of lesser vs. greater is
+    // arbitrary.  Someday we'll choose to promote the deeper side perhaps...
+    
+    // First, unhook the whole tree from the parent.
+    deleteIndexParentChild(parentKey);
+    
+    // Now look for a promotion candidate to hook in in its place.
+    long promotionCandidate = -1L;
+    for (int i = 0 ; i < columnNames.length ; i++)
+    {
+      String currentColumn = columnNames[i];
+      promotionCandidate = readIndexNodeLesserNode(deleteNodeID,currentColumn);
+      if (promotionCandidate != -1L)
+      {
+        // We found our promotion candidate!
+        deleteIndexNodeLesserNode(deleteNodeID,currentColumn);
+        break;
+      }
+      promotionCandidate = readIndexNodeGreaterNode(deleteNodeID,currentColumn);
+      if (promotionCandidate != -1L)
+      {
+        // Candidate found
+        deleteIndexNodeGreaterNode(deleteNodeID,currentColumn);
+        break;
+      }
+    }
+    
+    if (promotionCandidate != -1L)
+    {
+      // Hook in the promotion candidate as child of the parent.
+      setIndexParentChild(parentKey,promotionCandidate);
+      // Transfer the remaining lesser/greater children into the promotionCandidate node
+      for (int i = 0 ; i < columnNames.length ; i++)
+      {
+        String currentColumn = columnNames[i];
+        long lesserChild = readIndexNodeLesserNode(deleteNodeID,currentColumn);
+        if (lesserChild != -1L)
+        {
+          // Peel it away from the deleteNodeID
+          deleteIndexNodeLesserNode(deleteNodeID,currentColumn);
+          // Now insert this node into promotionCandidate via parentKey
+          addNodeInto(lesserChild,parentKey,readIndexNodeTableRow(lesserChild));
+        }
+        long greaterChild = readIndexNodeGreaterNode(deleteNodeID,currentColumn);
+        if (greaterChild != -1L)
+        {
+          // Delete the reference from the deletion node
+          deleteIndexNodeGreaterNode(deleteNodeID,currentColumn);
+          // Now insert this node into promotionCandidate via parentKey
+          addNodeInto(greaterChild,parentKey,readIndexNodeTableRow(greaterChild));
+        }
+      }
+    }
+    
+    // Delete the row reference, to complete the node destruction.
+    deleteIndexNodeTableRow(deleteNodeID);
   }
   
-  /** Get the index name */
-  public String getName()
+  
+  // Protected methods
+  
+  /** Allocate the next index node number.
+  */
+  protected long allocateNextIndexNode()
     throws WHException
   {
-    return indexName;
+    IndexNodeIDFactoryKey tlk = new IndexNodeIDFactoryKey(indexName);
+    LongValue tlv = (LongValue)ts.get(tlk);
+    if (tlv == null)
+      throw new WHDeadlockException();
+    long rval = tlv.getValue();
+    ts.put(tlk,new LongValue(rval+1L));
+    return rval;
+  }
+
+  
+  /** Get the table row for an index node.
+  */
+  protected long readIndexNodeTableRow(long nodeID)
+    throws WHException
+  {
+    LongValue rowID = (LongValue)ts.get(new IndexNodeRowRefKey(indexName,nodeID));
+    if (rowID == null)
+      throw new WHDeadlockException();
+    return rowID.getValue();
+  }
+
+  /** Get the index node for a table row.
+  */
+  protected long readTableRowIndexNode(long rowID)
+    throws WHException
+  {
+    LongValue nodeID = (LongValue)ts.get(new IndexRowNodeRefKey(indexName,rowID));
+    if (nodeID == null)
+      throw new WHDeadlockException();
+    return nodeID.getValue();
+  }
+  
+  /** Set the table row for an index node, and visa versa.  Presumes that no such reference already exists.
+  */
+  protected void setIndexNodeTableRow(long nodeID, long rowID)
+    throws WHException
+  {
+    // Sets both forward and back pointers!!
+    ts.put(new IndexNodeRowRefKey(indexName,nodeID),new LongValue(rowID));
+    ts.put(new IndexRowNodeRefKey(indexName,rowID),new LongValue(nodeID));
+  }
+  
+  /** Delete the table row for an index node.  Presumes that there is a non-null reference.
+  */
+  protected void deleteIndexNodeTableRow(long nodeID)
+    throws WHException
+  {
+    IndexNodeRowRefKey key = new IndexNodeRowRefKey(indexName,nodeID);
+    LongValue rowIDRef = (LongValue)ts.get(key);
+    if (rowIDRef == null)
+      throw new WHDeadlockException();
+    ts.put(key,null);
+    ts.put(new IndexRowNodeRefKey(indexName,rowIDRef.getValue()),null);
+  }
+
+  /** Get the lesser child reference for an index node.
+  */
+  protected long readIndexNodeLesserNode(long nodeID, String columnName)
+    throws WHException
+  {
+    LongValue outNodeID = (LongValue)ts.get(new IndexNodeLesserKey(indexName,nodeID,columnName));
+    if (outNodeID == null)
+      return -1L;
+    return outNodeID.getValue();
+  }
+
+  /** Set the lesser child reference for an index node.  Presumes that no such reference already exists.
+  */
+  protected void setIndexNodeLesserNode(long nodeID, String columnName, long refNodeID)
+    throws WHException
+  {
+    IndexNodeLesserKey key = new IndexNodeLesserKey(indexName,nodeID,columnName);
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,refNodeID);
+    ts.put(key,new LongValue(refNodeID));
+    ts.put(parentKey,key);
+  }
+
+  /** Delete the lesser child reference for an index node.  Presumes that the reference exists.
+  */
+  protected void deleteIndexNodeLesserNode(long nodeID, String columnName)
+    throws WHException
+  {
+    IndexNodeLesserKey key = new IndexNodeLesserKey(indexName,nodeID,columnName);
+    LongValue childReference = (LongValue)ts.get(key);
+    if (childReference == null)
+      throw new WHDeadlockException();
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,childReference.getValue());
+    ts.put(key,null);
+    ts.put(parentKey,null);
+  }
+
+  /** Get the greater child reference for an index node.
+  */
+  protected long readIndexNodeGreaterNode(long nodeID, String columnName)
+    throws WHException
+  {
+    LongValue outNodeID = (LongValue)ts.get(new IndexNodeGreaterKey(indexName,nodeID,columnName));
+    if (outNodeID == null)
+      return -1L;
+    return outNodeID.getValue();
+  }
+  
+  /** Set the greater child reference for an index node.  Presumes that the reference is currently empty.
+  */
+  protected void setIndexNodeGreaterNode(long nodeID, String columnName, long refNodeID)
+    throws WHException
+  {
+    IndexNodeGreaterKey key = new IndexNodeGreaterKey(indexName,nodeID,columnName);
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,refNodeID);
+    ts.put(key,new LongValue(refNodeID));
+    ts.put(parentKey,key);
+  }
+
+  /** Delete the greater child reference for an index node.  Presumes that the reference exists.
+  */
+  protected void deleteIndexNodeGreaterNode(long nodeID, String columnName)
+    throws WHException
+  {
+    IndexNodeGreaterKey key = new IndexNodeGreaterKey(indexName,nodeID,columnName);
+    LongValue childReference = (LongValue)ts.get(key);
+    if (childReference == null)
+      throw new WHDeadlockException();
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,childReference.getValue());
+    ts.put(key,null);
+    ts.put(parentKey,null);
+  }
+  
+  /** Get the equals child reference for an index node.
+  */
+  protected long readIndexNodeEqualsNode(long nodeID)
+    throws WHException
+  {
+    LongValue outNodeID = (LongValue)ts.get(new IndexNodeEqualsKey(indexName,nodeID));
+    if (outNodeID == null)
+      return -1L;
+    return outNodeID.getValue();
+  }
+  
+  /** Set the equals child reference for an index node.  Presumes that a reference doesn't yet exist.
+  */
+  protected void setIndexNodeEqualsNode(long nodeID, long refNodeID)
+    throws WHException
+  {
+    IndexNodeEqualsKey key = new IndexNodeEqualsKey(indexName,nodeID);
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,refNodeID);
+    ts.put(key,new LongValue(refNodeID));
+    ts.put(parentKey,key);
+  }
+
+  /** Delete the equals child reference for an index node.  Presumes that the reference exists.
+  */
+  protected void deleteIndexNodeEqualsNode(long nodeID)
+    throws WHException
+  {
+    IndexNodeEqualsKey key = new IndexNodeEqualsKey(indexName,nodeID);
+    LongValue childReference = (LongValue)ts.get(key);
+    if (childReference == null)
+      throw new WHDeadlockException();
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,childReference.getValue());
+    ts.put(key,null);
+    ts.put(parentKey,null);
+  }
+
+  /** Get the parent reference for an index node.
+  */
+  protected WHKey readIndexNodeParentKey(long nodeID)
+    throws WHException
+  {
+    WHKey rval = (WHKey)ts.get(new IndexNodeParentKey(indexName,nodeID));
+    if (rval == null)
+      throw new WHDeadlockException();
+    return rval;
   }
   
+  /** Read the child node of a specified parent node.
+  */
+  protected long readIndexParentChild(WHKey parentKey)
+    throws WHException
+  {
+    LongValue value = (LongValue)ts.get(parentKey);
+    if (value == null)
+      return -1L;
+    return value.getValue();
+  }
+  
+  /** Set an index parent's child node.  Presumes this child is not set yet.
+  */
+  protected void setIndexParentChild(WHKey parentKey, long nodeID)
+    throws WHException
+  {
+    ts.put(parentKey,new LongValue(nodeID));
+    ts.put(new IndexNodeParentKey(indexName,nodeID),parentKey);
+  }
+  
+  /** Remove an index parent's child node reference.  Presumes that this child exists.
+  */
+  protected void deleteIndexParentChild(WHKey parentKey)
+    throws WHException
+  {
+    // Get the existing child
+    LongValue childNodeRef = (LongValue)ts.get(parentKey);
+    if (childNodeRef == null)
+      throw new WHDeadlockException();
+    ts.put(parentKey,null);
+    ts.put(new IndexNodeParentKey(indexName,childNodeRef.getValue()),null);
+  }
+  
+  /** Get the root pointer for an index.
+  */
+  protected long readIndexRootNode()
+    throws WHException
+  {
+    LongValue outNodeID = (LongValue)ts.get(new IndexRootKey(indexName));
+    if (outNodeID == null)
+      return -1L;
+    return outNodeID.getValue();
+  }
+  
+  /** Set the root pointer for an index.  Presumes the root pointer does not currently exist.
+  */
+  protected void setIndexRootNode(long rootNodeID)
+    throws WHException
+  {
+    IndexRootKey key = new IndexRootKey(indexName);
+    IndexNodeParentKey parentKey = new IndexNodeParentKey(indexName,rootNodeID);
+    ts.put(key,new LongValue(rootNodeID));
+    ts.put(parentKey,key);
+  }
+
+  /** Delete the root node reference for an index.  Presumes that the reference exists.
+  */
+  protected void deleteIndexRootNode()
+    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());
+    ts.put(key,null);
+    ts.put(parentKey,null);
+  }
+  
+
 }

Added: 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=1204224&view=auto
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexAccessor.java (added)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexAccessor.java Sun Nov 20 19:32:57 2011
@@ -0,0 +1,263 @@
+/* $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.*;
+import java.util.*;
+
+/** Index accessor, with criteria.
+* The problem with writing an index accessor is the requirement that you be allowed to remove the node you just returned without anything bad
+* happening to the state.  This restriction severely limits how we can store the 'current node'.  Keeping state in a 'stack' won't work because
+* the parent node may well be destroyed, and thus when it becomes time to "pop" up a level we'll have meaningless state to work with.
+* The alternative - keeping a back pointer for each node - is better, since it allows us to keep the entire state using one node reference, but
+* it too has problems.  Specifically, all state is lost when descent into the child occurs, so upon returning to the parent, we don't know where
+* we are or which branches we've already taken.
+*
+* Another alternative is to keep nodes that we've "discovered" in an in-memory ordered queue.  Thus, when we visit a node, we assess immediately
+* which branches we will be taking, and which we will be skipping, and push the "taking" node id's onto the queue in proper order before doing anything else.
+* Since we pull nodes off the queue from the front, and since only that node can be deleted, by definition we cannot mess up the queue.  This is the
+* alternative this class uses.
+*/
+public class IndexAccessor implements WHAccessor
+{
+  protected TableStore ts;
+  protected Index index;
+  protected String tableName;
+  protected String[] indexColumns;
+  protected WHComparator[] comparators;
+  protected IndexCriteria[] indexCriteria;
+
+  /** This is the current node queue.  Nodes on the queue are unevaluated!! */
+  protected NodeQueue queue = new NodeQueue();
+  
+  /** The current (matching) rowID, to be returned */
+  protected long nextRowID = -1L;
+  
+  /** Constructor */
+  public IndexAccessor(TableStore ts, Index index, IndexCriteria[] indexCriteria)
+    throws WHException
+  {
+    this.ts = ts;
+    this.index = index;
+    this.tableName = index.getTable().getName();
+    this.indexColumns = index.getColumnNames();
+    this.comparators = index.getComparators();
+    this.indexCriteria = indexCriteria;
+    long rootNodeID = index.readIndexRootNode();
+    if (rootNodeID != -1L)
+      queue.pushNeedsAnalysis(rootNodeID);
+  }
+    
+  /** Are there any more rows?
+  */
+  public boolean hasNext()
+    throws WHException
+  {
+    return getNextRowID() != -1L;
+  }
+    
+  /** Read the next matching relationship row ID,
+  */
+  public long getNext()
+    throws WHException
+  {
+    long rowID = getNextRowID();
+    nextRowID = -1L;
+    return rowID;
+  }
+  
+  /** Get the next row ID */
+  protected long getNextRowID()
+    throws WHException
+  {
+    if (nextRowID != -1L)
+      return nextRowID;
+    
+    while (true)
+    {
+      // Find the next node, using the queue
+      Node node = queue.pop();
+      if (node == null)
+        return -1L;
+
+      if (node.getAction() == ACTION_DEREFERENCE)
+      {
+        nextRowID = index.readIndexNodeTableRow(node.getNodeID());
+        return nextRowID;
+      }
+
+      if (node.getAction() == ACTION_CHASE_EQUALS)
+      {
+        // We can skip all analysis, and just chase the equals chain.
+        long nodeID = node.getNodeID();
+        queue.pushNeedsDereference(nodeID);
+        // Now find the next node in the equals chain.
+        long nextEqualsNode = index.readIndexNodeEqualsNode(nodeID);
+        if (nextEqualsNode != -1L)
+        {
+          // 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);
+        }
+        continue;
+      }
+      
+      // This node needs analysis.
+      // Evaluate the node, pushing its descendents, and make a decision whether to
+      // use the row or not.
+      
+      // Look at the node and decide about whether to queue up all its pointers.
+      // We can only add at the beginning of the queue, so we must be careful to push
+      // nodes in backwards order!!
+      
+      handleColumn(node.getNodeID(),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 nodeID, int columnIndex)
+    throws WHException
+  {
+    if (columnIndex == indexColumns.length)
+    {
+      // We hit the end, which means we've got a match.
+      queue.pushNeedsDereference(nodeID);
+      // Now find the next node in the equals chain.
+      long nextEqualsNode = index.readIndexNodeEqualsNode(nodeID);
+      if (nextEqualsNode != -1L)
+      {
+        // 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);
+      }
+      return;
+    }
+    
+    // Evaluate this column
+    String currentColumn = indexColumns[columnIndex];
+    // Get the table row
+    long rowID = index.readIndexNodeTableRow(nodeID);
+    // Get the column value
+    WHValue columnValue = ts.getTableColumnValue(tableName,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 childNodeID = index.readIndexNodeGreaterNode(nodeID,currentColumn);
+      if (childNodeID != -1L)
+        queue.pushNeedsAnalysis(childNodeID);
+    }
+    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(nodeID,columnIndex+1);
+    }
+    if ((criteria & IndexCriteria.SIGNAL_LESSER) != 0)
+    {
+      // Dereference the lesser child for this column and push that node for analysis
+      long childNodeID = index.readIndexNodeLesserNode(nodeID,currentColumn);
+      if (childNodeID != -1L)
+        queue.pushNeedsAnalysis(childNodeID);
+    }
+  }
+
+  // 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;
+  /** Chase equals chain (no analysis needed) */
+  protected static final int ACTION_CHASE_EQUALS = 1;
+  /** Just dereference to rowID */
+  protected static final int ACTION_DEREFERENCE = 2;
+  
+  /** The node queue */
+  protected static class NodeQueue
+  {
+    protected List<Node> nodeList = new ArrayList<Node>();
+    
+    public NodeQueue()
+    {
+    }
+    
+    public void pushNeedsAnalysis(long nodeID)
+    {
+      nodeList.add(new Node(nodeID,ACTION_FULL_ANALYSIS));
+    }
+    
+    public void pushChaseEquals(long nodeID)
+    {
+      nodeList.add(new Node(nodeID,ACTION_CHASE_EQUALS));
+    }
+    
+    public void pushNeedsDereference(long nodeID)
+    {
+      nodeList.add(new Node(nodeID,ACTION_DEREFERENCE));
+    }
+    
+    public Node pop()
+    {
+      if (nodeList.size() == 0)
+        return null;
+      return nodeList.remove(nodeList.size()-1);
+    }
+  }
+  
+  /** A node in the queue */
+  protected static class Node
+  {
+    protected long nodeID;
+    protected int action;
+    
+    /** Constructor */
+    public Node(long nodeID, int action)
+    {
+      this.nodeID = nodeID;
+      this.action = action;
+    }
+    
+    /** Get the node id.
+    */
+    public long getNodeID()
+    {
+      return nodeID;
+    }
+    
+    /** Get whether this node should be treated as needing dereference or needing analysis.
+    */
+    public int getAction()
+    {
+      return action;
+    }
+    
+  }
+  
+}

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

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

Added: 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=1204224&view=auto
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeEqualsKey.java (added)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeEqualsKey.java Sun Nov 20 19:32:57 2011
@@ -0,0 +1,67 @@
+/* $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.*;
+
+/** Key for the btree link when all index criteria are the same */
+public class IndexNodeEqualsKey implements WHKey
+{
+  protected String indexName;
+  protected long nodeID;
+    
+  /** Constructor */
+  public IndexNodeEqualsKey(String indexName, long nodeID)
+  {
+    this.indexName = indexName;
+    this.nodeID = nodeID;
+  }
+    
+  public IndexNodeEqualsKey(byte[] data)
+  {
+    BufferPointer bp = new BufferPointer(data);
+    this.indexName = StringKey.readObject(bp);
+    this.nodeID = 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,nodeID);
+    return rval;
+  }
+    
+  public long getHashCode()
+  {
+    return StringKey.calculateHashCode(indexName) + LongKey.calculateHashCode(nodeID);
+  }
+    
+  public boolean isEquals(WHKey o)
+  {
+    IndexNodeEqualsKey key = (IndexNodeEqualsKey)o;
+    return key.indexName.equals(indexName) &&
+      key.nodeID == nodeID;
+  }
+
+}

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

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

Added: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeGreaterKey.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeGreaterKey.java?rev=1204224&view=auto
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeGreaterKey.java (added)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeGreaterKey.java Sun Nov 20 19:32:57 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 greater pointer key */
+public class IndexNodeGreaterKey extends IndexNodeKey
+{
+  /** Constructor */
+  public IndexNodeGreaterKey(String indexName, long nodeID, String columnName)
+  {
+    super(indexName,nodeID,columnName);
+  }
+    
+  public IndexNodeGreaterKey(byte[] data)
+  {
+    super(data);
+  }
+}
\ No newline at end of file

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

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

Added: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeKey.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeKey.java?rev=1204224&view=auto
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeKey.java (added)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeKey.java Sun Nov 20 19:32:57 2011
@@ -0,0 +1,73 @@
+/* $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.*;
+
+/** Base class for node lesser/greater keys */
+public class IndexNodeKey implements WHKey
+{
+  protected String indexName;
+  protected long nodeID;
+  protected String columnName;
+    
+  /** Constructor */
+  public IndexNodeKey(String indexName, long nodeID, String columnName)
+  {
+    this.indexName = indexName;
+    this.nodeID = nodeID;
+    this.columnName = columnName;
+  }
+    
+  public IndexNodeKey(byte[] data)
+  {
+    BufferPointer bp = new BufferPointer(data);
+    this.indexName = StringKey.readObject(bp);
+    this.nodeID = LongKey.readObject(bp);
+    this.columnName = StringKey.readObject(bp);
+  }
+
+  public byte[] serializeObject()
+  {
+    byte[] rval = new byte[StringKey.sizeObject(indexName)+
+      LongKey.sizeObject() + StringKey.sizeObject(columnName)];
+    BufferPointer bp = new BufferPointer(rval);
+    StringKey.writeObject(bp,indexName);
+    LongKey.writeObject(bp,nodeID);
+    StringKey.writeObject(bp,columnName);
+    return rval;
+  }
+    
+  public long getHashCode()
+  {
+    return StringKey.calculateHashCode(indexName) + LongKey.calculateHashCode(nodeID) +
+      StringKey.calculateHashCode(columnName);
+  }
+    
+  public boolean isEquals(WHKey o)
+  {
+    IndexNodeKey key = (IndexNodeKey)o;
+    return key.indexName.equals(indexName) &&
+      key.nodeID == nodeID &&
+      key.columnName.equals(columnName);
+  }
+
+}

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

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

Added: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeLesserKey.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeLesserKey.java?rev=1204224&view=auto
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeLesserKey.java (added)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeLesserKey.java Sun Nov 20 19:32:57 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 lesser pointer key */
+public class IndexNodeLesserKey extends IndexNodeKey
+{
+  /** Constructor */
+  public IndexNodeLesserKey(String indexName, long nodeID, String columnName)
+  {
+    super(indexName,nodeID,columnName);
+  }
+    
+  public IndexNodeLesserKey(byte[] data)
+  {
+    super(data);
+  }
+}
\ No newline at end of file

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

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

Added: 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=1204224&view=auto
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeParentKey.java (added)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeParentKey.java Sun Nov 20 19:32:57 2011
@@ -0,0 +1,68 @@
+/* $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.*;
+
+/** 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
+{
+  protected String indexName;
+  protected long nodeID;
+    
+  /** Constructor */
+  public IndexNodeParentKey(String indexName, long nodeID)
+  {
+    this.indexName = indexName;
+    this.nodeID = nodeID;
+  }
+    
+  public IndexNodeParentKey(byte[] data)
+  {
+    BufferPointer bp = new BufferPointer(data);
+    this.indexName = StringKey.readObject(bp);
+    this.nodeID = 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,nodeID);
+    return rval;
+  }
+    
+  public long getHashCode()
+  {
+    return StringKey.calculateHashCode(indexName) + LongKey.calculateHashCode(nodeID);
+  }
+    
+  public boolean isEquals(WHKey o)
+  {
+    IndexNodeParentKey key = (IndexNodeParentKey)o;
+    return key.indexName.equals(indexName) &&
+      key.nodeID == nodeID;
+  }
+
+}

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

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

Added: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeRowRefKey.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeRowRefKey.java?rev=1204224&view=auto
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeRowRefKey.java (added)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexNodeRowRefKey.java Sun Nov 20 19:32:57 2011
@@ -0,0 +1,67 @@
+/* $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.*;
+
+/** Key for the reference from a btree node back to the relationship row */
+public class IndexNodeRowRefKey implements WHKey
+{
+  protected String indexName;
+  protected long nodeID;
+    
+  /** Constructor */
+  public IndexNodeRowRefKey(String indexName, long nodeID)
+  {
+    this.indexName = indexName;
+    this.nodeID = nodeID;
+  }
+    
+  public IndexNodeRowRefKey(byte[] data)
+  {
+    BufferPointer bp = new BufferPointer(data);
+    this.indexName = StringKey.readObject(bp);
+    this.nodeID = 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,nodeID);
+    return rval;
+  }
+    
+  public long getHashCode()
+  {
+    return StringKey.calculateHashCode(indexName) + LongKey.calculateHashCode(nodeID);
+  }
+    
+  public boolean isEquals(WHKey o)
+  {
+    IndexNodeRowRefKey key = (IndexNodeRowRefKey)o;
+    return key.indexName.equals(indexName) &&
+      key.nodeID == nodeID;
+  }
+
+}

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

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

Added: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexRootKey.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexRootKey.java?rev=1204224&view=auto
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexRootKey.java (added)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexRootKey.java Sun Nov 20 19:32:57 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.*;
+
+/** Key for the btree root node link */
+public class IndexRootKey extends StringKey
+{
+  /** Constructor */
+  public IndexRootKey(String indexName)
+  {
+    super(indexName);
+  }
+    
+  public IndexRootKey(byte[] data)
+  {
+    super(data);
+  }
+}

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

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

Added: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexRowNodeRefKey.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexRowNodeRefKey.java?rev=1204224&view=auto
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexRowNodeRefKey.java (added)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/IndexRowNodeRefKey.java Sun Nov 20 19:32:57 2011
@@ -0,0 +1,67 @@
+/* $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.*;
+
+/** Key for the reference from a relationship row back to a corresponding index node */
+public class IndexRowNodeRefKey implements WHKey
+{
+  protected String indexName;
+  protected long rowID;
+    
+  /** Constructor */
+  public IndexRowNodeRefKey(String indexName, long rowID)
+  {
+    this.indexName = indexName;
+    this.rowID = rowID;
+  }
+    
+  public IndexRowNodeRefKey(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;
+  }
+    
+  public long getHashCode()
+  {
+    return StringKey.calculateHashCode(indexName) + LongKey.calculateHashCode(rowID);
+  }
+    
+  public boolean isEquals(WHKey o)
+  {
+    IndexRowNodeRefKey key = (IndexRowNodeRefKey)o;
+    return key.indexName.equals(indexName) &&
+      key.rowID == rowID;
+  }
+
+}

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

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

Added: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/LongRowID.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/LongRowID.java?rev=1204224&view=auto
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/LongRowID.java (added)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/LongRowID.java Sun Nov 20 19:32:57 2011
@@ -0,0 +1,41 @@
+/* $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.*;
+
+/** Implementation of WHRowID which uses a Long as the rowID.
+*/
+public class LongRowID extends LongKey implements WHRowID
+{
+  /** Constructor */
+  public LongRowID(long value)
+  {
+    super(value);
+  }
+  
+  public LongRowID(byte[] data)
+  {
+    super(data);
+  }
+
+}
+

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

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

Modified: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/Table.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/Table.java?rev=1204224&r1=1204223&r2=1204224&view=diff
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/Table.java (original)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/Table.java Sun Nov 20 19:32:57 2011
@@ -130,11 +130,12 @@ public class Table implements WHTable
   public WHAccessor buildAccessor()
     throws WHException
   {
-    return ts.buildTableAccessor(tableName);
+    return new TableAccessor(ts,tableName,ts.readFirstTableRowID(tableName));
   }
 
   /** Get name */
   public String getName()
+    throws WHException
   {
     return tableName;
   }

Modified: incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/TableStore.java
URL: http://svn.apache.org/viewvc/incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/TableStore.java?rev=1204224&r1=1204223&r2=1204224&view=diff
==============================================================================
--- incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/TableStore.java (original)
+++ incubator/lcf/branches/CONNECTORS-286/warthog/src/main/java/org/apache/warthog/tablestore/TableStore.java Sun Nov 20 19:32:57 2011
@@ -193,6 +193,22 @@ public class TableStore implements WHTab
 
   // Non-interface public methods
   
+  /** Read a value from current transaction.
+  */
+  public WHValue get(WHKey key)
+    throws WHException
+  {
+    return currentTransaction.get(key);
+  }
+  
+  /** Write a value to current transaction.
+  */
+  public void put(WHKey key, WHValue value)
+    throws WHException
+  {
+    currentTransaction.put(key,value);
+  }
+  
   /** Delete a table row from all the indexes that are based on a table.
   */
   public void deleteIndexRow(String tableName, long rowID, Set<String> columns)
@@ -309,18 +325,21 @@ public class TableStore implements WHTab
     return currentTransaction.get(key);
   }
   
-  /** Build a table accessor, which accesses all the table rows.
+  /** Read the first table row ID.
   */
-  public WHAccessor buildTableAccessor(String tableName)
+  public long readFirstTableRowID(String tableName)
     throws WHException
   {
-    // Read the head pointer
     TableHeadKey headKey = new TableHeadKey(tableName);
     LongValue headValue = (LongValue)currentTransaction.get(headKey);
-    return new TableAccessor(this,tableName,(headValue==null)?-1L:headValue.getValue());
+    if (headValue == null)
+      return -1L;
+    return headValue.getValue();
   }
   
-  protected long readNextTableRowID(String tableName, long currentRowID)
+  /** Reade the next table row ID.
+  */
+  public long readNextTableRowID(String tableName, long currentRowID)
     throws WHException
   {
     // Read the row's next pointer
@@ -345,20 +364,6 @@ public class TableStore implements WHTab
     return rval;
   }
   
-  /** Allocate the next index node number.
-  */
-  public long allocateNextIndexNode(String indexName)
-    throws WHException
-  {
-    IndexNodeIDFactoryKey tlk = new IndexNodeIDFactoryKey(indexName);
-    LongValue tlv = (LongValue)currentTransaction.get(tlk);
-    if (tlv == null)
-      throw new WHDeadlockException();
-    long rval = tlv.getValue();
-    currentTransaction.put(tlk,new LongValue(rval+1L));
-    return rval;
-  }
-  
   // Protected classes and methods
 
   /** Delete a table definition.
@@ -375,7 +380,7 @@ public class TableStore implements WHTab
     }
     
     // Now that the indexes are gone, delete all the table rows
-    t.deleteRows(buildTableAccessor(t.getName()),null);
+    t.deleteRows(t.buildAccessor(),null);
 
     // Delete the keys that belong to the table, and clean up cached values
     tables.remove(t.getName());



Mime
View raw message