Author: shawkins Date: 2011-03-28 12:51:03 -0400 (Mon, 28 Mar 2011) New Revision: 3044 Modified: trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/NewCalculateCostUtil.java trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleAssignOutputElements.java trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleImplementJoinStrategy.java trunk/engine/src/main/java/org/teiid/query/tempdata/TempTable.java trunk/engine/src/main/java/org/teiid/query/tempdata/TempTableDataManager.java trunk/engine/src/test/java/org/teiid/query/processor/TestTempTables.java Log: TEIID-1528 fix for using keys in implement join strategy Modified: trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/NewCalculateCostUtil.java =================================================================== --- trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/NewCalculateCostUtil.java 2011-03-28 14:35:36 UTC (rev 3043) +++ trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/NewCalculateCostUtil.java 2011-03-28 16:51:03 UTC (rev 3044) @@ -1009,9 +1009,13 @@ static boolean usesKey(PlanNode planNode, Collection<? extends SingleElementSymbol> allElements, QueryMetadataInterface metadata) throws QueryMetadataException, TeiidComponentException { //TODO: key preserved joins should be marked - return NodeEditor.findAllNodes(planNode, NodeConstants.Types.SOURCE, NodeConstants.Types.JOIN | NodeConstants.Types.SET_OP).size() == 1 + return isSingleTable(planNode) && usesKey(allElements, metadata); } + + static boolean isSingleTable(PlanNode planNode) { + return NodeEditor.findAllNodes(planNode, NodeConstants.Types.SOURCE, NodeConstants.Types.JOIN | NodeConstants.Types.SET_OP).size() == 1; + } public static boolean usesKey(Criteria crit, QueryMetadataInterface metadata) throws QueryMetadataException, TeiidComponentException { HashSet<ElementSymbol> elements = new HashSet<ElementSymbol>(); @@ -1028,12 +1032,17 @@ throws QueryMetadataException, TeiidComponentException { return usesKey(allElements, null, metadata, true); } - + public static boolean usesKey(Collection<? extends SingleElementSymbol> allElements, Set<GroupSymbol> groups, QueryMetadataInterface metadata, boolean unique) throws QueryMetadataException, TeiidComponentException { + return getKeyUsed(allElements, groups, metadata, unique) != null; + } + + public static Object getKeyUsed(Collection<? extends SingleElementSymbol> allElements, Set<GroupSymbol> groups, QueryMetadataInterface metadata, Boolean unique) + throws QueryMetadataException, TeiidComponentException { if(allElements == null || allElements.size() == 0) { - return false; + return null; } // Sort elements into groups @@ -1041,7 +1050,7 @@ for (SingleElementSymbol ses : allElements) { Expression ex = SymbolMap.getExpression(ses); if (!(ex instanceof ElementSymbol)) { - continue; + continue; //TODO: function based indexes are possible, but we don't have the metadata } ElementSymbol element = (ElementSymbol)ex; GroupSymbol group = element.getGroupSymbol(); @@ -1063,26 +1072,31 @@ // Look up keys Collection keys = null; - if (unique) { + if ((unique != null && unique) || unique == null) { keys = metadata.getUniqueKeysInGroup(group.getMetadataID()); - } else { - keys = metadata.getIndexesInGroup(group.getMetadataID()); + } + if ((unique != null && !unique) || unique == null) { + if (keys != null) { + keys = new ArrayList<Object>(keys); + } else { + keys = new ArrayList<Object>(2); + } + keys.addAll(metadata.getIndexesInGroup(group.getMetadataID())); } if(keys != null && keys.size() > 0) { // For each key, get key elements - Iterator keyIter = keys.iterator(); - while(keyIter.hasNext()) { - List keyElements = metadata.getElementIDsInKey(keyIter.next()); + for (Object key : keys) { + List keyElements = metadata.getElementIDsInKey(key); if(elements.containsAll(keyElements)) { // Used all elements of the key - return true; + return key; } } } } - return false; + return null; } private static float safeLog(float x) { Modified: trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleAssignOutputElements.java =================================================================== --- trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleAssignOutputElements.java 2011-03-28 14:35:36 UTC (rev 3043) +++ trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleAssignOutputElements.java 2011-03-28 16:51:03 UTC (rev 3044) @@ -351,10 +351,7 @@ PlanNode projectNode = allProjects.get(i); List<SingleElementSymbol> projectCols = (List<SingleElementSymbol>) projectNode.getProperty(NodeConstants.Info.PROJECT_COLS); - newCols = new ArrayList<SingleElementSymbol>(); - for(int j=0; j<filteredIndex.length; j++) { - newCols.add(projectCols.get(filteredIndex[j])); - } + newCols = filter(filteredIndex, projectCols); projectNode.setProperty(NodeConstants.Info.PROJECT_COLS, newCols); if (updateGroups) { @@ -406,6 +403,15 @@ return newCols; } + static List<SingleElementSymbol> filter(int[] filteredIndex, + List<SingleElementSymbol> projectCols) { + List<SingleElementSymbol> newCols = new ArrayList<SingleElementSymbol>(); + for(int j=0; j<filteredIndex.length; j++) { + newCols.add(projectCols.get(filteredIndex[j])); + } + return newCols; + } + /** * Check all branches for either a dup removal or a non all union. * Modified: trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleImplementJoinStrategy.java =================================================================== --- trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleImplementJoinStrategy.java 2011-03-28 14:35:36 UTC (rev 3043) +++ trunk/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleImplementJoinStrategy.java 2011-03-28 16:51:03 UTC (rev 3044) @@ -40,10 +40,14 @@ import org.teiid.query.optimizer.relational.plantree.NodeEditor; import org.teiid.query.optimizer.relational.plantree.NodeFactory; import org.teiid.query.optimizer.relational.plantree.PlanNode; +import org.teiid.query.optimizer.relational.plantree.NodeConstants.Info; import org.teiid.query.processor.relational.JoinNode.JoinStrategyType; import org.teiid.query.processor.relational.MergeJoinStrategy.SortOption; +import org.teiid.query.sql.lang.CompareCriteria; +import org.teiid.query.sql.lang.Criteria; import org.teiid.query.sql.lang.JoinType; import org.teiid.query.sql.lang.OrderBy; +import org.teiid.query.sql.symbol.ElementSymbol; import org.teiid.query.sql.symbol.GroupSymbol; import org.teiid.query.sql.symbol.SingleElementSymbol; import org.teiid.query.sql.util.SymbolMap; @@ -107,10 +111,66 @@ pushLeft = leftCost < context.getProcessorBatchSize() || leftCost / rightCost < 8; pushRight = rightCost < context.getProcessorBatchSize() || rightCost / leftCost < 8 || joinNode.getProperty(NodeConstants.Info.DEPENDENT_VALUE_SOURCE) != null; } - } + } - boolean pushedLeft = insertSort(joinNode.getFirstChild(), (List<SingleElementSymbol>) joinNode.getProperty(NodeConstants.Info.LEFT_EXPRESSIONS), joinNode, metadata, capabilitiesFinder, pushLeft); - insertSort(joinNode.getLastChild(), (List<SingleElementSymbol>) joinNode.getProperty(NodeConstants.Info.RIGHT_EXPRESSIONS), joinNode, metadata, capabilitiesFinder, pushRight); + List<SingleElementSymbol> leftExpressions = (List<SingleElementSymbol>) joinNode.getProperty(NodeConstants.Info.LEFT_EXPRESSIONS); + List<SingleElementSymbol> rightExpressions = (List<SingleElementSymbol>) joinNode.getProperty(NodeConstants.Info.RIGHT_EXPRESSIONS); + + //check index information on each side + //TODO: don't do null order compensation - in fact we should check what the order actually is, but we don't have that metadata + Object key = null; + boolean right = true; + //we check the right first, since it should be larger + if (joinNode.getLastChild().getType() == NodeConstants.Types.ACCESS && NewCalculateCostUtil.isSingleTable(joinNode.getLastChild())) { + key = NewCalculateCostUtil.getKeyUsed(rightExpressions, null, metadata, null); + } + if (key == null && joinNode.getFirstChild().getType() == NodeConstants.Types.ACCESS && NewCalculateCostUtil.isSingleTable(joinNode.getFirstChild())) { + key = NewCalculateCostUtil.getKeyUsed(leftExpressions, null, metadata, null); + right = false; + } + if (key != null) { + //redo the join predicates based upon the key alone + List<Object> keyCols = metadata.getElementIDsInKey(key); + int[] reorder = new int[keyCols.size()]; + List<Integer> toCriteria = new ArrayList<Integer>(rightExpressions.size() - keyCols.size()); + List<SingleElementSymbol> keyExpressions = right?rightExpressions:leftExpressions; + for (int j = 0; j < keyExpressions.size(); j++) { + SingleElementSymbol ses = keyExpressions.get(j); + if (!(ses instanceof ElementSymbol)) { + continue; + } + ElementSymbol es = (ElementSymbol)ses; + boolean found = false; + for (int i = 0; !found && i < keyCols.size(); i++) { + if (es.getMetadataID().equals(keyCols.get(i))) { + reorder[i] = j; + found = true; + } + } + if (!found) { + toCriteria.add(j); + } + } + List<Criteria> joinCriteria = (List<Criteria>) joinNode.getProperty(Info.JOIN_CRITERIA); + for (int index : toCriteria) { + SingleElementSymbol lses = leftExpressions.get(index); + SingleElementSymbol rses = rightExpressions.get(index); + CompareCriteria cc = new CompareCriteria(lses, CompareCriteria.EQ, rses); + if (joinCriteria == null || joinCriteria.isEmpty()) { + joinCriteria = new ArrayList<Criteria>(); + joinCriteria.add(cc); + joinNode.setProperty(Info.JOIN_TYPE, JoinType.JOIN_INNER); + } + } + joinNode.setProperty(Info.JOIN_CRITERIA, joinCriteria); + leftExpressions = RuleAssignOutputElements.filter(reorder, leftExpressions); + rightExpressions = RuleAssignOutputElements.filter(reorder, rightExpressions); + joinNode.setProperty(NodeConstants.Info.LEFT_EXPRESSIONS, leftExpressions); + joinNode.setProperty(NodeConstants.Info.RIGHT_EXPRESSIONS, rightExpressions); + } + + boolean pushedLeft = insertSort(joinNode.getFirstChild(), leftExpressions, joinNode, metadata, capabilitiesFinder, pushLeft); + insertSort(joinNode.getLastChild(), rightExpressions, joinNode, metadata, capabilitiesFinder, pushRight); if (joinNode.getProperty(NodeConstants.Info.JOIN_TYPE) == JoinType.JOIN_INNER && (!pushRight || !pushedLeft)) { joinNode.setProperty(NodeConstants.Info.JOIN_STRATEGY, JoinStrategyType.PARTITIONED_SORT); Modified: trunk/engine/src/main/java/org/teiid/query/tempdata/TempTable.java =================================================================== --- trunk/engine/src/main/java/org/teiid/query/tempdata/TempTable.java 2011-03-28 14:35:36 UTC (rev 3043) +++ trunk/engine/src/main/java/org/teiid/query/tempdata/TempTable.java 2011-03-28 16:51:03 UTC (rev 3044) @@ -281,6 +281,7 @@ private List<Integer> notNull = new LinkedList<Integer>(); private Map<Integer, AtomicInteger> sequences; + private int uniqueColIndex; TempTable(TempMetadataID tid, BufferManager bm, List<ElementSymbol> columns, int primaryKeyLength, String sessionID) { this.tid = tid; @@ -294,6 +295,7 @@ rowId = new AtomicInteger(); tree = bm.createSTree(columns, sessionID, 1); } else { + this.uniqueColIndex = primaryKeyLength; tree = bm.createSTree(columns, sessionID, primaryKeyLength); } this.columnMap = RelationalNode.createLookupMap(columns); @@ -321,7 +323,7 @@ this.leafBatchSize = bm.getSchemaSize(columns.subList(0, primaryKeyLength)); } - void addIndex(List<ElementSymbol> indexColumns) throws TeiidComponentException, TeiidProcessingException { + void addIndex(List<ElementSymbol> indexColumns, boolean unique) throws TeiidComponentException, TeiidProcessingException { List<ElementSymbol> keyColumns = columns.subList(0, tree.getKeyLength()); if (keyColumns.equals(indexColumns) || (indexTables != null && indexTables.containsKey(indexColumns))) { return; @@ -335,6 +337,9 @@ TempTable indexTable = new TempTable(new TempMetadataID("idx", Collections.EMPTY_LIST), this.bm, allColumns, allColumns.size(), this.sessionID); //$NON-NLS-1$ indexTable.setPreferMemory(this.tree.isPreferMemory()); indexTable.lock = this.lock; + if (unique) { + indexTable.uniqueColIndex = indexColumns.size(); + } if (indexTables == null) { indexTables = new LinkedHashMap<List<ElementSymbol>, TempTable>(); indexTables.put(indexColumns, indexTable); @@ -447,19 +452,24 @@ * TODO: this should also factor in the block size */ private int estimateCost(OrderBy orderBy, IndexInfo ii, int rowCost) { + int initialCost = rowCost; if (ii.valueSet.size() != 0) { int length = ii.valueSet.get(0).size(); rowCost = ii.valueSet.size() * (ii.table.getPkLength() - length + 1); + if (ii.table.uniqueColIndex != length) { + rowCost *= 3; + } } else if (ii.upper != null) { rowCost /= 3; } else if (ii.lower != null) { rowCost /= 3; } - int cost = Math.max(1, rowCost); + int additionalCost = Math.max(0, initialCost - rowCost); + int cost = Math.min(initialCost, Math.max(1, rowCost)); if (cost > 1 && (!ii.covering || (orderBy != null && ii.ordering == null))) { cost *= (32 - Integer.numberOfLeadingZeros(cost - 1)); } - return cost; + return cost + additionalCost; } private TupleBrowser createTupleBrower(Criteria condition, boolean direction) throws TeiidComponentException { Modified: trunk/engine/src/main/java/org/teiid/query/tempdata/TempTableDataManager.java =================================================================== --- trunk/engine/src/main/java/org/teiid/query/tempdata/TempTableDataManager.java 2011-03-28 14:35:36 UTC (rev 3043) +++ trunk/engine/src/main/java/org/teiid/query/tempdata/TempTableDataManager.java 2011-03-28 16:51:03 UTC (rev 3044) @@ -523,11 +523,11 @@ //TODO: could pre-process indexes to remove overlap for (Object index : metadata.getIndexesInGroup(group.getMetadataID())) { List<ElementSymbol> columns = resolveIndex(metadata, allColumns, index); - table.addIndex(columns); + table.addIndex(columns, false); } for (Object key : metadata.getUniqueKeysInGroup(group.getMetadataID())) { List<ElementSymbol> columns = resolveIndex(metadata, allColumns, key); - table.addIndex(columns); + table.addIndex(columns, true); } table.setUpdatable(updatable); } catch (TeiidComponentException e) { Modified: trunk/engine/src/test/java/org/teiid/query/processor/TestTempTables.java =================================================================== --- trunk/engine/src/test/java/org/teiid/query/processor/TestTempTables.java 2011-03-28 14:35:36 UTC (rev 3043) +++ trunk/engine/src/test/java/org/teiid/query/processor/TestTempTables.java 2011-03-28 16:51:03 UTC (rev 3044) @@ -38,6 +38,8 @@ import org.teiid.dqp.internal.process.SessionAwareCache; import org.teiid.metadata.FunctionMethod.Determinism; import org.teiid.query.metadata.TempMetadataAdapter; +import org.teiid.query.optimizer.TestOptimizer; +import org.teiid.query.optimizer.TestOptimizer.ComparisonMode; import org.teiid.query.tempdata.TempTableDataManager; import org.teiid.query.tempdata.TempTableStore; import org.teiid.query.unittest.FakeMetadataFactory; @@ -50,8 +52,10 @@ private TempTableDataManager dataManager; private TempTableStore tempStore; - private void execute(String sql, List[] expectedResults) throws Exception { - execute(TestProcessor.helpGetPlan(sql, metadata), expectedResults); + private ProcessorPlan execute(String sql, List[] expectedResults) throws Exception { + ProcessorPlan plan = TestProcessor.helpGetPlan(sql, metadata); + execute(plan, expectedResults); + return plan; } private void execute(ProcessorPlan processorPlan, List[] expectedResults) throws Exception { @@ -296,6 +300,15 @@ execute("exec pm1.vsp60()", new List[] {Arrays.asList("First"), Arrays.asList("Second"), Arrays.asList("Third")}); } + /** + * Note that the order by reflects the key order, not the order in which the criteria was entered + */ + @Test public void testCompositeKeyJoinUsesKeyOrder() throws Exception { + execute("create local temporary table x (e1 string, e2 integer, primary key (e1, e2))", new List[] {Arrays.asList(0)}); //$NON-NLS-1$ + execute("create local temporary table x1 (e1 string, e2 integer)", new List[] {Arrays.asList(0)}); //$NON-NLS-1$ + TestOptimizer.helpPlan("select * from x, x1 where x.e2 = x1.e2 and x.e1 = x1.e1", this.metadata, new String[] {"SELECT x1.e2, x1.e1 FROM x1 ORDER BY x1.e1, x1.e2", "SELECT x.e2, x.e1 FROM x ORDER BY x.e1, x.e2"}, ComparisonMode.EXACT_COMMAND_STRING); + } + private void sampleTable() throws Exception { execute("create local temporary table x (e1 string, e2 integer, primary key (e1, e2))", new List[] {Arrays.asList(0)}); //$NON-NLS-1$ execute("insert into x (e2, e1) values (3, 'b')", new List[] {Arrays.asList(1)}); //$NON-NLS-1$