geode-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jasonhu...@apache.org
Subject incubator-geode git commit: GEODE-730: Optimize single filter join queries
Date Tue, 09 Feb 2016 18:49:39 GMT
Repository: incubator-geode
Updated Branches:
  refs/heads/develop 820cfd632 -> d232e2594


GEODE-730: Optimize single filter join queries

When executing a join query with additional filters on a single region, we now detect this scenario and
instead of creating a CompositeGroupJunction, we create a regular GroupJunction.  When we being cutdown
and expansion, we then create new compiled comparisons so that we can do an index lookup.

For example "select * from /region1 a, /region2 b where a.name = "joe" and a.id = b.id"
We will now execute the a.name first assuming an index is present on a.name

During cutdown and expand, we determine that the comparison a.id = b.id can create a new compiled comparison
because the alias a from a.id matches our original filter a.name.  We can evaluate a.id at this point, say id
evaluated to 8.  So we create a compiled comparison of b.id = 8.  We can now do a lookup using the index on b.id.
We retrieve these results and place them into a map.  This map will be used to continue to derive additional joins
if they exist.  Such as b.id = c.id, etc...

We can continue with the iteration but instead of iterating the entire b region, we can now go over derived results.

This also includes a fix to not unlock an index lock when reevaluating an inner query.


Project: http://git-wip-us.apache.org/repos/asf/incubator-geode/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-geode/commit/d232e259
Tree: http://git-wip-us.apache.org/repos/asf/incubator-geode/tree/d232e259
Diff: http://git-wip-us.apache.org/repos/asf/incubator-geode/diff/d232e259

Branch: refs/heads/develop
Commit: d232e25947a8e223f35feb1feffe3150875dc5f5
Parents: 820cfd6
Author: Jason Huynh <huynhja@gmail.com>
Authored: Tue Jan 26 10:09:25 2016 -0800
Committer: Jason Huynh <huynhja@gmail.com>
Committed: Tue Feb 9 10:57:35 2016 -0800

----------------------------------------------------------------------
 .../query/internal/CompiledComparison.java      |   4 +-
 .../cache/query/internal/CompiledJunction.java  |  94 +++-
 .../cache/query/internal/CompiledSelect.java    |  22 +-
 .../cache/query/internal/DerivedInfo.java       | 306 +++++++++++++
 .../cache/query/internal/GroupJunction.java     |   5 +-
 .../cache/query/internal/QueryUtils.java        |  61 ++-
 .../query/internal/index/IndexManager.java      |   4 +
 .../query/internal/index/EquijoinDUnitTest.java | 437 +++++++++++++++++++
 .../PartitionedRegionEquijoinDUnitTest.java     | 130 ++++++
 9 files changed, 1022 insertions(+), 41 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/d232e259/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledComparison.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledComparison.java b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledComparison.java
