0001: /*
0002:
0003: Derby - Class org.apache.derby.impl.sql.compile.PredicateList
0004:
0005: Licensed to the Apache Software Foundation (ASF) under one or more
0006: contributor license agreements. See the NOTICE file distributed with
0007: this work for additional information regarding copyright ownership.
0008: The ASF licenses this file to you under the Apache License, Version 2.0
0009: (the "License"); you may not use this file except in compliance with
0010: the License. You may obtain a copy of the License at
0011:
0012: http://www.apache.org/licenses/LICENSE-2.0
0013:
0014: Unless required by applicable law or agreed to in writing, software
0015: distributed under the License is distributed on an "AS IS" BASIS,
0016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0017: See the License for the specific language governing permissions and
0018: limitations under the License.
0019:
0020: */
0021:
0022: package org.apache.derby.impl.sql.compile;
0023:
0024: import org.apache.derby.iapi.services.loader.GeneratedMethod;
0025:
0026: import org.apache.derby.iapi.services.compiler.MethodBuilder;
0027: import org.apache.derby.iapi.services.compiler.LocalField;
0028: import org.apache.derby.iapi.reference.ClassName;
0029: import org.apache.derby.iapi.services.classfile.VMOpcode;
0030:
0031: import org.apache.derby.iapi.error.StandardException;
0032:
0033: import org.apache.derby.iapi.sql.compile.CompilerContext;
0034: import org.apache.derby.iapi.sql.compile.ExpressionClassBuilderInterface;
0035: import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
0036: import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
0037: import org.apache.derby.iapi.sql.compile.Optimizable;
0038: import org.apache.derby.iapi.sql.compile.AccessPath;
0039: import org.apache.derby.iapi.sql.compile.C_NodeTypes;
0040:
0041: import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
0042:
0043: import org.apache.derby.iapi.sql.execute.ExecIndexRow;
0044: import org.apache.derby.iapi.sql.execute.ExecutionFactory;
0045:
0046: import org.apache.derby.iapi.sql.Activation;
0047: import org.apache.derby.iapi.sql.Row;
0048:
0049: import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
0050: import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
0051: import org.apache.derby.iapi.sql.dictionary.StatisticsDescriptor;
0052: import org.apache.derby.iapi.types.DataValueDescriptor;
0053: import org.apache.derby.iapi.types.DataValueDescriptor;
0054:
0055: import org.apache.derby.iapi.store.access.Qualifier;
0056: import org.apache.derby.iapi.store.access.ScanController;
0057:
0058: import org.apache.derby.impl.sql.compile.ExpressionClassBuilder;
0059: import org.apache.derby.impl.sql.compile.ActivationClassBuilder;
0060:
0061: import org.apache.derby.iapi.services.sanity.SanityManager;
0062:
0063: import org.apache.derby.iapi.util.JBitSet;
0064:
0065: import java.lang.reflect.Modifier;
0066:
0067: import java.sql.Types;
0068:
0069: import java.util.ArrayList;
0070: import java.util.Enumeration;
0071: import java.util.Properties;
0072: import java.util.Vector;
0073:
0074: /**
0075: * A PredicateList represents the list of top level predicates.
0076: * Each top level predicate consists of an AndNode whose leftOperand is the
0077: * top level predicate and whose rightOperand is true. It extends
0078: * QueryTreeNodeVector.
0079: *
0080: * @author Jerry Brenner
0081: */
0082:
0083: public class PredicateList extends QueryTreeNodeVector implements
0084: OptimizablePredicateList {
0085: private int numberOfStartPredicates;
0086: private int numberOfStopPredicates;
0087: private int numberOfQualifiers;
0088:
0089: public PredicateList() {
0090: }
0091:
0092: /*
0093: * OptimizableList interface
0094: */
0095:
0096: /**
0097: * @see org.apache.derby.iapi.sql.compile.OptimizablePredicateList#getOptPredicate
0098: */
0099: public OptimizablePredicate getOptPredicate(int index) {
0100: return (OptimizablePredicate) elementAt(index);
0101: }
0102:
0103: /**
0104: * @see org.apache.derby.iapi.sql.compile.OptimizablePredicateList#removeOptPredicate
0105: *
0106: * @exception StandardException Thrown on error
0107: */
0108: public final void removeOptPredicate(int predCtr)
0109: throws StandardException {
0110: Predicate predicate = (Predicate) remove(predCtr);
0111:
0112: if (predicate.isStartKey())
0113: numberOfStartPredicates--;
0114: if (predicate.isStopKey())
0115: numberOfStopPredicates--;
0116: if (predicate.isQualifier())
0117: numberOfQualifiers--;
0118: }
0119:
0120: /**
0121: * Another version of removeOptPredicate that takes the Predicate to be
0122: * removed, rather than the position of the Predicate. This is not part
0123: * any interface (yet).
0124: */
0125: public final void removeOptPredicate(OptimizablePredicate pred) {
0126: removeElement((Predicate) pred);
0127:
0128: if (pred.isStartKey())
0129: numberOfStartPredicates--;
0130: if (pred.isStopKey())
0131: numberOfStopPredicates--;
0132: if (pred.isQualifier())
0133: numberOfQualifiers--;
0134: }
0135:
0136: /** @see OptimizablePredicateList#addOptPredicate */
0137: public void addOptPredicate(OptimizablePredicate optPredicate) {
0138: addElement((Predicate) optPredicate);
0139:
0140: if (optPredicate.isStartKey())
0141: numberOfStartPredicates++;
0142: if (optPredicate.isStopKey())
0143: numberOfStopPredicates++;
0144: if (optPredicate.isQualifier())
0145: numberOfQualifiers++;
0146: }
0147:
0148: /**
0149: * Another flavor of addOptPredicate that inserts the given predicate
0150: * at a given position. This is not yet part of any interface.
0151: */
0152: public void addOptPredicate(OptimizablePredicate optPredicate,
0153: int position) {
0154: insertElementAt((Predicate) optPredicate, position);
0155:
0156: if (optPredicate.isStartKey())
0157: numberOfStartPredicates++;
0158: if (optPredicate.isStopKey())
0159: numberOfStopPredicates++;
0160: if (optPredicate.isQualifier())
0161: numberOfQualifiers++;
0162: }
0163:
0164: /**
0165: * @see OptimizablePredicateList#useful
0166: * @exception StandardException Thrown on error
0167: */
0168: public boolean useful(Optimizable optTable,
0169: ConglomerateDescriptor cd) throws StandardException {
0170: boolean retval = false;
0171:
0172: /*
0173: ** Most of this assumes BTREE,
0174: ** so should move into a configurable module
0175: */
0176:
0177: /* If the conglomerate isn't an index, the predicate isn't useful */
0178: if (!cd.isIndex())
0179: return false;
0180:
0181: /*
0182: ** A PredicateList is useful for a BTREE if it contains a relational
0183: ** operator directly below a top-level AND comparing the first column
0184: ** in the index to an expression that does not contain a reference
0185: ** to the table in question. Let's look for that.
0186: */
0187: int size = size();
0188: for (int index = 0; index < size; index++) {
0189: Predicate pred = (Predicate) elementAt(index);
0190:
0191: /*
0192: ** Skip over it if it's not a relational operator (this includes
0193: ** BinaryComparisonOperators and IsNullNodes.
0194: */
0195: RelationalOperator relop = pred.getRelop();
0196: boolean isIn = false;
0197: InListOperatorNode inNode = null;
0198:
0199: if (relop == null) {
0200: /* if it's "in" operator, we generate dynamic start and stop key
0201: * to improve index scan performance, beetle 3858.
0202: */
0203: if (pred.getAndNode().getLeftOperand() instanceof InListOperatorNode
0204: && !((InListOperatorNode) pred.getAndNode()
0205: .getLeftOperand()).getTransformed()) {
0206: isIn = true;
0207: inNode = (InListOperatorNode) pred.getAndNode()
0208: .getLeftOperand();
0209: } else
0210: continue;
0211: }
0212:
0213: /*
0214: ** If the relational operator is neither a useful start key
0215: ** nor a useful stop key for this table, it is not useful
0216: ** for limiting an index scan.
0217: */
0218: if ((!isIn) && (!relop.usefulStartKey(optTable))
0219: && (!relop.usefulStopKey(optTable))) {
0220: continue;
0221: }
0222:
0223: /*
0224: ** Look for a the first column of the index on one side of the
0225: ** relop. If it's not found, this Predicate is not optimizable.
0226: */
0227: ColumnReference indexCol = null;
0228:
0229: if (isIn) {
0230: if (inNode.getLeftOperand() instanceof ColumnReference) {
0231: indexCol = (ColumnReference) inNode
0232: .getLeftOperand();
0233: if (indexCol.getColumnNumber() != cd
0234: .getIndexDescriptor().baseColumnPositions()[0]) {
0235: indexCol = null;
0236: }
0237: }
0238: } else {
0239: indexCol = relop.getColumnOperand(optTable, cd
0240: .getIndexDescriptor().baseColumnPositions()[0]);
0241: }
0242:
0243: if (indexCol == null) {
0244: continue;
0245: }
0246:
0247: /*
0248: ** Look at the expression that the index column is compared to.
0249: ** If it contains columns from the table in question, the
0250: ** Predicate is not optimizable.
0251: */
0252: if ((isIn && inNode.selfReference(indexCol))
0253: || (!isIn && relop.selfComparison(indexCol))) {
0254: continue;
0255: }
0256:
0257: /* The Predicate is optimizable */
0258: retval = true;
0259: break;
0260: }
0261:
0262: return retval;
0263: }
0264:
0265: /**
0266: * @see OptimizablePredicateList#pushUsefulPredicates
0267: *
0268: * @exception StandardException Thrown on error
0269: */
0270: public void pushUsefulPredicates(Optimizable optTable)
0271: throws StandardException {
0272: AccessPath ap = optTable.getTrulyTheBestAccessPath();
0273:
0274: orderUsefulPredicates(optTable, ap.getConglomerateDescriptor(),
0275: true, ap.getNonMatchingIndexScan(), ap
0276: .getCoveringIndexScan());
0277: }
0278:
0279: /**
0280: * @see OptimizablePredicateList#classify
0281: *
0282: * @exception StandardException Thrown on error
0283: */
0284: public void classify(Optimizable optTable, ConglomerateDescriptor cd)
0285: throws StandardException {
0286: /*
0287: ** Don't push the predicates - at this point, we are only determining
0288: ** which predicates are useful. Also, we don't know yet whether
0289: ** we have a non-matching index scan or a covering index scan -
0290: ** this method call will help determine that. So, let's say they're
0291: ** false for now.
0292: */
0293: orderUsefulPredicates(optTable, cd, false, false, false);
0294: }
0295:
0296: /** @see OptimizablePredicateList#markAllPredicatesQualifiers */
0297: public void markAllPredicatesQualifiers() {
0298: int size = size();
0299: for (int index = 0; index < size; index++) {
0300: ((Predicate) elementAt(index)).markQualifier();
0301: }
0302:
0303: numberOfQualifiers = size;
0304: }
0305:
0306: /**
0307: * @see OptimizablePredicateList#hasOptimizableEqualityPredicate
0308: *
0309: * @exception StandardException Thrown on error
0310: */
0311: public boolean hasOptimizableEqualityPredicate(
0312: Optimizable optTable, int columnNumber, boolean isNullOkay)
0313: throws StandardException {
0314: int size = size();
0315: for (int index = 0; index < size; index++) {
0316: AndNode andNode;
0317: Predicate predicate;
0318: predicate = (Predicate) elementAt(index);
0319:
0320: andNode = (AndNode) predicate.getAndNode();
0321:
0322: // skip non-equality predicates
0323: ValueNode opNode = andNode.getLeftOperand();
0324:
0325: if (opNode.optimizableEqualityNode(optTable, columnNumber,
0326: isNullOkay)) {
0327: return true;
0328: }
0329: }
0330:
0331: return false;
0332: }
0333:
0334: /**
0335: * @see OptimizablePredicateList#hasOptimizableEquijoin
0336: *
0337: * @exception StandardException Thrown on error
0338: */
0339: public boolean hasOptimizableEquijoin(Optimizable optTable,
0340: int columnNumber) throws StandardException {
0341: int size = size();
0342: for (int index = 0; index < size; index++) {
0343: AndNode andNode;
0344: Predicate predicate;
0345: predicate = (Predicate) elementAt(index);
0346:
0347: // This method is used by HashJoinStrategy to determine if
0348: // there are any equality predicates that can be used to
0349: // perform a hash join (see the findHashKeyColumns()
0350: // method in HashJoinStrategy.java). That said, if the
0351: // predicate was scoped and pushed down from an outer query,
0352: // then it's no longer possible to perform the hash join
0353: // because one of the operands is in an outer query and
0354: // the other (scoped) operand is down in a subquery. Thus
0355: // we skip this predicate if it has been scoped.
0356: if (predicate.isScopedForPush()) {
0357: continue;
0358: }
0359:
0360: andNode = (AndNode) predicate.getAndNode();
0361:
0362: ValueNode opNode = andNode.getLeftOperand();
0363:
0364: if (!opNode.optimizableEqualityNode(optTable, columnNumber,
0365: false)) {
0366: continue;
0367: }
0368:
0369: /*
0370: ** Skip comparisons that are not qualifiers for the table
0371: ** in question.
0372: */
0373: if (!((RelationalOperator) opNode).isQualifier(optTable,
0374: false)) {
0375: continue;
0376: }
0377:
0378: /*
0379: ** Skip non-join comparisons.
0380: */
0381: if (predicate.getReferencedMap().hasSingleBitSet()) {
0382: continue;
0383: }
0384:
0385: // We found a match
0386: return true;
0387: }
0388:
0389: return false;
0390: }
0391:
0392: /**
0393: * @see OptimizablePredicateList#putOptimizableEqualityPredicateFirst
0394: *
0395: * @exception StandardException Thrown on error
0396: */
0397: public void putOptimizableEqualityPredicateFirst(
0398: Optimizable optTable, int columnNumber)
0399: throws StandardException {
0400: int size = size();
0401: for (int index = 0; index < size; index++) {
0402: Predicate predicate = (Predicate) elementAt(index);
0403: AndNode andNode;
0404:
0405: andNode = (AndNode) predicate.getAndNode();
0406:
0407: // skip non-equality predicates
0408: ValueNode opNode = andNode.getLeftOperand();
0409:
0410: if (!opNode.optimizableEqualityNode(optTable, columnNumber,
0411: false))
0412: continue;
0413:
0414: // We found a match - make this entry first in the list
0415: if (index != 0) {
0416: removeElementAt(index);
0417: insertElementAt(predicate, 0);
0418: }
0419:
0420: return;
0421: }
0422:
0423: /* We should never get here since this method only called when we
0424: * know that the desired equality predicate exists.
0425: */
0426: if (SanityManager.DEBUG) {
0427: SanityManager
0428: .THROWASSERT("Could not find the expected equality predicate on column #"
0429: + columnNumber);
0430: }
0431: }
0432:
0433: private void orderUsefulPredicates(Optimizable optTable,
0434: ConglomerateDescriptor cd, boolean pushPreds,
0435: boolean nonMatchingIndexScan, boolean coveringIndexScan)
0436: throws StandardException {
0437: boolean[] deletes;
0438: int[] baseColumnPositions;
0439: boolean[] isAscending;
0440: int size = size();
0441: Predicate[] usefulPredicates = new Predicate[size];
0442: int usefulCount = 0;
0443: Predicate predicate;
0444:
0445: /*
0446: ** Clear all the scan flags for this predicate list, so that the
0447: ** flags that get set are only for the given conglomerate.
0448: */
0449: for (int index = 0; index < size; index++) {
0450: predicate = (Predicate) elementAt(index);
0451:
0452: predicate.clearScanFlags();
0453: }
0454:
0455: /*
0456: ** RESOLVE: For now, not pushing any predicates for heaps. When this
0457: ** changes, we also need to make the scan in
0458: ** TableScanResultSet.getCurrentRow() check the qualifiers to see
0459: ** if the row still qualifies (there is a new method in ScanController
0460: ** for this.
0461: */
0462:
0463: /* Is a heap scan or a non-matching index scan on a covering index? */
0464: if ((cd == null) || (!cd.isIndex())
0465: || (nonMatchingIndexScan && coveringIndexScan)) {
0466: /*
0467: ** For the heap, the useful predicates are the relational
0468: ** operators that have a column from the table on one side,
0469: ** and an expression that doesn't have a column from that
0470: ** table on the other side.
0471: **
0472: ** For the heap, all useful predicates become Qualifiers, so
0473: ** they don't have to be in any order.
0474: **
0475: ** NOTE: We can logically delete the current element when
0476: ** traversing the Vector in the next loop,
0477: ** so we must build an array of elements to
0478: ** delete while looping and then delete them
0479: ** in reverse order after completing the loop.
0480: */
0481: Predicate[] preds = new Predicate[size];
0482:
0483: for (int index = 0; index < size; index++) {
0484: Predicate pred = (Predicate) elementAt(index);
0485:
0486: /*
0487: ** Skip over it if it's not a relational operator (this includes
0488: ** BinaryComparisonOperators and IsNullNodes.
0489: */
0490: RelationalOperator relop = pred.getRelop();
0491:
0492: if (relop == null) {
0493: // possible OR clause, check for it.
0494:
0495: if (!pred.isPushableOrClause(optTable)) {
0496: // NOT an OR or AND, so go on to next predicate.
0497: continue;
0498: }
0499: } else {
0500: if (!relop.isQualifier(optTable, pushPreds)) {
0501: // NOT a qualifier, go on to next predicate.
0502: continue;
0503: }
0504: }
0505:
0506: pred.markQualifier();
0507:
0508: if (pushPreds) {
0509: /* Push the predicate down.
0510: * (Just record for now.)
0511: */
0512: if (optTable.pushOptPredicate(pred)) {
0513: preds[index] = pred;
0514: }
0515: }
0516: }
0517:
0518: /* Now we actually push the predicates down */
0519: for (int inner = size - 1; inner >= 0; inner--) {
0520: if (preds[inner] != null) {
0521: removeOptPredicate(preds[inner]);
0522: }
0523: }
0524:
0525: return;
0526: }
0527:
0528: baseColumnPositions = cd.getIndexDescriptor()
0529: .baseColumnPositions();
0530: isAscending = cd.getIndexDescriptor().isAscending();
0531:
0532: /*
0533: ** Create an array of useful predicates. Also, count how many
0534: ** useful predicates there are.
0535: */
0536: for (int index = 0; index < size; index++) {
0537: Predicate pred = (Predicate) elementAt(index);
0538: ColumnReference indexCol = null;
0539: int indexPosition;
0540:
0541: /*
0542: ** Skip over it if it's not a relational operator (this includes
0543: ** BinaryComparisonOperators and IsNullNodes.
0544: */
0545: RelationalOperator relop = pred.getRelop();
0546:
0547: /* if it's "in" operator, we generate dynamic start and stop key
0548: * to improve index scan performance, beetle 3858.
0549: */
0550: boolean isIn = false;
0551: InListOperatorNode inNode = null;
0552:
0553: if (relop == null) {
0554: if (pred.getAndNode().getLeftOperand() instanceof InListOperatorNode
0555: && !((InListOperatorNode) pred.getAndNode()
0556: .getLeftOperand()).getTransformed()) {
0557: isIn = true;
0558: inNode = (InListOperatorNode) pred.getAndNode()
0559: .getLeftOperand();
0560: } else
0561: continue;
0562: }
0563:
0564: if (!isIn && !relop.isQualifier(optTable, pushPreds))
0565: continue;
0566:
0567: /* Look for an index column on one side of the relop */
0568: for (indexPosition = 0; indexPosition < baseColumnPositions.length; indexPosition++) {
0569: if (isIn) {
0570: if (inNode.getLeftOperand() instanceof ColumnReference) {
0571: indexCol = (ColumnReference) inNode
0572: .getLeftOperand();
0573: if ((optTable.getTableNumber() != indexCol
0574: .getTableNumber())
0575: || (indexCol.getColumnNumber() != baseColumnPositions[indexPosition])
0576: || inNode.selfReference(indexCol))
0577: indexCol = null;
0578: }
0579: } else {
0580: indexCol = relop.getColumnOperand(optTable,
0581: baseColumnPositions[indexPosition]);
0582: }
0583: if (indexCol != null)
0584: break;
0585: }
0586:
0587: /*
0588: ** Skip over it if there is no index column on one side of the
0589: ** operand.
0590: */
0591: if (indexCol == null)
0592: continue;
0593:
0594: pred.setIndexPosition(indexPosition);
0595:
0596: /* Remember the useful predicate */
0597: usefulPredicates[usefulCount++] = pred;
0598: }
0599:
0600: /* We can end up with no useful
0601: * predicates with a force index override -
0602: * Each predicate is on a non-key column or both
0603: * sides of the operator are columns from the same table.
0604: * There's no predicates to push down, so return and we'll
0605: * evaluate them in a PRN.
0606: */
0607: if (usefulCount == 0)
0608: return;
0609:
0610: /* The array of useful predicates may have unused slots. Shrink it */
0611: if (usefulPredicates.length > usefulCount) {
0612: Predicate[] shrink = new Predicate[usefulCount];
0613:
0614: System.arraycopy(usefulPredicates, 0, shrink, 0,
0615: usefulCount);
0616:
0617: usefulPredicates = shrink;
0618: }
0619:
0620: /* Sort the array of useful predicates in index position order */
0621: java.util.Arrays.sort(usefulPredicates);
0622:
0623: /* Push the sorted predicates down to the Optimizable table */
0624: int currentStartPosition = -1;
0625: boolean gapInStartPositions = false;
0626: int currentStopPosition = -1;
0627: boolean gapInStopPositions = false;
0628: boolean seenNonEquals = false;
0629: int firstNonEqualsPosition = -1;
0630: int lastStartEqualsPosition = -1;
0631:
0632: /* beetle 4572. We need to truncate if necessary potential multi-column
0633: * start key up to the first one whose start operator is GT, and make
0634: * start operator GT;
0635: * or start operator is GE if there's no such column. We need to
0636: * truncate if necessary potential multi-column stop key up to the
0637: * first one whose stop operator is GE, and make stop operator GE; or
0638: * stop operator is GT if no such column.
0639: * eg., start key (a,b,c,d,e,f), potential start operators
0640: * (GE,GE,GE,GT,GE,GT)
0641: * then start key should really be (a,b,c,d) with start operator GT.
0642: */
0643: boolean seenGE = false, seenGT = false;
0644:
0645: for (int i = 0; i < usefulCount; i++) {
0646: Predicate this Pred = usefulPredicates[i];
0647: int this IndexPosition = this Pred.getIndexPosition();
0648: boolean this PredMarked = false;
0649: RelationalOperator relop = this Pred.getRelop();
0650: int this Operator = -1;
0651:
0652: boolean isIn = false;
0653: InListOperatorNode inNode = null;
0654:
0655: if (relop == null) {
0656: isIn = true;
0657: inNode = (InListOperatorNode) this Pred.getAndNode()
0658: .getLeftOperand();
0659: } else {
0660: this Operator = relop.getOperator();
0661: }
0662:
0663: /* Allow only one start and stop position per index column */
0664: if (currentStartPosition != this IndexPosition) {
0665: /*
0666: ** We're working on a new index column for the start position.
0667: ** Is it just one more than the previous position?
0668: */
0669: if ((this IndexPosition - currentStartPosition) > 1) {
0670: /*
0671: ** There's a gap in the start positions. Don't mark any
0672: ** more predicates as start predicates.
0673: */
0674: gapInStartPositions = true;
0675: } else if ((this Operator == RelationalOperator.EQUALS_RELOP)
0676: || (this Operator == RelationalOperator.IS_NULL_RELOP)) {
0677: /* Remember the last "=" or IS NULL predicate in the start
0678: * position. (The sort on the predicates above has ensured
0679: * that these predicates appear 1st within the predicates on
0680: * a specific column.)
0681: */
0682: lastStartEqualsPosition = this IndexPosition;
0683: }
0684:
0685: if (!gapInStartPositions) {
0686: /*
0687: ** There is no gap in start positions. Is this predicate
0688: ** useful as a start position? This depends on the
0689: ** operator - for example, indexCol = <expr> is useful,
0690: ** while indexCol < <expr> is not useful with asc index
0691: ** we simply need to reverse the logic for desc indexes
0692: **
0693: ** The relop has to figure out whether the index column
0694: ** is on the left or the right, so pass the Optimizable
0695: ** table to help it.
0696: */
0697: if (!seenGT
0698: && (isIn || ((relop
0699: .usefulStartKey(optTable) && isAscending[this IndexPosition]) || (relop
0700: .usefulStopKey(optTable) && !isAscending[this IndexPosition])))) {
0701: this Pred.markStartKey();
0702: currentStartPosition = this IndexPosition;
0703: this PredMarked = true;
0704: seenGT = (this Pred.getStartOperator(optTable) == ScanController.GT);
0705: }
0706: }
0707: }
0708:
0709: /* Same as above, except for stop keys */
0710: if (currentStopPosition != this IndexPosition) {
0711: if ((this IndexPosition - currentStopPosition) > 1) {
0712: gapInStopPositions = true;
0713: }
0714:
0715: if (!gapInStopPositions) {
0716: if (!seenGE
0717: && (isIn || ((relop.usefulStopKey(optTable) && isAscending[this IndexPosition]) || (relop
0718: .usefulStartKey(optTable) && !isAscending[this IndexPosition])))) {
0719: this Pred.markStopKey();
0720: currentStopPosition = this IndexPosition;
0721: this PredMarked = true;
0722: seenGE = (this Pred.getStopOperator(optTable) == ScanController.GE);
0723: }
0724: }
0725: }
0726:
0727: /* Mark this predicate as a qualifier if it is not a start/stop
0728: * position or if we have already seen a previous column whose
0729: * RELOPS do not include "=" or IS NULL. For example, if
0730: * the index is on (a, b, c) and the predicates are a > 1 and b = 1
0731: * and c = 1, then b = 1 and c = 1 also need to be a qualifications,
0732: * otherwise we may match on (2, 0, 3).
0733: */
0734: if ((!isIn) && // store can never treat "in" as qualifier
0735: ((!this PredMarked) || (seenNonEquals && this IndexPosition != firstNonEqualsPosition))) {
0736: this Pred.markQualifier();
0737: }
0738:
0739: /* Remember if we have seen a column without an "=" */
0740: if (lastStartEqualsPosition != this IndexPosition
0741: && firstNonEqualsPosition == -1
0742: && (this Operator != RelationalOperator.EQUALS_RELOP)
0743: && (this Operator != RelationalOperator.IS_NULL_RELOP)) {
0744: seenNonEquals = true;
0745: /* Remember the column */
0746: firstNonEqualsPosition = this IndexPosition;
0747: }
0748:
0749: if (pushPreds) {
0750: /* we only roughly detected that the predicate may be useful
0751: * earlier, it may turn out that it's not actually start/stop
0752: * key because another better predicate on the column is chosen.
0753: * We don't want to push "in" in this case, since it's not a
0754: * qualifier. Beetle 4316.
0755: */
0756: if (isIn && !this PredMarked)
0757: continue;
0758:
0759: /*
0760: ** Push the predicate down. They get pushed down in the
0761: ** order of the index.
0762: */
0763:
0764: /* If this is an InListOperator predicate, make a copy of the
0765: * the predicate (including the AND node contained within it)
0766: * and then push the _copy_ (instead of the original) into
0767: * optTable. We need to do this to avoid having the exact
0768: * same Predicate object (and in particular, the exact same
0769: * AndNode object) be referenced in both optTable and this.v,
0770: * which can lead to an infinite recursion loop when we get to
0771: * restorePredicates(), and thus to stack overflow
0772: * (beetle 4974).
0773: */
0774: Predicate predToPush;
0775: if (isIn) {
0776: AndNode andCopy = (AndNode) getNodeFactory()
0777: .getNode(
0778: C_NodeTypes.AND_NODE,
0779: this Pred.getAndNode()
0780: .getLeftOperand(),
0781: this Pred.getAndNode()
0782: .getRightOperand(),
0783: getContextManager());
0784: andCopy.copyFields(this Pred.getAndNode());
0785: Predicate predCopy = (Predicate) getNodeFactory()
0786: .getNode(C_NodeTypes.PREDICATE, andCopy,
0787: this Pred.getReferencedSet(),
0788: getContextManager());
0789: predCopy.copyFields(this Pred);
0790: predToPush = predCopy;
0791: } else {
0792: predToPush = this Pred;
0793: }
0794:
0795: if (optTable.pushOptPredicate(predToPush)) {
0796: /* although we generated dynamic start and stop key for "in"
0797: * , we still need this predicate for further restriction
0798: */
0799: if (!isIn)
0800: removeOptPredicate(this Pred);
0801: // restore origin
0802: } else if (SanityManager.DEBUG) {
0803: SanityManager.ASSERT(false,
0804: "pushOptPredicate expected to be true");
0805: }
0806: } else {
0807: /*
0808: ** We're not pushing the predicates down, so put them at the
0809: ** beginning of this predicate list in index order.
0810: */
0811: removeOptPredicate(this Pred);
0812: addOptPredicate(this Pred, i);
0813: }
0814: }
0815: }
0816:
0817: /**
0818: * Add a Predicate to the list.
0819: *
0820: * @param predicate A Predicate to add to the list
0821: *
0822: * @exception StandardException Thrown on error
0823: */
0824:
0825: public void addPredicate(Predicate predicate)
0826: throws StandardException {
0827: if (predicate.isStartKey())
0828: numberOfStartPredicates++;
0829: if (predicate.isStopKey())
0830: numberOfStopPredicates++;
0831: if (predicate.isQualifier())
0832: numberOfQualifiers++;
0833:
0834: addElement(predicate);
0835: }
0836:
0837: /**
0838: * Transfer the non-qualifiers from this predicate list to the specified
0839: * predicate list.
0840: * This is useful for arbitrary hash join, where we need to separate the 2
0841: * as the qualifiers get applied when probing the hash table and the
0842: * non-qualifiers get * applied afterwards.
0843: *
0844: * @param optTable The optimizable that we want qualifiers for
0845: * @param otherPL ParameterList for non-qualifiers
0846: *
0847: * @exception StandardException Thrown on error
0848: */
0849: protected void transferNonQualifiers(Optimizable optTable,
0850: PredicateList otherPL) throws StandardException {
0851: /* Walk list backwards since we can delete while
0852: * traversing the list.
0853: */
0854: for (int index = size() - 1; index >= 0; index--) {
0855: Predicate pred = (Predicate) elementAt(index);
0856:
0857: RelationalOperator relop = pred.getRelop();
0858: // Transfer each non-qualifier
0859: if (relop == null || !relop.isQualifier(optTable, false)) {
0860: pred.clearScanFlags();
0861: removeElementAt(index);
0862: otherPL.addElement(pred);
0863: }
0864: }
0865:
0866: // Mark all remaining predicates as qualifiers
0867: markAllPredicatesQualifiers();
0868: }
0869:
0870: /**
0871: * Categorize the predicates in the list. Initially, this means
0872: * building a bit map of the referenced tables for each predicate.
0873: *
0874: * @exception StandardException Thrown on error
0875: */
0876: public void categorize() throws StandardException {
0877: int size = size();
0878:
0879: for (int index = 0; index < size; index++) {
0880: ((Predicate) elementAt(index)).categorize();
0881: }
0882: }
0883:
0884: /**
0885: * Prints the sub-nodes of this object. See QueryTreeNode.java for
0886: * how tree printing is supposed to work.
0887: *
0888: * @param depth The depth of this node in the tree
0889: */
0890:
0891: public void printSubNodes(int depth) {
0892: if (SanityManager.DEBUG) {
0893: Predicate predicate;
0894:
0895: super .printSubNodes(depth);
0896:
0897: for (int index = 0; index < size(); index++) {
0898: predicate = (Predicate) elementAt(index);
0899: predicate.treePrint(depth + 1);
0900: }
0901: }
0902: }
0903:
0904: /**
0905: * Eliminate predicates of the form:
0906: * AndNode
0907: * / \
0908: * true BooleanConstantNode true BooleanConstantNode
0909: * This is useful when checking for a NOP PRN as the
0910: * Like transformation on c1 like 'ASDF%' can leave
0911: * one of these predicates in the list.
0912: */
0913: public void eliminateBooleanTrueAndBooleanTrue() {
0914: /* Walk list backwards since we can delete while
0915: * traversing the list.
0916: */
0917: for (int index = size() - 1; index >= 0; index--) {
0918: AndNode nextAnd;
0919: /* Look at the current predicate from the predicate list */
0920: nextAnd = ((Predicate) elementAt(index)).getAndNode();
0921:
0922: if ((nextAnd.getLeftOperand().isBooleanTrue())
0923: && (nextAnd.getRightOperand().isBooleanTrue())) {
0924: removeElementAt(index);
0925: }
0926: }
0927:
0928: }
0929:
0930: /**
0931: * Rebuild a constant expression tree from the remaining constant
0932: * predicates and delete those entries from the PredicateList.
0933: * The rightOperand of every top level AndNode is always a true
0934: * BooleanConstantNode, so we can blindly overwrite that pointer.
0935: * Optimizations:
0936: *
0937: * We take this opportunity to eliminate:
0938: * AndNode
0939: * / \
0940: * true BooleanConstantNode true BooleanConstantNode
0941: *
0942: * We remove the AndNode if the predicate list is a single AndNode:
0943: * AndNode
0944: * / \
0945: * LeftOperand RightOperand
0946: *
0947: * becomes:
0948: * LeftOperand
0949: *
0950: * If the leftOperand of any AndNode is False, then the entire expression
0951: * will be False. The expression simple becomes:
0952: * false BooleanConstantNode
0953: *
0954: * @return ValueNode The rebuilt expression tree.
0955: */
0956: public ValueNode restoreConstantPredicates()
0957: throws StandardException {
0958: AndNode nextAnd;
0959: AndNode falseAnd = null;
0960: ValueNode restriction = null;
0961:
0962: /* Walk list backwards since we can delete while
0963: * traversing the list.
0964: */
0965: for (int index = size() - 1; index >= 0; index--) {
0966: /* Look at the current predicate from the predicate list */
0967: nextAnd = ((Predicate) elementAt(index)).getAndNode();
0968:
0969: // Skip over the predicate if it is not a constant expression
0970: if (!nextAnd.isConstantExpression()) {
0971: continue;
0972: }
0973:
0974: // This node is a constant expression, so we can remove it from the list
0975: removeElementAt(index);
0976:
0977: /* We can skip over TRUE AND TRUE */
0978: if ((nextAnd.getLeftOperand().isBooleanTrue())
0979: && (nextAnd.getRightOperand().isBooleanTrue())) {
0980: continue;
0981: }
0982:
0983: /* Remember if we see a false BooleanConstantNode */
0984: if (nextAnd.getLeftOperand().isBooleanFalse()) {
0985: falseAnd = nextAnd;
0986: }
0987:
0988: if (restriction != null) {
0989: nextAnd.setRightOperand(restriction);
0990: /* If any of the predicates is nullable, then the resulting
0991: * tree must be nullable.
0992: */
0993: if (restriction.getTypeServices().isNullable()) {
0994: nextAnd.getTypeServices().setNullability(true);
0995: }
0996: }
0997: restriction = nextAnd;
0998: }
0999:
1000: /* If restriction is a single AndNode, then it's rightOperand must be
1001: * a true BooleanConstantNode. We simply chop out the AndNode and set
1002: * restriction to AndNode.leftOperand.
1003: */
1004: if ((restriction != null)
1005: && (((AndNode) restriction).getRightOperand()
1006: .isBooleanTrue())) {
1007: restriction = ((AndNode) restriction).getLeftOperand();
1008: } else if (falseAnd != null) {
1009: /* Expression is ... AND FALSE AND ...
1010: * Replace the entire expression with a false BooleanConstantNode.
1011: */
1012: restriction = falseAnd.getLeftOperand();
1013: }
1014:
1015: return restriction;
1016: }
1017:
1018: /**
1019: * Rebuild an expression tree from the remaining predicates and delete those
1020: * entries from the PredicateList.
1021: * The rightOperand of every top level AndNode is always a true
1022: * BooleanConstantNode, so we can blindly overwrite that pointer.
1023: * Optimizations:
1024: *
1025: * We take this opportunity to eliminate:
1026: * AndNode
1027: * / \
1028: * true BooleanConstantNode true BooleanConstantNode
1029: *
1030: * We remove the AndNode if the predicate list is a single AndNode:
1031: * AndNode
1032: * / \
1033: * LeftOperand RightOperand
1034: *
1035: * becomes:
1036: * LeftOperand
1037: *
1038: * If the leftOperand of any AndNode is False, then the entire expression
1039: * will be False. The expression simple becomes:
1040: * false BooleanConstantNode
1041: *
1042: * @return ValueNode The rebuilt expression tree.
1043: */
1044: public ValueNode restorePredicates() throws StandardException {
1045: AndNode nextAnd;
1046: AndNode falseAnd = null;
1047: ValueNode restriction = null;
1048:
1049: int size = size();
1050: for (int index = 0; index < size; index++) {
1051: nextAnd = ((Predicate) elementAt(index)).getAndNode();
1052:
1053: /* We can skip over TRUE AND TRUE */
1054: if ((nextAnd.getLeftOperand().isBooleanTrue())
1055: && (nextAnd.getRightOperand().isBooleanTrue())) {
1056: continue;
1057: }
1058:
1059: /* Remember if we see a false BooleanConstantNode */
1060: if (nextAnd.getLeftOperand().isBooleanFalse()) {
1061: falseAnd = nextAnd;
1062: }
1063:
1064: if (restriction != null) {
1065: nextAnd.setRightOperand(restriction);
1066: /* If any of the predicates is nullable, then the resulting
1067: * tree must be nullable.
1068: */
1069: if (restriction.getTypeServices().isNullable()) {
1070: nextAnd.getTypeServices().setNullability(true);
1071: }
1072: }
1073: restriction = nextAnd;
1074: }
1075:
1076: /* If restriction is a single AndNode, then it's rightOperand must be
1077: * a true BooleanConstantNode. We simply chop out the AndNode and set
1078: * restriction to AndNode.leftOperand.
1079: */
1080: if ((restriction != null)
1081: && (((AndNode) restriction).getRightOperand()
1082: .isBooleanTrue())) {
1083: restriction = ((AndNode) restriction).getLeftOperand();
1084: } else if (falseAnd != null) {
1085: /* Expression is ... AND FALSE AND ...
1086: * Replace the entire expression with a simple false
1087: * BooleanConstantNode.
1088: */
1089: restriction = falseAnd.getLeftOperand();
1090: }
1091:
1092: /* Remove all predicates from the list */
1093: removeAllElements();
1094: return restriction;
1095: }
1096:
1097: /**
1098: * Remap all ColumnReferences in this tree to be clones of the
1099: * underlying expression.
1100: *
1101: * @exception StandardException Thrown on error
1102: */
1103: public void remapColumnReferencesToExpressions()
1104: throws StandardException {
1105: Predicate pred;
1106:
1107: int size = size();
1108: for (int index = 0; index < size; index++) {
1109: pred = (Predicate) elementAt(index);
1110:
1111: pred.setAndNode((AndNode) pred.getAndNode()
1112: .remapColumnReferencesToExpressions());
1113: }
1114: }
1115:
1116: /**
1117: * Break apart the search clause into matching a PredicateList
1118: * where each top level predicate is a separate element in the list.
1119: * Build a bit map to represent the FromTables referenced within each
1120: * top level predicate.
1121: * NOTE: We want the rightOperand of every AndNode to be true, in order
1122: * to simplify the algorithm for putting the predicates back into the tree.
1123: * (As we put an AndNode back into the tree, we can ignore it's rightOperand.)
1124: *
1125: * @param numTables Number of tables in the DML Statement
1126: * @param searchClause The search clause to operate on.
1127: *
1128: * @exception StandardException Thrown on error
1129: */
1130: void pullExpressions(int numTables, ValueNode searchClause)
1131: throws StandardException {
1132: AndNode this And;
1133: AndNode topAnd;
1134: JBitSet newJBitSet;
1135: Predicate newPred;
1136: BooleanConstantNode trueNode = null;
1137:
1138: if (searchClause != null) {
1139: topAnd = (AndNode) searchClause;
1140: searchClause = null;
1141: trueNode = (BooleanConstantNode) getNodeFactory().getNode(
1142: C_NodeTypes.BOOLEAN_CONSTANT_NODE, Boolean.TRUE,
1143: getContextManager());
1144:
1145: while (topAnd.getRightOperand() instanceof AndNode) {
1146: /* Break out the next top AndNode */
1147: this And = topAnd;
1148: topAnd = (AndNode) topAnd.getRightOperand();
1149: this And.setRightOperand(null);
1150:
1151: /* Set the rightOperand to true */
1152: this And.setRightOperand(trueNode);
1153:
1154: /* Add the top AndNode to the PredicateList */
1155: newJBitSet = new JBitSet(numTables);
1156: newPred = (Predicate) getNodeFactory().getNode(
1157: C_NodeTypes.PREDICATE, this And, newJBitSet,
1158: getContextManager());
1159: addPredicate(newPred);
1160: }
1161:
1162: /* Add the last top AndNode to the PredicateList */
1163: newJBitSet = new JBitSet(numTables);
1164: newPred = (Predicate) getNodeFactory().getNode(
1165: C_NodeTypes.PREDICATE, topAnd, newJBitSet,
1166: getContextManager());
1167: addPredicate(newPred);
1168: }
1169: }
1170:
1171: /**
1172: * XOR fromMap with the referenced table map in every remaining
1173: * Predicate in the list. This is useful when pushing down
1174: * multi-table predicates.
1175: *
1176: * @param fromMap The JBitSet to XOR with.
1177: */
1178: public void xorReferencedSet(JBitSet fromMap) {
1179: Predicate predicate;
1180:
1181: int size = size();
1182: for (int index = 0; index < size; index++) {
1183: predicate = (Predicate) elementAt(index);
1184:
1185: if (SanityManager.DEBUG) {
1186: SanityManager
1187: .ASSERT(
1188: fromMap.size() == predicate
1189: .getReferencedSet().size(),
1190: "fromMap.size() ("
1191: + fromMap.size()
1192: + ") does not equal predicate.getReferencedSet().size() ("
1193: + predicate.getReferencedSet()
1194: .size());
1195: }
1196:
1197: predicate.getReferencedSet().xor(fromMap);
1198: }
1199: }
1200:
1201: private void countScanFlags() {
1202: Predicate predicate;
1203:
1204: int size = size();
1205: for (int index = 0; index < size; index++) {
1206: predicate = (Predicate) elementAt(index);
1207: if (predicate.isStartKey())
1208: numberOfStartPredicates++;
1209: if (predicate.isStopKey())
1210: numberOfStopPredicates++;
1211: if (predicate.isQualifier())
1212: numberOfQualifiers++;
1213: }
1214: }
1215:
1216: /**
1217: * Push all predicates, which can be pushed, into the underlying select.
1218: * A predicate can be pushed into an underlying select if the source of
1219: * every ColumnReference in the predicate is itself a ColumnReference.
1220: *
1221: * This is useful when attempting to push predicates into non-flattenable
1222: * views or derived tables or into unions.
1223: *
1224: * @param select The underlying SelectNode.
1225: * @param copyPredicate Whether to make a copy of the predicate
1226: * before pushing
1227: *
1228: * @exception StandardException Thrown on error
1229: */
1230: void pushExpressionsIntoSelect(SelectNode select,
1231: boolean copyPredicate) throws StandardException {
1232: /* Walk list backwards since we can delete while
1233: * traversing the list.
1234: */
1235: for (int index = size() - 1; index >= 0; index--) {
1236: Predicate predicate;
1237: predicate = (Predicate) elementAt(index);
1238:
1239: CollectNodesVisitor getCRs = new CollectNodesVisitor(
1240: ColumnReference.class);
1241:
1242: predicate.getAndNode().accept(getCRs);
1243: Vector colRefs = getCRs.getList();
1244:
1245: /* state doesn't become true until we find the 1st
1246: * ColumnReference. (We probably will always find
1247: * at least 1 CR, but just to be safe, ...)
1248: */
1249: boolean state = colRefs.size() > 0;
1250: if (state) {
1251: for (Enumeration e = colRefs.elements(); e
1252: .hasMoreElements();) {
1253: ColumnReference ref = (ColumnReference) e
1254: .nextElement();
1255: if (!ref.pointsToColumnReference()) {
1256: state = false;
1257: break;
1258: }
1259: }
1260: }
1261:
1262: if (!state)
1263: continue;
1264:
1265: if (copyPredicate) {
1266: // Copy this predicate and push this instead
1267: AndNode andNode = predicate.getAndNode();
1268: ValueNode leftOperand;
1269: ColumnReference crNode;
1270: BinaryRelationalOperatorNode opNode = null;
1271: InListOperatorNode inNode = null;
1272:
1273: // Make sure we are only pushing binary relations and InList for
1274: // copyPredicate case. It should be benificial to push expressions that
1275: // can be pushed, so they can be applied closer to the data.
1276:
1277: if (andNode.getLeftOperand() instanceof BinaryRelationalOperatorNode) {
1278: opNode = (BinaryRelationalOperatorNode) andNode
1279: .getLeftOperand();
1280: // Investigate using invariant interface to check rightOperand
1281: if (!(opNode.getLeftOperand() instanceof ColumnReference)
1282: || !(opNode.getRightOperand() instanceof ConstantNode || opNode
1283: .getRightOperand() instanceof ParameterNode))
1284: continue;
1285:
1286: crNode = (ColumnReference) opNode.getLeftOperand();
1287: } else if (andNode.getLeftOperand() instanceof InListOperatorNode) {
1288: inNode = (InListOperatorNode) andNode
1289: .getLeftOperand();
1290: if (!(inNode.getRightOperandList()
1291: .isConstantExpression()))
1292: continue;
1293:
1294: crNode = (ColumnReference) inNode.getLeftOperand();
1295: } else
1296: continue;
1297:
1298: // Remap this crNode to underlying column reference in the select, if possible.
1299: ColumnReference newCRNode = select
1300: .findColumnReferenceInResult(crNode.columnName);
1301: if (newCRNode == null)
1302: continue;
1303:
1304: // Create a copy of the predicate to push down
1305: // <column> <relop> <value> AND TRUE
1306: if (andNode.getLeftOperand() instanceof BinaryRelationalOperatorNode) {
1307: BinaryRelationalOperatorNode newRelop = (BinaryRelationalOperatorNode) getNodeFactory()
1308: .getNode(opNode.getNodeType(), newCRNode,
1309: opNode.getRightOperand(),
1310: getContextManager());
1311: newRelop.bindComparisonOperator();
1312: leftOperand = newRelop;
1313: } else {
1314: InListOperatorNode newInNode = (InListOperatorNode) getNodeFactory()
1315: .getNode(C_NodeTypes.IN_LIST_OPERATOR_NODE,
1316: newCRNode,
1317: inNode.getRightOperandList(),
1318: getContextManager());
1319: newInNode.setType(inNode.getTypeServices());
1320: leftOperand = newInNode;
1321: }
1322:
1323: // Convert the predicate into CNF form
1324: ValueNode trueNode = (ValueNode) getNodeFactory()
1325: .getNode(C_NodeTypes.BOOLEAN_CONSTANT_NODE,
1326: Boolean.TRUE, getContextManager());
1327: AndNode newAnd = (AndNode) getNodeFactory().getNode(
1328: C_NodeTypes.AND_NODE, leftOperand, trueNode,
1329: getContextManager());
1330: newAnd.postBindFixup();
1331: JBitSet tableMap = new JBitSet(
1332: select.referencedTableMap.size());
1333:
1334: // Use newly constructed predicate
1335: predicate = (Predicate) getNodeFactory().getNode(
1336: C_NodeTypes.PREDICATE, newAnd, tableMap,
1337: getContextManager());
1338: } else {
1339: // keep the counters up to date when removing a predicate
1340: if (predicate.isStartKey())
1341: numberOfStartPredicates--;
1342: if (predicate.isStopKey())
1343: numberOfStopPredicates--;
1344: if (predicate.isQualifier())
1345: numberOfQualifiers--;
1346:
1347: /* Clear all of the scan flags since they may be different
1348: * due to the splitting of the list.
1349: */
1350: predicate.clearScanFlags();
1351: // Remove this predicate from the list
1352: removeElementAt(index);
1353: }
1354:
1355: // Push it into the select
1356: select.pushExpressionsIntoSelect(predicate);
1357: }
1358: }
1359:
1360: /**
1361: * Mark all of the RCs and the RCs in their RC/VCN chain
1362: * referenced in the predicate list as referenced.
1363: *
1364: * @exception StandardException Thrown on error
1365: */
1366: void markReferencedColumns() throws StandardException {
1367: CollectNodesVisitor collectCRs = new CollectNodesVisitor(
1368: ColumnReference.class);
1369:
1370: int size = size();
1371: for (int index = 0; index < size; index++) {
1372: Predicate predicate = (Predicate) elementAt(index);
1373: predicate.getAndNode().accept(collectCRs);
1374: }
1375:
1376: Vector colRefs = collectCRs.getList();
1377: for (Enumeration e = colRefs.elements(); e.hasMoreElements();) {
1378: ColumnReference ref = (ColumnReference) e.nextElement();
1379: ref.getSource().markAllRCsInChainReferenced();
1380: }
1381: }
1382:
1383: /**
1384: * Update the array of columns in = conditions with constants
1385: * or correlation or join columns. This is useful when doing
1386: * subquery flattening on the basis of an equality condition.
1387: *
1388: * @param tableNumber The tableNumber of the table from which
1389: * the columns of interest come from.
1390: * @param eqOuterCols Array of booleans for noting which columns
1391: * are in = predicates with constants or
1392: * correlation columns.
1393: * @param tableNumbers Array of table numbers in this query block.
1394: * @param resultColTable tableNumber is the table the result columns are
1395: * coming from
1396: *
1397: * @exception StandardException Thrown on error
1398: */
1399: void checkTopPredicatesForEqualsConditions(int tableNumber,
1400: boolean[] eqOuterCols, int[] tableNumbers,
1401: JBitSet[] tableColMap, boolean resultColTable)
1402: throws StandardException {
1403: int size = size();
1404: for (int index = 0; index < size; index++) {
1405: AndNode and = (AndNode) ((Predicate) elementAt(index))
1406: .getAndNode();
1407: and.checkTopPredicatesForEqualsConditions(tableNumber,
1408: eqOuterCols, tableNumbers, tableColMap,
1409: resultColTable);
1410: }
1411: }
1412:
1413: /**
1414: * Check if all of the predicates in the list are pushable.
1415: *
1416: * @return Whether or not all of the predicates in the list are pushable.
1417: */
1418: boolean allPushable() {
1419: int size = size();
1420: for (int index = 0; index < size; index++) {
1421: Predicate predicate = (Predicate) elementAt(index);
1422: if (!predicate.getPushable()) {
1423: return false;
1424: }
1425: }
1426: return true;
1427: }
1428:
1429: /**
1430: * Build a list of pushable predicates, if any,
1431: * that satisfy the referencedTableMap.
1432: *
1433: * @param referencedTableMap The referenced table map
1434: *
1435: * @return A list of pushable predicates, if any,
1436: * that satisfy the referencedTableMap.
1437: *
1438: * @exception StandardException Thrown on error
1439: */
1440: PredicateList getPushablePredicates(JBitSet referencedTableMap)
1441: throws StandardException {
1442: PredicateList pushPList = null;
1443:
1444: // Walk the list backwards because of possible deletes
1445: for (int index = size() - 1; index >= 0; index--) {
1446: Predicate predicate = (Predicate) elementAt(index);
1447: if (!predicate.getPushable()) {
1448: continue;
1449: }
1450:
1451: JBitSet curBitSet = predicate.getReferencedSet();
1452:
1453: /* Do we have a match? */
1454: if (referencedTableMap.contains(curBitSet)) {
1455: /* Add the matching predicate to the push list */
1456: if (pushPList == null) {
1457: pushPList = (PredicateList) getNodeFactory()
1458: .getNode(C_NodeTypes.PREDICATE_LIST,
1459: getContextManager());
1460: }
1461: pushPList.addPredicate(predicate);
1462:
1463: /* Remap all of the ColumnReferences to point to the
1464: * source of the values.
1465: */
1466: RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
1467: predicate.getAndNode().accept(rcrv);
1468:
1469: /* Remove the matching predicate from the outer list */
1470: removeElementAt(index);
1471: }
1472: }
1473: return pushPList;
1474: }
1475:
1476: /**
1477: * Decrement the level of any CRs from the subquery's
1478: * FROM list that are interesting to transitive closure.
1479: *
1480: * @param fromList The subquery's FROM list.
1481: * @param decrement Decrement size.
1482: */
1483: void decrementLevel(FromList fromList, int decrement) {
1484: int[] tableNumbers = fromList.getTableNumbers();
1485:
1486: /* For each top level relop, find all top level
1487: * CRs from the subquery and decrement their
1488: * nesting level.
1489: */
1490: int size = size();
1491: for (int index = 0; index < size; index++) {
1492: ColumnReference cr1 = null;
1493: ColumnReference cr2 = null;
1494: Predicate predicate = (Predicate) elementAt(index);
1495: ValueNode vn = predicate.getAndNode().getLeftOperand();
1496:
1497: if (vn instanceof BinaryOperatorNode) {
1498: BinaryOperatorNode bon = (BinaryOperatorNode) vn;
1499: if (bon.getLeftOperand() instanceof ColumnReference) {
1500: cr1 = (ColumnReference) bon.getLeftOperand();
1501: }
1502: if (bon.getRightOperand() instanceof ColumnReference) {
1503: cr2 = (ColumnReference) bon.getRightOperand();
1504: }
1505: } else if (vn instanceof UnaryOperatorNode) {
1506: UnaryOperatorNode uon = (UnaryOperatorNode) vn;
1507: if (uon.getOperand() instanceof ColumnReference) {
1508: cr1 = (ColumnReference) uon.getOperand();
1509: }
1510: }
1511:
1512: /* See if any of the CRs need to have their
1513: * source level decremented.
1514: */
1515: if (cr1 != null) {
1516: int sourceTable = cr1.getTableNumber();
1517: for (int inner = 0; inner < tableNumbers.length; inner++)
1518: if (tableNumbers[inner] == sourceTable) {
1519: cr1.setSourceLevel(cr1.getSourceLevel()
1520: - decrement);
1521: break;
1522: }
1523: }
1524:
1525: if (cr2 != null) {
1526: int sourceTable = cr2.getTableNumber();
1527: for (int inner = 0; inner < tableNumbers.length; inner++)
1528: if (tableNumbers[inner] == sourceTable) {
1529: cr2.setSourceLevel(cr2.getSourceLevel()
1530: - decrement);
1531: break;
1532: }
1533: }
1534: }
1535: }
1536:
1537: /**
1538: * Perform transitive closure on join clauses. For each table in the query,
1539: * we build a list of equijoin clauses of the form:
1540: * <ColumnReference> <=> <ColumnReference>
1541: * Each join clause is put on 2 lists since it joins 2 tables.
1542: *
1543: * We then walk the array of lists. We first walk it as the outer list.
1544: * For each equijoin predicate, we assign an equivalence class if it does
1545: * not yet have one. We then walk the predicate list (as middle) for the
1546: * other table, searching for other equijoins with the middle table number
1547: * and column number. All such predicates are assigned the same
1548: * equivalence class. We then walk the predicate list (as inner) for the
1549: * other side of the middle predicate to see if we can find an equijoin
1550: * between outer and inner. If so, then we simply assign it to the same
1551: * equivalence class. If not, then we add the new equijoin clause.
1552: *
1553: * @param numTables The number of tables in the query
1554: * @param fromList The FromList in question.
1555: * @param cc The CompilerContext to use
1556: *
1557: * @exception StandardException Thrown on error
1558: */
1559: void joinClauseTransitiveClosure(int numTables, FromList fromList,
1560: CompilerContext cc) throws StandardException {
1561: // Nothing to do if < 3 tables
1562: if (fromList.size() < 3) {
1563: return;
1564: }
1565:
1566: /* Create an array of numTables PredicateLists to hold the join clauses. */
1567: PredicateList[] joinClauses = new PredicateList[numTables];
1568: for (int index = 0; index < numTables; index++) {
1569: joinClauses[index] = new PredicateList();
1570: }
1571:
1572: /* Pull the equijoin clauses, putting each one in the list for
1573: * each of the tables being joined.
1574: */
1575: int size = size();
1576: for (int index = 0; index < size; index++) {
1577: Predicate predicate = (Predicate) elementAt(index);
1578: ValueNode vn = predicate.getAndNode().getLeftOperand();
1579:
1580: if (!(vn.isBinaryEqualsOperatorNode())) {
1581: continue;
1582: }
1583:
1584: /* Is this an equijoin clause between 2 ColumnReferences? */
1585: BinaryRelationalOperatorNode equals = (BinaryRelationalOperatorNode) vn;
1586: ValueNode left = equals.getLeftOperand();
1587: ValueNode right = equals.getRightOperand();
1588:
1589: if ((left instanceof ColumnReference && right instanceof ColumnReference)) {
1590: ColumnReference leftCR = (ColumnReference) left;
1591: ColumnReference rightCR = (ColumnReference) right;
1592: if (leftCR.getSourceLevel() == rightCR.getSourceLevel()
1593: && leftCR.getTableNumber() != rightCR
1594: .getTableNumber()) {
1595: // Add the equijoin clause to each of the lists
1596: joinClauses[leftCR.getTableNumber()]
1597: .addElement(predicate);
1598: joinClauses[rightCR.getTableNumber()]
1599: .addElement(predicate);
1600: }
1601: continue;
1602: }
1603: }
1604:
1605: /* Walk each of the PredicateLists, using each 1 as the starting point
1606: * of an equivalence class.
1607: */
1608: for (int index = 0; index < numTables; index++) {
1609: PredicateList outerJCL = joinClauses[index];
1610:
1611: // Skip the empty lists
1612: if (outerJCL.size() == 0) {
1613: continue;
1614: }
1615:
1616: /* Put all of the join clauses that already have an equivalence
1617: * class at the head of the outer list to optimize search.
1618: */
1619: Vector movePreds = new Vector();
1620: for (int jcIndex = outerJCL.size() - 1; jcIndex >= 0; jcIndex--) {
1621: Predicate predicate = (Predicate) outerJCL
1622: .elementAt(jcIndex);
1623: if (predicate.getEquivalenceClass() != -1) {
1624: outerJCL.removeElementAt(jcIndex);
1625: movePreds.addElement(predicate);
1626: }
1627: }
1628: for (int mpIndex = 0; mpIndex < movePreds.size(); mpIndex++) {
1629: outerJCL.insertElementAt((Predicate) movePreds
1630: .elementAt(mpIndex), 0);
1631: }
1632:
1633: // Walk this list as the outer
1634: for (int outerIndex = 0; outerIndex < outerJCL.size(); outerIndex++) {
1635: ColumnReference innerCR = null;
1636: ColumnReference outerCR = null;
1637: int outerTableNumber = index;
1638: int middleTableNumber;
1639: int outerColumnNumber;
1640: int middleColumnNumber;
1641: int outerEC;
1642:
1643: /* Assign an equivalence class to those Predicates
1644: * that have not already been assigned an equivalence class.
1645: */
1646: Predicate outerP = (Predicate) outerJCL
1647: .elementAt(outerIndex);
1648: if (outerP.getEquivalenceClass() == -1) {
1649: outerP.setEquivalenceClass(cc
1650: .getNextEquivalenceClass());
1651: }
1652: outerEC = outerP.getEquivalenceClass();
1653:
1654: // Get the table and column numbers
1655: BinaryRelationalOperatorNode equals = (BinaryRelationalOperatorNode) outerP
1656: .getAndNode().getLeftOperand();
1657: ColumnReference leftCR = (ColumnReference) equals
1658: .getLeftOperand();
1659: ColumnReference rightCR = (ColumnReference) equals
1660: .getRightOperand();
1661:
1662: if (leftCR.getTableNumber() == outerTableNumber) {
1663: outerColumnNumber = leftCR.getColumnNumber();
1664: middleTableNumber = rightCR.getTableNumber();
1665: middleColumnNumber = rightCR.getColumnNumber();
1666: outerCR = leftCR;
1667: } else {
1668: outerColumnNumber = rightCR.getColumnNumber();
1669: middleTableNumber = leftCR.getTableNumber();
1670: middleColumnNumber = leftCR.getColumnNumber();
1671: outerCR = rightCR;
1672: }
1673:
1674: /* Walk the other list as the middle to find other join clauses
1675: * in the chain/equivalence class
1676: */
1677: PredicateList middleJCL = joinClauses[middleTableNumber];
1678: for (int middleIndex = 0; middleIndex < middleJCL
1679: .size(); middleIndex++) {
1680: /* Skip those Predicates that have already been
1681: * assigned a different equivalence class.
1682: */
1683: Predicate middleP = (Predicate) middleJCL
1684: .elementAt(middleIndex);
1685: if (middleP.getEquivalenceClass() != -1
1686: && middleP.getEquivalenceClass() != outerEC) {
1687: continue;
1688: }
1689:
1690: int innerTableNumber;
1691: int innerColumnNumber;
1692:
1693: // Get the table and column numbers
1694: BinaryRelationalOperatorNode middleEquals = (BinaryRelationalOperatorNode) middleP
1695: .getAndNode().getLeftOperand();
1696: ColumnReference mLeftCR = (ColumnReference) middleEquals
1697: .getLeftOperand();
1698: ColumnReference mRightCR = (ColumnReference) middleEquals
1699: .getRightOperand();
1700:
1701: /* Find the other side of the equijoin, skipping this predicate if
1702: * not on middleColumnNumber.
1703: */
1704: if (mLeftCR.getTableNumber() == middleTableNumber) {
1705: if (mLeftCR.getColumnNumber() != middleColumnNumber) {
1706: continue;
1707: }
1708: innerTableNumber = mRightCR.getTableNumber();
1709: innerColumnNumber = mRightCR.getColumnNumber();
1710: } else {
1711: if (mRightCR.getColumnNumber() != middleColumnNumber) {
1712: continue;
1713: }
1714: innerTableNumber = mLeftCR.getTableNumber();
1715: innerColumnNumber = mLeftCR.getColumnNumber();
1716: }
1717:
1718: // Skip over outerTableNumber.outerColumnNumber = middleTableNumber.middleColumnNumber
1719: if (outerTableNumber == innerTableNumber
1720: && outerColumnNumber == innerColumnNumber) {
1721: continue;
1722: }
1723:
1724: // Put this predicate into the outer equivalence class
1725: middleP.setEquivalenceClass(outerEC);
1726:
1727: /* Now go to the inner list and see if there is an equijoin
1728: * between inner and outer on innerColumnNumber and outerColumnNumber.
1729: * If so, then we continue our walk across middle, otherwise we
1730: * add a new equijoin to both the inner and outer lists before
1731: * continuing to walk across middle.
1732: */
1733:
1734: int newTableNumber;
1735: int newColumnNumber;
1736: Predicate innerP = null;
1737: PredicateList innerJCL = joinClauses[innerTableNumber];
1738: int innerIndex = 0;
1739: for (; innerIndex < innerJCL.size(); innerIndex++) {
1740: innerP = (Predicate) innerJCL
1741: .elementAt(innerIndex);
1742:
1743: // Skip over predicates with other equivalence classes
1744: if (innerP.getEquivalenceClass() != -1
1745: && innerP.getEquivalenceClass() != outerEC) {
1746: continue;
1747: }
1748:
1749: /* Now we see if the inner predicate completes the loop.
1750: * If so, then add it to the outer equivalence class
1751: * and stop.
1752: */
1753:
1754: // Get the table and column numbers
1755: BinaryRelationalOperatorNode innerEquals = (BinaryRelationalOperatorNode) innerP
1756: .getAndNode().getLeftOperand();
1757: ColumnReference iLeftCR = (ColumnReference) innerEquals
1758: .getLeftOperand();
1759: ColumnReference iRightCR = (ColumnReference) innerEquals
1760: .getRightOperand();
1761:
1762: if (iLeftCR.getTableNumber() == innerTableNumber) {
1763: if (iLeftCR.getColumnNumber() != innerColumnNumber) {
1764: continue;
1765: }
1766: newTableNumber = iRightCR.getTableNumber();
1767: newColumnNumber = iRightCR
1768: .getColumnNumber();
1769: innerCR = iLeftCR;
1770: } else {
1771: if (iRightCR.getColumnNumber() != innerColumnNumber) {
1772: continue;
1773: }
1774: newTableNumber = iLeftCR.getTableNumber();
1775: newColumnNumber = iLeftCR.getColumnNumber();
1776: innerCR = iRightCR;
1777: }
1778:
1779: // Did we find the equijoin between inner and outer
1780: if (newTableNumber == outerTableNumber
1781: && newColumnNumber == outerColumnNumber) {
1782: break;
1783: }
1784: }
1785:
1786: // Did we find an equijoin on inner and outer
1787: if (innerIndex != innerJCL.size()) {
1788: // match found
1789: // Put this predicate into the outer equivalence class
1790: innerP.setEquivalenceClass(outerEC);
1791: continue;
1792: }
1793:
1794: // No match, add new equijoin
1795: // Build a new predicate
1796: BinaryRelationalOperatorNode newEquals = (BinaryRelationalOperatorNode) getNodeFactory()
1797: .getNode(
1798: C_NodeTypes.BINARY_EQUALS_OPERATOR_NODE,
1799: outerCR.getClone(),
1800: innerCR.getClone(),
1801: getContextManager());
1802: newEquals.bindComparisonOperator();
1803: /* Create the AND */
1804: ValueNode trueNode = (ValueNode) getNodeFactory()
1805: .getNode(C_NodeTypes.BOOLEAN_CONSTANT_NODE,
1806: Boolean.TRUE, getContextManager());
1807: AndNode newAnd = (AndNode) getNodeFactory()
1808: .getNode(C_NodeTypes.AND_NODE, newEquals,
1809: trueNode, getContextManager());
1810: newAnd.postBindFixup();
1811: // Add a new predicate to both the equijoin clauses and this list
1812: JBitSet tableMap = new JBitSet(numTables);
1813: newAnd.categorize(tableMap, false);
1814: Predicate newPred = (Predicate) getNodeFactory()
1815: .getNode(C_NodeTypes.PREDICATE, newAnd,
1816: tableMap, getContextManager());
1817: newPred.setEquivalenceClass(outerEC);
1818: addPredicate(newPred);
1819: /* Add the new predicate right after the outer position
1820: * so that we can follow all of the predicates in equivalence
1821: * classes before those that do not yet have equivalence classes.
1822: */
1823: if (outerIndex != outerJCL.size() - 1) {
1824: outerJCL.insertElementAt(newPred,
1825: outerIndex + 1);
1826: } else {
1827: outerJCL.addElement(newPred);
1828: }
1829: innerJCL.addElement(newPred);
1830: }
1831: }
1832: }
1833: }
1834:
1835: /**
1836: * Perform transitive closure on search clauses. We build a
1837: * list of search clauses of the form:
1838: * <ColumnReference> <RelationalOperator> [<ConstantNode>]
1839: * We also build a list of equijoin conditions of form:
1840: * <ColumnReference1> = <ColumnReference2>
1841: * where both columns are from different tables in the same query block.
1842: * For each search clause in the list, we search the equijoin list to see
1843: * if there is an equijoin clause on the same column. If so, then we
1844: * search the search clause list for a search condition on the column
1845: * being joined against with the same relation operator and constant. If
1846: * a match is found, then there is no need to add a new predicate.
1847: * Otherwise, we add a new search condition on the column being joined
1848: * with. In either case, if the relational operator in the search
1849: * clause is an "=" then we mark the equijoin clause as being redundant.
1850: * Redundant equijoin clauses will be removed at the end of the search as
1851: * they are * unnecessary.
1852: *
1853: * @param numTables The number of tables in the query
1854: * @param hashJoinSpecified Whether or not user specified a hash join
1855: *
1856: * @exception StandardException Thrown on error
1857: */
1858: void searchClauseTransitiveClosure(int numTables,
1859: boolean hashJoinSpecified) throws StandardException {
1860: PredicateList equijoinClauses = new PredicateList();
1861: PredicateList searchClauses = new PredicateList();
1862: RelationalOperator equalsNode = null;
1863:
1864: int size = size();
1865: for (int index = 0; index < size; index++) {
1866: Predicate predicate = (Predicate) elementAt(index);
1867: AndNode andNode = predicate.getAndNode();
1868:
1869: // Skip anything that's not a RelationalOperator
1870: if (!(andNode.getLeftOperand() instanceof RelationalOperator)) {
1871: continue;
1872: }
1873:
1874: RelationalOperator operator = (RelationalOperator) andNode
1875: .getLeftOperand();
1876: // Is this an equijoin?
1877: if (((ValueNode) operator).isBinaryEqualsOperatorNode()) {
1878: BinaryRelationalOperatorNode equals = (BinaryRelationalOperatorNode) operator;
1879: // Remember any equals node for redundancy check at end
1880: equalsNode = equals;
1881: ValueNode left = equals.getLeftOperand();
1882: ValueNode right = equals.getRightOperand();
1883: if ((left instanceof ColumnReference && right instanceof ColumnReference)) {
1884: ColumnReference leftCR = (ColumnReference) left;
1885: ColumnReference rightCR = (ColumnReference) right;
1886: if (leftCR.getSourceLevel() == rightCR
1887: .getSourceLevel()
1888: && leftCR.getTableNumber() != rightCR
1889: .getTableNumber()) {
1890: equijoinClauses.addElement(predicate);
1891: }
1892: continue;
1893: }
1894: }
1895:
1896: // Is this a usable search clause?
1897: if (operator instanceof UnaryComparisonOperatorNode) {
1898: if (((UnaryComparisonOperatorNode) operator)
1899: .getOperand() instanceof ColumnReference) {
1900: searchClauses.addElement(predicate);
1901: }
1902: continue;
1903: } else if (operator instanceof BinaryComparisonOperatorNode) {
1904: BinaryComparisonOperatorNode bcon = (BinaryComparisonOperatorNode) operator;
1905: ValueNode left = bcon.getLeftOperand();
1906: ValueNode right = bcon.getRightOperand();
1907:
1908: // RESOLVE: Consider using variant type of the expression, instead of
1909: // ConstantNode or ParameterNode in the future.
1910: if (left instanceof ColumnReference
1911: && (right instanceof ConstantNode || right instanceof ParameterNode)) {
1912: searchClauses.addElement(predicate);
1913: } else if (right instanceof ConstantNode
1914: && left instanceof ColumnReference) {
1915: // put the ColumnReference on the left to simplify things
1916: bcon.swapOperands();
1917: searchClauses.addElement(predicate);
1918: }
1919: continue;
1920: }
1921: }
1922:
1923: // Nothing to do if no search clauses or equijoin clauses
1924: if (equijoinClauses.size() == 0 || searchClauses.size() == 0) {
1925: return;
1926: }
1927:
1928: /* Now we do the real work.
1929: * NOTE: We can append to the searchClauses while walking
1930: * them, thus we cannot cache the value of size().
1931: */
1932: for (int scIndex = 0; scIndex < searchClauses.size(); scIndex++) {
1933: ColumnReference searchCR;
1934: DataValueDescriptor searchODV = null;
1935: RelationalOperator ro = (RelationalOperator) ((AndNode) ((Predicate) searchClauses
1936: .elementAt(scIndex)).getAndNode()).getLeftOperand();
1937:
1938: // Find the ColumnReference and constant value, if any, in the search clause
1939: if (ro instanceof UnaryComparisonOperatorNode) {
1940: searchCR = (ColumnReference) ((UnaryComparisonOperatorNode) ro)
1941: .getOperand();
1942: } else {
1943: searchCR = (ColumnReference) ((BinaryComparisonOperatorNode) ro)
1944: .getLeftOperand();
1945:
1946: // Don't get value for parameterNode since not known yet.
1947: if (((BinaryComparisonOperatorNode) ro)
1948: .getRightOperand() instanceof ConstantNode) {
1949: ConstantNode currCN = (ConstantNode) ((BinaryComparisonOperatorNode) ro)
1950: .getRightOperand();
1951: searchODV = (DataValueDescriptor) currCN.getValue();
1952: } else
1953: searchODV = null;
1954: }
1955: // Cache the table and column numbers of searchCR
1956: int tableNumber = searchCR.getTableNumber();
1957: int colNumber = searchCR.getColumnNumber();
1958:
1959: // Look for any equijoin clauses of interest
1960: int ejcSize = equijoinClauses.size();
1961: for (int ejcIndex = 0; ejcIndex < ejcSize; ejcIndex++) {
1962: /* Skip the current equijoin clause if it has already been used
1963: * when adding a new search clause of the same type
1964: * via transitive closure.
1965: * NOTE: We check the type of the search clause instead of just the
1966: * fact that a search clause was added because multiple search clauses
1967: * can get added when preprocessing LIKE and BETWEEN.
1968: */
1969: Predicate predicate = (Predicate) equijoinClauses
1970: .elementAt(ejcIndex);
1971: if (predicate.transitiveSearchClauseAdded(ro)) {
1972: continue;
1973: }
1974:
1975: BinaryRelationalOperatorNode equals = (BinaryRelationalOperatorNode) ((AndNode) predicate
1976: .getAndNode()).getLeftOperand();
1977: ColumnReference leftCR = (ColumnReference) equals
1978: .getLeftOperand();
1979: ColumnReference rightCR = (ColumnReference) equals
1980: .getRightOperand();
1981: ColumnReference otherCR;
1982:
1983: if (leftCR.getTableNumber() == tableNumber
1984: && leftCR.getColumnNumber() == colNumber) {
1985: otherCR = rightCR;
1986: } else if (rightCR.getTableNumber() == tableNumber
1987: && rightCR.getColumnNumber() == colNumber) {
1988: otherCR = leftCR;
1989: } else {
1990: // this is not a matching equijoin clause
1991: continue;
1992: }
1993:
1994: /* At this point we've found a search clause and an equijoin that
1995: * are candidates for adding a new search clause via transitive
1996: * closure. Look to see if a matching search clause already
1997: * exists on the other table. If not, then add one.
1998: * NOTE: In either case we mark the join clause has having added
1999: * a search clause of this type to short circuit any future searches
2000: */
2001: predicate.setTransitiveSearchClauseAdded(ro);
2002:
2003: boolean match = false;
2004: ColumnReference searchCR2 = null;
2005: RelationalOperator ro2 = null;
2006: int scSize = searchClauses.size();
2007: for (int scIndex2 = 0; scIndex2 < scSize; scIndex2++) {
2008: DataValueDescriptor currODV = null;
2009: ro2 = (RelationalOperator) ((AndNode) ((Predicate) searchClauses
2010: .elementAt(scIndex2)).getAndNode())
2011: .getLeftOperand();
2012:
2013: // Find the ColumnReference in the search clause
2014: if (ro2 instanceof UnaryComparisonOperatorNode) {
2015: searchCR2 = (ColumnReference) ((UnaryComparisonOperatorNode) ro2)
2016: .getOperand();
2017: } else {
2018: searchCR2 = (ColumnReference) ((BinaryComparisonOperatorNode) ro2)
2019: .getLeftOperand();
2020: if (((BinaryComparisonOperatorNode) ro2)
2021: .getRightOperand() instanceof ConstantNode) {
2022: ConstantNode currCN = (ConstantNode) ((BinaryComparisonOperatorNode) ro2)
2023: .getRightOperand();
2024: currODV = (DataValueDescriptor) currCN
2025: .getValue();
2026: } else
2027: currODV = null;
2028: }
2029:
2030: /* Is this a match? A match is a search clause with
2031: * the same operator on the same column with a comparison against
2032: * the same value.
2033: */
2034: if (searchCR2.getTableNumber() == otherCR
2035: .getTableNumber()
2036: && searchCR2.getColumnNumber() == otherCR
2037: .getColumnNumber()
2038: && ((currODV != null && searchODV != null && currODV
2039: .compare(searchODV) == 0) || (currODV == null && searchODV == null))
2040: && ro2.getOperator() == ro.getOperator()
2041: && ro2.getClass().getName().equals(
2042: ro.getClass().getName())) {
2043: match = true;
2044: break;
2045: }
2046: }
2047:
2048: // Add the new search clause if no match found
2049: if (!match) {
2050: // Build a new predicate
2051: RelationalOperator roClone = ro
2052: .getTransitiveSearchClause((ColumnReference) otherCR
2053: .getClone());
2054:
2055: /* Set type info for the operator node */
2056: if (roClone instanceof BinaryComparisonOperatorNode) {
2057: ((BinaryComparisonOperatorNode) roClone)
2058: .bindComparisonOperator();
2059: } else {
2060: ((UnaryComparisonOperatorNode) roClone)
2061: .bindComparisonOperator();
2062: }
2063:
2064: /* Create the AND */
2065: ValueNode trueNode = (ValueNode) getNodeFactory()
2066: .getNode(C_NodeTypes.BOOLEAN_CONSTANT_NODE,
2067: Boolean.TRUE, getContextManager());
2068: AndNode newAnd = (AndNode) getNodeFactory()
2069: .getNode(C_NodeTypes.AND_NODE, roClone,
2070: trueNode, getContextManager());
2071: newAnd.postBindFixup();
2072: // Add a new predicate to both the search clauses and this list
2073: JBitSet tableMap = new JBitSet(numTables);
2074: newAnd.categorize(tableMap, false);
2075: Predicate newPred = (Predicate) getNodeFactory()
2076: .getNode(C_NodeTypes.PREDICATE, newAnd,
2077: tableMap, getContextManager());
2078: addPredicate(newPred);
2079: searchClauses.addElement(newPred);
2080: }
2081: }
2082: }
2083:
2084: /* Finally, we eliminate any equijoin clauses made redundant by
2085: * transitive closure, but only if the user did not specify a hash join
2086: * in the current query block.
2087: */
2088: if (hashJoinSpecified) {
2089: return;
2090: }
2091:
2092: /* Walk list backwards since we can delete while
2093: * traversing the list.
2094: */
2095: for (int index = size() - 1; index >= 0; index--) {
2096: Predicate predicate = (Predicate) elementAt(index);
2097:
2098: if (predicate.transitiveSearchClauseAdded(equalsNode)) {
2099: removeElementAt(index);
2100: }
2101: }
2102: }
2103:
2104: /**
2105: * Remove redundant predicates. A redundant predicate has an equivalence
2106: * class (!= -1) and there are other predicates in the same equivalence
2107: * class after it in the list. (Actually, we remove all of the predicates
2108: * in the same equivalence class that appear after this one.)
2109: */
2110: void removeRedundantPredicates() {
2111: /* Walk backwards since we may remove 1 or more
2112: * elements for each predicate in the outer pass.
2113: */
2114: int outer = size() - 1;
2115: while (outer >= 0) {
2116: Predicate predicate = (Predicate) elementAt(outer);
2117: int equivalenceClass = predicate.getEquivalenceClass();
2118:
2119: if (equivalenceClass == -1) {
2120: outer--;
2121: continue;
2122: }
2123:
2124: // Walk the rest of the list backwards.
2125: for (int inner = outer - 1; inner >= 0; inner--) {
2126: Predicate innerPredicate = (Predicate) elementAt(inner);
2127: if (innerPredicate.getEquivalenceClass() == equivalenceClass) {
2128: /* Only 1 predicate per column can be marked as a start
2129: * and/or a stop position.
2130: * When removing a redundant predicate, we need to make sure
2131: * that the outer predicate gets marked as a start and/or
2132: * stop key if the inner predicate is a start and/or stop
2133: * key. In this case, we are not changing the number of
2134: * start and/or stop positions, so we leave that count alone.
2135: */
2136: if (innerPredicate.isStartKey()) {
2137: predicate.markStartKey();
2138: }
2139: if (innerPredicate.isStopKey()) {
2140: predicate.markStopKey();
2141: }
2142: if (innerPredicate.isStartKey()
2143: || innerPredicate.isStopKey()) {
2144: if (innerPredicate.isQualifier()) {
2145: // Bug 5868 - Query returns duplicate rows. In order to fix this,
2146: // If the inner predicate is a qualifer along with being a start and/or stop,
2147: // then mark the outer predicate as a qualifer too(along with marking it as a start
2148: // and/or stop) if it is not already marked as qualifer and increment the qualifiers counter
2149: // The reason we do this is that a start and/or stop key is not equivalent to
2150: // a qualifier. In the orderUsefulPredicates method in this class(comment on line 786),
2151: // we mark a start/stop as qualifier if we have already seen a previous column in composite
2152: // index whose RELOPS do not include '=' or IS NULL. And hence we should not disregard
2153: // the qualifier flag of inner predicate
2154: if (!predicate.isQualifier()) {
2155: predicate.markQualifier();
2156: numberOfQualifiers++;
2157: }
2158: }
2159: }
2160: /*
2161: * If the redundant predicate is a qualifier, then we must
2162: * decrement the qualifier count. (Remaining predicate is
2163: * already marked correctly.)
2164: */
2165: if (innerPredicate.isQualifier()) {
2166: numberOfQualifiers--;
2167: }
2168: removeElementAt(inner);
2169: outer--;
2170: }
2171: }
2172:
2173: outer--;
2174: }
2175: }
2176:
2177: /**
2178: * @see OptimizablePredicateList#transferPredicates
2179: *
2180: * @exception StandardException Thrown on error
2181: */
2182: public void transferPredicates(OptimizablePredicateList otherList,
2183: JBitSet referencedTableMap, Optimizable table)
2184: throws StandardException {
2185: Predicate predicate;
2186: PredicateList theOtherList = (PredicateList) otherList;
2187:
2188: /* Walk list backwards since we can delete while
2189: * traversing the list.
2190: */
2191: for (int index = size() - 1; index >= 0; index--) {
2192: predicate = (Predicate) elementAt(index);
2193:
2194: if (SanityManager.DEBUG) {
2195: if (referencedTableMap.size() != predicate
2196: .getReferencedSet().size()) {
2197: SanityManager
2198: .THROWASSERT("referencedTableMap.size() ("
2199: + referencedTableMap.size()
2200: + ") does not equal predicate.getReferencedSet().size() ("
2201: + predicate.getReferencedSet()
2202: .size());
2203: }
2204: }
2205:
2206: if (referencedTableMap.contains(predicate
2207: .getReferencedSet())) {
2208: // We need to keep the counters up to date when removing a predicate
2209: if (predicate.isStartKey())
2210: numberOfStartPredicates--;
2211: if (predicate.isStopKey())
2212: numberOfStopPredicates--;
2213: if (predicate.isQualifier())
2214: numberOfQualifiers--;
2215:
2216: /* Clear all of the scan flags since they may be different
2217: * due to the splitting of the list.
2218: */
2219: predicate.clearScanFlags();
2220: // Do the actual xfer
2221: theOtherList.addPredicate(predicate);
2222: removeElementAt(index);
2223: }
2224: }
2225:
2226: // order the useful predicates on the other list
2227: AccessPath ap = table.getTrulyTheBestAccessPath();
2228: theOtherList.orderUsefulPredicates(table, ap
2229: .getConglomerateDescriptor(), false, ap
2230: .getNonMatchingIndexScan(), ap.getCoveringIndexScan());
2231:
2232: // count the start/stop positions and qualifiers
2233: theOtherList.countScanFlags();
2234: }
2235:
2236: /**
2237: * @see OptimizablePredicateList#transferAllPredicates
2238: *
2239: * @exception StandardException Thrown on error
2240: */
2241: public void transferAllPredicates(OptimizablePredicateList otherList)
2242: throws StandardException {
2243: PredicateList theOtherList = (PredicateList) otherList;
2244:
2245: int size = size();
2246: for (int index = 0; index < size; index++) {
2247: Predicate predicate = (Predicate) elementAt(index);
2248:
2249: /*
2250: ** Clear all of the scan flags since they may be different
2251: ** when the new list is re-classified
2252: */
2253: predicate.clearScanFlags();
2254:
2255: // Add the predicate to the other list
2256: theOtherList.addPredicate(predicate);
2257: }
2258:
2259: // Remove all of the predicates from this list
2260: removeAllElements();
2261:
2262: /*
2263: ** This list is now empty, so there are no start predicates,
2264: ** stop predicates, or qualifiers.
2265: */
2266: numberOfStartPredicates = 0;
2267: numberOfStopPredicates = 0;
2268: numberOfQualifiers = 0;
2269: }
2270:
2271: /**
2272: * @see OptimizablePredicateList#copyPredicatesToOtherList
2273: *
2274: * @exception StandardException Thrown on error
2275: */
2276: public void copyPredicatesToOtherList(
2277: OptimizablePredicateList otherList)
2278: throws StandardException {
2279: for (int i = 0; i < size(); i++) {
2280: otherList.addOptPredicate(getOptPredicate(i));
2281: }
2282: }
2283:
2284: /**
2285: * @see OptimizablePredicateList#isRedundantPredicate
2286: */
2287: public boolean isRedundantPredicate(int predNum) {
2288: Predicate pred = (Predicate) elementAt(predNum);
2289: if (pred.getEquivalenceClass() == -1) {
2290: return false;
2291: }
2292: for (int index = 0; index < predNum; index++) {
2293: if (((Predicate) elementAt(index)).getEquivalenceClass() == pred
2294: .getEquivalenceClass()) {
2295: return true;
2296: }
2297: }
2298: return false;
2299: }
2300:
2301: /**
2302: * @see OptimizablePredicateList#setPredicatesAndProperties
2303: *
2304: * @exception StandardException Thrown on error
2305: */
2306: public void setPredicatesAndProperties(
2307: OptimizablePredicateList otherList)
2308: throws StandardException {
2309: PredicateList theOtherList = (PredicateList) otherList;
2310:
2311: theOtherList.removeAllElements();
2312:
2313: for (int i = 0; i < size(); i++) {
2314: theOtherList.addOptPredicate(getOptPredicate(i));
2315: }
2316:
2317: theOtherList.numberOfStartPredicates = numberOfStartPredicates;
2318: theOtherList.numberOfStopPredicates = numberOfStopPredicates;
2319: theOtherList.numberOfQualifiers = numberOfQualifiers;
2320: }
2321:
2322: /** @see OptimizablePredicateList#startOperator */
2323: public int startOperator(Optimizable optTable) {
2324: int startOperator;
2325:
2326: /*
2327: ** This is the value we will use if there are no keys. It doesn't
2328: ** matter what it is, as long as the operator is one of GT or GE
2329: ** (to match the openScan() interface).
2330: */
2331: startOperator = ScanController.GT;
2332:
2333: int size = size();
2334: /* beetle 4572. start operator should be the last start key column's
2335: * start operator. Note that all previous ones should be GE.
2336: */
2337: for (int index = size - 1; index >= 0; index--) {
2338: Predicate pred = ((Predicate) elementAt(index));
2339:
2340: if (!pred.isStartKey())
2341: continue;
2342:
2343: startOperator = pred.getStartOperator(optTable);
2344: break;
2345: }
2346: return startOperator;
2347: }
2348:
2349: /**
2350: * @see OptimizablePredicateList#generateStopKey
2351: *
2352: * @exception StandardException Thrown on error
2353: */
2354: public void generateStopKey(ExpressionClassBuilderInterface acbi,
2355: MethodBuilder mb, Optimizable optTable)
2356: throws StandardException {
2357: ExpressionClassBuilder acb = (ExpressionClassBuilder) acbi;
2358:
2359: /*
2360: ** To make the stop-key allocating function we cycle through
2361: ** the Predicates and generate the function and initializer:
2362: **
2363: ** private ExecIndexRow exprN()
2364: ** { ExecIndexRow r = getExecutionFactory().getIndexableRow(# stop keys);
2365: ** for (pred = each predicate in list)
2366: ** {
2367: ** if (pred.isStartKey())
2368: ** {
2369: ** pred.generateKey(acb);
2370: ** }
2371: ** }
2372: ** }
2373: **
2374: ** If there are no start predicates, we do not generate anything.
2375: */
2376:
2377: if (numberOfStopPredicates != 0) {
2378: /* This sets up the method and the static field */
2379: MethodBuilder exprFun = acb.newExprFun();
2380:
2381: /* Now we fill in the body of the method */
2382: LocalField rowField = generateIndexableRow(acb,
2383: numberOfStopPredicates);
2384:
2385: int colNum = 0;
2386: int size = size();
2387: for (int index = 0; index < size; index++) {
2388: Predicate pred = ((Predicate) elementAt(index));
2389:
2390: if (!pred.isStopKey())
2391: continue;
2392:
2393: generateSetColumn(acb, exprFun, colNum, pred, optTable,
2394: rowField, false);
2395:
2396: colNum++;
2397: }
2398:
2399: if (SanityManager.DEBUG) {
2400: SanityManager.ASSERT(colNum == numberOfStopPredicates,
2401: "Number of stop predicates does not match");
2402: }
2403:
2404: finishKey(acb, mb, exprFun, rowField);
2405: return;
2406: }
2407:
2408: mb.pushNull(ClassName.GeneratedMethod);
2409: }
2410:
2411: /** @see OptimizablePredicateList#stopOperator */
2412: public int stopOperator(Optimizable optTable) {
2413: int stopOperator;
2414:
2415: /*
2416: ** This is the value we will use if there are no keys. It doesn't
2417: ** matter what it is, as long as the operator is one of GT or GE
2418: ** (to match the openScan() interface).
2419: */
2420: stopOperator = ScanController.GT;
2421:
2422: int size = size();
2423: /* beetle 4572. stop operator should be the last start key column's
2424: * stop operator. Note that all previous ones should be GT.
2425: */
2426: for (int index = size - 1; index >= 0; index--) {
2427: Predicate pred = ((Predicate) elementAt(index));
2428:
2429: if (!pred.isStopKey())
2430: continue;
2431:
2432: stopOperator = pred.getStopOperator(optTable);
2433: break;
2434: }
2435: return stopOperator;
2436: }
2437:
2438: private void generateSingleQualifierCode(MethodBuilder consMB,
2439: Optimizable optTable, boolean absolute,
2440: ExpressionClassBuilder acb, RelationalOperator or_node,
2441: LocalField qualField, int array_idx_1, int array_idx_2)
2442: throws StandardException {
2443: consMB.getField(qualField); // first arg for setQualifier
2444:
2445: // get instance for getQualifier call
2446: consMB.pushThis();
2447: consMB.callMethod(VMOpcode.INVOKEVIRTUAL, acb
2448: .getBaseClassName(), "getExecutionFactory",
2449: ExecutionFactory.MODULE, 0);
2450:
2451: // Column Id - first arg
2452: if (absolute)
2453: or_node.generateAbsoluteColumnId(consMB, optTable);
2454: else
2455: or_node.generateRelativeColumnId(consMB, optTable);
2456:
2457: // Operator - second arg
2458: or_node.generateOperator(consMB, optTable);
2459:
2460: // Method to evaluate qualifier -- third arg
2461: or_node.generateQualMethod(acb, consMB, optTable);
2462:
2463: // Receiver for above method - fourth arg
2464: acb.pushThisAsActivation(consMB);
2465:
2466: // Ordered Nulls? - fifth arg
2467: or_node.generateOrderedNulls(consMB);
2468:
2469: /*
2470: ** "Unknown" return value. For qualifiers,
2471: ** we never want to return rows where the
2472: ** result of a comparison is unknown.
2473: ** But we can't just generate false, because
2474: ** the comparison result could be negated.
2475: ** So, generate the same as the negation
2476: ** operand - that way, false will not be
2477: ** negated, and true will be negated to false.
2478: */
2479: or_node.generateNegate(consMB, optTable);
2480:
2481: /* Negate comparison result? */
2482: or_node.generateNegate(consMB, optTable);
2483:
2484: /* variantType for qualifier's orderable */
2485: consMB.push(or_node.getOrderableVariantType(optTable));
2486:
2487: consMB.callMethod(VMOpcode.INVOKEINTERFACE,
2488: ExecutionFactory.MODULE, "getQualifier",
2489: ClassName.Qualifier, 8);
2490:
2491: // result of getQualifier() is second arg for setQualifier
2492:
2493: consMB.push(array_idx_1); // third arg for setQualifier
2494: consMB.push(array_idx_2); // fourth arg for setQualifier
2495:
2496: consMB.callMethod(VMOpcode.INVOKESTATIC,
2497: acb.getBaseClassName(), "setQualifier", "void", 4);
2498: }
2499:
2500: /**
2501: * @see OptimizablePredicateList#generateQualifiers
2502: *
2503: * @exception StandardException Thrown on error
2504: */
2505: public void generateQualifiers(
2506: ExpressionClassBuilderInterface acbi, MethodBuilder mb,
2507: Optimizable optTable, boolean absolute)
2508: throws StandardException {
2509: ExpressionClassBuilder acb = (ExpressionClassBuilder) acbi;
2510:
2511: String retvalType = ClassName.Qualifier + "[][]";
2512: MethodBuilder consMB = acb.getConstructor();
2513: MethodBuilder executeMB = acb.getExecuteMethod();
2514:
2515: /* Create and initialize the array of Qualifiers */
2516: LocalField qualField = acb.newFieldDeclaration(
2517: Modifier.PRIVATE, retvalType);
2518:
2519: /*
2520: ** Stick a reinitialize of the Qualifier array in execute().
2521: ** Done because although we call Exec/Qualifier.clearOrderableCache()
2522: ** before each query, we only clear the cache for VARIANT and
2523: ** SCAN_INVARIANT qualifiers. However, each time the same
2524: ** statement is executed, even the QUERY_INVARIANT qualifiers
2525: ** need to be flushed. For example:
2526: ** prepare select c1 from t where c1 = (select max(c1) from t) as p;
2527: ** execute p; -- we now have the materialized subquery result (1)
2528: ** -- in our predicate
2529: ** insert into t values 666;
2530: ** execute p; -- we need to clear out 1 and recache the subq result
2531: */
2532:
2533: // PUSHCOMPILER
2534: // if (mb == executeMB) {
2535: // System.out.println("adding code to method in two places");
2536: // new Throwable().printStackTrace();
2537: // }
2538: //
2539: // generate code to reinitializeQualifiers(Qualifier[][] qualifiers)
2540: executeMB.getField(qualField); // first arg to reinitializeQualifiers()
2541: executeMB.callMethod(VMOpcode.INVOKESTATIC, acb
2542: .getBaseClassName(), "reinitializeQualifiers", "void",
2543: 1);
2544:
2545: /*
2546: ** Initialize the Qualifier array to a new Qualifier[][] if
2547: ** there are any qualifiers. It is automatically initialized to
2548: ** null if it isn't explicitly initialized.
2549: */
2550: if (numberOfQualifiers != 0) {
2551: if (SanityManager.DEBUG) {
2552: if (numberOfQualifiers > size()) {
2553: SanityManager.THROWASSERT("numberOfQualifiers("
2554: + numberOfQualifiers + ") > size(" + size()
2555: + ")." + ":" + this .hashCode());
2556: }
2557: }
2558:
2559: // Determine number of leading AND qualifiers, and subsequent
2560: // trailing OR qualifiers.
2561: int num_of_or_conjunctions = 0;
2562: for (int i = 0; i < numberOfQualifiers; i++) {
2563: if (((Predicate) elementAt(i)).isOrList()) {
2564: num_of_or_conjunctions++;
2565: }
2566: }
2567:
2568: /* Assign the initializer to the Qualifier[] field */
2569: consMB.pushNewArray(ClassName.Qualifier + "[]",
2570: (int) num_of_or_conjunctions + 1);
2571: consMB.setField(qualField);
2572:
2573: // Allocate qualifiers[0] which is an entry for each of the leading
2574: // AND clauses.
2575:
2576: consMB.getField(qualField); // 1st arg allocateQualArray
2577: consMB.push((int) 0); // 2nd arg allocateQualArray
2578: consMB.push((int) numberOfQualifiers
2579: - num_of_or_conjunctions); // 3rd arg allocateQualArray
2580:
2581: consMB
2582: .callMethod(VMOpcode.INVOKESTATIC, acb
2583: .getBaseClassName(), "allocateQualArray",
2584: "void", 3);
2585: }
2586:
2587: /* Sort the qualifiers by "selectivity" before generating.
2588: * We want the qualifiers ordered by selectivity with the
2589: * most selective ones first. There are 3 groups of qualifiers:
2590: * = and IS NULL are the most selective,
2591: * <> and IS NOT NULL are the least selective and
2592: * all of the other RELOPs are in between.
2593: * We break the list into 4 parts (3 types of qualifiers and
2594: * then everything else) and then rebuild the ordered list.
2595: * RESOLVE - we will eventually want to order the qualifiers
2596: * by (column #, selectivity) once the store does just in time
2597: * instantiation.
2598: */
2599: if (numberOfQualifiers > 0) {
2600: orderQualifiers();
2601: }
2602:
2603: /* Generate each of the qualifiers, if any */
2604:
2605: // First generate the "leading" AND qualifiers.
2606: int qualNum = 0;
2607: int size = size();
2608: boolean gotOrQualifier = false;
2609:
2610: for (int index = 0; index < size; index++) {
2611:
2612: Predicate pred = ((Predicate) elementAt(index));
2613:
2614: if (!pred.isQualifier()) {
2615: continue;
2616: } else if (pred.isOrList()) {
2617: gotOrQualifier = true;
2618:
2619: // will generate the OR qualifiers below.
2620: break;
2621: } else {
2622: generateSingleQualifierCode(consMB, optTable, absolute,
2623: acb, pred.getRelop(), qualField, 0, qualNum);
2624:
2625: qualNum++;
2626: }
2627: }
2628:
2629: if (gotOrQualifier) {
2630:
2631: // process each set of or's into a list which are AND'd. Each
2632: // predicate will become an array list in the qualifier array of
2633: // array's.
2634: //
2635: // The first list of And's went into qual[0][0...N]
2636: // Now each subquent predicate is actually a list of OR's so
2637: // will be passed as:
2638: // 1st OR predicate -> qual[1][0.. number of OR terms]
2639: // 2nd OR predicate -> qual[2][0.. number of OR terms]
2640: // ...
2641: //
2642: int and_idx = 1;
2643:
2644: // The remaining qualifiers must all be OR predicates, which
2645: // are pushed slightly differently than the leading AND qualifiers.
2646:
2647: for (int index = qualNum; index < size; index++, and_idx++) {
2648:
2649: Predicate pred = ((Predicate) elementAt(index));
2650:
2651: if (SanityManager.DEBUG) {
2652: SanityManager.ASSERT(pred.isOrList());
2653: }
2654:
2655: // create an ArrayList of the OR nodes. We need the count
2656: // of Or's in order to first generate the allocateQualArray()
2657: // call, then we walk the list assigning each of the OR's to
2658: // entries in the array in generateSingleQualifierCode().
2659: ArrayList a_list = new ArrayList();
2660:
2661: QueryTreeNode node = pred.getAndNode().getLeftOperand();
2662:
2663: while (node instanceof OrNode) {
2664: OrNode or_node = (OrNode) node;
2665:
2666: // The left operand of OR node is one of the terms,
2667: // (ie. A = 1)
2668: if (or_node.getLeftOperand() instanceof RelationalOperator) {
2669: a_list.add(or_node.getLeftOperand());
2670: }
2671:
2672: // The next OR node in the list if linked to the right.
2673: node = or_node.getRightOperand();
2674: }
2675:
2676: // Allocate an array to hold each of the terms of this OR,
2677: // clause. ie. (a = 1 or b = 2), will allocate a 2 entry array.
2678:
2679: consMB.getField(qualField); // 1st arg allocateQualArray
2680: consMB.push((int) and_idx); // 2nd arg allocateQualArray
2681: consMB.push((int) a_list.size()); // 3rd arg allocateQualArray
2682:
2683: consMB.callMethod(VMOpcode.INVOKESTATIC, acb
2684: .getBaseClassName(), "allocateQualArray",
2685: "void", 3);
2686:
2687: // finally transfer the nodes to the 2-d qualifier
2688: for (int i = 0; i < a_list.size(); i++) {
2689: generateSingleQualifierCode(consMB, optTable,
2690: absolute, acb, (RelationalOperator) a_list
2691: .get(i), qualField, and_idx, i);
2692:
2693: }
2694:
2695: qualNum++;
2696: }
2697:
2698: }
2699:
2700: if (SanityManager.DEBUG) {
2701: SanityManager.ASSERT(qualNum == numberOfQualifiers, qualNum
2702: + " Qualifiers found, " + numberOfQualifiers
2703: + " expected.");
2704: }
2705:
2706: /*
2707: ** Return a reference to the field that holds the initialized
2708: ** array of Qualifiers.
2709: */
2710: mb.getField(qualField);
2711: }
2712:
2713: /* Sort the qualifiers by "selectivity" before generating.
2714: * We want the qualifiers ordered by selectivity with the
2715: * most selective ones first. There are 3 groups of qualifiers:
2716: * = and IS NULL are the most selective,
2717: * <> and IS NOT NULL are the least selective and
2718: * all of the other RELOPs are in between.
2719: * We break the list into 4 parts (3 types of qualifiers and
2720: * then everything else) and then rebuild the ordered list.
2721: * RESOLVE - we will eventually want to order the qualifiers
2722: * by (column #, selectivity) once the store does just in time
2723: * instantiation.
2724: */
2725: private static final int QUALIFIER_ORDER_EQUALS = 0;
2726: private static final int QUALIFIER_ORDER_OTHER_RELOP = 1;
2727: private static final int QUALIFIER_ORDER_NOT_EQUALS = 2;
2728: private static final int QUALIFIER_ORDER_NON_QUAL = 3;
2729: private static final int QUALIFIER_ORDER_OR_CLAUSE = 4;
2730: private static final int QUALIFIER_NUM_CATEGORIES = 5;
2731:
2732: private void orderQualifiers() {
2733: // Sort the predicates into buckets, sortList[0] is the most
2734: // selective, while sortList[4] is the least restrictive.
2735: //
2736: // sortList[0]: "= and IS NULL"
2737: // sortList[1]: "a set of OR'd conjunctions"
2738: // sortList[2]: "all other relop's"
2739: // sortList[3]: "<> and IS NOT NULL"
2740: // sortList[4]: "everything else"
2741: PredicateList[] sortList = new PredicateList[QUALIFIER_NUM_CATEGORIES];
2742:
2743: for (int i = sortList.length - 1; i >= 0; i--)
2744: sortList[i] = new PredicateList();
2745:
2746: int predIndex;
2747: int size = size();
2748: for (predIndex = 0; predIndex < size; predIndex++) {
2749: Predicate pred = (Predicate) elementAt(predIndex);
2750:
2751: if (!pred.isQualifier()) {
2752: sortList[QUALIFIER_ORDER_NON_QUAL].addElement(pred);
2753: continue;
2754: }
2755:
2756: AndNode node = pred.getAndNode();
2757:
2758: if (!(node.getLeftOperand() instanceof OrNode)) {
2759: RelationalOperator relop = (RelationalOperator) node
2760: .getLeftOperand();
2761:
2762: int op = relop.getOperator();
2763:
2764: switch (op) {
2765: case RelationalOperator.EQUALS_RELOP:
2766: case RelationalOperator.IS_NULL_RELOP:
2767: sortList[QUALIFIER_ORDER_EQUALS].addElement(pred);
2768: break;
2769:
2770: case RelationalOperator.NOT_EQUALS_RELOP:
2771: case RelationalOperator.IS_NOT_NULL_RELOP:
2772: sortList[QUALIFIER_ORDER_NOT_EQUALS]
2773: .addElement(pred);
2774: break;
2775:
2776: default:
2777: sortList[QUALIFIER_ORDER_OTHER_RELOP]
2778: .addElement(pred);
2779: }
2780: } else {
2781: sortList[QUALIFIER_ORDER_OR_CLAUSE].addElement(pred);
2782: }
2783: }
2784:
2785: /* Rebuild the list */
2786: predIndex = 0;
2787:
2788: for (int index = 0; index < QUALIFIER_NUM_CATEGORIES; index++) {
2789: for (int items = 0; items < sortList[index].size(); items++) {
2790: setElementAt(sortList[index].elementAt(items),
2791: predIndex++);
2792: }
2793: }
2794: }
2795:
2796: /**
2797: * @see OptimizablePredicateList#generateStartKey
2798: *
2799: * @exception StandardException Thrown on error
2800: */
2801: public void generateStartKey(ExpressionClassBuilderInterface acbi,
2802: MethodBuilder mb, Optimizable optTable)
2803: throws StandardException {
2804: ExpressionClassBuilder acb = (ExpressionClassBuilder) acbi;
2805:
2806: /*
2807: ** To make the start-key allocating function we cycle through
2808: ** the Predicates and generate the function and initializer:
2809: **
2810: ** private Object exprN()
2811: ** { ExecIndexRow r = getExecutionFactory().getIndexableRow(# start keys);
2812: ** for (pred = each predicate in list)
2813: ** {
2814: ** if (pred.isStartKey())
2815: ** {
2816: ** pred.generateKey(acb);
2817: ** }
2818: ** }
2819: ** }
2820: **
2821: ** If there are no start predicates, we do not generate anything.
2822: */
2823:
2824: if (numberOfStartPredicates != 0) {
2825: /* This sets up the method and the static field */
2826: MethodBuilder exprFun = acb.newExprFun();
2827:
2828: /* Now we fill in the body of the method */
2829: LocalField rowField = generateIndexableRow(acb,
2830: numberOfStartPredicates);
2831:
2832: int colNum = 0;
2833: int size = size();
2834: for (int index = 0; index < size; index++) {
2835: Predicate pred = ((Predicate) elementAt(index));
2836:
2837: if (!pred.isStartKey())
2838: continue;
2839:
2840: generateSetColumn(acb, exprFun, colNum, pred, optTable,
2841: rowField, true);
2842:
2843: colNum++;
2844: }
2845:
2846: if (SanityManager.DEBUG) {
2847: SanityManager.ASSERT(colNum == numberOfStartPredicates,
2848: "Number of start predicates does not match");
2849: }
2850:
2851: finishKey(acb, mb, exprFun, rowField);
2852: return;
2853: }
2854:
2855: mb.pushNull(ClassName.GeneratedMethod);
2856: }
2857:
2858: /**
2859: * @see OptimizablePredicateList#sameStartStopPosition
2860: *
2861: * @exception StandardException Thrown on error
2862: */
2863: public boolean sameStartStopPosition() throws StandardException {
2864: /* We can only use the same row for both the
2865: * start and stop positions if the number of
2866: * start and stop predicates are the same.
2867: */
2868: if (numberOfStartPredicates != numberOfStopPredicates) {
2869: return false;
2870: }
2871:
2872: /* We can only use the same row for both the
2873: * start and stop positions when a predicate is
2874: * a start key iff it is a stop key.
2875: */
2876: int size = size();
2877: for (int index = 0; index < size; index++) {
2878: Predicate pred = ((Predicate) elementAt(index));
2879:
2880: if ((pred.isStartKey() && (!pred.isStopKey()))
2881: || (pred.isStopKey() && (!pred.isStartKey()))) {
2882: return false;
2883: }
2884: /* "in"'s dynamic start and stop key are not the same, beetle 3858
2885: */
2886: if (pred.getAndNode().getLeftOperand() instanceof InListOperatorNode)
2887: return false;
2888: }
2889:
2890: return true;
2891: }
2892:
2893: /**
2894: * Generate the indexable row for a start key or stop key.
2895: *
2896: * @param acb The ActivationClassBuilder for the class we're building
2897: * @param numberOfColumns The number of columns in the key
2898: *
2899: * @return The field that holds the indexable row
2900: */
2901: private LocalField generateIndexableRow(ExpressionClassBuilder acb,
2902: int numberOfColumns) {
2903: MethodBuilder mb = acb.getConstructor();
2904: /*
2905: ** Generate a call to get an indexable row
2906: ** with the given number of columns
2907: */
2908: acb.pushGetExecutionFactoryExpression(mb); // instance
2909: mb.push(numberOfColumns);
2910: mb.callMethod(VMOpcode.INVOKEINTERFACE,
2911: ClassName.ExecutionFactory, "getIndexableRow",
2912: ClassName.ExecIndexRow, 1);
2913:
2914: /*
2915: ** Assign the indexable row to a field, and put this assignment into
2916: ** the constructor for the activation class. This way, we only have
2917: ** to get the row once.
2918: */
2919: LocalField field = acb.newFieldDeclaration(Modifier.PRIVATE,
2920: ClassName.ExecIndexRow);
2921:
2922: mb.setField(field);
2923:
2924: return field;
2925: }
2926:
2927: /**
2928: * Generate the code to set the value from a predicate in an index column.
2929: *
2930: * @param acb The ActivationClassBuilder for the class we're building
2931: * @param exprFun The MethodBuilder for the method we're building
2932: * @param columnNumber The position number of the column we're setting
2933: * the value in (zero-based)
2934: * @param pred The Predicate with the value to put in the index column
2935: * @param optTable The Optimizable table the column is in
2936: * @param rowField The field that holds the indexable row
2937: * @param isStartKey Are we generating start or stop key? This information
2938: * is useful for "in"'s dynamic start/stop key, bug 3858
2939: *
2940: * @exception StandardException Thrown on error
2941: */
2942: private void generateSetColumn(ExpressionClassBuilder acb,
2943: MethodBuilder exprFun, int columnNumber, Predicate pred,
2944: Optimizable optTable, LocalField rowField,
2945: boolean isStartKey) throws StandardException {
2946: MethodBuilder mb;
2947:
2948: /* Code gets generated in constructor if comparison against
2949: * a constant, otherwise gets generated in the current
2950: * statement block.
2951: */
2952: boolean withKnownConstant = false;
2953: if (pred.compareWithKnownConstant(optTable, false)) {
2954: withKnownConstant = true;
2955: mb = acb.getConstructor();
2956: } else {
2957: mb = exprFun;
2958: }
2959:
2960: int[] baseColumns = optTable.getTrulyTheBestAccessPath()
2961: .getConglomerateDescriptor().getIndexDescriptor()
2962: .baseColumnPositions();
2963: boolean[] isAscending = optTable.getTrulyTheBestAccessPath()
2964: .getConglomerateDescriptor().getIndexDescriptor()
2965: .isAscending();
2966: boolean isIn = pred.getAndNode().getLeftOperand() instanceof InListOperatorNode;
2967:
2968: /*
2969: ** Generate statements of the form
2970: **
2971: ** r.setColumn(columnNumber, columnExpression);
2972: **
2973: ** and put the generated statement in the allocator function.
2974: */
2975: mb.getField(rowField);
2976: mb.push(columnNumber + 1);
2977:
2978: // second arg
2979: if (isIn) {
2980: InListOperatorNode inNode = (InListOperatorNode) pred
2981: .getAndNode().getLeftOperand();
2982: inNode.generateStartStopKey(isAscending[columnNumber],
2983: isStartKey, acb, mb);
2984: } else
2985: pred.generateExpressionOperand(optTable,
2986: baseColumns[columnNumber], acb, mb);
2987:
2988: mb.upCast(ClassName.DataValueDescriptor);
2989:
2990: mb.callMethod(VMOpcode.INVOKEINTERFACE, ClassName.Row,
2991: "setColumn", "void", 2);
2992:
2993: /* Also tell the row if this column uses ordered null semantics */
2994: if (!isIn) {
2995: RelationalOperator relop = pred.getRelop();
2996: boolean setOrderedNulls = relop.orderedNulls();
2997:
2998: /* beetle 4464, performance work. If index column is not nullable
2999: * (which is frequent), we should treat it as though nulls are
3000: * ordered (indeed because they don't exist) so that we do not have
3001: * to check null at scan time for each row, each column. This is
3002: * an overload to "is null" operator, so that we have less overhead,
3003: * provided that they don't interfere. It doesn't interfere if it
3004: * doesn't overload if key is null. If key is null, but operator
3005: * is not orderedNull type (is null), skipScan will use this flag
3006: * (false) to skip scan.
3007: */
3008: if ((!setOrderedNulls)
3009: && !relop.getColumnOperand(optTable)
3010: .getTypeServices().isNullable()) {
3011: if (withKnownConstant)
3012: setOrderedNulls = true;
3013: else {
3014: ValueNode keyExp = relop.getExpressionOperand(
3015: optTable.getTableNumber(),
3016: baseColumns[columnNumber],
3017: (FromTable) optTable);
3018:
3019: if (keyExp instanceof ColumnReference)
3020: setOrderedNulls = !((ColumnReference) keyExp)
3021: .getTypeServices().isNullable();
3022: }
3023: }
3024: if (setOrderedNulls) {
3025: mb.getField(rowField);
3026: mb.push(columnNumber);
3027: mb.callMethod(VMOpcode.INVOKEINTERFACE,
3028: ClassName.ExecIndexRow, "orderedNulls", "void",
3029: 1);
3030: }
3031: }
3032: }
3033:
3034: /**
3035: * Finish generating a start or stop key
3036: *
3037: * @param acb The ActivationClassBuilder for the class we're building
3038: * @param exprFun The MethodBuilder for the method we're building
3039: * @param rowField The name of the field that holds the indexable row
3040: */
3041: private void finishKey(ExpressionClassBuilder acb,
3042: MethodBuilder mb, MethodBuilder exprFun, LocalField rowField) {
3043: /* Generate return statement and add to exprFun */
3044: exprFun.getField(rowField);
3045: exprFun.methodReturn();
3046: /* We are done putting stuff in exprFun */
3047: exprFun.complete();
3048:
3049: /*
3050: ** What we use is the access of the static field,
3051: ** i.e. the pointer to the method.
3052: */
3053: acb.pushMethodReference(mb, exprFun);
3054: }
3055:
3056: /* Class implementation */
3057: boolean constantColumn(ColumnReference colRef) {
3058: boolean retval = false;
3059:
3060: /*
3061: ** Walk this list
3062: */
3063: int size = size();
3064: for (int index = 0; index < size; index++) {
3065: Predicate pred = (Predicate) elementAt(index);
3066: RelationalOperator relop = pred.getRelop();
3067:
3068: if (relop != null) {
3069: if (relop.getOperator() == RelationalOperator.EQUALS_RELOP) {
3070: ValueNode exprOp = relop.getOperand(colRef, pred
3071: .getReferencedSet().size(), true);
3072:
3073: if (exprOp != null) {
3074: if (exprOp.isConstantExpression()) {
3075: retval = true;
3076: break;
3077: }
3078: }
3079: } else if (relop.getOperator() == RelationalOperator.IS_NULL_RELOP) {
3080: ColumnReference columnOp = (ColumnReference) relop
3081: .getOperand(colRef, pred.getReferencedSet()
3082: .size(), false);
3083:
3084: if (columnOp != null) {
3085: retval = true;
3086: }
3087: }
3088: }
3089: }
3090:
3091: return retval;
3092: }
3093:
3094: /**
3095: * @see OptimizablePredicateList#selectivity
3096: */
3097: public double selectivity(Optimizable optTable)
3098: throws StandardException {
3099: TableDescriptor td = optTable.getTableDescriptor();
3100: ConglomerateDescriptor[] conglomerates = td
3101: .getConglomerateDescriptors();
3102:
3103: int numPredicates = size();
3104: int numConglomerates = conglomerates.length;
3105:
3106: if (numConglomerates == 1)
3107: return -1.0d; // one conglomerate; must be heap.
3108:
3109: if (numPredicates == 0)
3110: return -1.0d; // no predicates why bother?
3111:
3112: boolean nothingYet = true;
3113:
3114: /* before we start, lets select non-redundant prediates into a working
3115: * list; we'll work with the workingPredicates list from now on in this
3116: * routine.
3117: */
3118: PredicateList workingPredicates = new PredicateList();
3119:
3120: for (int i = 0; i < numPredicates; i++) {
3121: if (isRedundantPredicate(i))
3122: continue;
3123:
3124: /* to workingPredicates only add useful predicates... */
3125: workingPredicates.addOptPredicate((Predicate) elementAt(i));
3126: }
3127:
3128: int numWorkingPredicates = workingPredicates.size();
3129:
3130: /*--------------------------------------------------------------------
3131: * In the first phase, the routine initializes an array of
3132: * predicateWrapperLists-- one list for each conglomerate that has
3133: * statistics.
3134: *
3135: * predsForConglomerates is an array of pwList. For each conglomerate we
3136: * keep a pwList of predicates that have an equals predicate on a column
3137: * in the conglomerate.
3138: *
3139: * As an example consider a table T, with indices on
3140: * T(c1)-->conglom_one, T(c2,c1)-->conglom_two.
3141: *
3142: * if we have the following predicates:
3143: * T.c1=T1.x (p1) and T.c1=T2.y (p2) and T.c2=T1.z (p3), then we'll have the
3144: * after the first loop is done, we'll have the following setup.
3145: *
3146: * conglom_one: pwList [p1,p2]
3147: * conglom_two: pwList [p1,p2,p3].
3148: *
3149: * Note that although p1,p2 appear on both conglomerates, the
3150: * indexPosition of p1 and p2 on the first list is 0 (first index
3151: * position) while the index position of p1,p2 on the second list is 1
3152: * (second index position).
3153: *
3154: * PredicateWrapper and PredicateWrapperLists are inner classes used
3155: * only in this file.
3156: * -------------------------------------------------------------------- */
3157: PredicateWrapperList[] predsForConglomerates = new PredicateWrapperList[numConglomerates];
3158:
3159: for (int i = 0; i < numConglomerates; i++) {
3160: ConglomerateDescriptor cd = conglomerates[i];
3161:
3162: if (!cd.isIndex())
3163: continue;
3164:
3165: if (!td.statisticsExist(cd))
3166: continue;
3167:
3168: int[] baseColumnList = cd.getIndexDescriptor()
3169: .baseColumnPositions();
3170:
3171: for (int j = 0; j < numWorkingPredicates; j++) {
3172: Predicate pred = (Predicate) workingPredicates
3173: .elementAt(j);
3174:
3175: int ip = pred.hasEqualOnColumnList(baseColumnList,
3176: optTable);
3177:
3178: if (ip < 0)
3179: continue; // look at the next predicate.
3180:
3181: nothingYet = false;
3182: if (predsForConglomerates[i] == null) {
3183: predsForConglomerates[i] = new PredicateWrapperList(
3184: numWorkingPredicates);
3185: }
3186: PredicateWrapper newpw = new PredicateWrapper(ip, pred,
3187: j);
3188: predsForConglomerates[i].insert(newpw);
3189: } // for (j = 0;
3190: } // for (i = 0; i < ...)
3191:
3192: if (nothingYet) {
3193: return -1.0;
3194: }
3195:
3196: /*------------------------------------------------------------------
3197: * In the second phase we,
3198: * walk the predsForConglomerateList again-- if we find
3199: * a break in the indexPositions we remove the predicates
3200: * after the gap. To clarify, if we have equal predicates on the first
3201: * and the third index positions, we can throw away the predicate on
3202: * the 3rd index position-- it doesn't do us any good.
3203: *-------------------------------------------------------------------*/
3204:
3205: int maxOverlap = -1;
3206: for (int i = 0; i < numConglomerates; i++) {
3207: if (predsForConglomerates[i] == null)
3208: continue;
3209:
3210: predsForConglomerates[i].retainLeadingContiguous();
3211: } // for (i = 0; i < ...)
3212:
3213: calculateWeight(predsForConglomerates, numWorkingPredicates);
3214:
3215: /*-------------------------------------------------------------------
3216: * In the third phase we loop through predsForConglomerates choosing the
3217: * best fit (chooseLongestMatch) of predicates. we use the statistics
3218: * for the set of predicates returned by chooseLongestMatch and then
3219: * loop until we can't find any more statistics or we have exhausted all
3220: * the predicates for which we are trying to find statistics.
3221: *--------------------------------------------------------------------*/
3222: Vector statistics = new Vector(numWorkingPredicates);
3223:
3224: double selectivity = 1.0;
3225:
3226: Vector maxPreds = new Vector();
3227:
3228: while (true) {
3229: maxPreds.removeAllElements();
3230: int conglomIndex = chooseLongestMatch(
3231: predsForConglomerates, maxPreds,
3232: numWorkingPredicates);
3233:
3234: if (conglomIndex == -1)
3235: break; // no more stats available.
3236:
3237: selectivity *= td.selectivityForConglomerate(
3238: conglomerates[conglomIndex], maxPreds.size());
3239:
3240: for (int i = 0; i < maxPreds.size(); i++) {
3241: /* remove the predicates that we've calculated the selectivity
3242: * of, from workingPredicates.
3243: */
3244: Predicate p = (Predicate) maxPreds.elementAt(i);
3245: workingPredicates.removeOptPredicate(p);
3246: }
3247:
3248: if (workingPredicates.size() == 0)
3249: break;
3250: }
3251:
3252: if (workingPredicates.size() != 0) {
3253: selectivity *= workingPredicates
3254: .selectivityNoStatistics(optTable);
3255: }
3256:
3257: return selectivity;
3258: }
3259:
3260: /* assign a weight to each predicate-- the maximum weight that a predicate
3261: * can have is numUsefulPredicates. If a predicate corresponds to the first
3262: * index position then its weight is numUsefulPredicates. The weight of a
3263: * pwlist is the sum of the weights of individual predicates.
3264: */
3265: private void calculateWeight(PredicateWrapperList[] pwList,
3266: int numUsefulPredicates) {
3267: int[] s = new int[numUsefulPredicates];
3268:
3269: for (int i = 0; i < pwList.length; i++) {
3270: if (pwList[i] == null)
3271: continue;
3272:
3273: for (int j = 0; j < pwList[i].size(); j++) {
3274: s[pwList[i].elementAt(j).getPredicateID()] += (numUsefulPredicates - j);
3275: }
3276: }
3277:
3278: for (int i = 0; i < pwList.length; i++) {
3279: int w = 0;
3280:
3281: if (pwList[i] == null)
3282: continue;
3283:
3284: for (int j = 0; j < pwList[i].size(); j++) {
3285: w += s[pwList[i].elementAt(j).getPredicateID()];
3286: }
3287: pwList[i].setWeight(w);
3288: }
3289: }
3290:
3291: /**
3292: * choose the statistic which has the maximum match with the predicates.
3293: * value is returned in ret.
3294: */
3295: private int chooseLongestMatch(PredicateWrapperList[] predArray,
3296: Vector ret, int numWorkingPredicates) {
3297: int max = 0, maxWeight = 0;
3298: int position = -1;
3299: int weight;
3300:
3301: for (int i = 0; i < predArray.length; i++) {
3302: if (predArray[i] == null)
3303: continue;
3304:
3305: if (predArray[i].uniqueSize() == 0)
3306: continue;
3307:
3308: if (predArray[i].uniqueSize() > max) {
3309: max = predArray[i].uniqueSize();
3310: position = i;
3311: maxWeight = predArray[i].getWeight();
3312: }
3313:
3314: if (predArray[i].uniqueSize() == max) {
3315: /* if the matching length is the same, choose the one with the
3316: * lower weight.
3317: */
3318: if (predArray[i].getWeight() > maxWeight)
3319: continue;
3320:
3321: position = i;
3322: max = predArray[i].uniqueSize();
3323: maxWeight = predArray[i].getWeight();
3324: }
3325: }
3326:
3327: if (position == -1)
3328: return -1;
3329:
3330: /* the problem here is that I might have more than one predicate
3331: * matching on the same index position; i.e
3332: * col_1 = .. [p1] AND col_1 = .. [p2] AND col_2 = ..[p3];
3333: * In that case that maximum matching predicate is [p1] and [p3] but
3334: * [p2] shuld be considered again later.
3335: */
3336: PredicateWrapperList pwl = predArray[position];
3337: Vector uniquepreds = pwl.createLeadingUnique();
3338:
3339: /* uniqueprds is a vector of predicate (along with wrapper) that I'm
3340: going to use to get statistics from-- we now have to delete these
3341: predicates from all the predicateWrapperLists!
3342: */
3343: for (int i = 0; i < uniquepreds.size(); i++) {
3344: Predicate p = ((PredicateWrapper) uniquepreds.elementAt(i))
3345: .getPredicate();
3346: ret.addElement(p);
3347: for (int j = 0; j < predArray.length; j++) {
3348: if (predArray[j] == null)
3349: continue;
3350:
3351: pwl = predArray[j];
3352: /* note that we use object identity with the predicate and not
3353: * the predicatewrapper to remove it from the prediate wrapper
3354: * lists.
3355: */
3356: pwl.removeElement(p);
3357: }
3358: }
3359:
3360: /* if removing this predicate caused a gap, get rid of everything after
3361: * the gaps.
3362: */
3363: for (int i = 0; i < predArray.length; i++) {
3364: if (predArray[i] == null)
3365: continue;
3366: predArray[i].retainLeadingContiguous();
3367: }
3368:
3369: /* recalculate the weights of the pwlists... */
3370: calculateWeight(predArray, numWorkingPredicates);
3371: return position;
3372: }
3373:
3374: /**
3375: * Compute selectivity the old fashioned way.
3376: */
3377: private double selectivityNoStatistics(Optimizable optTable)
3378: throws StandardException {
3379: double selectivity = 1.0;
3380:
3381: for (int i = 0; i < size(); i++) {
3382: OptimizablePredicate pred = (OptimizablePredicate) elementAt(i);
3383: selectivity *= pred.selectivity((Optimizable) optTable);
3384: }
3385:
3386: return selectivity;
3387: }
3388:
3389: /**
3390: * Inner class which helps statistics routines do their work.
3391: * We need to keep track of the index position for each predicate for each
3392: * index while we're manipulating predicates and statistics. Each predicate
3393: * does have internal state for indexPosition, but this is a more permanent
3394: * sort of indexPosition, which keeps track of the position for the index
3395: * being considered in estimateCost. For us, each predicate can have
3396: * different index positions for different indices.
3397: */
3398: private class PredicateWrapper {
3399: int indexPosition;
3400: Predicate pred;
3401: int predicateID;
3402:
3403: PredicateWrapper(int ip, Predicate p, int predicateID) {
3404: this .indexPosition = ip;
3405: this .pred = p;
3406: this .predicateID = predicateID;
3407: }
3408:
3409: int getIndexPosition() {
3410: return indexPosition;
3411: }
3412:
3413: Predicate getPredicate() {
3414: return pred;
3415: }
3416:
3417: int getPredicateID() {
3418: return predicateID;
3419: }
3420:
3421: /* a predicatewrapper is BEFORE another predicate wrapper iff its index
3422: * position is less than the index position of the other.
3423: */
3424: boolean before(PredicateWrapper other) {
3425: return (indexPosition < other.getIndexPosition());
3426: }
3427:
3428: /* for our purposes two predicates at the same index
3429: position are contiguous. (have i spelled this right?)
3430: */
3431: boolean contiguous(PredicateWrapper other) {
3432: int otherIP = other.getIndexPosition();
3433: return ((indexPosition == otherIP)
3434: || (indexPosition - otherIP == 1) || (indexPosition
3435: - otherIP == -1));
3436: }
3437:
3438: }
3439:
3440: /** Another inner class which is basically a List of Predicate Wrappers.
3441: */
3442: private class PredicateWrapperList {
3443: Vector pwList;
3444: int numPreds;
3445: int numDuplicates;
3446: int weight;
3447:
3448: PredicateWrapperList(int maxValue) {
3449: pwList = new Vector(maxValue);
3450: }
3451:
3452: void removeElement(PredicateWrapper pw) {
3453: int index = pwList.indexOf(pw);
3454: if (index >= 0)
3455: removeElementAt(index);
3456: }
3457:
3458: void removeElement(Predicate p) {
3459: for (int i = numPreds - 1; i >= 0; i--) {
3460: Predicate predOnList = elementAt(i).getPredicate();
3461: if (predOnList == p) // object equality is what we need
3462: removeElementAt(i);
3463: }
3464: }
3465:
3466: void removeElementAt(int index) {
3467: if (index < numPreds - 1) {
3468: PredicateWrapper nextPW = elementAt(index + 1);
3469: if (nextPW.getIndexPosition() == index)
3470: numDuplicates--;
3471: }
3472: pwList.removeElementAt(index);
3473: numPreds--;
3474: }
3475:
3476: PredicateWrapper elementAt(int i) {
3477: return (PredicateWrapper) pwList.elementAt(i);
3478: }
3479:
3480: void insert(PredicateWrapper pw) {
3481: int i;
3482: for (i = 0; i < pwList.size(); i++) {
3483: if (pw.getIndexPosition() == elementAt(i)
3484: .getIndexPosition())
3485: numDuplicates++;
3486:
3487: if (pw.before(elementAt(i)))
3488: break;
3489: }
3490: numPreds++;
3491: pwList.insertElementAt(pw, i);
3492: }
3493:
3494: int size() {
3495: return numPreds;
3496: }
3497:
3498: /* number of unique references to a column; i.e two predicates which
3499: * refer to the same column in the table will give rise to duplicates.
3500: */
3501: int uniqueSize() {
3502: if (numPreds > 0)
3503: return numPreds - numDuplicates;
3504: return 0;
3505: }
3506:
3507: /* From a list of PredicateWrappers, retain only contiguous ones. Get
3508: * rid of everything after the first gap.
3509: */
3510: void retainLeadingContiguous() {
3511: if (pwList == null)
3512: return;
3513:
3514: if (pwList.size() == 0)
3515: return;
3516:
3517: if (elementAt(0).getIndexPosition() != 0) {
3518: pwList.removeAllElements();
3519: numPreds = numDuplicates = 0;
3520: return;
3521: }
3522:
3523: int j;
3524: for (j = 0; j < numPreds - 1; j++) {
3525: if (!(elementAt(j).contiguous(elementAt(j + 1))))
3526: break;
3527: }
3528:
3529: /* j points to the last good one; i.e
3530: * 0 1 1 2 4 4
3531: * j points to 2. remove 4 and everything after it.
3532: * Beetle 4321 - need to remove from back to front
3533: * to prevent array out of bounds problems
3534: *
3535: */
3536:
3537: for (int k = numPreds - 1; k > j; k--) {
3538: if (elementAt(k).getIndexPosition() == elementAt(k - 1)
3539: .getIndexPosition())
3540: numDuplicates--;
3541: pwList.removeElementAt(k);
3542: }
3543: numPreds = j + 1;
3544: }
3545:
3546: /* From a list of PW, extract the leading unique predicates; i.e if the
3547: * PW's with index positions are strung together like this:
3548: * 0 0 1 2 3 3
3549: * I need to extract out 0 1 2 3.
3550: * leaving 0 2 3 in there.
3551: */
3552: Vector createLeadingUnique() {
3553: Vector scratch = new Vector();
3554:
3555: if (numPreds == 0)
3556: return null;
3557:
3558: int lastIndexPosition = elementAt(0).getIndexPosition();
3559:
3560: if (lastIndexPosition != 0)
3561: return null;
3562:
3563: scratch.addElement(elementAt(0)); // always add 0.
3564:
3565: for (int i = 1; i < numPreds; i++) {
3566: if (elementAt(i).getIndexPosition() == lastIndexPosition)
3567: continue;
3568: lastIndexPosition = elementAt(i).getIndexPosition();
3569: scratch.addElement(elementAt(i));
3570: }
3571: return scratch;
3572: }
3573:
3574: void setWeight(int weight) {
3575: this .weight = weight;
3576: }
3577:
3578: int getWeight() {
3579: return weight;
3580: }
3581: }
3582: }
|