| /*========================================================================= |
| * Copyright (c) 2010-2014 Pivotal Software, Inc. All Rights Reserved. |
| * This product is protected by U.S. and international copyright |
| * and intellectual property laws. Pivotal products are covered by |
| * one or more patents listed at http://www.pivotal.io/patents. |
| *========================================================================= |
| */ |
| /* |
| * Created on Nov 18, 2005 |
| * |
| */ |
| package com.gemstone.gemfire.cache.query.internal; |
| |
| import java.util.ArrayList; |
| import java.util.Collections; |
| import java.util.Iterator; |
| import java.util.LinkedList; |
| import java.util.List; |
| import java.util.SortedSet; |
| import java.util.TreeSet; |
| 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.SelectResults; |
| import com.gemstone.gemfire.cache.query.TypeMismatchException; |
| import com.gemstone.gemfire.cache.query.internal.parse.OQLLexerTokenTypes; |
| import com.gemstone.gemfire.cache.query.internal.types.StructTypeImpl; |
| import com.gemstone.gemfire.cache.query.internal.SelectResultsComparator; |
| import com.gemstone.gemfire.cache.query.types.ObjectType; |
| import com.gemstone.gemfire.cache.query.types.StructType; |
| |
| /** |
| * An object of this class gets created during the organization of operands in a |
| * CompiledJunction. It gets created if there exists an equi join condition |
| * across two regions with range indexes available on both LHS as well as RHS of |
| * the condition. The CompositeGroupJunction may wrap GroupJunctions belonging |
| * to the regions participating in the equi join condition. A single |
| * CompositeGroupJunction may span multiple Regions and hence may contain |
| * multiple filter evaluatable equi join conditions of different regions as well |
| * as their GroupJunctions if any. |
| * |
| * @author asif |
| * |
| */ |
| public class CompositeGroupJunction extends AbstractCompiledValue implements |
| Filter, OQLLexerTokenTypes { |
| |
| private int operator = 0; |
| // Asif :This class Object creation itself indicates that there will be |
| // at least one filterable CC |
| private List filterableCC = new ArrayList(); |
| // Asif : Can be null |
| private List groupJunctions = null; |
| private boolean completeExpansion = false; |
| // TODO:Asif : Convert it into an array of independent iterators if possible. |
| private List indpndntItrs = null; |
| // Asif : can be null |
| private List iterOperands = null; |
| private RuntimeIterator[] indpndnts = null; |
| |
| CompositeGroupJunction(int operator, CompiledValue filterableCondn) { |
| this.operator = operator; |
| this.filterableCC.add(filterableCondn); |
| this.indpndntItrs = new ArrayList(); |
| } |
| |
| @Override |
| public List getChildren() { |
| List children = new ArrayList(); |
| if (this.groupJunctions != null) { |
| children.addAll(this.groupJunctions); |
| } |
| children.addAll(this.filterableCC); |
| return children; |
| } |
| |
| public Object evaluate(ExecutionContext context) { |
| throw new AssertionError("Should not have come here"); |
| } |
| |
| public int getType() { |
| return COMPOSITEGROUPJUNCTION; |
| } |
| |
| @Override |
| public SelectResults filterEvaluate(ExecutionContext context, |
| SelectResults intermediateResults) throws FunctionDomainException, |
| TypeMismatchException, NameResolutionException, |
| QueryInvocationTargetException { |
| if (this.operator == LITERAL_and) { |
| return evaluateAndJunction(context); |
| } |
| else { |
| return evaluateOrJunction(context); |
| } |
| } |
| |
| void addFilterableCompositeCondition(CompiledValue cv) { |
| this.filterableCC.add(cv); |
| } |
| |
| /** |
| * Add the Independent iterator of the Group which is constituent of this |
| * CompositeGroupJunction |
| * |
| * @param itr RuntimeIterator The independent iterator for the region forming |
| * the CompositeGroupJunction |
| */ |
| void addIndependentIterators(RuntimeIterator itr) { |
| this.indpndntItrs.add(itr); |
| } |
| |
| /** |
| * Add the GroupJunction for a Region as a part of CompositeGroupJunction , |
| * implying that their exists atleast one equi join condition which involes |
| * the Region which the GroupJunction represents |
| * |
| * @param gj GroupJunction object which is a part of CompositeGroupJunction |
| */ |
| void addGroupOrRangeJunction(AbstractGroupOrRangeJunction gj) { |
| if (this.groupJunctions == null) { |
| this.groupJunctions = new ArrayList(); |
| } |
| this.groupJunctions.add(gj); |
| } |
| |
| /** |
| * |
| * @param iterOps List of CompiledValues representing conditions which are |
| * iter evaluatable. This will be set only if there does not exist |
| * any independent condition or filter evaluatabel subtree |
| * CompiledJunction and the complete expansion flag is turned on |
| */ |
| void addIterOperands(List iterOps) { |
| if (this.iterOperands == null) { |
| this.iterOperands = new ArrayList(); |
| } |
| this.iterOperands.addAll(iterOps); |
| } |
| |
| /** |
| * |
| * This flag gets toggled if only a Single CompositeGroupJunction gets |
| * created. It means that an AllGroupJunction will not exist and the result |
| * obtained from the evaluation of CompositeGroupJunction will be expanded to |
| * the level of query from clause ( i.e top level iterators). |
| * |
| */ |
| void setCompleteExpansionOn() { |
| this.completeExpansion = true; |
| if (this.groupJunctions != null && this.groupJunctions.size() == 1) { |
| AbstractGroupOrRangeJunction gj = (AbstractGroupOrRangeJunction) this.groupJunctions.get(0); |
| gj.setCompleteExpansionOn(); |
| } |
| } |
| |
| void setArrayOfIndependentItrs() { |
| this.indpndnts = new RuntimeIterator[this.indpndntItrs.size()]; |
| this.indpndnts = (RuntimeIterator[]) this.indpndntItrs |
| .toArray(this.indpndnts); |
| //TODO:Asif identifying a cleaner way of making the |
| this.indpndntItrs = null; |
| } |
| |
| /** |
| * |
| * @param temp CompositeGroupJunction which gets merged in this |
| * CompositeGroupJunction. This fusion occurs during creation of |
| * junction if the order in which the conditions of where clause |
| * arrival are such that condition1 tying region1 & region2 , |
| * condition 2 tying region 3 & region 4 and condition 3 tying region |
| * 3 and region 4. In such case , finally it should result in a |
| * single CompositeGroupJunction containing region1, region2 , region |
| * 3 and region4 conditions and theire correspodning GroupJunctions |
| * if any. |
| */ |
| void mergeFilterableCCsAndIndependentItrs(CompositeGroupJunction temp) { |
| this.filterableCC.addAll(temp.filterableCC); |
| this.indpndntItrs.addAll(temp.indpndntItrs); |
| } |
| |
| private SelectResults evaluateAndJunction(ExecutionContext context) |
| throws FunctionDomainException, TypeMismatchException, |
| NameResolutionException, QueryInvocationTargetException { |
| // Asif: We will evaluate the iter operand while getting the result of |
| // composite condition iff there exists only one Filterable Composite |
| // Condition & no GroupJunction |
| CompiledValue iterOp = null; |
| SelectResults intermediateResults = null; |
| // TODO: Check if null can come for the iter operand List |
| if (this.iterOperands != null && !this.iterOperands.isEmpty()) { |
| int len = this.iterOperands.size(); |
| if (len == 1) { |
| iterOp = (CompiledValue) this.iterOperands.get(0); |
| } |
| else { |
| CompiledValue[] newOperands = new CompiledValue[len]; |
| newOperands = (CompiledValue[]) this.iterOperands.toArray(newOperands); |
| iterOp = new CompiledJunction(newOperands, this.operator); |
| } |
| } |
| SortedSet intersectionSet = new TreeSet(new SelectResultsComparator()); |
| // TODO:Asif: Clean this logic. If the iter operand is not null when should |
| // we evaluate it.? Ideally if we were to stick to our logic of delaying |
| // evaluation of condition , then we shoudl ideally first do intersection of |
| // results obtained using indexes on conditions & then apply iter operand on |
| // it. But some how it appears that the final iteration will be more |
| // expensive then evaluation. So we use for time being following idea. If |
| // the iter condition is not null & there exists atleast one Group Junction |
| // ( then we are sure it will need expansion to CompositeGroupJunction |
| // level, so the iter operand can be evaluated at that point, else we will |
| // evaluate it with the first available filterable cc |
| |
| // Asif : Obtain results of Filter evaluatable composite conditions |
| // Support.Assert( iterOp == null || ( iterOp !=null && |
| // this.filterableCC.size() == 1 && this.groupJunctions == null), "The Iter |
| // operand can be not null only if there exists single filterable CC & no |
| // group junction"); |
| boolean delayIterOpEval = (this.groupJunctions != null && this.groupJunctions |
| .size() != 0); |
| Iterator itr = this.filterableCC.iterator(); |
| int filterableCCSize = this.filterableCC.size(); |
| if (filterableCCSize > 1) { |
| for (int i = 0; i < (filterableCCSize - 1); i++) { |
| CompiledValue cc = (CompiledValue) itr.next(); |
| intermediateResults = ((Filter) cc) |
| .filterEvaluate(context, intermediateResults, false, |
| null/* iterOpn = null */, null/* send independent itrs null */, false,true, false); |
| if (intermediateResults.isEmpty()) { |
| StructType structType = QueryUtils .createStructTypeForRuntimeIterators( |
| this.completeExpansion ? context.getCurrentIterators() : QueryUtils. |
| getDependentItrChainForIndpndntItrs( this.indpndnts, context)); |
| return QueryUtils.createStructCollection(context, structType) ; |
| } |
| } |
| } |
| CompiledValue cc = (CompiledValue) itr.next(); |
| intermediateResults = ((Filter) cc).filterEvaluate(context, |
| intermediateResults, this.completeExpansion, delayIterOpEval ? null |
| : iterOp, this.indpndnts /* |
| * Since this is the last condition pass |
| * the indpndt. grp of itrs so that result |
| * structset with correct placement of itrs |
| * can be formed |
| */, false,true,false); |
| intersectionSet.add(intermediateResults); |
| intermediateResults = null; |
| if (iterOp != null && !delayIterOpEval) { |
| iterOp = null; |
| } |
| Support |
| .Assert( |
| iterOp == null || (this.groupJunctions != null), |
| "The Iter operand can be not null only if there exists atleast one group junction"); |
| // TODO:Asif Put this function in some Util class so that both |
| // AllGroupJunction & CompositeGroupJunction |
| // can use it. Identify a cleaner approach to it other than null check |
| if (this.groupJunctions != null) { |
| int len = this.groupJunctions.size(); |
| if (len > 1) { |
| // Asif : Create an array of SelectResults for each of the GroupJunction |
| // For each Group Junction there will be a corresponding array of |
| // RuntimeIterators |
| // which will map to the fields of the ResultSet obtained from |
| // Group Junction |
| SelectResults[] results = new SelectResults[len]; |
| // Asif : the final list will be some of all the iterators depending on |
| // each of indpendent group if complete expansion is not needed |
| List finalList = null; |
| if (this.completeExpansion) { |
| finalList = context.getCurrentIterators(); |
| } |
| else { |
| finalList = QueryUtils.getDependentItrChainForIndpndntItrs( |
| this.indpndnts, context); |
| } |
| List expansionList = new LinkedList(finalList); |
| RuntimeIterator[][] itrsForResultFields = new RuntimeIterator[len][]; |
| AbstractGroupOrRangeJunction gj = null; |
| Iterator junctionItr = this.groupJunctions.iterator(); |
| List grpItrs = null; |
| int j = 0; |
| RuntimeIterator tempItr = null; |
| while (junctionItr.hasNext()) { |
| gj = (AbstractGroupOrRangeJunction) junctionItr.next(); |
| SelectResults filterResults = ((Filter) gj).filterEvaluate(context, |
| null); |
| Support.Assert(filterResults != null, |
| "FilterResults cannot be null here"); |
| if (filterResults.isEmpty()) { |
| // TODO Asif : Compact the code of creation of empty set. |
| // Asif: Create an empty resultset of the required type & return |
| // it. e cannot use the existing Resultset as it may not be expanded |
| // to the required level. |
| SelectResults empty = null; |
| if (finalList.size() == 1) { |
| ObjectType type = ((RuntimeIterator) finalList.iterator().next()) |
| .getElementType(); |
| if (type instanceof StructType) { |
| empty = QueryUtils.createStructCollection(context, (StructTypeImpl) type) ; |
| } |
| else { |
| empty = QueryUtils.createResultCollection(context, type); |
| } |
| } |
| else { |
| StructType strucType =QueryUtils.createStructTypeForRuntimeIterators(finalList); |
| empty = QueryUtils.createStructCollection(context, strucType) ; |
| } |
| return empty; |
| } |
| else { |
| results[j] = filterResults; |
| grpItrs = context.getCurrScopeDpndntItrsBasedOnSingleIndpndntItr(gj |
| .getIndependentIteratorForGroup()[0]); |
| itrsForResultFields[j] = new RuntimeIterator[grpItrs.size()]; |
| Iterator grpItr = grpItrs.iterator(); |
| int k = 0; |
| while (grpItr.hasNext()) { |
| tempItr = (RuntimeIterator) grpItr.next(); |
| itrsForResultFields[j][k++] = tempItr; |
| expansionList.remove(tempItr); |
| } |
| ++j; |
| } |
| } |
| // Do the cartesian of the different group junction results. |
| //TODO:Asif Remove the time |
| QueryObserver observer = QueryObserverHolder.getInstance(); |
| observer |
| .beforeCartesianOfGroupJunctionsInCompositeGroupJunctionOfType_AND(results); |
| SelectResults grpCartRs = QueryUtils.cartesian(results, |
| itrsForResultFields, expansionList, finalList, context, iterOp); |
| observer |
| .afterCartesianOfGroupJunctionsInCompositeGroupJunctionOfType_AND(); |
| Support.Assert(grpCartRs != null, |
| "ResultsSet obtained was NULL in CompositeGroupJunction"); |
| intersectionSet.add(grpCartRs); |
| } |
| else { |
| // TODO:Asif : Examine this logic as expansion of a GroupJunction to a a |
| // CompositeGroupJunction level may not be a good idea, as each filter |
| // evaluatable condition in a GroupJunction will have to be |
| // unnecessarily expanded to the Composite GroupJunction level . This |
| // will be a heavy operation & also the size of the sets to be |
| // intersected will also be quite large. Ideally we should expand the |
| // GroupJunction to CompositeGroupJunction level only if there exists a |
| // single filter evaluatable condition in a GroupJunction. Asif : If |
| // there exists only one GroupJunction in a CompsoiteGroupJunction , |
| // then we can afford to expand the result of GroupJunction to the level |
| // of CompositeGroupJunction directly within the GroupJunction Thus |
| // create a new GroupJunction with independent group of iterators same |
| // as that of CompositeGroupJunction if complete expansion is false. If |
| // complete expansion is true then create a new GroupJunction only if |
| // there is residual iter operand. Thus this is the only special case (& |
| // iff completeExpansion boolean false) where in a GroupJunction will |
| // contain more than one independent iterators TODO:ASIF: CHECK IT |
| // OUT.................. |
| |
| AbstractGroupOrRangeJunction newGJ = (AbstractGroupOrRangeJunction) this.groupJunctions.get(0); |
| if (!this.completeExpansion) { |
| newGJ = newGJ.recreateFromOld( this.completeExpansion,this.indpndnts, iterOp); |
| } |
| else if (iterOp != null) { |
| // Asif :Complete expansion is true. In this case we should not pass |
| // the Group of iterators belonging to the CompositeGroupJunction but |
| // stick to independent iterator for the group. Also we are creating a |
| // new GroupJunction below only bcoz of extra iter operand. For |
| // toggling the complete xpansion flag of Grp Junction to on , that |
| // task is alreday done. in setCompleteExpansionOn of CGJ |
| |
| newGJ = newGJ.recreateFromOld(this.completeExpansion, newGJ.getIndependentIteratorForGroup(), iterOp); |
| } |
| SelectResults rs = newGJ.filterEvaluate(context, null); |
| if (rs.isEmpty()) { |
| return rs; |
| } |
| else { |
| intersectionSet.add(rs); |
| } |
| } |
| } |
| Iterator iter = intersectionSet.iterator(); |
| while (iter.hasNext()) { |
| SelectResults sr = (SelectResults) iter.next(); |
| intermediateResults = (intermediateResults == null) ? sr : QueryUtils |
| .intersection(intermediateResults, sr, context); |
| } |
| return intermediateResults; |
| } |
| |
| /** invariant: the operand is known to be evaluated by iteration */ |
| private SelectResults evaluateOrJunction(ExecutionContext context) |
| throws FunctionDomainException, TypeMismatchException, |
| NameResolutionException, QueryInvocationTargetException { |
| SelectResults intermediateResults = null; |
| Iterator itr = this.filterableCC.iterator(); |
| Support.Assert(this.iterOperands == null || this.iterOperands.isEmpty(), |
| "The iter operands shoudl not have been present for OR junction"); |
| while (itr.hasNext()) { |
| CompiledValue cc = (CompiledComparison) itr.next(); |
| SelectResults sr = ((Filter) cc).filterEvaluate(context, null, |
| this.completeExpansion, null, this.indpndnts,false,true,false); |
| intermediateResults = (intermediateResults == null) ? sr : QueryUtils |
| .union(intermediateResults, sr, context); |
| } |
| //TODO:Asif Identify a cleaner approach |
| if (this.groupJunctions != null) { |
| int len = this.groupJunctions.size(); |
| if (len > 1) { |
| // Asif : Create an array of SelectResults for each of the GroupJunction |
| // For each Group Junction there will be a corresponding array of |
| // RuntimeIterators which will map to the fields of the ResultSet |
| // obtained from Group Junction. |
| SelectResults[] grpResults = new SelectResults[1]; |
| // Asif : the final list will be some of all the iterators depending on |
| // each of indpendent group if complete expansion is not needed |
| List finalList = null; |
| if (this.completeExpansion) { |
| finalList = context.getCurrentIterators(); |
| } |
| else { |
| finalList = QueryUtils.getDependentItrChainForIndpndntItrs( |
| this.indpndnts, context); |
| } |
| RuntimeIterator[][] itrsForResultFields = new RuntimeIterator[1][]; |
| |
| AbstractGroupOrRangeJunction gj = null; |
| Iterator junctionItr = this.groupJunctions.iterator(); |
| List grpItrs = null; |
| RuntimeIterator tempItr = null; |
| while (junctionItr.hasNext()) { |
| List expansionList = new LinkedList(finalList); |
| gj = (AbstractGroupOrRangeJunction) junctionItr.next(); |
| grpResults[0] = ((Filter) gj).filterEvaluate(context, null); |
| grpItrs = context.getCurrScopeDpndntItrsBasedOnSingleIndpndntItr(gj |
| .getIndependentIteratorForGroup()[0]); |
| itrsForResultFields[0] = new RuntimeIterator[grpItrs.size()]; |
| Iterator grpItr = grpItrs.iterator(); |
| int k = 0; |
| while (grpItr.hasNext()) { |
| tempItr = (RuntimeIterator) grpItr.next(); |
| itrsForResultFields[0][k++] = tempItr; |
| expansionList.remove(tempItr); |
| } |
| SelectResults expandedResult = QueryUtils.cartesian(grpResults, |
| itrsForResultFields, expansionList, finalList, context, null/* |
| * Iter |
| * oprenad |
| * for |
| * OR |
| * Junction |
| * evaluation |
| * should |
| * be |
| * null |
| */); |
| intermediateResults = (intermediateResults == null) ? expandedResult |
| : QueryUtils.union(expandedResult, intermediateResults, context); |
| } |
| } |
| else { |
| // Asif : If there exists only one GroupJunction in a |
| // CompsoiteGroupJunction , then we can afford to expand the |
| // result of GroupJunction to the level of CompositeGroupJunction |
| // directly within the GroupJunction Thus create a new GroupJunction |
| // with independent group of iterators same as that of |
| // CompositeGroupJunction This is the only special case where in |
| // GroupJunction will contain more than one independent iterators If |
| // Complete expansion is true, In this case we should not pass the |
| // Group of iterators belonging to the CompositeGroupJunction but stick |
| // to independent iterator for the group. |
| AbstractGroupOrRangeJunction newGJ = (AbstractGroupOrRangeJunction) this.groupJunctions.get(0); |
| if (!this.completeExpansion) { |
| //TODO:Asif: Check it out .................. |
| newGJ = newGJ.recreateFromOld( this.completeExpansion, this.indpndnts, null); |
| } |
| SelectResults rs = newGJ.filterEvaluate(context, null); |
| intermediateResults = (intermediateResults == null) ? rs : QueryUtils |
| .union(rs, intermediateResults, context); |
| } |
| } |
| return intermediateResults; |
| } |
| |
| /* Package methods */ |
| public int getOperator() { |
| return operator; |
| } |
| |
| /** |
| * @return Array of RuntimeIterator which represent the independent iterators |
| * of each Group which form the CompositeGroupJunction |
| */ |
| //TODO:Asif : Identify a way to make it unmodifiable |
| RuntimeIterator[] getIndependentIteratorsOfCJ() { |
| return this.indpndnts; |
| } |
| |
| /** |
| * |
| * @return List containing the filter evaluatable Composite Comparison |
| * conditions ( equi join conditions across the regions) |
| */ |
| List getFilterableCCList() { |
| // return unmodifiable copy |
| return Collections.unmodifiableList(this.filterableCC); |
| } |
| |
| /** |
| * |
| * @return List containg GroupJunctions which are part of this |
| * CompositeGroupJunction. It can be null if there does not exist any |
| * filter evaluatable condition belonging solely to an independent |
| * region or its group of iterators, constituting the |
| * CompositeGroupJunction, so that no GroupJunctions get assosciated |
| * with the CompositeGroupJunction |
| * |
| */ |
| List getGroupJunctionList() { |
| // return unmodifiable copy |
| return this.groupJunctions != null ? Collections |
| .unmodifiableList(this.groupJunctions) : null; |
| } |
| |
| /** |
| * |
| * @return List containing the iter evaluatable conditions.This Can be null in |
| * case there exists more than one filter operand in CompiledJunction |
| * in which case all the iter ops will become part of iter operand of |
| * CompiledJunction. This can be not null iff the complete expansion |
| * flag is true |
| */ |
| List getIterOperands() { |
| return this.iterOperands != null ? Collections |
| .unmodifiableList(this.iterOperands) : null; |
| } |
| |
| boolean getExpansionFlag() { |
| return this.completeExpansion; |
| } |
| |
| public int getSizeEstimate(ExecutionContext context)throws FunctionDomainException, TypeMismatchException, NameResolutionException, QueryInvocationTargetException { |
| return 1; |
| } |
| } |
