KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > derby > impl > sql > compile > InListOperatorNode


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