001: /*
002:
003: Derby - Class org.apache.derby.impl.sql.compile.InListOperatorNode
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.sql.compile;
023:
024: import org.apache.derby.iapi.sql.compile.C_NodeTypes;
025:
026: import org.apache.derby.iapi.error.StandardException;
027:
028: import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
029:
030: import org.apache.derby.iapi.sql.dictionary.DataDictionary;
031: import org.apache.derby.iapi.reference.ClassName;
032:
033: import org.apache.derby.iapi.types.TypeId;
034: import org.apache.derby.iapi.types.DataValueDescriptor;
035:
036: import org.apache.derby.iapi.services.compiler.MethodBuilder;
037: import org.apache.derby.iapi.services.compiler.LocalField;
038:
039: import org.apache.derby.iapi.services.sanity.SanityManager;
040:
041: import org.apache.derby.iapi.sql.compile.Optimizable;
042:
043: import org.apache.derby.impl.sql.compile.ExpressionClassBuilder;
044:
045: import org.apache.derby.iapi.util.JBitSet;
046: import org.apache.derby.iapi.services.classfile.VMOpcode;
047:
048: import java.lang.reflect.Modifier;
049:
050: /**
051: * An InListOperatorNode represents an IN list.
052: *
053: * @author Jerry Brenner
054: */
055:
056: public final class InListOperatorNode extends BinaryListOperatorNode {
057: private boolean isOrdered;
058:
059: /**
060: * Initializer for a InListOperatorNode
061: *
062: * @param leftOperand The left operand of the node
063: * @param rightOperandList The right operand list of the node
064: */
065:
066: public void init(Object leftOperand, Object rightOperandList) {
067: init(leftOperand, rightOperandList, "IN", "in");
068: }
069:
070: /**
071: * Convert this object to a String. See comments in QueryTreeNode.java
072: * for how this should be done for tree printing.
073: *
074: * @return This object as a String
075: */
076:
077: public String toString() {
078: if (SanityManager.DEBUG) {
079: return "isOrdered: " + isOrdered + "\n" + super .toString();
080: } else {
081: return "";
082: }
083: }
084:
085: /**
086: * Preprocess an expression tree. We do a number of transformations
087: * here (including subqueries, IN lists, LIKE and BETWEEN) plus
088: * subquery flattening.
089: * NOTE: This is done before the outer ResultSetNode is preprocessed.
090: *
091: * @param numTables Number of tables in the DML Statement
092: * @param outerFromList FromList from outer query block
093: * @param outerSubqueryList SubqueryList from outer query block
094: * @param outerPredicateList PredicateList from outer query block
095: *
096: * @return The modified expression
097: *
098: * @exception StandardException Thrown on error
099: */
100: public ValueNode preprocess(int numTables, FromList outerFromList,
101: SubqueryList outerSubqueryList,
102: PredicateList outerPredicateList) throws StandardException {
103: super .preprocess(numTables, outerFromList, outerSubqueryList,
104: outerPredicateList);
105:
106: /* Check for the degenerate case of a single element in the IN list.
107: * If found, then convert to "=".
108: */
109: if (rightOperandList.size() == 1) {
110: BinaryComparisonOperatorNode equal = (BinaryComparisonOperatorNode) getNodeFactory()
111: .getNode(C_NodeTypes.BINARY_EQUALS_OPERATOR_NODE,
112: leftOperand,
113: (ValueNode) rightOperandList.elementAt(0),
114: getContextManager());
115: /* Set type info for the operator node */
116: equal.bindComparisonOperator();
117: return equal;
118: } else if ((leftOperand instanceof ColumnReference)
119: && rightOperandList.containsAllConstantNodes()) {
120: /* When sorting or choosing min/max in the list, if types are not an exact
121: * match, we use the left operand's type as the "judge", assuming that they
122: * are compatible, as also the case with DB2.
123: */
124: TypeId judgeTypeId = leftOperand.getTypeServices()
125: .getTypeId();
126: DataValueDescriptor judgeODV = null; //no judge, no argument
127: if (!rightOperandList.allSamePrecendence(judgeTypeId
128: .typePrecedence()))
129: judgeODV = (DataValueDescriptor) judgeTypeId.getNull();
130:
131: //Sort the list in ascending order
132: rightOperandList.sortInAscendingOrder(judgeODV);
133: isOrdered = true;
134:
135: /* If the leftOperand is a ColumnReference
136: * and the IN list is all constants, then we generate
137: * an additional BETWEEN clause of the form:
138: * CRClone BETWEEN minValue and maxValue
139: */
140: ValueNode leftClone = leftOperand.getClone();
141: ValueNode minValue = (ValueNode) rightOperandList
142: .elementAt(0); //already sorted
143: ValueNode maxValue = (ValueNode) rightOperandList
144: .elementAt(rightOperandList.size() - 1);
145:
146: /* Handle the degenerate case where
147: * the min and the max are the same value.
148: */
149: DataValueDescriptor minODV = ((ConstantNode) minValue)
150: .getValue();
151: DataValueDescriptor maxODV = ((ConstantNode) maxValue)
152: .getValue();
153: if ((judgeODV == null && minODV.compare(maxODV) == 0)
154: || (judgeODV != null && judgeODV.equals(minODV,
155: maxODV).equals(true))) {
156: BinaryComparisonOperatorNode equal = (BinaryComparisonOperatorNode) getNodeFactory()
157: .getNode(
158: C_NodeTypes.BINARY_EQUALS_OPERATOR_NODE,
159: leftOperand, minValue,
160: getContextManager());
161: /* Set type info for the operator node */
162: equal.bindComparisonOperator();
163: return equal;
164: }
165:
166: // Build the Between
167: ValueNodeList vnl = (ValueNodeList) getNodeFactory()
168: .getNode(C_NodeTypes.VALUE_NODE_LIST,
169: getContextManager());
170: vnl.addValueNode(minValue);
171: vnl.addValueNode(maxValue);
172:
173: BetweenOperatorNode bon = (BetweenOperatorNode) getNodeFactory()
174: .getNode(C_NodeTypes.BETWEEN_OPERATOR_NODE,
175: leftClone, vnl, getContextManager());
176:
177: /* The transformed tree has to be normalized:
178: * AND
179: * / \
180: * IN LIST AND
181: * / \
182: * >= AND
183: * / \
184: * <= TRUE
185: */
186:
187: /* Create the AND */
188: AndNode newAnd;
189:
190: newAnd = (AndNode) getNodeFactory().getNode(
191: C_NodeTypes.AND_NODE,
192: this ,
193: bon.preprocess(numTables, outerFromList,
194: outerSubqueryList, outerPredicateList),
195: getContextManager());
196: newAnd.postBindFixup();
197:
198: /* Mark this node as transformed so that we don't get
199: * calculated into the selectivity mulitple times.
200: */
201: setTransformed();
202:
203: // Return new AndNode
204: return newAnd;
205: } else {
206: return this ;
207: }
208: }
209:
210: /**
211: * Eliminate NotNodes in the current query block. We traverse the tree,
212: * inverting ANDs and ORs and eliminating NOTs as we go. We stop at
213: * ComparisonOperators and boolean expressions. We invert
214: * ComparisonOperators and replace boolean expressions with
215: * boolean expression = false.
216: * NOTE: Since we do not recurse under ComparisonOperators, there
217: * still could be NotNodes left in the tree.
218: *
219: * @param underNotNode Whether or not we are under a NotNode.
220: *
221: *
222: * @return The modified expression
223: *
224: * @exception StandardException Thrown on error
225: */
226: ValueNode eliminateNots(boolean underNotNode)
227: throws StandardException {
228: AndNode newAnd = null;
229: BinaryComparisonOperatorNode leftBCO;
230: BinaryComparisonOperatorNode rightBCO;
231: int listSize = rightOperandList.size();
232: ValueNode leftSide;
233:
234: if (SanityManager.DEBUG)
235: SanityManager.ASSERT(listSize > 0,
236: "rightOperandList.size() is expected to be > 0");
237:
238: if (!underNotNode) {
239: return this ;
240: }
241:
242: /* we want to convert the IN List into = OR = ... as
243: * described below.
244: */
245:
246: /* Convert:
247: * leftO IN rightOList.elementAt(0) , rightOList.elementAt(1) ...
248: * to:
249: * leftO <> rightOList.elementAt(0) AND leftO <> rightOList.elementAt(1) ...
250: * NOTE - We do the conversion here since the single table clauses
251: * can be pushed down and the optimizer may eventually have a filter factor
252: * for <>.
253: */
254:
255: /* leftO <> rightOList.at(0) */
256: /* If leftOperand is a ColumnReference, it may be remapped during optimization, and that
257: * requires each <> node to have a separate object.
258: */
259: ValueNode leftClone = (leftOperand instanceof ColumnReference) ? leftOperand
260: .getClone()
261: : leftOperand;
262: leftBCO = (BinaryComparisonOperatorNode) getNodeFactory()
263: .getNode(C_NodeTypes.BINARY_NOT_EQUALS_OPERATOR_NODE,
264: leftClone,
265: (ValueNode) rightOperandList.elementAt(0),
266: getContextManager());
267: /* Set type info for the operator node */
268: leftBCO.bindComparisonOperator();
269:
270: leftSide = leftBCO;
271:
272: for (int elemsDone = 1; elemsDone < listSize; elemsDone++) {
273:
274: /* leftO <> rightOList.elementAt(elemsDone) */
275: leftClone = (leftOperand instanceof ColumnReference) ? leftOperand
276: .getClone()
277: : leftOperand;
278: rightBCO = (BinaryComparisonOperatorNode) getNodeFactory()
279: .getNode(
280: C_NodeTypes.BINARY_NOT_EQUALS_OPERATOR_NODE,
281: leftClone,
282: (ValueNode) rightOperandList
283: .elementAt(elemsDone),
284: getContextManager());
285: /* Set type info for the operator node */
286: rightBCO.bindComparisonOperator();
287:
288: /* Create the AND */
289: newAnd = (AndNode) getNodeFactory().getNode(
290: C_NodeTypes.AND_NODE, leftSide, rightBCO,
291: getContextManager());
292: newAnd.postBindFixup();
293:
294: leftSide = newAnd;
295: }
296:
297: return leftSide;
298: }
299:
300: /**
301: * See if this IN list operator is referencing the same table.
302: *
303: * @param cr The column reference.
304: *
305: * @return true if in list references the same table as in cr.
306: *
307: * @exception StandardException Thrown on error
308: */
309: public boolean selfReference(ColumnReference cr)
310: throws StandardException {
311: int size = rightOperandList.size();
312: for (int i = 0; i < size; i++) {
313: ValueNode vn = (ValueNode) rightOperandList.elementAt(i);
314: if (vn.getTablesReferenced().get(cr.getTableNumber()))
315: return true;
316: }
317: return false;
318: }
319:
320: /**
321: * The selectivity for an "IN" predicate is generally very small.
322: * This is an estimate applicable when in list are not all constants.
323: */
324: public double selectivity(Optimizable optTable) {
325: return 0.3d;
326: }
327:
328: /**
329: * Do code generation for this IN list operator.
330: *
331: * @param acb The ExpressionClassBuilder for the class we're generating
332: * @param mb The MethodBuilder the expression will go into
333: *
334: * @exception StandardException Thrown on error
335: */
336:
337: public void generateExpression(ExpressionClassBuilder acb,
338: MethodBuilder mb) throws StandardException {
339: int listSize = rightOperandList.size();
340: String resultTypeName;
341: String receiverType = ClassName.DataValueDescriptor;
342:
343: String leftInterfaceType = ClassName.DataValueDescriptor;
344: String rightInterfaceType = ClassName.DataValueDescriptor
345: + "[]";
346:
347: if (SanityManager.DEBUG) {
348: SanityManager.ASSERT(listSize > 0,
349: "listSize is expected to be > 0");
350: }
351:
352: /*
353: ** There are 2 parts to the code generation for an IN list -
354: ** the code in the constructor and the code for the expression evaluation.
355: ** The code that gets generated for the constructor is:
356: ** DataValueDescriptor[] field = new DataValueDescriptor[size];
357: ** For each element in the IN list that is a constant, we also generate:
358: ** field[i] = rightOperandList[i];
359: **
360: ** If the IN list is composed entirely of constants, then we generate the
361: ** the following:
362: ** leftOperand.in(rightOperandList, leftOperand, isNullable(), ordered, result);
363: **
364: ** Otherwise, we create a new method. This method contains the
365: ** assignment of the non-constant elements into the array and the call to the in()
366: ** method, which is in the new method's return statement. We then return a call
367: ** to the new method.
368: */
369:
370: receiver = leftOperand;
371:
372: /* Figure out the result type name */
373: resultTypeName = getTypeCompiler().interfaceName();
374:
375: // Generate the code to build the array
376: LocalField arrayField = acb.newFieldDeclaration(
377: Modifier.PRIVATE, rightInterfaceType);
378:
379: /* The array gets created in the constructor.
380: * All constant elements in the array are initialized
381: * in the constructor. All non-constant elements, if any,
382: * are initialized each time the IN list is evaluated.
383: */
384: /* Assign the initializer to the DataValueDescriptor[] field */
385: MethodBuilder cb = acb.getConstructor();
386: cb.pushNewArray(ClassName.DataValueDescriptor, listSize);
387: cb.setField(arrayField);
388:
389: /* Set the array elements that are constant */
390: int numConstants = 0;
391: MethodBuilder nonConstantMethod = null;
392: MethodBuilder currentConstMethod = cb;
393: for (int index = 0; index < listSize; index++) {
394: MethodBuilder setArrayMethod;
395:
396: if (rightOperandList.elementAt(index) instanceof ConstantNode) {
397: numConstants++;
398:
399: /*if too many statements are added to a method,
400: *size of method can hit 65k limit, which will
401: *lead to the class format errors at load time.
402: *To avoid this problem, when number of statements added
403: *to a method is > 2048, remaing statements are added to a new function
404: *and called from the function which created the function.
405: *See Beetle 5135 or 4293 for further details on this type of problem.
406: */
407: if (currentConstMethod.statementNumHitLimit(1)) {
408: MethodBuilder genConstantMethod = acb
409: .newGeneratedFun("void", Modifier.PRIVATE);
410: currentConstMethod.pushThis();
411: currentConstMethod.callMethod(
412: VMOpcode.INVOKEVIRTUAL, (String) null,
413: genConstantMethod.getName(), "void", 0);
414: //if it is a generate function, close the metod.
415: if (currentConstMethod != cb) {
416: currentConstMethod.methodReturn();
417: currentConstMethod.complete();
418: }
419: currentConstMethod = genConstantMethod;
420: }
421: setArrayMethod = currentConstMethod;
422: } else {
423: if (nonConstantMethod == null)
424: nonConstantMethod = acb.newGeneratedFun("void",
425: Modifier.PROTECTED);
426: setArrayMethod = nonConstantMethod;
427:
428: }
429:
430: setArrayMethod.getField(arrayField); // first arg
431: ((ValueNode) rightOperandList.elementAt(index))
432: .generateExpression(acb, setArrayMethod);
433: setArrayMethod.upCast(receiverType); // second arg
434: setArrayMethod.setArrayElement(index);
435: }
436:
437: //if a generated function was created to reduce the size of the methods close the functions.
438: if (currentConstMethod != cb) {
439: currentConstMethod.methodReturn();
440: currentConstMethod.complete();
441: }
442:
443: if (nonConstantMethod != null) {
444: nonConstantMethod.methodReturn();
445: nonConstantMethod.complete();
446: mb.pushThis();
447: mb.callMethod(VMOpcode.INVOKEVIRTUAL, (String) null,
448: nonConstantMethod.getName(), "void", 0);
449: }
450:
451: /*
452: ** Call the method for this operator.
453: */
454: /*
455: ** Generate (field = <left expression>). This assignment is
456: ** used as the receiver of the method call for this operator,
457: ** and the field is used as the left operand:
458: **
459: ** (field = <left expression>).method(field, <right expression>...)
460: */
461:
462: //LocalField receiverField =
463: // acb.newFieldDeclaration(Modifier.PRIVATE, receiverType);
464: leftOperand.generateExpression(acb, mb);
465: mb.dup();
466: //mb.putField(receiverField); // instance for method call
467: /*mb.getField(receiverField);*/mb.upCast(leftInterfaceType); // first arg
468: mb.getField(arrayField); // second arg
469: mb.push(isOrdered); // third arg
470: mb.callMethod(VMOpcode.INVOKEINTERFACE, receiverType,
471: methodName, resultTypeName, 3);
472:
473: }
474:
475: /**
476: * Generate start/stop key for this IN list operator. Bug 3858.
477: *
478: * @param isAsc is the index ascending on the column in question
479: * @param isStartKey are we generating start key or not
480: * @param acb The ExpressionClassBuilder for the class we're generating
481: * @param mb The MethodBuilder the expression will go into
482: *
483: * @exception StandardException Thrown on error
484: */
485: public void generateStartStopKey(boolean isAsc, boolean isStartKey,
486: ExpressionClassBuilder acb, MethodBuilder mb)
487: throws StandardException {
488: /* left side of the "in" operator is our "judge" when we try to get
489: * the min/max value of the operands on the right side. Judge's type
490: * is important for us, and is input parameter to min/maxValue.
491: */
492: int leftTypeFormatId = leftOperand.getTypeId()
493: .getTypeFormatId();
494: int leftJDBCTypeId = leftOperand.getTypeId()
495: .isUserDefinedTypeId() ? leftOperand.getTypeId()
496: .getJDBCTypeId() : -1;
497:
498: int listSize = rightOperandList.size();
499: int numLoops, numValInLastLoop, currentOpnd = 0;
500:
501: /* We first calculate how many times (loops) we generate a call to
502: * min/maxValue function accumulatively, since each time it at most
503: * takes 4 input values. An example of the calls generated will be:
504: * minVal(minVal(...minVal(minVal(v1,v2,v3,v4,judge), v5,v6,v7,judge),
505: * ...), vn-1, vn, NULL, judge)
506: * Unused value parameters in the last call are filled with NULLs.
507: */
508: if (listSize < 5) {
509: numLoops = 1;
510: numValInLastLoop = (listSize - 1) % 4 + 1;
511: } else {
512: numLoops = (listSize - 5) / 3 + 2;
513: numValInLastLoop = (listSize - 5) % 3 + 1;
514: }
515:
516: for (int i = 0; i < numLoops; i++) {
517: /* generate value parameters of min/maxValue
518: */
519: int numVals = (i == numLoops - 1) ? numValInLastLoop
520: : ((i == 0) ? 4 : 3);
521: for (int j = 0; j < numVals; j++) {
522: ValueNode vn = (ValueNode) rightOperandList
523: .elementAt(currentOpnd++);
524: vn.generateExpression(acb, mb);
525: mb.upCast(ClassName.DataValueDescriptor);
526: }
527:
528: /* since we have fixed number of input values (4), unused ones
529: * in the last loop are filled with NULLs
530: */
531: int numNulls = (i < numLoops - 1) ? 0
532: : ((i == 0) ? 4 - numValInLastLoop
533: : 3 - numValInLastLoop);
534: for (int j = 0; j < numNulls; j++)
535: mb.pushNull(ClassName.DataValueDescriptor);
536:
537: /* have to put judge's types in the end
538: */
539: mb.push(leftTypeFormatId);
540: mb.push(leftJDBCTypeId);
541:
542: /* decide to get min or max value
543: */
544: String methodName;
545: if ((isAsc && isStartKey) || (!isAsc && !isStartKey))
546: methodName = "minValue";
547: else
548: methodName = "maxValue";
549:
550: mb.callMethod(VMOpcode.INVOKESTATIC,
551: ClassName.BaseExpressionActivation, methodName,
552: ClassName.DataValueDescriptor, 6);
553:
554: }
555: }
556: }
|