Author: jolee Date: 2013-05-14 10:53:25 -0400 (Tue, 14 May 2013) New Revision: 4564 Modified: branches/7.7.x/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleImplementJoinStrategy.java branches/7.7.x/engine/src/main/java/org/teiid/query/processor/relational/EnhancedSortMergeJoinStrategy.java branches/7.7.x/engine/src/test/java/org/teiid/query/processor/TestOptionalJoins.java branches/7.7.x/engine/src/test/java/org/teiid/query/processor/relational/TestJoinNode.java branches/7.7.x/test-integration/common/src/test/java/org/teiid/systemmodel/TestODBCSchema.java Log: TEIID-2482: Allow the use of the enhanced join for left outer joins Modified: branches/7.7.x/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleImplementJoinStrategy.java =================================================================== --- branches/7.7.x/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleImplementJoinStrategy.java 2013-05-08 18:29:01 UTC (rev 4563) +++ branches/7.7.x/engine/src/main/java/org/teiid/query/optimizer/relational/rules/RuleImplementJoinStrategy.java 2013-05-14 14:53:25 UTC (rev 4564) @@ -42,13 +42,13 @@ import org.teiid.query.optimizer.relational.OptimizerRule; import org.teiid.query.optimizer.relational.RuleStack; import org.teiid.query.optimizer.relational.plantree.NodeConstants; +import org.teiid.query.optimizer.relational.plantree.NodeConstants.Info; 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.RelationalNode; import org.teiid.query.processor.relational.JoinNode.JoinStrategyType; import org.teiid.query.processor.relational.MergeJoinStrategy.SortOption; +import org.teiid.query.processor.relational.RelationalNode; import org.teiid.query.sql.lang.CompareCriteria; import org.teiid.query.sql.lang.CompoundCriteria; import org.teiid.query.sql.lang.Criteria; @@ -202,8 +202,8 @@ } boolean pushedRight = insertSort(joinNode.getLastChild(), rightExpressions, joinNode, metadata, capabilitiesFinder, pushRight); - - if (joinNode.getProperty(NodeConstants.Info.JOIN_TYPE) == JoinType.JOIN_INNER && (!pushedRight || !pushedLeft)) { + JoinType joinType = (JoinType) joinNode.getProperty(NodeConstants.Info.JOIN_TYPE); + if ((!pushedRight || !pushedLeft) && (joinType == JoinType.JOIN_INNER || (joinType == JoinType.JOIN_LEFT_OUTER && !pushedLeft))) { joinNode.setProperty(NodeConstants.Info.JOIN_STRATEGY, JoinStrategyType.ENHANCED_SORT); } } Modified: branches/7.7.x/engine/src/main/java/org/teiid/query/processor/relational/EnhancedSortMergeJoinStrategy.java =================================================================== --- branches/7.7.x/engine/src/main/java/org/teiid/query/processor/relational/EnhancedSortMergeJoinStrategy.java 2013-05-08 18:29:01 UTC (rev 4563) +++ branches/7.7.x/engine/src/main/java/org/teiid/query/processor/relational/EnhancedSortMergeJoinStrategy.java 2013-05-14 14:53:25 UTC (rev 4564) @@ -41,6 +41,7 @@ import org.teiid.logging.LogManager; import org.teiid.logging.MessageLevel; import org.teiid.query.processor.relational.SourceState.ImplicitBuffer; +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.SingleElementSymbol; @@ -100,6 +101,7 @@ private SourceState sortedSource; private SourceState notSortedSource; private List<?> currentTuple; + private boolean matched; private TupleBrowser tb; private SingleTupleSource keyTs; private int reserved; @@ -240,14 +242,14 @@ protected void loadRight() throws TeiidComponentException, TeiidProcessingException { //the checks are done in a particular order to ensure we don't buffer if possible - if (processingSortRight == SortOption.SORT && shouldIndexIfSmall(this.leftSource)) { + if (processingSortRight == SortOption.SORT && this.joinNode.getJoinType() != JoinType.JOIN_LEFT_OUTER && shouldIndexIfSmall(this.leftSource)) { this.processingSortRight = SortOption.NOT_SORTED; } else if (!this.leftSource.hasBuffer() && processingSortLeft == SortOption.SORT && shouldIndexIfSmall(this.rightSource)) { this.processingSortLeft = SortOption.NOT_SORTED; } else { - if (!this.rightSource.hasBuffer() && processingSortRight == SortOption.SORT && shouldIndexIfSmall(this.leftSource)) { + if (!this.rightSource.hasBuffer() && processingSortRight == SortOption.SORT && this.joinNode.getJoinType() != JoinType.JOIN_LEFT_OUTER && shouldIndexIfSmall(this.leftSource)) { this.processingSortRight = SortOption.NOT_SORTED; - } else if (processingSortRight == SortOption.SORT && shouldIndex(this.leftSource, this.rightSource)) { + } else if (processingSortRight == SortOption.SORT && this.joinNode.getJoinType() != JoinType.JOIN_LEFT_OUTER && shouldIndex(this.leftSource, this.rightSource)) { this.processingSortRight = SortOption.NOT_SORTED; } else if (processingSortLeft == SortOption.SORT && shouldIndex(this.rightSource, this.leftSource)) { this.processingSortLeft = SortOption.NOT_SORTED; @@ -302,15 +304,34 @@ } private boolean shouldIndex(SourceState possibleIndex, SourceState other) throws TeiidComponentException, TeiidProcessingException { - if (possibleIndex.getRowCount() * 4 > other.getRowCount()) { + long size = joinNode.getBatchSize(); + int indexSize = possibleIndex.hasBuffer()?possibleIndex.getRowCount():-1; + int otherSize = other.hasBuffer()?other.getRowCount():-1; + //determine sizes in an incremental fashion as to avoid a full buffer of the unsorted side + while (size < Integer.MAX_VALUE && (indexSize == -1 || otherSize == -1)) { + if (indexSize == -1 && (possibleIndex.rowCountLE((int)size) || possibleIndex.hasBuffer())) { + indexSize = possibleIndex.getRowCount(); + } + if (otherSize == -1 && (other.rowCountLE((int)size) || other.hasBuffer())) { + otherSize = other.getRowCount(); + } + if (indexSize == -1 && otherSize != -1 && size * 4 > otherSize) { + return false; + } + if (indexSize != -1 && otherSize == -1 && indexSize * 4 <= size) { + break; + } + size *=2; + } + if ((size > Integer.MAX_VALUE && (indexSize == -1 || otherSize == -1)) || (indexSize != -1 && otherSize != -1 && indexSize * 4 > otherSize)) { return false; //index is too large } int schemaSize = this.joinNode.getBufferManager().getSchemaSize(other.getSource().getOutputElements()); int toReserve = this.joinNode.getBufferManager().getMaxProcessingSize(); //check if the other side can be sorted in memory - if (other.getRowCount() <= this.joinNode.getBatchSize() - || (possibleIndex.getRowCount() > this.joinNode.getBatchSize() && other.getRowCount()/this.joinNode.getBatchSize() < toReserve/schemaSize)) { - return false; + if (other.hasBuffer() && ((other.getRowCount() <= this.joinNode.getBatchSize()) + || (possibleIndex.getRowCount() > this.joinNode.getBatchSize() && other.getRowCount()/this.joinNode.getBatchSize() < toReserve/schemaSize))) { + return false; //just use a merge join } boolean useIndex = false; int indexSchemaSize = this.joinNode.getBufferManager().getSchemaSize(possibleIndex.getSource().getOutputElements()); @@ -323,8 +344,14 @@ } if (useIndex) { reserved = this.joinNode.getBufferManager().reserveBuffers(toReserve, BufferReserveMode.FORCE); + if (other.hasBuffer()) { + other.getTupleBuffer().setForwardOnly(true); + } return true; } + if (joinNode.getJoinType() == JoinType.JOIN_LEFT_OUTER) { + return false; //repeated is not supported as it could produce multiple outer matches + } this.repeatedMerge = true; possibleIndex.setImplicitBuffer(ImplicitBuffer.FULL); return true; @@ -342,7 +369,7 @@ super.process(); return; } - if (this.sortedSource.getRowCount() == 0) { + if (this.sortedSource.getRowCount() == 0 && joinNode.getJoinType() != JoinType.JOIN_LEFT_OUTER) { return; } if (repeatedMerge) { @@ -361,9 +388,15 @@ while (true) { if (this.currentTuple == null) { currentTuple = this.currentSource.nextTuple(); + matched = false; if (currentTuple == null) { return; } + //short-cut when a match is not possible + if (this.sortedSource.getRowCount() == 0 && joinNode.getJoinType() == JoinType.JOIN_LEFT_OUTER) { + outerMatch(); + continue; + } if (validSemiDep) { List<?> tuple = this.currentTuple; this.currentTuple = null; @@ -377,7 +410,7 @@ sortedTuple = tb.nextTuple(); if (sortedTuple == null) { - currentTuple = null; + outerMatch(); continue; } } @@ -387,10 +420,19 @@ boolean matches = this.joinNode.matchesCriteria(outputTuple); this.sortedTuple = null; if (matches) { + matched = true; this.joinNode.addBatchRow(outputTuple); } } } + + private void outerMatch() { + List<?> tuple = currentTuple; + currentTuple = null; + if (!matched && joinNode.getJoinType() == JoinType.JOIN_LEFT_OUTER) { + this.joinNode.addBatchRow(outputTuple(tuple, this.rightSource.getOuterVals())); + } + } @Override public EnhancedSortMergeJoinStrategy clone() { Modified: branches/7.7.x/engine/src/test/java/org/teiid/query/processor/TestOptionalJoins.java =================================================================== --- branches/7.7.x/engine/src/test/java/org/teiid/query/processor/TestOptionalJoins.java 2013-05-08 18:29:01 UTC (rev 4563) +++ branches/7.7.x/engine/src/test/java/org/teiid/query/processor/TestOptionalJoins.java 2013-05-14 14:53:25 UTC (rev 4564) @@ -26,10 +26,9 @@ import java.util.List; import org.junit.Test; -import org.teiid.query.processor.ProcessorPlan; import org.teiid.query.unittest.RealMetadataFactory; - +@SuppressWarnings("rawtypes") public class TestOptionalJoins { @Test public void testOptionalJoinNode1() { @@ -134,10 +133,10 @@ @Test public void testOptionalJoinNode5() { // Create query - String sql = "SELECT pm1.g1.e1 FROM (pm1.g1 LEFT OUTER JOIN pm1.g2 on pm1.g1.e1 = pm1.g2.e1) LEFT OUTER JOIN /* optional */ pm1.g3 on pm1.g1.e1 = pm1.g3.e1"; //$NON-NLS-1$ + String sql = "SELECT pm1.g1.e1 FROM (pm1.g1 LEFT OUTER JOIN pm1.g2 on pm1.g1.e1 = pm1.g2.e1) LEFT OUTER JOIN /* optional */ pm1.g3 on pm1.g1.e1 = pm1.g3.e1 order by e1"; //$NON-NLS-1$ // Create expected results - List[] expected = new List[] { + List<?>[] expected = new List<?>[] { Arrays.asList(new Object[] { null }), Arrays.asList(new Object[] { "a" }), //$NON-NLS-1$ Arrays.asList(new Object[] { "a" }), //$NON-NLS-1$ @@ -165,7 +164,7 @@ @Test public void testOptionalJoinNode6() { // Create query - String sql = "SELECT pm1.g1.e1 FROM (pm1.g1 LEFT OUTER JOIN /* optional */ pm1.g2 on pm1.g1.e1 = pm1.g2.e1) LEFT OUTER JOIN pm1.g3 on pm1.g1.e1 = pm1.g3.e1"; //$NON-NLS-1$ + String sql = "SELECT pm1.g1.e1 FROM (pm1.g1 LEFT OUTER JOIN /* optional */ pm1.g2 on pm1.g1.e1 = pm1.g2.e1) LEFT OUTER JOIN pm1.g3 on pm1.g1.e1 = pm1.g3.e1 order by e1"; //$NON-NLS-1$ // Create expected results List[] expected = new List[] { Modified: branches/7.7.x/engine/src/test/java/org/teiid/query/processor/relational/TestJoinNode.java =================================================================== --- branches/7.7.x/engine/src/test/java/org/teiid/query/processor/relational/TestJoinNode.java 2013-05-08 18:29:01 UTC (rev 4563) +++ branches/7.7.x/engine/src/test/java/org/teiid/query/processor/relational/TestJoinNode.java 2013-05-14 14:53:25 UTC (rev 4564) @@ -51,7 +51,7 @@ import org.teiid.query.unittest.RealMetadataFactory; import org.teiid.query.util.CommandContext; -@SuppressWarnings("unchecked") +@SuppressWarnings({"unchecked", "rawtypes"}) public class TestJoinNode { private static final int NO_CRITERIA = 0; private static final int EQUAL_CRITERIA = 1; @@ -640,6 +640,77 @@ this.join.setJoinStrategy(joinStrategy); helpTestJoinDirect(expected, batchSize, 1); } + + @Test public void testMergeJoinOptimizationLeftOuter() throws Exception { + this.joinType = JoinType.JOIN_LEFT_OUTER; + int rows = 12; + List[] data = new List[rows]; + for(int i=0; i<rows; i++) { + data[i] = new ArrayList(); + Integer value = new Integer((i*17) % 45); + data[i].add(value); + } + this.leftTuples = data; + this.rightTuples = createTuples2(); + expected = new List[] { + Arrays.asList(new Object[] { 0, null }), + Arrays.asList(new Object[] {17, null }), + Arrays.asList(new Object[] {34, null }), + Arrays.asList(new Object[] { 6, 6 }), + Arrays.asList(new Object[] {23, null }), + Arrays.asList(new Object[] {40, null }), + Arrays.asList(new Object[] {12, null }), + Arrays.asList(new Object[] {29, null }), + Arrays.asList(new Object[] { 1, 1 }), + Arrays.asList(new Object[] {18, null }), + Arrays.asList(new Object[] {35, null }), + Arrays.asList(new Object[] { 7, 7 }), + Arrays.asList(new Object[] { 7, 7 }), + }; + + System.out.println(Arrays.toString(this.leftTuples)); + helpCreateJoin(); + EnhancedSortMergeJoinStrategy esmjs = new EnhancedSortMergeJoinStrategy(SortOption.NOT_SORTED, SortOption.SORT); + this.joinStrategy = esmjs; + this.join.setJoinStrategy(joinStrategy); + + helpTestJoinDirect(expected, 10, 1); + } + + @Test public void testMergeJoinOptimizationLeftOuterEmpty() throws Exception { + this.joinType = JoinType.JOIN_LEFT_OUTER; + int rows = 12; + List[] data = new List[rows]; + for(int i=0; i<rows; i++) { + data[i] = new ArrayList(); + Integer value = new Integer((i*17) % 45); + data[i].add(value); + } + this.leftTuples = data; + this.rightTuples = new List[0]; + expected = new List[] { + Arrays.asList(new Object[] { 0, null }), + Arrays.asList(new Object[] {17, null }), + Arrays.asList(new Object[] {34, null }), + Arrays.asList(new Object[] { 6, null }), + Arrays.asList(new Object[] {23, null }), + Arrays.asList(new Object[] {40, null }), + Arrays.asList(new Object[] {12, null }), + Arrays.asList(new Object[] {29, null }), + Arrays.asList(new Object[] { 1, null }), + Arrays.asList(new Object[] {18, null }), + Arrays.asList(new Object[] {35, null }), + Arrays.asList(new Object[] { 7, null }), + }; + + System.out.println(Arrays.toString(this.leftTuples)); + helpCreateJoin(); + EnhancedSortMergeJoinStrategy esmjs = new EnhancedSortMergeJoinStrategy(SortOption.NOT_SORTED, SortOption.SORT); + this.joinStrategy = esmjs; + this.join.setJoinStrategy(joinStrategy); + + helpTestJoinDirect(expected, 10, 1); + } @Test public void testMergeJoinOptimizationMultiBatch() throws Exception { helpTestEnhancedSortMergeJoin(10); Modified: branches/7.7.x/test-integration/common/src/test/java/org/teiid/systemmodel/TestODBCSchema.java =================================================================== --- branches/7.7.x/test-integration/common/src/test/java/org/teiid/systemmodel/TestODBCSchema.java 2013-05-08 18:29:01 UTC (rev 4563) +++ branches/7.7.x/test-integration/common/src/test/java/org/teiid/systemmodel/TestODBCSchema.java 2013-05-14 14:53:25 UTC (rev 4564) @@ -31,7 +31,7 @@ } @Test public void test_PG_ATTRDEF() throws Exception { - execute("select * FROM pg_attrdef"); //$NON-NLS-1$ + execute("select * FROM pg_attrdef order by adrelid, adnum"); //$NON-NLS-1$ TestMMDatabaseMetaData.compareResultSet(this.internalResultSet); }