index 75eaaad..9084351 100644
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledComparison.java
+++ b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledComparison.java
@@ -52,8 +52,8 @@ public class CompiledComparison extends AbstractCompiledValue implements
     Negatable, OQLLexerTokenTypes, Indexable {
 
   // persistent inst vars
-  private final CompiledValue _left;
-  private final CompiledValue _right;
+  public final CompiledValue _left;
+  public final CompiledValue _right;
   private int _operator;
 
   // List groupRuntimeItrs = null;

http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/d232e259/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledJunction.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledJunction.java b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledJunction.java
index 6bc68de..902aecd 100644
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledJunction.java
+++ b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledJunction.java
@@ -16,11 +16,28 @@
  */
 package com.gemstone.gemfire.cache.query.internal;
 
-import java.util.*;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
 
 import com.gemstone.gemfire.InternalGemFireError;
 import com.gemstone.gemfire.cache.EntryDestroyedException;
-import com.gemstone.gemfire.cache.query.*;
+import com.gemstone.gemfire.cache.query.AmbiguousNameException;
+import com.gemstone.gemfire.cache.query.FunctionDomainException;
+import com.gemstone.gemfire.cache.query.NameResolutionException;
+import com.gemstone.gemfire.cache.query.QueryInvocationTargetException;
+import com.gemstone.gemfire.cache.query.QueryService;
+import com.gemstone.gemfire.cache.query.SelectResults;
+import com.gemstone.gemfire.cache.query.Struct;
+import com.gemstone.gemfire.cache.query.TypeMismatchException;
+import com.gemstone.gemfire.cache.query.internal.index.IndexManager;
 import com.gemstone.gemfire.cache.query.internal.index.IndexProtocol;
 import com.gemstone.gemfire.cache.query.internal.parse.OQLLexerTokenTypes;
 import com.gemstone.gemfire.cache.query.internal.types.StructTypeImpl;
@@ -116,7 +133,12 @@ public class CompiledJunction extends AbstractCompiledValue implements
   private int _operator = 0;
   private List unevaluatedFilterOperands = null; 
   
-
+  //A token to place into the samesort map.  This is to let the engine know there is more than one index
+  //being used for this junction but allows actual operands to form range junctions if enough exist. 
+  //The mechanism checks to see if the mapped object is an integer, if so, it increments, if it's not it sets as 1
+  //Because we are a string place holder, the next actual operand would just start at one.  If the join is added
+  //after a valid operand has already set the counter to an integer, we instead just ignore and do not set the place holder
+  private final static String PLACEHOLDER_FOR_JOIN = "join";  
   CompiledJunction(CompiledValue[] operands, int operator) {
     // invariant: operator must be LITERAL_and or LITERAL_or
     // invariant: at least two operands
@@ -502,6 +524,7 @@ public class CompiledJunction extends AbstractCompiledValue implements
     Map iterToOperands = new HashMap();
     CompiledValue operand = null;
     boolean isJunctionNeeded = false;
+    boolean indexExistsOnNonJoinOp = false;
 
     for (int i = 0; i < _operands.length; i++) {
       // Asif : If we are inside this function this itself indicates
@@ -554,8 +577,9 @@ public class CompiledJunction extends AbstractCompiledValue implements
         }
         
         for (CompiledValue expndOperand : expandedOperands) {
+          boolean operandEvalAsFilter = expndOperand.getPlanInfo(context).evalAsFilter;
           isJunctionNeeded = isJunctionNeeded
-              || expndOperand.getPlanInfo(context).evalAsFilter;
+              || operandEvalAsFilter;
           Set set = QueryUtils.getCurrentScopeUltimateRuntimeIteratorsIfAny(
               expndOperand, context);
           if (set.size() != 1) {
@@ -563,7 +587,7 @@ public class CompiledJunction extends AbstractCompiledValue implements
             // than 1, will mean a composite condition. For a Composite
             // Condition which is filter evaluable that means necessarily that
             // RHS is dependent on one independent iterator & LHS on the other.
-            if ((expndOperand.getPlanInfo(context).evalAsFilter)) {
+            if (operandEvalAsFilter) {
               Support.Assert(set.size() == 2,
                   " The no of independent iterators should be equal to 2");
               compositeFilterOpsMap.put(expndOperand, set);
@@ -582,6 +606,9 @@ public class CompiledJunction extends AbstractCompiledValue implements
               operandsList = new ArrayList();
               iterToOperands.put(rIter, operandsList);
             }
+            if (operandEvalAsFilter && _operator == LITERAL_and) {
+              indexExistsOnNonJoinOp = true;
+            }
             operandsList.add(expndOperand);
           }
         }
@@ -606,7 +633,7 @@ public class CompiledJunction extends AbstractCompiledValue implements
       // There exists at least one condition which must have an index available.
       Filter junction = createJunction(compositeIterOperands,
           compositeFilterOpsMap, iterToOperands, context, indexCount,
-          evalOperands);
+          evalOperands, indexExistsOnNonJoinOp);
       // Asif Ensure that independent operands are always at the start
       evalOperands.add(indexCount++, junction);
     }
@@ -774,11 +801,15 @@ public class CompiledJunction extends AbstractCompiledValue implements
       //TODO:Do not club Like predicate in an existing range
       if (evalAsFilter ) {
         indx = ((Indexable)tempOp).getIndexInfo(context);
-        Assert.assertTrue(indx.length == 1,
-            "There should have been just one index for the condition");
-        listOrPosition = sameIndexOperands.get(indx[0]._index);
+        //We are now sorting these for joins, therefore we need to weed out the join indexes
+        if (!IndexManager.JOIN_OPTIMIZATION || indx.length == 1) {
+          Assert.assertTrue(indx.length == 1,
+              "There should have been just one index for the condition");
+          listOrPosition = sameIndexOperands.get(indx[0]._index);
+        }
       }
-      if (listOrPosition != null) {
+    
+     if (listOrPosition != null) {
         if (listOrPosition instanceof Integer) {
           int position = ((Integer)listOrPosition).intValue();
           List operands = new ArrayList(size);
@@ -788,16 +819,31 @@ public class CompiledJunction extends AbstractCompiledValue implements
           sameIndexOperands.put(indx[0]._index, operands);
           needsCompacting = true;
         }
-        else {
+        else if (listOrPosition instanceof List){
           List operands = (List)listOrPosition;
           operands.add(tempOp);
         }
-      }
-      else {
+        else {
+          //a join was present here, let's now occupy that spot and remove the placeholder
+          listOrPosition = null;
+        }
+     }
+      if (listOrPosition == null) {
         cv[i] = tempOp;
-        // TODO: Enable only for AND junction for now
-        if (evalAsFilter && this._operator == OQLLexerTokenTypes.LITERAL_and) {
-          sameIndexOperands.put(indx[0]._index, Integer.valueOf(i));
+        if (indx != null && indx.length == 1) {
+          // TODO: Enable only for AND junction for now
+          if (evalAsFilter && this._operator == OQLLexerTokenTypes.LITERAL_and) {
+            sameIndexOperands.put(indx[0]._index, Integer.valueOf(i));
+          }
+        } else if (indx != null && indx.length == 2) {
+          if (evalAsFilter && this._operator == OQLLexerTokenTypes.LITERAL_and) {
+            if (!sameIndexOperands.containsKey(indx[0]._index)) {
+              sameIndexOperands.put(indx[0]._index, PLACEHOLDER_FOR_JOIN);
+            }
+            if (!sameIndexOperands.containsKey(indx[1]._index)) {
+              sameIndexOperands.put(indx[1]._index, PLACEHOLDER_FOR_JOIN);
+            }
+          }
         }
       }
     }
@@ -805,10 +851,10 @@ public class CompiledJunction extends AbstractCompiledValue implements
   }
   //This is called only if the CompiledJunction was either independent or filter evaluable.
   public int getSizeEstimate(ExecutionContext context)throws FunctionDomainException, TypeMismatchException, NameResolutionException, QueryInvocationTargetException  {
-    if( this.isDependentOnCurrentScope(context)) {	  
-	return Integer.MAX_VALUE;
+    if( this.isDependentOnCurrentScope(context)) {    
+  return Integer.MAX_VALUE;
     }else {
-    	return 0;
+      return 0;
     }
   }
 
@@ -816,7 +862,7 @@ public class CompiledJunction extends AbstractCompiledValue implements
   // Lists
   private Filter createJunction(List compositeIterOperands,
       Map compositeFilterOpsMap, Map iterToOperands, ExecutionContext context,
-      int indexCount, List evalOperands) throws FunctionDomainException,
+      int indexCount, List evalOperands, boolean indexExistsOnNonJoinOp) throws FunctionDomainException,
       TypeMismatchException, NameResolutionException,
       QueryInvocationTargetException {
     Support.Assert(!(iterToOperands.isEmpty() && compositeFilterOpsMap
@@ -825,7 +871,13 @@ public class CompiledJunction extends AbstractCompiledValue implements
     CompiledValue junction = null;
     int size;
     /*---------- Create only a  GroupJunction */
-    if (iterToOperands.size() == 1 && compositeFilterOpsMap.isEmpty()) {
+    if (iterToOperands.size() == 1 && (compositeFilterOpsMap.isEmpty()
+        || (indexExistsOnNonJoinOp && IndexManager.JOIN_OPTIMIZATION))) {
+      if ((indexExistsOnNonJoinOp && IndexManager.JOIN_OPTIMIZATION)) {
+        // For the optimization we will want to add the compositeFilterOpsMap 848
+        // without the optimization we only fall into here if it's empty anyways, but have not tested the removal of this if clause
+        evalOperands.addAll(compositeFilterOpsMap.keySet());
+      }
       // Asif :Create only a GroupJunction. The composite conditions can be
       // evaluated as iter operands inside GroupJunction.
       Map.Entry entry = (Map.Entry) iterToOperands.entrySet().iterator().next();

http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/d232e259/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledSelect.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledSelect.java b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledSelect.java
index 205acaa..ec7c51e 100644
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledSelect.java
+++ b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/CompiledSelect.java
@@ -82,6 +82,19 @@ public class CompiledSelect extends AbstractCompiledValue {
 
   //used as a key in a context to identify the scope of this CompiledSelect 
   private Object scopeID = new Object(); 
+  
+  /*
+   * Set in context for the where clause to signify that it has been evaluated at least one time
+   * for any other CompiledValue that may use precalculated indexes
+   * we want to mark this as Evaluated so that we don't unlock locks
+   * that don't belong to this iteration of evaluate.
+   * This is similar to how CompiledComparisons store their IndexInfo in the context
+   * but for example a CompiledJunction that uses 2 Comparisons
+   * would have unlocked the readlocks because we check to see if the clause has a mapped value
+   * in the context. Because CompiledJunctions did not, we unlocked the read locks.
+   * Now we set a value so that it will not do this. See where we use this value to see how unlock is determined
+   */
+  private final static String CLAUSE_EVALUATED = "Evaluated";
 
   public CompiledSelect(boolean distinct, boolean count, CompiledValue whereClause,
                         List iterators, List projAttrs,List<CompiledSortCriterion> orderByAttrs, CompiledValue limit,
@@ -464,7 +477,7 @@ public class CompiledSelect extends AbstractCompiledValue {
           }
           boolean unlock = true;
           Object obj = context.cacheGet(this.whereClause);
-          if(obj != null && obj instanceof IndexInfo[]) {
+          if(obj != null && (obj instanceof IndexInfo[] || obj.equals(CLAUSE_EVALUATED))) {
             // if indexinfo is cached means the read lock 
             // is not being taken this time, so releasing 
             // the lock is not required
@@ -473,6 +486,9 @@ public class CompiledSelect extends AbstractCompiledValue {
           // see if we should evaluate as filters,
           // and count how many actual index lookups will be performed
           PlanInfo planInfo = this.whereClause.getPlanInfo(context);
+          if (context.cacheGet(this.whereClause) == null) {
+            context.cachePut(this.whereClause, CLAUSE_EVALUATED);
+          }
           try {
             evalAsFilters = planInfo.evalAsFilter;
             // let context know if there is exactly one index lookup
@@ -1089,10 +1105,10 @@ public class CompiledSelect extends AbstractCompiledValue {
     if (elementType.isStructType()) {
       if (isSorted) { // sorted struct
         return prepareEmptySortedStructSet((StructTypeImpl)elementType);
-	}
+  }
       else { // unsorted struct
         return new StructBag((StructType)elementType,  context.getCachePerfStats());
-	}
+  }
     }
     else { // non-struct
       if (isSorted) { // sorted non-struct

http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/d232e259/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/DerivedInfo.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/DerivedInfo.java b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/DerivedInfo.java
new file mode 100644
index 0000000..a934524
--- /dev/null
+++ b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/DerivedInfo.java
@@ -0,0 +1,306 @@
+/*
+ * 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 com.gemstone.gemfire.cache.query.internal;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import com.gemstone.gemfire.cache.query.FunctionDomainException;
+import com.gemstone.gemfire.cache.query.Index;
+import com.gemstone.gemfire.cache.query.NameResolutionException;
+import com.gemstone.gemfire.cache.query.QueryInvocationTargetException;
+import com.gemstone.gemfire.cache.query.SelectResults;
+import com.gemstone.gemfire.cache.query.Struct;
+import com.gemstone.gemfire.cache.query.TypeMismatchException;
+import com.gemstone.gemfire.cache.query.internal.index.AbstractIndex;
+import com.gemstone.gemfire.cache.query.internal.index.IndexProtocol;
+import com.gemstone.gemfire.cache.query.internal.index.PartitionedIndex;
+import com.gemstone.gemfire.cache.query.internal.parse.OQLLexerTokenTypes;
+import com.gemstone.gemfire.cache.query.types.CollectionType;
+import com.gemstone.gemfire.cache.query.types.ObjectType;
+
+public class DerivedInfo {
+  public Map<String, SelectResults> derivedResults;
+  public List<Object[]> newDerivatives;
+  public List successfulOps = new LinkedList();
+  public List originalOps;
+  public CompiledValue currentOp;
+  private List expansionList;
+
+  public DerivedInfo() {
+    derivedResults = new HashMap<String, SelectResults>();
+    newDerivatives = new ArrayList<Object[]>();
+  }
+
+  public List getExpansionList() {
+    return expansionList;
+  }
+
+  public void setExpansionList(List expansionList) {
+    this.expansionList = expansionList;
+  }
+
+  public void setOriginalOps(List opsList) {
+    originalOps = new LinkedList(opsList);
+  }
+
+  public List getRemainingOps() {
+    List remainingOps = new LinkedList(originalOps);
+    remainingOps.removeAll(successfulOps);
+    return remainingOps;
+  }
+
+  public void addDerivedResults(IndexInfo indexInfo, SelectResults sr) {
+    IndexProtocol index = indexInfo._index;
+    String key = QueryUtils.getCompiledIdFromPath(indexInfo._path).getId() + ":" + index.getCanonicalizedIteratorDefinitions()[0];
+    // String key = index.getCanonicalizedIteratorDefinitions()[0];
+    if (derivedResults.containsKey(key)) {
+      derivedResults.get(key).addAll(sr);
+    } else {
+      derivedResults.put(key, sr);
+    }
+    newDerivatives.add(new Object[] { QueryUtils.getCompiledIdFromPath(indexInfo._path).getId(), sr });
+    successfulOps.add(currentOp);
+  }
+
+  public void addDerivedResults(IndexInfo indexInfo, SelectResults[] srs) {
+    addDerivedResults(indexInfo, srs[0]);
+    // Nested / range index is not supported at this time due to the way we cross the results
+    // This solution would have duplicates. The problem is the way we doNestedIteration. The map would
+    // have all values be associated with the current nested level object which is not what the values would represent
+    // IndexProtocol index = indexInfo._index;
+    // String[] definitions = index.getCanonicalizedIteratorDefinitions();
+    // for (int i = 0 ; i < definitions.length; i++) {
+    // String key = QueryUtils.getCompiledIdFromPath(indexInfo._path).getId() + ":" + definitions[i];
+    // if (derivedResults.containsKey(key)) {
+    // derivedResults.get(key).addAll(srs[i]);
+    // }
+    // else {
+    // derivedResults.put(key, srs[i]);
+    // }
+    // }
+    //
+    // int indexToIterateOn = QueryUtils.figureOutWhichStructIndexToExtract(index);
+    // newDerivatives.add(new Object[]{getCompiledIdFromPath(indexInfo._path).getId(), srs[indexToIterateOn]});
+    // successfulOps.add(currentOp);
+
+  }
+
+  public void computeDerivedJoinResults(IndexInfo theCallingIndex, ExecutionContext context, CompiledValue iterOps) throws FunctionDomainException, TypeMismatchException, NameResolutionException,
+      QueryInvocationTargetException {
+    // Call this computeDerivedResults()
+    // We are looking for join conditions so we can filter eval instead of iterate eval
+    // Then we can apply the rest of the ops on the results
+    if (theCallingIndex != null && iterOps != null) {
+      if (iterOps instanceof CompiledJunction) {
+        List opsList = ((CompiledJunction) iterOps).getOperands();
+        this.setOriginalOps(opsList);
+        createDerivedJoinResultsFromOpsList((QueryUtils.getCompiledIdFromPath(theCallingIndex._path)).getId(), context, opsList);
+      } else if (iterOps.getType() == CompiledValue.COMPARISON) {
+        createDerivedJoinResultsFromCC((QueryUtils.getCompiledIdFromPath(theCallingIndex._path)).getId(), (CompiledComparison) iterOps, context);
+      }
+    }
+  }
+
+  private void createDerivedJoinResultsFromOpsList(String theCallingIndexId, ExecutionContext context, List opsList) throws FunctionDomainException, TypeMismatchException, NameResolutionException,
+      QueryInvocationTargetException {
+    Iterator iter = opsList.iterator();
+    while (iter.hasNext()) {
+      CompiledValue cv = (CompiledValue) iter.next();
+      this.currentOp = cv;
+
+      if (cv.getType() == CompiledValue.COMPARISON) {
+        createDerivedJoinResultsFromCC(theCallingIndexId, (CompiledComparison) cv, context);
+      }
+    }
+    // Now let's derive from our derivatives (for multiple join clauses that can be chained, such as a.id = 1 and a.id = b.id and b.id = c.id
+    List<Object[]> newDerivatives = new ArrayList<Object[]>(this.newDerivatives);
+    this.newDerivatives.clear();
+    if (newDerivatives.size() > 0) {
+      Iterator<Object[]> iterator = newDerivatives.iterator();
+      while (iterator.hasNext()) {
+        Object[] idDerivedAndResults = iterator.next();
+        derivedDerivative(idDerivedAndResults, context, this.getExpansionList());
+      }
+    }
+  }
+
+  private void derivedDerivative(Object[] idDerivedAndResults, ExecutionContext context, List expansionList) throws FunctionDomainException, TypeMismatchException, NameResolutionException,
+      QueryInvocationTargetException {
+
+    String idDerived = (String) idDerivedAndResults[0];
+    SelectResults results = (SelectResults) idDerivedAndResults[1];
+    RuntimeIterator ritr = getMatchingRuntimeIterator(idDerived, expansionList);
+    List remainingOps = this.getRemainingOps();
+    Iterator iterator = results.iterator();
+    while (iterator.hasNext()) {
+      Object val = iterator.next();
+      ritr.setCurrent(val);
+      createDerivedJoinResultsFromOpsList(idDerived, context, remainingOps);
+    }
+
+  }
+
+  private RuntimeIterator getMatchingRuntimeIterator(String receiverId, List expansionList) throws QueryInvocationTargetException {
+    Iterator iterator = expansionList.iterator();
+    while (iterator.hasNext()) {
+      RuntimeIterator ritr = (RuntimeIterator) iterator.next();
+      if (ritr.getCmpIteratorDefn().getName().equals(receiverId)) {
+        return ritr;
+      }
+    }
+    throw new QueryInvocationTargetException("Unable to locate correct iterator for " + receiverId);
+  }
+
+  /*
+   Example query : "Select * from /region1 r, /region2 s where r.id = 1 and r.id = s.id"
+   Up until this point we have evaluated the r.id portion
+   We determine if the path (r) matches any of the paths in the current cc (r.id = s.id)
+   If so we figure out which side it matches (in this case the left side and create a new compiled comparison
+   This new cc will set the left side as s.id and the right side as the evaluated value, in this case it happens to be 1 but
+   it could be another field from the object instead.
+   */
+  private void createDerivedJoinResultsFromCC(String theCallingIndexReceiverId, CompiledComparison cc, ExecutionContext context) throws FunctionDomainException, TypeMismatchException,
+      NameResolutionException, QueryInvocationTargetException {
+    if (isCompiledPath(cc._right) && matchingPathIds(theCallingIndexReceiverId, cc._left)) {
+      evaluateDerivedJoin(context, cc._right, new CompiledLiteral(cc._left.evaluate(context)), cc.getOperator());
+    } else if (isCompiledPath(cc._left) && matchingPathIds(theCallingIndexReceiverId, cc._right)) {
+      evaluateDerivedJoin(context, cc._left, new CompiledLiteral(cc._right.evaluate(context)), cc.getOperator());
+    }
+  }
+ 
+  /*
+   Called by createDerivedJoinResultsFromCCa
+   Creates the new cc, executes the cc and releases any newly obtain index locks
+  */ 
+  private void evaluateDerivedJoin(ExecutionContext context, CompiledValue newLeftSide, CompiledValue newRightSide, int operator) 
+   throws TypeMismatchException, FunctionDomainException, NameResolutionException, QueryInvocationTargetException {
+   CompiledComparison dcc = createDerivedJoin(context, newLeftSide, newRightSide, operator);
+   IndexInfo[] indexInfos = (IndexInfo[]) dcc.getIndexInfo(context);
+   try {
+     if (indexInfos != null && isValidIndexTypeToDerive(indexInfos[0]._getIndex())) {
+       populateDerivedResultsFromDerivedJoin(context, dcc, indexInfos[0]);
+     }
+   } finally {
+     if (indexInfos != null) {
+       Index index = (Index) indexInfos[0]._index;
+       Index prIndex = ((AbstractIndex) index).getPRIndex();
+       if (prIndex != null) {
+         ((PartitionedIndex) prIndex).releaseIndexReadLockForRemove();
+       } else {
+         ((AbstractIndex) index).releaseIndexReadLockForRemove();
+       }
+     }
+   }
+  }
+
+  /*
+   Does the evaluation/execution of the cc and stores them into our map
+   We prevent limit and order by to be conducted by the index at this time as we do not those applied
+   We have no idea what the other operands are and do not want to limit results as the first X results may not 
+   fulfill all operands.
+   */
+  private void populateDerivedResultsFromDerivedJoin(ExecutionContext context, CompiledComparison dcc, IndexInfo indexInfo) throws FunctionDomainException, TypeMismatchException,
+      NameResolutionException, QueryInvocationTargetException {
+    // overwrite context values to disable limit, order by etc that should not be done by a derived join
+    // If we apply limit at this point, we cannot guarantee that after we iterate, the we do not continue to
+    // reduce the count below the limited amount
+    Boolean originalCanApplyLimit = (Boolean) context.cacheGet(CompiledValue.CAN_APPLY_LIMIT_AT_INDEX);
+    context.cachePut(CompiledValue.CAN_APPLY_LIMIT_AT_INDEX, Boolean.FALSE);
+    Boolean originalCanApplyOrderBy = (Boolean) context.cacheGet(CompiledValue.CAN_APPLY_ORDER_BY_AT_INDEX);
+    context.cachePut(CompiledValue.CAN_APPLY_ORDER_BY_AT_INDEX, Boolean.FALSE);
+
+    SelectResults sr = dcc.filterEvaluate(context, null, false, null, null, false, false, false);
+
+    context.cachePut(CompiledValue.CAN_APPLY_LIMIT_AT_INDEX, originalCanApplyLimit);
+    context.cachePut(CompiledValue.CAN_APPLY_ORDER_BY_AT_INDEX, originalCanApplyOrderBy);
+    ObjectType ot = indexInfo._index.getResultSetType();
+    //The following if block is not currently used other than the else
+    //This would be needed once we figure out how to handle nested object indexes (range, map, etc)
+    //The issue we have right now with these indexes is the results will come back as a tuple, if we use those as is, we end up 
+    //reusing the evaluated values even if they did not come from the top level object leading to duplicate results or incorrect tupling
+    if (ot.isStructType()) {
+      //createObjectResultsFromStructResults(indexInfo, sr);
+    } else if (ot.isMapType()) {
+
+    } else if (ot.isCollectionType()) {
+
+    } else {
+      this.addDerivedResults(dcc.getIndexInfo(context)[0], sr);
+    }
+  }
+
+  //Not used at this time.  Was left over from attempt to speed up Range Indexes
+  /*
+  private void createObjectResultsFromStructResults(IndexInfo indexInfo, SelectResults sr) {
+    Iterator srIterator = sr.iterator();
+    SelectResults[] newSrs = null;
+
+    while (srIterator.hasNext()) {
+      Struct struct = (Struct) srIterator.next();
+      Object[] fieldValues = struct.getFieldValues();
+      int structLength = struct.getFieldValues().length;
+      if (newSrs == null) {
+        newSrs = new FakeSelectResults[structLength];
+        for (int x = 0; x < structLength; x++) {
+          newSrs[x] = new FakeSelectResults();
+        }
+      }
+      for (int i = 0; i < structLength; i++) {
+        newSrs[i].add(fieldValues[i]);
+      }
+    }
+
+    if (newSrs != null) {
+      this.addDerivedResults(indexInfo, newSrs);
+    }
+  }
+  */
+
+  private boolean isValidIndexTypeToDerive(IndexProtocol index) {
+    ObjectType type = index.getResultSetType();
+    return !(type.isCollectionType() || type.isMapType() || type.isStructType());
+  }
+
+  private CompiledComparison createDerivedJoin(ExecutionContext context, CompiledValue newLeft, CompiledValue newRight, int op)
+    throws TypeMismatchException, NameResolutionException {
+    CompiledComparison cc = new CompiledComparison(newLeft, newRight, op);
+    cc.computeDependencies(context);
+    return cc;
+  }
+
+  //Given a compiled value, we check to see if the receiver id of a CompiledPath matches the receiverId passed in
+  private boolean matchingPathIds(String receiverId, CompiledValue cv) {
+    if (isCompiledPath(cv)) {
+      CompiledPath path = (CompiledPath)cv;
+      return receiverId.equals(QueryUtils.getCompiledIdFromPath(path).getId());
+    }
+    return false;
+  }
+
+  private boolean isCompiledPath(CompiledValue cv) {
+    return cv.getType() == CompiledValue.PATH;
+  }
+
+}

http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/d232e259/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/GroupJunction.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/GroupJunction.java b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/GroupJunction.java
index 37c13f2..6918436 100644
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/GroupJunction.java
+++ b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/GroupJunction.java
@@ -132,7 +132,10 @@ public class GroupJunction extends AbstractGroupOrRangeJunction {
           // either tru or false for an AND junction but always false for an
           // OR Junction.
           PlanInfo pi = _operands[i].getPlanInfo(context);
-          if (pi.evalAsFilter) {
+          //we check for size == 1 now because of the join optimization can 
+          //leave an operand with two indexes, but the key element is not set
+          //this will throw an npe
+          if (pi.evalAsFilter && pi.indexes.size() == 1) {       
             if(pi.isPreferred) {
               if(currentBestFilter != null) {
                 evalOperands.add(currentBestFilter);

http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/d232e259/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/QueryUtils.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/QueryUtils.java b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/QueryUtils.java
index 91e20f0..e19318c 100644
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/QueryUtils.java
+++ b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/QueryUtils.java
@@ -23,6 +23,7 @@ import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.ListIterator;
+import java.util.Map;
 import java.util.Set;
 
 import org.apache.logging.log4j.Logger;
@@ -38,6 +39,7 @@ import com.gemstone.gemfire.cache.query.Struct;
 import com.gemstone.gemfire.cache.query.TypeMismatchException;
 import com.gemstone.gemfire.cache.query.internal.index.AbstractIndex;
 import com.gemstone.gemfire.cache.query.internal.index.IndexData;
+import com.gemstone.gemfire.cache.query.internal.index.IndexManager;
 import com.gemstone.gemfire.cache.query.internal.index.IndexProtocol;
 import com.gemstone.gemfire.cache.query.internal.index.IndexUtils;
 import com.gemstone.gemfire.cache.query.internal.index.PartitionedIndex;
@@ -52,7 +54,6 @@ import com.gemstone.gemfire.internal.cache.CachePerfStats;
 import com.gemstone.gemfire.internal.cache.PartitionedRegion;
 import com.gemstone.gemfire.internal.i18n.LocalizedStrings;
 import com.gemstone.gemfire.internal.logging.LogService;
-import com.gemstone.gemfire.internal.logging.log4j.LocalizedMessage;
 
 /**
  * 
@@ -556,7 +557,7 @@ public class QueryUtils {
           indexFieldToItrsMapping[level], icdeh[level])) {
         if (level == (values.length - 1)) {
           doNestedIterationsForIndex(expansionListIterator.hasNext(), result,
-              finalItrs, expansionListIterator, context, iterOps, limit);
+              finalItrs, expansionListIterator, context, iterOps, limit, null);
           if (limit != -1 && result.size() >= limit) {
             break;
           }     
@@ -633,7 +634,7 @@ public class QueryUtils {
   private static SelectResults cutDownAndExpandIndexResults(
       SelectResults result, RuntimeIterator[] indexFieldToItrsMapping,
       List expansionList, List finalItrs, ExecutionContext context,
-      List checkList, CompiledValue iterOps) throws FunctionDomainException,
+      List checkList, CompiledValue iterOps, IndexInfo theFilteringIndex) throws FunctionDomainException,
       TypeMismatchException, NameResolutionException,
       QueryInvocationTargetException {
     SelectResults returnSet = null;
@@ -666,7 +667,7 @@ public class QueryUtils {
       
     }
     cutDownAndExpandIndexResults(returnSet, result, indexFieldToItrsMapping,
-        expansionList, finalItrs, context, checkList, iterOps);
+        expansionList, finalItrs, context, checkList, iterOps, theFilteringIndex);
     return returnSet;
   }
 
@@ -674,7 +675,7 @@ public class QueryUtils {
   private static void cutDownAndExpandIndexResults(SelectResults returnSet,
       SelectResults result, RuntimeIterator[] indexFieldToItrsMapping,
       List expansionList, List finalItrs, ExecutionContext context,
-      List checkList, CompiledValue iterOps) throws FunctionDomainException,
+      List checkList, CompiledValue iterOps, IndexInfo theFilteringIndex) throws FunctionDomainException,
       TypeMismatchException, NameResolutionException,
       QueryInvocationTargetException {
 //    Object[] checkFields = null;
@@ -692,13 +693,20 @@ public class QueryUtils {
     int limit = getLimitValue(context);
     
     while (itr.hasNext()) {
+      DerivedInfo derivedInfo = null;
+      if (IndexManager.JOIN_OPTIMIZATION) {
+        derivedInfo = new DerivedInfo();
+        derivedInfo.setExpansionList(expansionList);
+      }
       Object value = itr.next();
       if (setIndexFieldValuesInRespectiveIterators(value,  
           indexFieldToItrsMapping, icdeh)) {  //does that mean we don't get dupes even if they exist in the index?
         //         DO NESTED LOOPING
-       
+        if (IndexManager.JOIN_OPTIMIZATION) {
+          derivedInfo.computeDerivedJoinResults(theFilteringIndex, context, iterOps);
+        }  
         doNestedIterationsForIndex(expansionListIterator.hasNext(), returnSet,
-            finalItrs, expansionListIterator, context, iterOps, limit);
+            finalItrs, expansionListIterator, context, iterOps, limit, derivedInfo.derivedResults);
         if (limit != -1 && returnSet.size() >= limit) {
           break;
         }     
@@ -718,11 +726,19 @@ public class QueryUtils {
     }   
     return limit;
   }
+  
+  public static CompiledID getCompiledIdFromPath(CompiledValue path) {
+    int type = path.getType();
+    if (type == OQLLexerTokenTypes.Identifier) {
+      return (CompiledID) path;
+    } 
+    return getCompiledIdFromPath(path.getReceiver());
+  }
 
   //Add comments
   private static void doNestedIterationsForIndex(boolean continueRecursion,
       SelectResults resultSet, List finalItrs, ListIterator expansionItrs,
-      ExecutionContext context, CompiledValue iterOps, int limit)
+      ExecutionContext context, CompiledValue iterOps, int limit, Map<String, SelectResults> derivedResults)
       throws FunctionDomainException, TypeMismatchException,
       NameResolutionException, QueryInvocationTargetException {
     
@@ -768,7 +784,24 @@ public class QueryUtils {
     }
     else {
       RuntimeIterator currentLevel = (RuntimeIterator) expansionItrs.next();
-      SelectResults c = currentLevel.evaluateCollection(context);
+      SelectResults c = null;
+      // Calculate the key to find the derived join results. If we are a non nested lookup it will be a Compiled Region otherwise it will be a CompiledPath that
+      // we can extract the id from. In the end the result will be the alias which is used as a prefix
+      CompiledValue collectionExpression = currentLevel.getCmpIteratorDefn().getCollectionExpr();
+      String key = null;
+      boolean useDerivedResults = true;
+      if (currentLevel.getCmpIteratorDefn().getCollectionExpr().getType() == OQLLexerTokenTypes.RegionPath) {
+        key = currentLevel.getCmpIteratorDefn().getName() + ":" + currentLevel.getDefinition();
+      } else if (currentLevel.getCmpIteratorDefn().getCollectionExpr().getType() == OQLLexerTokenTypes.LITERAL_select) {
+        useDerivedResults = false;
+      } else {
+        key = getCompiledIdFromPath(currentLevel.getCmpIteratorDefn().getCollectionExpr()).getId() + ":" + currentLevel.getDefinition();
+      }
+      if (useDerivedResults && derivedResults != null && derivedResults.containsKey(key)) {
+        c = derivedResults.get(key);
+      } else {
+        c = currentLevel.evaluateCollection(context);
+      }
       //  RuntimeIterator next = expansionItrs.hasNext() ?
       // (RuntimeIterator)expansionItrs.next() : null;
       if (c == null) {
@@ -783,7 +816,7 @@ public class QueryUtils {
 
         currentLevel.setCurrent(cIter.next());
         doNestedIterationsForIndex(expansionItrs.hasNext(), resultSet,
-            finalItrs, expansionItrs, context, iterOps, limit);
+            finalItrs, expansionItrs, context, iterOps, limit, derivedResults);
         if (limit != -1 && resultSet.size() >= limit) {
           break;
         }     
@@ -1091,7 +1124,7 @@ public class QueryUtils {
             indexResults);
         indexResults = QueryUtils.cutDownAndExpandIndexResults(indexResults,
             ich.indexFieldToItrsMapping, ich.expansionList, ich.finalList,
-            context, ich.checkList, iterOperands);
+            context, ich.checkList, iterOperands, indexInfo);
       }
       finally {
         observer.afterCutDownAndExpansionOfSingleIndexResult(indexResults);
@@ -1108,7 +1141,7 @@ public class QueryUtils {
               indexInfo._index, indexResults);
           indexResults = QueryUtils.cutDownAndExpandIndexResults(indexResults,
               ich.indexFieldToItrsMapping, ich.expansionList, ich.finalList,
-              context, ich.checkList, iterOperands);
+              context, ich.checkList, iterOperands, indexInfo);
         }
         finally {
           observer.afterCutDownAndExpansionOfSingleIndexResult(indexResults);
@@ -1475,7 +1508,7 @@ public class QueryUtils {
               singlUsblIndxRes, context);
           cutDownAndExpandIndexResults(returnSet, singlUsblIndxRes,
               singleUsableICH.indexFieldToItrsMapping, totalExpList, finalList,
-              context, singleUsableICH.checkList, iterOperands);
+              context, singleUsableICH.checkList, iterOperands, singleUsableICH.indxInfo);
           singlUsblIndxRes.clear();
         }
       }
@@ -1700,7 +1733,7 @@ public class QueryUtils {
     return cutDownAndExpandIndexResults((SelectResults) dataList.get(0),
         (RuntimeIterator[]) dataList.get(1), (List) dataList.get(2),
         (List) dataList.get(3), (ExecutionContext) dataList.get(4),
-        (List) dataList.get(5), null);
+        (List) dataList.get(5), null, null);
   } 
   
   static List queryEquijoinConditionBucketIndexes(IndexInfo[] indxInfo,

http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/d232e259/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/IndexManager.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/IndexManager.java b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/IndexManager.java
index 534f757..3784327 100644
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/IndexManager.java
+++ b/gemfire-core/src/main/java/com/gemstone/gemfire/cache/query/internal/index/IndexManager.java
@@ -113,6 +113,8 @@ public class IndexManager  {
   // Threshold for Queue.
   private final int INDEX_MAINTENANCE_BUFFER = Integer.getInteger("gemfire.AsynchIndexMaintenanceThreshold", -1).intValue();
 
+  public static boolean JOIN_OPTIMIZATION = !Boolean.getBoolean("gemfire.index.DisableJoinOptimization");
+  
   // Added for test purposes only.
   public static boolean INPLACE_OBJECT_MODIFICATION_FOR_TEST = false;    
 
@@ -120,6 +122,8 @@ public class IndexManager  {
   public static boolean IS_TEST_LDM = false; 
 
   public static boolean IS_TEST_EXPANSION = false;
+  
+  
 
   /**
    * System property to maintain the ReverseMap to take care in-place modification of the 

http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/d232e259/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/EquijoinDUnitTest.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/EquijoinDUnitTest.java b/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/EquijoinDUnitTest.java
new file mode 100644
index 0000000..5718fce
--- /dev/null
+++ b/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/EquijoinDUnitTest.java
@@ -0,0 +1,437 @@
+/*
+ * 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 com.gemstone.gemfire.cache.query.internal.index;
+
+import java.io.Serializable;
+import java.text.ParseException;
+import java.util.HashMap;
+import java.util.Map;
+
+import junit.framework.TestCase;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.experimental.categories.Category;
+
+import com.gemstone.gemfire.cache.AttributesFactory;
+import com.gemstone.gemfire.cache.Cache;
+import com.gemstone.gemfire.cache.DataPolicy;
+import com.gemstone.gemfire.cache.Region;
+import com.gemstone.gemfire.cache.RegionAttributes;
+import com.gemstone.gemfire.cache.query.CacheUtils;
+import com.gemstone.gemfire.cache.query.FunctionDomainException;
+import com.gemstone.gemfire.cache.query.Index;
+import com.gemstone.gemfire.cache.query.IndexExistsException;
+import com.gemstone.gemfire.cache.query.IndexNameConflictException;
+import com.gemstone.gemfire.cache.query.NameResolutionException;
+import com.gemstone.gemfire.cache.query.QueryInvocationTargetException;
+import com.gemstone.gemfire.cache.query.QueryService;
+import com.gemstone.gemfire.cache.query.RegionNotFoundException;
+import com.gemstone.gemfire.cache.query.SelectResults;
+import com.gemstone.gemfire.cache.query.TypeMismatchException;
+import com.gemstone.gemfire.cache.query.functional.StructSetOrResultsSet;
+import com.gemstone.gemfire.test.junit.categories.IntegrationTest;
+
+@Category(IntegrationTest.class)
+public class EquijoinDUnitTest extends TestCase {
+  QueryService qs;
+  Region region1, region2, region3, region4;
+  
+  @Before
+  public void setUp() throws java.lang.Exception {
+    CacheUtils.startCache();
+    qs = CacheUtils.getQueryService();
+  }
+  
+  @After
+  public void tearDown() {
+    region2.destroyRegion();
+    region1.destroyRegion();
+  }
+  
+  protected void createRegions() throws Exception {
+    region1 = createReplicatedRegion("region1");
+    region2 = createReplicatedRegion("region2");
+  }
+  
+  protected void createAdditionalRegions() throws Exception {
+    region3 = createReplicatedRegion("region3");
+    region4 = createReplicatedRegion("region4");
+  }
+  
+  protected void destroyAdditionalRegions() throws Exception {
+    if (region3 != null) {
+      region3.destroyRegion();
+    }
+    if (region4 != null) {
+      region4.destroyRegion();
+    }
+  }
+
+  @Test
+  public void testSingleFilterWithSingleEquijoinOneToOneMapping() throws Exception {
+    createRegions();
+
+    String[] queries = new String[]{
+        "<trace>select * from /region1 c, /region2 s where c.pkid=1 and c.pkid = s.pkid",
+        "<trace>select * from /region1 c, /region2 s where c.pkid=1 and s.pkid = c.pkid",
+        "<trace>select * from /region1 c, /region2 s where c.pkid = s.pkid and c.pkid=1",
+        "<trace>select * from /region1 c, /region2 s where s.pkid = c.pkid and c.pkid=1",
+    };
+    
+    for (int i = 0; i < 1000; i++) {
+      region1.put( i, new Customer(i, i));
+      region2.put( i, new Customer(i, i));
+    }
+    
+    executeQueriesWithIndexCombinations(queries);
+  }
+  
+  @Test
+  public void testSingleFilterWithSingleEquijoinOneToOneMappingWithAdditionalJoins() throws Exception {
+    createRegions();
+    try {
+      createAdditionalRegions();
+      
+      String[] queries = new String[]{
+          "<trace>select * from /region1 c, /region2 s, /region3 d where c.pkid=1 and c.pkid = s.pkid and d.pkid = s.pkid",  //this should derive d after deriving s from c
+          "<trace>select * from /region1 c, /region2 s, /region3 d, /region4 f where c.pkid=1 and c.pkid = s.pkid and d.pkid = s.pkid and f.pkid = d.pkid",  //this should f from d from s from c
+          "<trace>select * from /region1 c, /region2 s, /region3 d where c.pkid=1 and c.pkid = s.pkid and d.pkid = c.pkid",  //this should derive d and s from c 
+          "<trace>select * from /region1 c, /region2 s, /region3 d where c.pkid=1 and c.pkid = s.pkid and s.pkid = d.pkid",  //this should derive d after deriving s from c (order is just switched in the query)
+      };
+      
+      for (int i = 0; i < 30; i++) {
+        region1.put( i, new Customer(i, i));
+        region2.put( i, new Customer(i, i));
+        region3.put( i, new Customer(i, i));
+        region4.put( i, new Customer(i, i));
+      }
+      
+      executeQueriesWithIndexCombinations(queries);
+    }
+    finally {
+      destroyAdditionalRegions();
+    }
+  }
+
+  
+  /**
+   * We do not want to test this with Primary Key on the many side or else only 1 result will be returned
+   */
+  @Test
+  public void testSingleFilterWithSingleEquijoinOneToManyMapping() throws Exception {
+    createRegions();
+
+    String[] queries = new String[]{
+        "select * from /region1 c, /region2 s where c.pkid=1 and c.pkid = s.pkid",
+        "select * from /region1 c, /region2 s where c.pkid=1 and s.pkid = c.pkid",
+        "select * from /region1 c, /region2 s where c.pkid = s.pkid and c.pkid=1",
+        "select * from /region1 c, /region2 s where s.pkid = c.pkid and c.pkid=1",
+    };
+    
+    for (int i = 0; i < 1000; i++) {
+      region1.put( i, new Customer(i, i));
+      region2.put( i, new Customer(i % 100, i));
+    }
+    
+    executeQueriesWithIndexCombinations(queries, new DefaultIndexCreatorCallback(qs) {
+      protected String[] createIndexTypesForRegion2() {
+        return new String[] { "Compact", "Hash"};
+      }
+    }, false);
+  }
+
+  @Test
+  public void testSingleFilterWithSingleEquijoinMultipleFiltersOnSameRegionOnSameIteratorMapping() throws Exception {
+    createRegions();
+
+    String[] queries = new String[]{
+        "select * from /region1 c, /region2 s where c.pkid=1 and c.pkid = s.pkid and c.id = 1",
+        "select * from /region1 c, /region2 s where c.id = 1 and c.pkid=1 and s.pkid = c.pkid",
+        
+    };
+    
+    for (int i = 0; i < 1000; i++) {
+      region1.put( i, new Customer(i, i % 10));
+      region2.put( i, new Customer(i, i));
+    }
+    
+    executeQueriesWithIndexCombinations(queries, new DefaultIndexCreatorCallback(qs) {
+      Index secondaryIndex;
+      
+      @Override
+      public void createIndexForRegion1(int indexTypeId) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException {
+        secondaryIndex = qs.createIndex("region1 id", "p.id", "/region1 p");
+        super.createIndexForRegion1(indexTypeId);
+      }
+
+      @Override
+      public void destroyIndexForRegion1(int indexTypeId) {
+        qs.removeIndex(secondaryIndex);
+        super.destroyIndexForRegion1(indexTypeId);
+      }
+      
+    }, false /*want to compare actual results and not size only*/);
+  }
+
+  @Test  
+  public void testSingleFilterWithSingleEquijoinWithRangeFilters() throws Exception {
+    createRegions();
+
+    String[] queries = new String[]{
+        "<trace>select * from /region1 c, /region2 s where c.pkid = 1 and c.id > 1 and c.id < 10 and c.pkid = s.pkid",
+        "<trace>select * from /region1 c, /region2 s where c.pkid >= 0 and c.pkid < 10 and c.id < 10 and c.pkid = s.pkid"
+    };
+    
+    //just need enough so that there are 1-10 ids per pkid
+    for (int i = 0; i < 1000; i++) {
+      region1.put(i, new Customer(i % 5, i % 10));
+      region2.put(i, new Customer(i, i));
+    }
+    
+    executeQueriesWithIndexCombinations(queries, new DefaultIndexCreatorCallback(qs) {
+      protected String[] createIndexTypesForRegion1() {
+        return new String[] { "Compact", "Hash"};
+      }
+    }, false /*want to compare actual results and not size only*/);
+  }
+
+  @Test 
+  public void testSingleFilterWithSingleEquijoinLimit() throws Exception {
+    //In this test we are hoping the index being used will properly use the limit while taking into consideration the filters of c.id and c.pkid
+    //This test is set up so that if the pkid index is used and limit applied, if id is not taken into consideration until later stages, it will lead to incorrect results (0)
+    createRegions();
+
+    String[] queries = new String[]{
+        "select * from /region1 c, /region2 s where c.id = 3 and c.pkid > 2  and c.pkid = s.pkid limit 1",
+    };
+    
+    for (int i = 0; i < 1000; i++) {
+      region1.put( i, new Customer(i, i % 10));
+      region2.put( i, new Customer(i, i));
+    }
+    
+    executeQueriesWithIndexCombinations(queries, new DefaultIndexCreatorCallback(qs) {
+      Index secondaryIndex;
+      
+      @Override
+      public void createIndexForRegion1(int indexTypeId) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException {
+        secondaryIndex = qs.createIndex("region1 id", "p.id", "/region1 p");
+        super.createIndexForRegion1(indexTypeId);
+      }
+
+      @Override
+      public void destroyIndexForRegion1(int indexTypeId) {
+        qs.removeIndex(secondaryIndex);
+        super.destroyIndexForRegion1(indexTypeId);
+      }
+      
+    }, true);
+  }
+
+  @Test
+  public void testSingleFilterWithSingleEquijoinNestedQuery() throws Exception {
+    createRegions();
+
+    String[] queries = new String[]{
+        "select * from /region1 c, /region2 s where c.pkid=1 and c.pkid = s.pkid and c.pkid in (select t.pkid from /region1 t,/region2 s where s.pkid=t.pkid and s.pkid = 1)",
+        "select * from /region1 c, /region2 s where c.pkid=1 and c.pkid = s.pkid or c.pkid in set (1,2,3,4)",
+    };
+    
+    for (int i = 0; i < 1000; i++) {
+      region1.put( i, new Customer(i, i));
+      region2.put( i, new Customer(i, i));
+    }
+    
+    executeQueriesWithIndexCombinations(queries);
+  }
+
+  public static class Customer implements Serializable {
+    public int pkid;
+    public int id;
+    public String name;
+    public Map<String, Customer> nested = new HashMap<String, Customer>();
+
+    public Customer(int pkid, int id) {
+      this.pkid = pkid;
+      this.id = id;
+      this.name = "name" + pkid;
+    }
+
+    public String toString() {
+      return "Customer pkid = " + pkid + ", id: " + id + " name:" + name;
+    }
+  }
+
+  private Region createReplicatedRegion(String regionName) throws ParseException {
+    Cache cache = CacheUtils.getCache();
+    AttributesFactory attributesFactory = new AttributesFactory();
+    attributesFactory.setDataPolicy(DataPolicy.REPLICATE);
+    RegionAttributes regionAttributes = attributesFactory.create();
+    return cache.createRegion(regionName, regionAttributes);
+  }
+
+  protected void executeQueriesWithIndexCombinations(String[] queries) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException, QueryInvocationTargetException, NameResolutionException, TypeMismatchException, FunctionDomainException {
+    executeQueriesWithIndexCombinations(queries, new DefaultIndexCreatorCallback(qs), false);
+  }
+  
+  protected void executeQueriesWithIndexCombinations(String[] queries, IndexCreatorCallback indexCreator, boolean sizeOnly) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException, QueryInvocationTargetException, NameResolutionException, TypeMismatchException, FunctionDomainException {
+    Object[] nonIndexedResults = executeQueries(queries);
+    
+    for (int r1Index = 0; r1Index < indexCreator.getNumIndexTypesForRegion1(); r1Index++) {
+      indexCreator.createIndexForRegion1(r1Index);
+      for (int r2Index = 0; r2Index < indexCreator.getNumIndexTypesForRegion2(); r2Index++) {
+        indexCreator.createIndexForRegion2(r2Index);
+        Object[] indexedResults = executeQueries(queries);
+        compareResults(nonIndexedResults, indexedResults, queries, sizeOnly);
+        indexCreator.destroyIndexForRegion2(r2Index);
+      }
+      indexCreator.destroyIndexForRegion1(r1Index);
+    }
+  }
+  
+  protected Object[] executeQueries(String[] queries) throws QueryInvocationTargetException, NameResolutionException, TypeMismatchException, FunctionDomainException {
+    Object[] results = new SelectResults[queries.length];
+    for (int i = 0; i < queries.length; i++) {
+      results[i] = qs.newQuery(queries[i]).execute();
+    }
+    return results;
+  }
+  
+  interface IndexCreatorCallback {
+    int getNumIndexTypesForRegion1();
+    int getNumIndexTypesForRegion2();
+    void createIndexForRegion1(int indexTypeId) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException;
+    void createIndexForRegion2(int indexTypeId) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException;
+    void destroyIndexForRegion1(int indexTypeId) ;
+    void destroyIndexForRegion2(int indexTypeId) ;
+  }
+  
+  static class DefaultIndexCreatorCallback implements IndexCreatorCallback {
+    protected String[] indexTypesForRegion1 = createIndexTypesForRegion1();
+    protected String[] indexTypesForRegion2 = createIndexTypesForRegion2();
+    protected Index indexOnR1, indexOnR2;
+    protected QueryService qs;
+    
+    DefaultIndexCreatorCallback(QueryService qs) {
+      this.qs = qs;
+    }
+    protected String[] createIndexTypesForRegion1() {
+      return new String[] { "Compact", "Hash", "PrimaryKey"};
+    }
+    
+    protected String[] createIndexTypesForRegion2() {
+      return new String[] { "Compact", "Hash", "PrimaryKey"};
+    }
+    
+    public int getNumIndexTypesForRegion1() {
+      return indexTypesForRegion1.length; 
+    }
+    
+    public int getNumIndexTypesForRegion2() {
+      return indexTypesForRegion2.length;
+    }
+    
+    public void createIndexForRegion1(int indexTypeId) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException {
+      indexOnR1 = createIndex(indexTypesForRegion1[indexTypeId], "region1", "pkid");
+
+    }
+    
+    public void createIndexForRegion2(int indexTypeId) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException {
+      indexOnR2 = createIndex(indexTypesForRegion2[indexTypeId], "region2", "pkid");
+    }
+
+    //Type id is not used here but at some future time we could store a map of indexes or find a use for this id?
+    public void destroyIndexForRegion1(int indexTypeId) {
+      qs.removeIndex(indexOnR1);
+    }
+    
+    public void destroyIndexForRegion2(int indexTypeId) {
+      qs.removeIndex(indexOnR2);
+    }
+    
+    
+    private Index createIndex(String type, String regionName, String field) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException {
+      Index index = null;
+      switch (type) {
+      case "Compact":
+        index = createCompactRangeIndex(regionName, field);
+        break;
+      case "Range":
+        index = createRangeIndexOnFirstIterator(regionName, field);
+        break;
+      case "Hash":
+        index = createHashIndex(regionName, field);
+        break;
+      case "PrimaryKey":
+        index = createPrimaryKeyIndex(regionName, field);
+        break;
+      }
+      return index;
+    }
+    
+    private Index createCompactRangeIndex(String regionName, String fieldName) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException {
+      String fromClause = "/" + regionName + " r";
+      String indexedExpression = "r." + fieldName;
+      return qs.createIndex("Compact " + fromClause + ":" + indexedExpression, indexedExpression, fromClause);
+    }
+    
+    private Index createHashIndex(String regionName, String fieldName) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException {
+      String fromClause = "/" + regionName + " r";
+      String indexedExpression = "r." + fieldName;
+      return qs.createHashIndex("Hash " + fromClause + ":" + indexedExpression, indexedExpression, fromClause);
+    }
+    
+    private Index createPrimaryKeyIndex(String regionName, String fieldName) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException {
+      String fromClause = "/" + regionName + " r";
+      String indexedExpression = "r." + fieldName;
+      return qs.createKeyIndex("PrimaryKey " + fromClause + ":" + indexedExpression, indexedExpression, fromClause);
+    }
+    
+    private Index createRangeIndexOnFirstIterator(String regionName, String fieldName) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException {
+      String fromClause = "/" + regionName + " r, r.nested.values v";
+      String indexedExpression = "r." + fieldName;
+      return qs.createIndex("Range " + fromClause + ":" + indexedExpression, indexedExpression, fromClause);
+    }
+    
+    private Index createRangeIndexOnSecondIterator(String regionName, String fieldName) throws RegionNotFoundException, IndexExistsException, IndexNameConflictException {
+      String fromClause = "/" + regionName + " r, r.nested.values v";
+      String indexedExpression = "v." + fieldName;
+      return qs.createIndex("Range " + fromClause + ":" + indexedExpression, indexedExpression, fromClause);
+    }
+  }
+  
+  private void compareResults(Object[] nonIndexedResults, Object[] indexedResults, String[] queries, boolean sizeOnly) {
+    if (sizeOnly) {
+      for (int i = 0; i < queries.length; i++) {
+        assertTrue(((SelectResults)nonIndexedResults[i]).size() == ((SelectResults)indexedResults[i]).size());
+        assertTrue(((SelectResults)nonIndexedResults[i]).size() > 0);
+      }
+    }
+    else {
+      StructSetOrResultsSet util = new StructSetOrResultsSet();
+      for (int i = 0; i < queries.length; i++) {
+        Object[][] resultsToCompare = new Object[1][2];
+        resultsToCompare[0][0] = nonIndexedResults[i];
+        resultsToCompare[0][1] = indexedResults[i];
+        util.CompareQueryResultsWithoutAndWithIndexes(resultsToCompare, 1, new String[]{queries[i]});
+        assertTrue(((SelectResults)nonIndexedResults[i]).size() > 0);
+      }
+    }
+  }
+}

http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/d232e259/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/PartitionedRegionEquijoinDUnitTest.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/PartitionedRegionEquijoinDUnitTest.java b/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/PartitionedRegionEquijoinDUnitTest.java
new file mode 100644
index 0000000..3fa6848
--- /dev/null
+++ b/gemfire-core/src/test/java/com/gemstone/gemfire/cache/query/internal/index/PartitionedRegionEquijoinDUnitTest.java
@@ -0,0 +1,130 @@
+/*
+ * 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 com.gemstone.gemfire.cache.query.internal.index;
+
+import java.util.ArrayList;
+
+import org.junit.Test;
+import org.junit.experimental.categories.Category;
+
+import com.gemstone.gemfire.cache.PartitionAttributesFactory;
+import com.gemstone.gemfire.cache.Region;
+import com.gemstone.gemfire.cache.RegionFactory;
+import com.gemstone.gemfire.cache.RegionShortcut;
+import com.gemstone.gemfire.cache.execute.Function;
+import com.gemstone.gemfire.cache.execute.FunctionContext;
+import com.gemstone.gemfire.cache.execute.FunctionService;
+import com.gemstone.gemfire.cache.execute.RegionFunctionContext;
+import com.gemstone.gemfire.cache.execute.ResultCollector;
+import com.gemstone.gemfire.cache.query.CacheUtils;
+import com.gemstone.gemfire.cache.query.QueryService;
+import com.gemstone.gemfire.cache.query.SelectResults;
+import com.gemstone.gemfire.test.junit.categories.IntegrationTest;
+
+@Category(IntegrationTest.class)
+public class PartitionedRegionEquijoinDUnitTest extends EquijoinDUnitTest {
+ 
+  @Override
+  protected void createRegions() {
+    region1 = createPartitionRegion("region1");
+    region2 = createColocatedPartitionRegion("region2", "region1");
+    FunctionService.registerFunction(equijoinTestFunction);
+  }
+  
+  @Override
+  protected void createAdditionalRegions() throws Exception {
+    region3 = createColocatedPartitionRegion("region3", "region1");
+    region4 = createColocatedPartitionRegion("region4", "region1");
+  }
+ 
+  @Test
+  public void testSingleFilterWithSingleEquijoinNestedQuery() throws Exception {
+    createRegions();
+
+    String[] queries = new String[]{
+        "select * from /region1 c, /region2 s where c.pkid=1 and c.pkid = s.pkid or c.pkid in set (1,2,3,4)",
+    };
+    
+    for (int i = 0; i < 1000; i++) {
+      region1.put( i, new Customer(i, i));
+      region2.put( i, new Customer(i, i));
+    }
+    
+    executeQueriesWithIndexCombinations(queries);
+  }
+
+  public Region createPartitionRegion(String regionName) {
+    PartitionAttributesFactory paf = new PartitionAttributesFactory();
+    RegionFactory factory = CacheUtils.getCache().createRegionFactory(RegionShortcut.PARTITION)
+        .setPartitionAttributes(paf.create());
+    return factory.create(regionName);
+  }
+ 
+  public Region createColocatedPartitionRegion(String regionName, final String colocatedRegion) {
+     PartitionAttributesFactory paf = new PartitionAttributesFactory();
+        paf.setColocatedWith(colocatedRegion);
+    RegionFactory factory = CacheUtils.getCache().createRegionFactory(RegionShortcut.PARTITION).setPartitionAttributes(paf.create());
+    return factory.create(regionName);
+  }
+  
+
+  @Override
+  protected Object[] executeQueries(String[] queries) {
+    ResultCollector collector = FunctionService.onRegion(region1).withArgs(queries).execute(equijoinTestFunction.getId());
+    Object result = collector.getResult();
+    return (Object[])((ArrayList)result).get(0);
+  }
+  
+  Function equijoinTestFunction = new Function(){
+    @Override
+    public boolean hasResult() {
+      return true;
+    }
+
+    @Override
+    public void execute(FunctionContext context) {
+      try {
+        String[] queries = (String[]) context.getArguments();
+        QueryService qs = CacheUtils.getCache().getQueryService();
+        
+        Object[] results = new SelectResults[queries.length];
+        for (int i = 0; i < queries.length; i++) {
+          results[i] = qs.newQuery(queries[i]).execute((RegionFunctionContext)context);
+        }
+        context.getResultSender().lastResult(results);
+      }
+      catch (Exception e) {
+        e.printStackTrace();
+      }
+    }
+
+    @Override
+    public String getId() {
+      return "Equijoin Query";
+    }
+
+    @Override
+    public boolean optimizeForWrite() {
+      return false;
+    }
+
+    @Override
+    public boolean isHA() {
+      return false;
+    }
+  };
+}


Mime
View raw message