0001: /*
0002:
0003: Derby - Class org.apache.derby.impl.sql.compile.Predicate
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.impl.sql.compile.ExpressionClassBuilder;
0025: import org.apache.derby.impl.sql.compile.ActivationClassBuilder;
0026:
0027: import org.apache.derby.iapi.sql.compile.C_NodeTypes;
0028: import org.apache.derby.iapi.sql.compile.Visitable;
0029: import org.apache.derby.iapi.sql.compile.Visitor;
0030: import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
0031: import org.apache.derby.iapi.sql.compile.Optimizable;
0032:
0033: import org.apache.derby.iapi.sql.dictionary.DataDictionary;
0034:
0035: import org.apache.derby.iapi.store.access.ScanController;
0036:
0037: import org.apache.derby.iapi.error.StandardException;
0038:
0039: import org.apache.derby.iapi.services.compiler.MethodBuilder;
0040:
0041: import org.apache.derby.iapi.services.sanity.SanityManager;
0042:
0043: import org.apache.derby.iapi.types.DataValueDescriptor;
0044:
0045: import org.apache.derby.iapi.util.JBitSet;
0046:
0047: import java.util.ArrayList;
0048: import java.util.Hashtable;
0049:
0050: /**
0051: * A Predicate represents a top level predicate.
0052: *
0053: * @author Jerry Brenner
0054: */
0055:
0056: public final class Predicate extends QueryTreeNode implements
0057: OptimizablePredicate, Comparable {
0058: /* Top of the predicate */
0059: AndNode andNode;
0060: boolean pushable;
0061: /* Bit map of referenced tables */
0062: JBitSet referencedSet;
0063: /* Join clauses are placed into equivalence classes when applying transitive
0064: * closure for join clauses. This is useful for eliminating redundant predicates.
0065: */
0066: int equivalenceClass = -1;
0067: int indexPosition;
0068: protected boolean startKey;
0069: protected boolean stopKey;
0070: protected boolean isQualifier;
0071:
0072: /* Hashtable used for tracking the search clause types that have been
0073: * pushed through this predicate (if an equijoin) via transitive closure.
0074: */
0075: private Hashtable searchClauseHT;
0076:
0077: // Whether or not this predicate has been scoped; see the
0078: // getPredScopedForResultSet() method of this class for more.
0079: private boolean scoped;
0080:
0081: /**
0082: * Initializer.
0083: *
0084: * @param andNode The top of the predicate
0085: * @param referencedSet Bit map of referenced tables
0086: */
0087:
0088: public void init(Object andNode, Object referencedSet) {
0089: this .andNode = (AndNode) andNode;
0090: pushable = false;
0091: this .referencedSet = (JBitSet) referencedSet;
0092: scoped = false;
0093: }
0094:
0095: /*
0096: * Optimizable interface
0097: */
0098:
0099: /**
0100: * @see org.apache.derby.iapi.sql.compile.OptimizablePredicate#getReferencedMap
0101: */
0102: public JBitSet getReferencedMap() {
0103: return referencedSet;
0104: }
0105:
0106: /**
0107: * @see org.apache.derby.iapi.sql.compile.OptimizablePredicate#hasSubquery
0108: */
0109: public boolean hasSubquery() {
0110: /* RESOLVE - Currently, we record whether or not a predicate is pushable based
0111: * on whether or not it contains a subquery or method call, but we do not
0112: * record the underlying info.
0113: */
0114: return !pushable;
0115: }
0116:
0117: /**
0118: * @see org.apache.derby.iapi.sql.compile.OptimizablePredicate#hasMethodCall
0119: */
0120: public boolean hasMethodCall() {
0121: /* RESOLVE - Currently, we record whether or not a predicate is pushable based
0122: * on whether or not it contains a subquery or method call, but we do not
0123: * record the underlying info.
0124: */
0125: return !pushable;
0126: }
0127:
0128: /** @see OptimizablePredicate#markStartKey */
0129: public void markStartKey() {
0130: startKey = true;
0131: }
0132:
0133: /** @see OptimizablePredicate#isStartKey */
0134: public boolean isStartKey() {
0135: return startKey;
0136: }
0137:
0138: /** @see OptimizablePredicate#markStopKey */
0139: public void markStopKey() {
0140: stopKey = true;
0141: }
0142:
0143: /** @see OptimizablePredicate#isStopKey */
0144: public boolean isStopKey() {
0145: return stopKey;
0146: }
0147:
0148: /** @see OptimizablePredicate#markQualifier */
0149: public void markQualifier() {
0150: isQualifier = true;
0151: }
0152:
0153: /** @see OptimizablePredicate#isQualifier */
0154: public boolean isQualifier() {
0155: return isQualifier;
0156: }
0157:
0158: /** @see OptimizablePredicate#compareWithKnownConstant */
0159: public boolean compareWithKnownConstant(Optimizable optTable,
0160: boolean considerParameters) {
0161: boolean retval = false;
0162: RelationalOperator relop = getRelop();
0163:
0164: /* if this is for "in" operator node's dynamic start/stop key, relop is
0165: * null, and it's not comparing with constant, beetle 3858
0166: */
0167: if (relop == null)
0168: return false;
0169:
0170: if (relop
0171: .compareWithKnownConstant(optTable, considerParameters))
0172: retval = true;
0173:
0174: return retval;
0175: }
0176:
0177: public int hasEqualOnColumnList(int[] baseColumnPositions,
0178: Optimizable optTable) throws StandardException {
0179: RelationalOperator relop = getRelop();
0180:
0181: if (relop == null)
0182: return -1;
0183:
0184: if (!(relop.getOperator() == RelationalOperator.EQUALS_RELOP))
0185: return -1;
0186:
0187: for (int i = 0; i < baseColumnPositions.length; i++) {
0188: ColumnReference cr = relop.getColumnOperand(optTable,
0189: baseColumnPositions[i]);
0190:
0191: if (cr == null)
0192: continue;
0193:
0194: if (relop.selfComparison(cr))
0195: continue;
0196:
0197: // If I made it thus far in the loop, we've found
0198: // something.
0199: return i;
0200: }
0201:
0202: return -1;
0203: }
0204:
0205: /**
0206: * @see OptimizablePredicate#getCompareValue
0207: *
0208: * @exception StandardException Thrown on error
0209: */
0210: public DataValueDescriptor getCompareValue(Optimizable optTable)
0211: throws StandardException {
0212: if (SanityManager.DEBUG) {
0213: SanityManager
0214: .ASSERT(compareWithKnownConstant(optTable, true),
0215: "Cannot get the compare value if not comparing with a known constant.");
0216: }
0217:
0218: RelationalOperator relop = getRelop();
0219:
0220: return relop.getCompareValue(optTable);
0221: }
0222:
0223: /** @see OptimizablePredicate#equalsComparisonWithConstantExpression */
0224: public boolean equalsComparisonWithConstantExpression(
0225: Optimizable optTable) {
0226: RelationalOperator relop = getRelop();
0227: boolean retval = false;
0228:
0229: if (relop != null) {
0230: retval = relop
0231: .equalsComparisonWithConstantExpression(optTable);
0232: }
0233:
0234: return retval;
0235: }
0236:
0237: /** @see OptimizablePredicate#selectivity */
0238: public double selectivity(Optimizable optTable)
0239: throws StandardException {
0240: return andNode.getLeftOperand().selectivity(optTable);
0241: }
0242:
0243: /** @see OptimizablePredicate#getIndexPosition */
0244: public int getIndexPosition() {
0245: return indexPosition;
0246: }
0247:
0248: /* Comparable interface */
0249:
0250: public int compareTo(Object other) {
0251: Predicate otherPred = (Predicate) other;
0252:
0253: /* Not all operators are "equal". If the predicates are on the
0254: * same key column, then a "=" opertor takes precedence over all
0255: * other operators. This ensures that the "=" will be both the start
0256: * and stop predicates. Otherwise, we could end up with it being one
0257: * but not the other and get incorrect results.
0258: *
0259: * Also, we want "<>" to come after all the other operators.
0260: * Other parts of the optimizer use the first predicate on an index
0261: * column to determine the cost of using the index, so we want the
0262: * "<>" to come last because it's not useful for limiting the scan.
0263: *
0264: * In other words, P1 is before() P2 if:
0265: * o The P1.indexPosition < P2.indexPosition
0266: * or o P1.indexPosition == P2.indexPosition and
0267: * P1's operator is ("=" or IS NULL) and
0268: * P2's operator is not ("=" or IS NULL)
0269: * or o P1.indexPosition == P2.indexPosition and
0270: * P1's operator is not ("<>" or IS NOT NULL) and
0271: * P2's operator is ("<>" or IS NOT NULL)
0272: *
0273: * (We have to impose an arbitrary, but reproducible ordering
0274: * on the the "=" predicates on the same column, otherwise an
0275: * ASSERTion, that after the predicates are order, Pn+1 is not
0276: * before() Pn, will be violated.
0277: */
0278:
0279: int otherIndexPosition = otherPred.getIndexPosition();
0280:
0281: if (indexPosition < otherIndexPosition)
0282: return -1;
0283:
0284: if (indexPosition > otherIndexPosition)
0285: return 1;
0286:
0287: // initialize these flags as if they are for "in" operator, then
0288: // change them if they are not
0289: //
0290: boolean this IsEquals = false, otherIsEquals = false;
0291: boolean this IsNotEquals = true, otherIsNotEquals = true;
0292:
0293: if (getRelop() != null) // this is not "in"
0294: {
0295: int this Operator = ((RelationalOperator) andNode
0296: .getLeftOperand()).getOperator();
0297: this IsEquals = (this Operator == RelationalOperator.EQUALS_RELOP || this Operator == RelationalOperator.IS_NULL_RELOP);
0298: this IsNotEquals = (this Operator == RelationalOperator.NOT_EQUALS_RELOP || this Operator == RelationalOperator.IS_NOT_NULL_RELOP);
0299: }
0300: if (otherPred.getRelop() != null) // other is not "in"
0301: {
0302: int otherOperator = ((RelationalOperator) (otherPred
0303: .getAndNode().getLeftOperand())).getOperator();
0304: otherIsEquals = (otherOperator == RelationalOperator.EQUALS_RELOP || otherOperator == RelationalOperator.IS_NULL_RELOP);
0305: otherIsNotEquals = (otherOperator == RelationalOperator.NOT_EQUALS_RELOP || otherOperator == RelationalOperator.IS_NOT_NULL_RELOP);
0306: }
0307:
0308: boolean this IsBefore = (this IsEquals && !otherIsEquals)
0309: || (!this IsNotEquals && otherIsNotEquals);
0310: if (this IsBefore)
0311: return -1;
0312:
0313: boolean otherIsBefore = (otherIsEquals && !this IsEquals)
0314: || (!otherIsNotEquals && this IsNotEquals);
0315: if (otherIsBefore)
0316: return 1;
0317: return 0;
0318: }
0319:
0320: /**
0321: * Return the andNode.
0322: *
0323: * @return AndNode The andNode.
0324: */
0325: public AndNode getAndNode() {
0326: return andNode;
0327: }
0328:
0329: /**
0330: * Set the andNode.
0331: *
0332: * @param andNode The new andNode.
0333: */
0334: public void setAndNode(AndNode andNode) {
0335: this .andNode = andNode;
0336: }
0337:
0338: /**
0339: * Return the pushable.
0340: *
0341: * @return boolean Whether or not the predicate is pushable.
0342: */
0343: public boolean getPushable() {
0344: return pushable;
0345: }
0346:
0347: /**
0348: * Set whether or not this predicate is pushable. This method
0349: * is intended for use when creating a copy of the predicate, ex
0350: * for predicate pushdown. We choose not to add this assignment
0351: * to copyFields() because the comments for that method say that
0352: * it should copy all fields _except_ the two specified at init
0353: * time; "pushable" is one of the two specified at init time.
0354: *
0355: * @param pushable Whether or not the predicate is pushable.
0356: */
0357: public void setPushable(boolean pushable) {
0358: this .pushable = pushable;
0359: }
0360:
0361: /**
0362: * Return the referencedSet.
0363: *
0364: * @return JBitSet The referencedSet.
0365: */
0366: public JBitSet getReferencedSet() {
0367: return referencedSet;
0368: }
0369:
0370: /**
0371: * Set the equivalence class, if any, for this predicate.
0372: *
0373: * @param equivalenceClass The equivalence class for this predicate.
0374: */
0375: void setEquivalenceClass(int equivalenceClass) {
0376: this .equivalenceClass = equivalenceClass;
0377: }
0378:
0379: /**
0380: * Get the equivalenceClass for this predicate.
0381: *
0382: * @return The equivalenceClass for this predicate.
0383: */
0384: int getEquivalenceClass() {
0385: return equivalenceClass;
0386: }
0387:
0388: /**
0389: * Categorize this predicate. Initially, this means
0390: * building a bit map of the referenced tables for each predicate.
0391: *
0392: * @exception StandardException Thrown on error
0393: */
0394: public void categorize() throws StandardException {
0395: pushable = andNode.categorize(referencedSet, false);
0396: }
0397:
0398: /**
0399: * Get the RelationalOperator on the left side of the AND node, if
0400: * there is one. If the left side is not a RelationalOperator, return
0401: * null.
0402: *
0403: * @return The RelationalOperator on the left side of the AND node,
0404: * if any.
0405: */
0406: public RelationalOperator getRelop() {
0407:
0408: if (andNode.getLeftOperand() instanceof RelationalOperator) {
0409: return (RelationalOperator) andNode.getLeftOperand();
0410: } else {
0411: return null;
0412: }
0413: }
0414:
0415: public final boolean isOrList() {
0416: return (andNode.getLeftOperand() instanceof OrNode);
0417: }
0418:
0419: /**
0420: * Is this predicate a possible Qualifier for store?
0421: * <p>
0422: * Current 2 types of predicates can be pushed to store:
0423: * 1) RelationalOperator -
0424: * represented with by left operand as instance of RelationalOperator.
0425: * 2) A single And'd term of a list of OR terms
0426: * represented by left operand as instance of OrNode.
0427: *
0428: * More checking specific operator's terms to see if they are finally
0429: * pushable to store. In the final push at execution each term of the AND
0430: * or OR must be a Relational operator with a column reference on one side
0431: * and a constant on the other.
0432: *
0433: *
0434: * @return true if term is wither a AND of a RelationalOperator, or an
0435: * OR of one or more Relational Operators.
0436: *
0437: *
0438: * @exception StandardException Standard exception policy.
0439: **/
0440: public final boolean isStoreQualifier() {
0441: if ((andNode.getLeftOperand() instanceof RelationalOperator)
0442: || (andNode.getLeftOperand() instanceof OrNode)) {
0443: return (true);
0444: } else {
0445: return (false);
0446: }
0447: }
0448:
0449: /**
0450: * Is this predicate an pushable OR list?
0451: * <p>
0452: * Does the predicate represent a AND'd list of OR term's, all of which
0453: * are pushable. To be pushable each of OR terms must be a legal
0454: * qualifier, which is a column reference on one side of a Relational
0455: * operator and a constant on the other.
0456: *
0457: * @return true if the predicate is a pushable set of OR clauses.
0458: *
0459: *
0460: * @exception StandardException Standard exception policy.
0461: **/
0462: public final boolean isPushableOrClause(Optimizable optTable)
0463: throws StandardException {
0464: boolean ret_val = true;
0465:
0466: if (andNode.getLeftOperand() instanceof OrNode) {
0467: QueryTreeNode node = andNode.getLeftOperand();
0468:
0469: while (node instanceof OrNode) {
0470: OrNode or_node = (OrNode) node;
0471:
0472: if (or_node.getLeftOperand() instanceof RelationalOperator) {
0473: // if any term of the OR clause is not a qualifier, then
0474: // reject the entire OR clause.
0475: if (!((RelationalOperator) or_node.getLeftOperand())
0476: .isQualifier(optTable, true)) {
0477: // one of the terms is not a pushable Qualifier.
0478: return (false);
0479: }
0480:
0481: node = or_node.getRightOperand();
0482: } else {
0483: // one of the terms is not a RelationalOperator
0484:
0485: return (false);
0486: }
0487: }
0488:
0489: return (true);
0490: } else {
0491: // Not an OR list
0492: return (false);
0493: }
0494: }
0495:
0496: /**
0497: * Return whether or not this predicate has been used
0498: * to add a new search clause of the specified type via transitive closure.
0499: * NOTE: This can only be true if this is an equijoin
0500: * between 2 column references.
0501: *
0502: * @param ro The search clause that we are currently considering
0503: * as the source for transitive closure
0504: *
0505: * @return Whether or not this predicate has been used
0506: * to add a new search clause of the specified type via transitive
0507: * closure.
0508: */
0509: boolean transitiveSearchClauseAdded(RelationalOperator ro) {
0510: if (searchClauseHT == null
0511: || searchClauseHT.get(new Integer(ro.getOperator())) == null) {
0512: return false;
0513: } else {
0514: return true;
0515: }
0516: }
0517:
0518: /**
0519: * Mark this predicate as having been used to add a new predicate
0520: * of the specified type via transitive closure on search clauses.
0521: *
0522: * @param ro The search clause that we are currently considering
0523: * as the source for transitive closure
0524: *
0525: */
0526: void setTransitiveSearchClauseAdded(RelationalOperator ro) {
0527: if (searchClauseHT == null) {
0528: searchClauseHT = new Hashtable();
0529: }
0530: /* I have to remember that this ro has been added to this predicate as a
0531: * transitive search clause.
0532: */
0533: Integer i = new Integer(ro.getOperator());
0534: searchClauseHT.put(i, i);
0535: }
0536:
0537: /**
0538: * Get the start operator for this predicate for a scan.
0539: *
0540: * @param optTable The optimizable table, so we can tell which side of
0541: * the operator the search column is on.
0542: *
0543: * @return The start operator for a start key on this column.
0544: */
0545: int getStartOperator(Optimizable optTable) {
0546: if (SanityManager.DEBUG) {
0547: SanityManager
0548: .ASSERT(startKey,
0549: "Getting a start operator from a Predicate that's not a start key.");
0550: }
0551:
0552: /* if it's for "in" operator's dynamic start key, operator is GE,
0553: * beetle 3858
0554: */
0555: if (andNode.getLeftOperand() instanceof InListOperatorNode)
0556: return ScanController.GE;
0557:
0558: return getRelop().getStartOperator(optTable);
0559: }
0560:
0561: int getStopOperator(Optimizable optTable) {
0562: if (SanityManager.DEBUG) {
0563: SanityManager
0564: .ASSERT(stopKey,
0565: "Getting a stop operator from a Predicate that's not a stop key.");
0566: }
0567:
0568: /* if it's for "in" operator's dynamic stop key, operator is GT,
0569: * beetle 3858
0570: */
0571: if (andNode.getLeftOperand() instanceof InListOperatorNode)
0572: return ScanController.GT;
0573:
0574: return getRelop().getStopOperator(optTable);
0575: }
0576:
0577: /**
0578: * Set the position of the index column that this predicate restricts
0579: *
0580: * @param indexPosition The position of the index column that this
0581: * predicate restricts.
0582: */
0583: void setIndexPosition(int indexPosition) {
0584: this .indexPosition = indexPosition;
0585: }
0586:
0587: /**
0588: * Clear the start/stop position and qualifier flags
0589: */
0590: void clearScanFlags() {
0591: startKey = false;
0592: stopKey = false;
0593: isQualifier = false;
0594: }
0595:
0596: /**
0597: * Clear the qualifier flag.
0598: */
0599: void clearQualifierFlag() {
0600: isQualifier = false;
0601: }
0602:
0603: void generateExpressionOperand(Optimizable optTable,
0604: int columnPosition, ExpressionClassBuilder acb,
0605: MethodBuilder mb) throws StandardException {
0606: getRelop().generateExpressionOperand(optTable, columnPosition,
0607: acb, mb);
0608: }
0609:
0610: void generateAbsoluteColumnId(MethodBuilder mb, Optimizable optTable) {
0611: getRelop().generateAbsoluteColumnId(mb, optTable);
0612: }
0613:
0614: void generateRelativeColumnId(MethodBuilder mb, Optimizable optTable) {
0615: getRelop().generateRelativeColumnId(mb, optTable);
0616: }
0617:
0618: void generateOperator(MethodBuilder mb, Optimizable optTable) {
0619: getRelop().generateOperator(mb, optTable);
0620: }
0621:
0622: void generateQualMethod(ExpressionClassBuilder acb,
0623: MethodBuilder mb, Optimizable optTable)
0624: throws StandardException {
0625: getRelop().generateQualMethod(acb, mb, optTable);
0626: }
0627:
0628: void generateOrderedNulls(MethodBuilder mb) {
0629: getRelop().generateOrderedNulls(mb);
0630: }
0631:
0632: void generateNegate(MethodBuilder mb, Optimizable optTable) {
0633: getRelop().generateNegate(mb, optTable);
0634: }
0635:
0636: void generateOrderableVariantType(MethodBuilder mb,
0637: Optimizable optTable) throws StandardException {
0638: int variantType = getRelop().getOrderableVariantType(optTable);
0639: mb.push(variantType);
0640:
0641: }
0642:
0643: /**
0644: * Convert this object to a String. See comments in QueryTreeNode.java
0645: * for how this should be done for tree printing.
0646: *
0647: * @return This object as a String
0648: */
0649:
0650: public String toString() {
0651: if (SanityManager.DEBUG) {
0652: return binaryRelOpColRefsToString() + "\nreferencedSet: "
0653: + referencedSet + "\n" + "pushable: " + pushable
0654: + "\n" + super .toString();
0655: } else {
0656: return "";
0657: }
0658: }
0659:
0660: /**
0661: * Get a string version of the column references for this predicate
0662: * IF it's a binary relational operator. We only print out the
0663: * names of the operands if they are column references; otherwise
0664: * we just print a dummy value. This is for debugging purposes
0665: * only--it's a convenient way to see what columns the predicate
0666: * is referencing, especially when tracing through code and printing
0667: * assert failure.
0668: */
0669: public String binaryRelOpColRefsToString() {
0670: // We only consider binary relational operators here.
0671: if (!(getAndNode().getLeftOperand() instanceof BinaryRelationalOperatorNode)) {
0672: return "";
0673: }
0674:
0675: final String DUMMY_VAL = "<expr>";
0676: java.lang.StringBuffer sBuf = new java.lang.StringBuffer();
0677: BinaryRelationalOperatorNode opNode = (BinaryRelationalOperatorNode) getAndNode()
0678: .getLeftOperand();
0679:
0680: // Get left operand's name.
0681: if (opNode.getLeftOperand() instanceof ColumnReference) {
0682: sBuf.append(((ColumnReference) opNode.getLeftOperand())
0683: .getTableName()
0684: + "."
0685: + ((ColumnReference) opNode.getLeftOperand())
0686: .getColumnName());
0687: } else
0688: sBuf.append(DUMMY_VAL);
0689:
0690: // Get the operator type.
0691: sBuf.append(" " + opNode.operator + " ");
0692:
0693: // Get right operand's name.
0694: if (opNode.getRightOperand() instanceof ColumnReference) {
0695: sBuf.append(((ColumnReference) opNode.getRightOperand())
0696: .getTableName()
0697: + "."
0698: + ((ColumnReference) opNode.getRightOperand())
0699: .getColumnName());
0700: } else
0701: sBuf.append(DUMMY_VAL);
0702:
0703: return sBuf.toString();
0704: }
0705:
0706: /**
0707: * Prints the sub-nodes of this object. See QueryTreeNode.java for
0708: * how tree printing is supposed to work.
0709: *
0710: * @param depth The depth of this node in the tree
0711: */
0712:
0713: public void printSubNodes(int depth) {
0714: if (SanityManager.DEBUG) {
0715: printLabel(depth, "andNode: ");
0716: andNode.treePrint(depth + 1);
0717: super .printSubNodes(depth);
0718: }
0719: }
0720:
0721: /**
0722: * Accept a visitor, and call v.visit()
0723: * on child nodes as necessary.
0724: *
0725: * @param v the visitor
0726: *
0727: * @exception StandardException on error
0728: */
0729: public Visitable accept(Visitor v) throws StandardException {
0730: if (v.skipChildren(this )) {
0731: return v.visit(this );
0732: }
0733:
0734: Visitable returnNode = super .accept(v);
0735:
0736: if (andNode != null && !v.stopTraversal()) {
0737: andNode = (AndNode) andNode.accept(v);
0738: }
0739:
0740: return returnNode;
0741: }
0742:
0743: /**
0744: * Copy all fields of this Predicate (except the two that
0745: * are set from 'init').
0746: *
0747: */
0748:
0749: public void copyFields(Predicate otherPred) {
0750:
0751: this .equivalenceClass = otherPred.getEquivalenceClass();
0752: this .indexPosition = otherPred.getIndexPosition();
0753: this .startKey = otherPred.isStartKey();
0754: this .stopKey = otherPred.isStopKey();
0755: this .isQualifier = otherPred.isQualifier();
0756: this .searchClauseHT = otherPred.getSearchClauseHT();
0757:
0758: }
0759:
0760: /**
0761: * Get the search clause Hash Table.
0762: */
0763:
0764: public Hashtable getSearchClauseHT() {
0765: return searchClauseHT;
0766: }
0767:
0768: /**
0769: * Determine whether or not this predicate is eligible for
0770: * push-down into subqueries. Right now the only predicates
0771: * we consider to be eligible are those which 1) are Binary
0772: * Relational operator nodes and 2) have a column reference
0773: * on BOTH sides, each of which has a reference to a base
0774: * table somewhere beneath it.
0775: *
0776: * @return Whether or not this predicate is eligible to be
0777: * pushed into subqueries.
0778: */
0779: protected boolean pushableToSubqueries() throws StandardException {
0780: if (!isJoinPredicate())
0781: return false;
0782:
0783: // Make sure both column references ultimately point to base
0784: // tables. If, for example, either column reference points to a
0785: // a literal or an aggregate, then we do not push the predicate.
0786: // This is because pushing involves remapping the references--
0787: // but if the reference doesn't have a base table beneath it,
0788: // the notion of "remapping" it doesn't (seem to) apply. RESOLVE:
0789: // it might be okay to make the "remap" operation a no-op for
0790: // such column references, but it's not clear whether that's
0791: // always a safe option; further investigation required.
0792:
0793: BinaryRelationalOperatorNode opNode = (BinaryRelationalOperatorNode) getAndNode()
0794: .getLeftOperand();
0795:
0796: JBitSet tNums = new JBitSet(getReferencedSet().size());
0797: BaseTableNumbersVisitor btnVis = new BaseTableNumbersVisitor(
0798: tNums);
0799: opNode.getLeftOperand().accept(btnVis);
0800: if (tNums.getFirstSetBit() == -1)
0801: return false;
0802:
0803: tNums.clearAll();
0804: opNode.getRightOperand().accept(btnVis);
0805: if (tNums.getFirstSetBit() == -1)
0806: return false;
0807:
0808: return true;
0809: }
0810:
0811: /**
0812: * Is this predicate a join predicate? In order to be so,
0813: * it must be a binary relational operator node that has
0814: * a column reference on both sides.
0815: *
0816: * @return Whether or not this is a join predicate.
0817: */
0818: protected boolean isJoinPredicate() {
0819: // If the predicate isn't a binary relational operator,
0820: // then it's not a join predicate.
0821: if (!(getAndNode().getLeftOperand() instanceof BinaryRelationalOperatorNode)) {
0822: return false;
0823: }
0824:
0825: BinaryRelationalOperatorNode opNode = (BinaryRelationalOperatorNode) getAndNode()
0826: .getLeftOperand();
0827:
0828: // If both sides are column references AND they point to different
0829: // tables, then this is a join pred.
0830: return ((opNode.getLeftOperand() instanceof ColumnReference)
0831: && (opNode.getRightOperand() instanceof ColumnReference) && (((ColumnReference) opNode
0832: .getLeftOperand()).getTableNumber() != ((ColumnReference) opNode
0833: .getRightOperand()).getTableNumber()));
0834: }
0835:
0836: /**
0837: * If this predicate's operator is a BinaryRelationalOperatorNode,
0838: * then look at the operands and return a new, equivalent predicate
0839: * that is "scoped" to the received ResultSetNode. By "scoped" we
0840: * mean that the operands, which shold be column references, have been
0841: * mapped to the appropriate result columns in the received RSN.
0842: * This is useful for pushing predicates from outer queries down
0843: * into inner queries, in which case the column references need
0844: * to be remapped.
0845: *
0846: * For example, let V1 represent
0847: *
0848: * select i,j from t1 UNION select i,j from t2
0849: *
0850: * and V2 represent
0851: *
0852: * select a,b from t3 UNION select a,b from t4
0853: *
0854: * Then assume we have the following query:
0855: *
0856: * select * from V1, V2 where V1.j = V2.b
0857: *
0858: * Let's further assume that this Predicate object represents the
0859: * "V1.j = V2.b" operator and that the childRSN we received
0860: * as a parameter represents one of the subqueries to which we
0861: * want to push the predicate; let's say it's:
0862: *
0863: * select i,j from t1
0864: *
0865: * Then this method will return a new predicate whose binary
0866: * operator represents the expression "T1.j = V2.b" (that is, V1.j
0867: * will be mapped to the corresponding column in T1). For more on
0868: * how that mapping is made, see the "getScopedOperand()" method
0869: * in BinaryRelationalOperatorNode.java.
0870: *
0871: * ASSUMPTION: We should only get to this method if we know that
0872: * at least one operand in this predicate can and should be mapped
0873: * to the received childRSN. For an example of where that check is
0874: * made, see the pushOptPredicate() method in SetOperatorNode.java.
0875: *
0876: * @param parentRSNsTables Set of all table numbers referenced by
0877: * the ResultSetNode that is _parent_ to the received childRSN.
0878: * We need this to make sure we don't scope the operands to a
0879: * ResultSetNode to which they don't apply.
0880: * @param childRSN The result set node for which we want to create
0881: * a scoped predicate.
0882: * @param whichRC If not -1 then this tells us which ResultColumn
0883: * in the received childRSN we need to use for the scoped predicate;
0884: * if -1 then the column position of the scoped column reference
0885: * will be stored in this array and passed back to the caller.
0886: * @return A new predicate whose operands have been scoped to the
0887: * received childRSN.
0888: */
0889: protected Predicate getPredScopedForResultSet(
0890: JBitSet parentRSNsTables, ResultSetNode childRSN,
0891: int[] whichRC) throws StandardException {
0892: // We only deal with binary relational operators here.
0893: if (!(getAndNode().getLeftOperand() instanceof BinaryRelationalOperatorNode)) {
0894: return this ;
0895: }
0896:
0897: // The predicate must have an AndNode in CNF, so we
0898: // need to create an AndNode representing:
0899: // <scoped_bin_rel_op> AND TRUE
0900: // First create the boolean constant for TRUE.
0901: ValueNode trueNode = (ValueNode) getNodeFactory().getNode(
0902: C_NodeTypes.BOOLEAN_CONSTANT_NODE, Boolean.TRUE,
0903: getContextManager());
0904:
0905: BinaryRelationalOperatorNode opNode = (BinaryRelationalOperatorNode) getAndNode()
0906: .getLeftOperand();
0907:
0908: // Create a new op node with left and right operands that point
0909: // to the received result set's columns as appropriate.
0910: BinaryRelationalOperatorNode newOpNode = (BinaryRelationalOperatorNode) getNodeFactory()
0911: .getNode(
0912: opNode.getNodeType(),
0913: opNode.getScopedOperand(
0914: BinaryRelationalOperatorNode.LEFT,
0915: parentRSNsTables, childRSN, whichRC),
0916: opNode.getScopedOperand(
0917: BinaryRelationalOperatorNode.RIGHT,
0918: parentRSNsTables, childRSN, whichRC),
0919: getContextManager());
0920:
0921: // Bind the new op node.
0922: newOpNode.bindComparisonOperator();
0923:
0924: // Create and bind a new AND node in CNF form,
0925: // i.e. "<newOpNode> AND TRUE".
0926: AndNode newAnd = (AndNode) getNodeFactory().getNode(
0927: C_NodeTypes.AND_NODE, newOpNode, trueNode,
0928: getContextManager());
0929: newAnd.postBindFixup();
0930:
0931: // Categorize the new AND node; among other things, this
0932: // call sets up the new operators's referenced table map,
0933: // which is important for correct pushing of the new
0934: // predicate.
0935: JBitSet tableMap = new JBitSet(childRSN.getReferencedTableMap()
0936: .size());
0937: newAnd.categorize(tableMap, false);
0938:
0939: // Now put the pieces together to get a new predicate.
0940: Predicate newPred = (Predicate) getNodeFactory().getNode(
0941: C_NodeTypes.PREDICATE, newAnd, tableMap,
0942: getContextManager());
0943:
0944: // Copy all of this predicates other fields into the new predicate.
0945: newPred.clearScanFlags();
0946: newPred.copyFields(this );
0947: newPred.setPushable(getPushable());
0948:
0949: // Take note of the fact that the new predicate is scoped for
0950: // the sake of pushing; we need this information during optimization
0951: // to figure out what we should and should not "pull" back up.
0952: newPred.markAsScopedForPush();
0953: return newPred;
0954: }
0955:
0956: /**
0957: * Indicate that this predicate is a scoped copy of some other
0958: * predicate (i.e. it was created as the result of a call to
0959: * getPredScopedForResultSet() on some other predicate).
0960: */
0961: protected void markAsScopedForPush() {
0962: this .scoped = true;
0963: }
0964:
0965: /**
0966: * Return whether or not this predicate is a scoped copy of
0967: * another predicate.
0968: */
0969: protected boolean isScopedForPush() {
0970: return scoped;
0971: }
0972:
0973: /**
0974: * When remapping a "normal" (i.e. non-scoped) predicate both
0975: * of the predicate's operands are remapped and that's it.
0976: * But when remapping a scoped predicate, things are slightly
0977: * different. This method handles remapping of scoped predicates.
0978: *
0979: * We know that, for a scoped predicate, exactly one operand has
0980: * been scoped for a specific target result set; the other operand
0981: * is pointing to some other instance of FromTable with which the
0982: * target result set is to be joined (see getScopedOperand() in
0983: * BinaryRelationalOperatorNode.java). For every level of the
0984: * query through which the scoped predicate is pushed, we have
0985: * to perform a remap operation of the scoped operand. We do
0986: * *not*, however, remap the non-scoped operand. The reason
0987: * is that the non-scoped operand is already pointing to the
0988: * result set against which it must be evaluated. As the scoped
0989: * predicate is pushed down the query tree, the non-scoped
0990: * operand should not change where it's pointing and thus should
0991: * not be remapped. For example, assume we have a query whose
0992: * tree has the following form:
0993: *
0994: * SELECT[0]
0995: * / \
0996: * PRN PRN
0997: * | |
0998: * SELECT[4] UNION
0999: * | / \
1000: * PRN SELECT[1] SELECT[2]
1001: * | | |
1002: * <FBT:T1> PRN PRN
1003: * | |
1004: * SELECT[3] <FromBaseTable:T2>
1005: * |
1006: * PRN
1007: * |
1008: * <FromBaseTable:T3>
1009: *
1010: * Assume also that we have some predicate "SELECT[4].i = <UNION>.j".
1011: * If the optimizer decides to push the predicate to the UNION
1012: * node, it (the predicate) will be scoped to the UNION's children,
1013: * yielding something like "SELECT[4].i = SELECT[1].j" for the
1014: * left child and "SELECT[4].i = SELECT[2].j" for the right child.
1015: * These scoped predicates will then be pushed to the PRNs above
1016: * SELECT[3] and T2, respectively. As part of that pushing
1017: * process a call to PRN.pushOptPredicate() will occur, which
1018: * brings us to this method. So let's assume we're here for
1019: * the scoped predicate "SELECT[4].i = SELECT[1].j". Then we want
1020: * to remap the scoped operand, "SELECT[1].j", so that it will
1021: * point to the correct column in "SELECT[3]". We do NOT, however,
1022: * want to remap the non-scoped operand "SELECT[4].i" because that
1023: * operand is already pointing to the correct result set--namely,
1024: * to a column in SELECT[4]. That non-scoped operand should not
1025: * change regardless of how far down the UNION subtree the scoped
1026: * predicate is pushed.
1027: *
1028: * If we did try to remap the non-scoped operand, it would end up
1029: * pointing to result sets too low in the tree, which could lead to
1030: * execution-time errors. So when we remap a scoped predicate, we
1031: * have to make sure we only remap the scoped operand. That's what
1032: * this method does.
1033: *
1034: * @return True if this predicate is a scoped predicate, in which
1035: * case we performed a one-sided remap. False if the predicate is
1036: * not scoped; the caller can then make the calls to perform a
1037: * "normal" remap on this predicate.
1038: */
1039: protected boolean remapScopedPred() {
1040: if (!scoped)
1041: return false;
1042:
1043: /* Note: right now the only predicates we scope are those
1044: * which are join predicates and all scoped predicates will
1045: * have the same relational operator as the predicates from
1046: * which they were scoped. Thus if we get here, we know
1047: * that andNode's leftOperand must be an instance of
1048: * BinaryRelationalOperatorNode (and therefore the following
1049: * cast is safe).
1050: */
1051: BinaryRelationalOperatorNode binRelOp = (BinaryRelationalOperatorNode) andNode
1052: .getLeftOperand();
1053:
1054: ValueNode operand = null;
1055:
1056: if (SanityManager.DEBUG) {
1057: /* If this predicate is scoped then one (and only one) of
1058: * its operands should be scoped. Note that it's possible
1059: * for an operand to be scoped to a non-ColumnReference
1060: * value; if either operand is not a ColumnReference, then
1061: * that operand must be the scoped operand.
1062: */
1063: operand = binRelOp.getLeftOperand();
1064: boolean leftIsScoped = !(operand instanceof ColumnReference)
1065: || ((ColumnReference) operand).isScoped();
1066:
1067: operand = binRelOp.getRightOperand();
1068: boolean rightIsScoped = !(operand instanceof ColumnReference)
1069: || ((ColumnReference) operand).isScoped();
1070:
1071: SanityManager.ASSERT(leftIsScoped ^ rightIsScoped,
1072: "All scoped predicates should have exactly one scoped "
1073: + "operand, but '"
1074: + binaryRelOpColRefsToString() + "' has "
1075: + (leftIsScoped ? "TWO" : "NONE") + ".");
1076: }
1077:
1078: // Find the scoped operand and remap it.
1079: operand = binRelOp.getLeftOperand();
1080: if ((operand instanceof ColumnReference)
1081: && ((ColumnReference) operand).isScoped()) {
1082: // Left operand is the scoped operand.
1083: ((ColumnReference) operand).remapColumnReferences();
1084: } else {
1085: operand = binRelOp.getRightOperand();
1086: if ((operand instanceof ColumnReference)
1087: && ((ColumnReference) operand).isScoped()) {
1088: // Right operand is the scoped operand.
1089: ((ColumnReference) operand).remapColumnReferences();
1090: }
1091:
1092: // Else scoped operand is not a ColumnReference, which
1093: // means it can't (and doesn't need to) be remapped. So
1094: // just fall through and return.
1095: }
1096:
1097: return true;
1098: }
1099:
1100: /**
1101: * Return true if this predicate is scoped AND the scoped
1102: * operand is a ColumnReference that points to a source result
1103: * set. If the scoped operand is not a ColumnReference that
1104: * points to a source result set then it must be pointing to
1105: * some kind of expression, such as a literal (ex. 'strlit'),
1106: * an aggregate value (ex. "count(*)"), or the result of a
1107: * function (ex. "sin(i)") or operator (ex. "i+1").
1108: *
1109: * This method is used when pushing predicates to determine how
1110: * far down the query tree a scoped predicate needs to be pushed
1111: * to allow for successful evaluation of the scoped operand. If
1112: * the scoped operand is not pointing to a source result set
1113: * then it should not be pushed any further down tree. The reason
1114: * is that evaluation of the expression to which the operand is
1115: * pointing may depend on other values from the current level
1116: * in the tree (ex. "sin(i)" depends on the value of "i", which
1117: * could be a column at the predicate's current level). If we
1118: * pushed the predicate further down, those values could become
1119: * inaccessible, leading to execution-time errors.
1120: *
1121: * If, on the other hand, the scoped operand *is* pointing to
1122: * a source result set, then we want to push it further down
1123: * the tree until it reaches that result set, which allows
1124: * evaluation of this predicate to occur as close to store as
1125: * possible. This method doesn't actually do the push, it just
1126: * returns "true" and then the caller can push as appropriate.
1127: */
1128: protected boolean isScopedToSourceResultSet()
1129: throws StandardException {
1130: if (!scoped)
1131: return false;
1132:
1133: /* Note: right now the only predicates we scope are those
1134: * which are join predicates and all scoped predicates will
1135: * have the same relational operator as the predicates from
1136: * which they were scoped. Thus if we get here, we know
1137: * that andNode's leftOperand must be an instance of
1138: * BinaryRelationalOperatorNode (and therefore the following
1139: * cast is safe).
1140: */
1141: BinaryRelationalOperatorNode binRelOp = (BinaryRelationalOperatorNode) andNode
1142: .getLeftOperand();
1143:
1144: ValueNode operand = binRelOp.getLeftOperand();
1145:
1146: /* If operand isn't a ColumnReference then is must be the
1147: * scoped operand. This is because both operands have to
1148: * be column references in order for scoping to occur (as
1149: * per pushableToSubqueries()) and only the scoped operand
1150: * can change (esp. can become a non-ColumnReference) as
1151: * part of the scoping process. And since it's not a
1152: * ColumnReference it can't be "a ColumnReference that
1153: * points to a source result set", so return false.
1154: */
1155: if (!(operand instanceof ColumnReference))
1156: return false;
1157:
1158: /* If the operand is a ColumnReference and is scoped,
1159: * then see if it is pointing to a ResultColumn whose
1160: * expression is either another a CR or a Virtual
1161: * ColumnNode. If it is then that operand applies
1162: * to a source result set further down the tree and
1163: * thus we return true.
1164: */
1165: ValueNode exp = null;
1166: ColumnReference cRef = (ColumnReference) operand;
1167: if (cRef.isScoped()) {
1168: exp = cRef.getSource().getExpression();
1169: return ((exp instanceof VirtualColumnNode) || (exp instanceof ColumnReference));
1170: }
1171:
1172: operand = binRelOp.getRightOperand();
1173: if (!(operand instanceof ColumnReference))
1174: return false;
1175:
1176: cRef = (ColumnReference) operand;
1177: if (SanityManager.DEBUG) {
1178: // If we got here then the left operand was NOT the scoped
1179: // operand; make sure the right one is scoped, then.
1180: SanityManager.ASSERT(cRef.isScoped(),
1181: "All scoped predicates should have exactly one scoped "
1182: + "operand, but '"
1183: + binaryRelOpColRefsToString()
1184: + "has NONE.");
1185: }
1186:
1187: exp = cRef.getSource().getExpression();
1188: return ((exp instanceof VirtualColumnNode) || (exp instanceof ColumnReference));
1189: }
1190: }
|