PredicateList


1   /*
2   
3      Derby - Class org.apache.derby.impl.sql.compile.PredicateList
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.services.loader.GeneratedMethod;
25  
26  import org.apache.derby.iapi.services.compiler.MethodBuilder;
27  import org.apache.derby.iapi.services.compiler.LocalField;
28  import org.apache.derby.iapi.reference.ClassName;
29  import org.apache.derby.iapi.services.classfile.VMOpcode;
30  
31  
32  import org.apache.derby.iapi.error.StandardException;
33  
34  import org.apache.derby.iapi.sql.compile.CompilerContext;
35  import org.apache.derby.iapi.sql.compile.ExpressionClassBuilderInterface;
36  import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
37  import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
38  import org.apache.derby.iapi.sql.compile.Optimizable;
39  import org.apache.derby.iapi.sql.compile.AccessPath;
40  import org.apache.derby.iapi.sql.compile.C_NodeTypes;
41  
42  import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
43  
44  import org.apache.derby.iapi.sql.execute.ExecIndexRow;
45  import org.apache.derby.iapi.sql.execute.ExecutionFactory;
46  
47  import org.apache.derby.iapi.sql.Activation;
48  import org.apache.derby.iapi.sql.Row;
49  
50  import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
51  import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
52  import org.apache.derby.iapi.sql.dictionary.StatisticsDescriptor;
53  import org.apache.derby.iapi.types.DataValueDescriptor;
54  import org.apache.derby.iapi.types.DataValueDescriptor;
55  
56  import org.apache.derby.iapi.store.access.Qualifier;
57  import org.apache.derby.iapi.store.access.ScanController;
58  
59  import org.apache.derby.impl.sql.compile.ExpressionClassBuilder;
60  import org.apache.derby.impl.sql.compile.ActivationClassBuilder;
61  
62  import org.apache.derby.iapi.services.sanity.SanityManager;
63  
64  import org.apache.derby.iapi.util.JBitSet;
65  
66  import java.lang.reflect.Modifier  ;
67  
68  import java.sql.Types  ;
69  
70  import java.util.ArrayList  ;
71  import java.util.Enumeration  ;
72  import java.util.Properties  ;
73  import java.util.Vector  ;
74  
75  /**
76   * A PredicateList represents the list of top level predicates.
77   * Each top level predicate consists of an AndNode whose leftOperand is the
78   * top level predicate and whose rightOperand is true.  It extends 
79   * QueryTreeNodeVector.
80   *
81   * @author Jerry Brenner
82   */
83  
84  public class PredicateList extends QueryTreeNodeVector implements OptimizablePredicateList
85  {
86      private int numberOfStartPredicates;
87      private int numberOfStopPredicates;
88      private int numberOfQualifiers;
89  
90      public PredicateList()
91      {
92      }
93  
94      /*
95       * OptimizableList interface
96       */
97  
98      /**
99       * @see org.apache.derby.iapi.sql.compile.OptimizablePredicateList#getOptPredicate
100      */
101     public OptimizablePredicate getOptPredicate(int index)
102     {
103         return (OptimizablePredicate) elementAt(index);
104     }
105 
106     /**
107      * @see org.apache.derby.iapi.sql.compile.OptimizablePredicateList#removeOptPredicate
108      *
109      * @exception StandardException     Thrown on error
110      */
111     public final void removeOptPredicate(int predCtr) throws StandardException
112     {
113         Predicate predicate = (Predicate) remove(predCtr);
114 
115         if (predicate.isStartKey())
116             numberOfStartPredicates--;
117         if (predicate.isStopKey())
118             numberOfStopPredicates--;
119         if (predicate.isQualifier())
120             numberOfQualifiers--;
121     }
122 
123     /**
124      * Another version of removeOptPredicate that takes the Predicate to be
125      * removed, rather than the position of the Predicate.  This is not part
126      * any interface (yet).
127      */
128     public final void removeOptPredicate(OptimizablePredicate pred)
129     {
130         removeElement((Predicate) pred);
131 
132         if (pred.isStartKey())
133             numberOfStartPredicates--;
134         if (pred.isStopKey())
135             numberOfStopPredicates--;
136         if (pred.isQualifier())
137             numberOfQualifiers--;
138     }
139 
140 
141     /** @see OptimizablePredicateList#addOptPredicate */
142     public void addOptPredicate(OptimizablePredicate optPredicate)
143     {
144         addElement((Predicate)optPredicate);
145 
146         if (optPredicate.isStartKey())
147             numberOfStartPredicates++;
148         if (optPredicate.isStopKey())
149             numberOfStopPredicates++;
150         if (optPredicate.isQualifier())
151             numberOfQualifiers++;
152     }
153 
154     /**
155      * Another flavor of addOptPredicate that inserts the given predicate
156      * at a given position.  This is not yet part of any interface.
157      */
158     public void addOptPredicate(OptimizablePredicate optPredicate, int position)
159     {
160         insertElementAt((Predicate) optPredicate, position);
161 
162         if (optPredicate.isStartKey())
163             numberOfStartPredicates++;
164         if (optPredicate.isStopKey())
165             numberOfStopPredicates++;
166         if (optPredicate.isQualifier())
167             numberOfQualifiers++;
168     }
169 
170 
171     /**
172      * @see OptimizablePredicateList#useful
173      * @exception StandardException     Thrown on error
174      */
175     public boolean useful(Optimizable optTable, ConglomerateDescriptor cd)
176         throws StandardException
177     {
178         boolean         retval = false;
179 
180         /*
181         ** Most of this assumes BTREE,
182         ** so should move into a configurable module
183         */
184 
185         /* If the conglomerate isn't an index, the predicate isn't useful */
186         if ( ! cd.isIndex())
187             return false;
188 
189         /*
190         ** A PredicateList is useful for a BTREE if it contains a relational
191         ** operator directly below a top-level AND comparing the first column
192         ** in the index to an expression that does not contain a reference
193         ** to the table in question.  Let's look for that.
194         */
195         int size = size();
196         for (int index = 0; index < size; index++)
197         {
198             Predicate   pred = (Predicate) elementAt(index);
199 
200             /*
201             ** Skip over it if it's not a relational operator (this includes
202             ** BinaryComparisonOperators and IsNullNodes.
203             */
204             RelationalOperator relop = pred.getRelop();
205             boolean isIn = false;
206             InListOperatorNode inNode = null;
207 
208             if (relop == null)
209             {
210                 /* if it's "in" operator, we generate dynamic start and stop key
211                  * to improve index scan performance, beetle 3858.
212                  */
213                 if (pred.getAndNode().getLeftOperand() instanceof InListOperatorNode &&
214                     ! ((InListOperatorNode)pred.getAndNode().getLeftOperand()).getTransformed())
215                 {
216                     isIn = true;
217                     inNode = (InListOperatorNode) pred.getAndNode().getLeftOperand();
218                 }
219                 else
220                     continue;
221             }
222 
223             /*
224             ** If the relational operator is neither a useful start key
225             ** nor a useful stop key for this table, it is not useful
226             ** for limiting an index scan.
227             */
228             if ( (! isIn) && ( ! relop.usefulStartKey(optTable) ) &&
229                  ( ! relop.usefulStopKey(optTable) ) )
230             {
231                 continue;
232             }
233 
234             /*
235             ** Look for a the first column of the index on one side of the
236             ** relop.  If it's not found, this Predicate is not optimizable.
237             */
238             ColumnReference indexCol = null;
239 
240             if (isIn)
241             {
242                 if (inNode.getLeftOperand() instanceof ColumnReference)
243                 {
244                     indexCol = (ColumnReference) inNode.getLeftOperand();
245                     if (indexCol.getColumnNumber() != 
246                             cd.getIndexDescriptor().baseColumnPositions()[0])
247                     {
248                         indexCol = null;
249                     }
250                 }
251             }
252             else
253             {
254                 indexCol = 
255                     relop.getColumnOperand(
256                         optTable, 
257                         cd.getIndexDescriptor().baseColumnPositions()[0]);
258             }
259 
260             if (indexCol == null)
261             {
262                 continue;
263             }
264 
265             /*
266             ** Look at the expression that the index column is compared to.
267             ** If it contains columns from the table in question, the
268             ** Predicate is not optimizable.
269             */
270             if ((isIn && inNode.selfReference(indexCol)) || 
271                 (! isIn && relop.selfComparison(indexCol)))
272             {
273                 continue;
274             }
275             
276             /* The Predicate is optimizable */
277             retval = true;
278             break;
279         }
280 
281         return retval;
282     }
283 
284     /**
285      * @see OptimizablePredicateList#pushUsefulPredicates
286      *
287      * @exception StandardException     Thrown on error
288      */
289     public void pushUsefulPredicates(Optimizable optTable)
290                         throws StandardException
291     {
292         AccessPath ap = optTable.getTrulyTheBestAccessPath();
293 
294         orderUsefulPredicates(optTable,
295                             ap.getConglomerateDescriptor(),
296                             true,
297                             ap.getNonMatchingIndexScan(),
298                             ap.getCoveringIndexScan());
299     }
300 
301     /**
302      * @see OptimizablePredicateList#classify
303      *
304      * @exception StandardException     Thrown on error
305      */
306     public void classify(Optimizable optTable, ConglomerateDescriptor cd)
307             throws StandardException
308     {
309         /*
310         ** Don't push the predicates - at this point, we are only determining
311         ** which predicates are useful.  Also, we don't know yet whether
312         ** we have a non-matching index scan or a covering index scan -
313         ** this method call will help determine that.  So, let's say they're
314         ** false for now.
315         */
316         orderUsefulPredicates(optTable, cd, false, false, false);
317     }
318 
319     /** @see OptimizablePredicateList#markAllPredicatesQualifiers */
320     public void markAllPredicatesQualifiers()
321     {
322         int size = size();
323         for (int index = 0; index < size; index++)
324         {
325             ((Predicate) elementAt(index)).markQualifier();
326         }
327 
328         numberOfQualifiers = size;
329     }
330 
331     /**
332      * @see OptimizablePredicateList#hasOptimizableEqualityPredicate
333      *
334      * @exception StandardException     Thrown on error
335      */
336     public boolean hasOptimizableEqualityPredicate(Optimizable optTable,
337                                                       int columnNumber,
338                                                       boolean isNullOkay)
339                             throws StandardException
340     {
341         int size = size();
342         for (int index = 0; index < size; index++)
343         {
344             AndNode         andNode;
345             Predicate       predicate;
346             predicate = (Predicate) elementAt(index);
347 
348             andNode = (AndNode) predicate.getAndNode();
349 
350             // skip non-equality predicates
351             ValueNode opNode = andNode.getLeftOperand();
352 
353             if (opNode.optimizableEqualityNode(optTable,
354                                                columnNumber,
355                                                isNullOkay))
356             {
357                 return true;
358             }
359         }
360 
361         return false;
362     }
363 
364     /**
365      * @see OptimizablePredicateList#hasOptimizableEquijoin
366      *
367      * @exception StandardException     Thrown on error
368      */
369     public boolean hasOptimizableEquijoin(Optimizable optTable,
370                                           int columnNumber)
371                     throws StandardException
372     {
373         int size = size();
374         for (int index = 0; index < size; index++)
375         {
376             AndNode         andNode;
377             Predicate       predicate;
378             predicate = (Predicate) elementAt(index);
379 
380             // This method is used by HashJoinStrategy to determine if
381             // there are any equality predicates that can be used to
382             // perform a hash join (see the findHashKeyColumns()
383             // method in HashJoinStrategy.java).  That said, if the
384             // predicate was scoped and pushed down from an outer query,
385             // then it's no longer possible to perform the hash join
386             // because one of the operands is in an outer query and
387             // the other (scoped) operand is down in a subquery. Thus
388             // we skip this predicate if it has been scoped.
389             if (predicate.isScopedForPush())
390             {
391                 continue;
392             }
393 
394             andNode = (AndNode) predicate.getAndNode();
395 
396             ValueNode opNode = andNode.getLeftOperand();
397 
398             if ( ! opNode.optimizableEqualityNode(optTable,
399                                                   columnNumber,
400                                                   false))
401             {
402                 continue;
403             }
404 
405             /*
406             ** Skip comparisons that are not qualifiers for the table
407             ** in question.
408             */
409             if ( ! ((RelationalOperator) opNode).isQualifier(optTable, false))
410             {
411                 continue;
412             }
413 
414             /*
415             ** Skip non-join comparisons.
416             */
417             if (predicate.getReferencedMap().hasSingleBitSet())
418             {
419                 continue;
420             }
421 
422             // We found a match
423             return true;
424         }
425 
426         return false;
427     }
428 
429     /**
430      * @see OptimizablePredicateList#putOptimizableEqualityPredicateFirst
431      *
432      * @exception StandardException     Thrown on error
433      */
434     public void putOptimizableEqualityPredicateFirst(Optimizable optTable,
435                                                         int columnNumber)
436                     throws StandardException
437     {
438         int size = size();
439         for (int index = 0; index < size; index++)
440         {
441             Predicate       predicate = (Predicate) elementAt(index);
442             AndNode         andNode;
443 
444             andNode = (AndNode) predicate.getAndNode();
445 
446             // skip non-equality predicates
447             ValueNode opNode = andNode.getLeftOperand();
448 
449             if (!opNode.optimizableEqualityNode(optTable, columnNumber, false))
450                 continue;
451 
452             // We found a match - make this entry first in the list
453             if (index != 0)
454             {
455                 removeElementAt(index);
456                 insertElementAt(predicate, 0);
457             }
458             
459             return;
460         }
461 
462         /* We should never get here since this method only called when we
463          * know that the desired equality predicate exists.
464          */
465         if (SanityManager.DEBUG)
466         {
467             SanityManager.THROWASSERT(
468                 "Could  not find the expected equality predicate on column #" +
469                 columnNumber);
470         }
471     }
472 
473     private void orderUsefulPredicates(Optimizable optTable,
474                                         ConglomerateDescriptor cd,
475                                         boolean pushPreds,
476                                         boolean nonMatchingIndexScan,
477                                         boolean coveringIndexScan)
478                         throws StandardException
479     {
480         boolean[]   deletes;
481         int[]       baseColumnPositions;
482         boolean[]   isAscending;
483         int         size = size();
484         Predicate[] usefulPredicates = new Predicate[size];
485         int         usefulCount = 0;
486         Predicate   predicate;
487 
488 
489         /*
490         ** Clear all the scan flags for this predicate list, so that the
491         ** flags that get set are only for the given conglomerate.
492         */
493         for (int index = 0; index < size; index++)
494         {
495             predicate = (Predicate) elementAt(index);
496 
497             predicate.clearScanFlags();
498         }
499 
500         /*
501         ** RESOLVE: For now, not pushing any predicates for heaps.  When this
502         ** changes, we also need to make the scan in
503         ** TableScanResultSet.getCurrentRow() check the qualifiers to see
504         ** if the row still qualifies (there is a new method in ScanController
505         ** for this.
506         */
507 
508         /* Is a heap scan or a non-matching index scan on a covering index? */
509         if ((cd == null) ||  (! cd.isIndex()) || 
510              (nonMatchingIndexScan && coveringIndexScan))
511         {
512             /*
513             ** For the heap, the useful predicates are the relational
514             ** operators that have a column from the table on one side,
515             ** and an expression that doesn't have a column from that
516             ** table on the other side.
517             **
518             ** For the heap, all useful predicates become Qualifiers, so
519             ** they don't have to be in any order.
520             **
521             ** NOTE: We can logically delete the current element when
522             ** traversing the Vector in the next loop,
523             ** so we must build an array of elements to
524             ** delete while looping and then delete them
525             ** in reverse order after completing the loop.
526             */
527             Predicate[] preds = new Predicate[size];
528 
529             for (int index = 0; index < size; index++)
530             {
531                 Predicate   pred = (Predicate) elementAt(index);
532 
533                 /*
534                 ** Skip over it if it's not a relational operator (this includes
535                 ** BinaryComparisonOperators and IsNullNodes.
536                 */
537                 RelationalOperator relop = pred.getRelop();
538 
539                 if (relop == null)
540                 {
541                     // possible OR clause, check for it.
542 
543                     if (!pred.isPushableOrClause(optTable))
544                     {
545                         // NOT an OR or AND, so go on to next predicate.
546                         continue;
547                     }
548                 }
549                 else
550                 {
551                     if ( ! relop.isQualifier(optTable, pushPreds))
552                     {
553                         // NOT a qualifier, go on to next predicate.
554                         continue;
555                     }
556                 }
557 
558                 pred.markQualifier();
559 
560                 if (pushPreds)
561                 {
562                     /* Push the predicate down.
563                      * (Just record for now.)
564                      */
565                     if (optTable.pushOptPredicate(pred))
566                     {
567                         preds[index] = pred;
568                     }
569                 }
570             }
571 
572             /* Now we actually push the predicates down */
573             for (int inner = size - 1; inner >= 0; inner--)
574             {
575                 if (preds[inner] != null)
576                 {
577                     removeOptPredicate(preds[inner]);
578                 }
579             }
580 
581             return;
582         }
583 
584         baseColumnPositions = cd.getIndexDescriptor().baseColumnPositions();
585         isAscending = cd.getIndexDescriptor().isAscending();
586 
587         /*
588         ** Create an array of useful predicates.  Also, count how many
589         ** useful predicates there are.
590         */
591         for (int index = 0; index < size; index++)
592         {
593             Predicate pred = (Predicate) elementAt(index);
594             ColumnReference indexCol = null;
595             int         indexPosition;
596 
597             /*
598             ** Skip over it if it's not a relational operator (this includes
599             ** BinaryComparisonOperators and IsNullNodes.
600             */
601             RelationalOperator relop = pred.getRelop();
602 
603             /* if it's "in" operator, we generate dynamic start and stop key
604              * to improve index scan performance, beetle 3858.
605              */
606             boolean isIn = false;
607             InListOperatorNode inNode = null;
608 
609             if (relop == null)
610             {
611                 if (pred.getAndNode().getLeftOperand() instanceof InListOperatorNode &&
612                     ! ((InListOperatorNode)pred.getAndNode().getLeftOperand()).getTransformed())
613                 {
614                     isIn = true;
615                     inNode = (InListOperatorNode) pred.getAndNode().getLeftOperand();
616                 }
617                 else
618                     continue;
619             }
620 
621             if ( !isIn && ! relop.isQualifier(optTable, pushPreds))
622                 continue;
623 
624             /* Look for an index column on one side of the relop */
625             for (indexPosition = 0;
626                 indexPosition < baseColumnPositions.length;
627                 indexPosition++)
628             {
629                 if (isIn)
630                 {
631                     if (inNode.getLeftOperand() instanceof ColumnReference)
632                     {
633                         indexCol = (ColumnReference) inNode.getLeftOperand();
634                         if ((optTable.getTableNumber() != indexCol.getTableNumber()) ||
635                                 (indexCol.getColumnNumber() != baseColumnPositions[indexPosition]) ||
636                                 inNode.selfReference(indexCol))
637                             indexCol = null;
638                     }
639                 }
640                 else
641                 {
642                     indexCol =
643                         relop.getColumnOperand(
644                             optTable,
645                             baseColumnPositions[indexPosition]);
646                 }
647                 if (indexCol != null)
648                     break;
649             }
650                 
651             /*
652             ** Skip over it if there is no index column on one side of the
653             ** operand.
654             */
655             if (indexCol == null)
656                 continue;
657 
658             pred.setIndexPosition(indexPosition);
659 
660             /* Remember the useful predicate */
661             usefulPredicates[usefulCount++] = pred;
662         }
663 
664         /* We can end up with no useful
665          * predicates with a force index override -
666          * Each predicate is on a non-key column or both
667          * sides of the operator are columns from the same table.
668          * There's no predicates to push down, so return and we'll
669          * evaluate them in a PRN.
670          */
671         if (usefulCount == 0)
672             return;
673 
674         /* The array of useful predicates may have unused slots.  Shrink it */
675         if (usefulPredicates.length > usefulCount)
676         {
677             Predicate[] shrink = new Predicate[usefulCount];
678 
679             System.arraycopy(usefulPredicates, 0, shrink, 0, usefulCount);
680 
681             usefulPredicates = shrink;
682         }
683 
684         /* Sort the array of useful predicates in index position order */
685         java.util.Arrays.sort(usefulPredicates);
686 
687         /* Push the sorted predicates down to the Optimizable table */
688         int     currentStartPosition = -1;
689         boolean gapInStartPositions = false;
690         int     currentStopPosition = -1;
691         boolean gapInStopPositions = false;
692         boolean seenNonEquals = false;
693         int     firstNonEqualsPosition = -1;
694         int     lastStartEqualsPosition = -1;
695 
696         /* beetle 4572. We need to truncate if necessary potential multi-column 
697          * start key up to the first one whose start operator is GT, and make 
698          * start operator GT;
699          * or start operator is GE if there's no such column.  We need to 
700          * truncate if necessary potential multi-column stop key up to the 
701          * first one whose stop operator is GE, and make stop operator GE; or 
702          * stop operator is GT if no such column.
703          * eg., start key (a,b,c,d,e,f), potential start operators 
704          * (GE,GE,GE,GT,GE,GT)
705          * then start key should really be (a,b,c,d) with start operator GT.
706          */
707         boolean seenGE = false, seenGT = false;
708 
709         for (int i = 0; i < usefulCount; i++)
710         {
711             Predicate           thisPred          = usefulPredicates[i];
712             int                 thisIndexPosition = thisPred.getIndexPosition();
713             boolean             thisPredMarked    = false;
714             RelationalOperator  relop             = thisPred.getRelop();
715             int                 thisOperator      = -1;
716 
717             boolean             isIn              = false;
718             InListOperatorNode  inNode            = null;
719 
720             if (relop == null)
721             {
722                 isIn = true;
723                 inNode = (InListOperatorNode) 
724                     thisPred.getAndNode().getLeftOperand();
725             }
726             else
727             {
728                 thisOperator = relop.getOperator();
729             }
730 
731             /* Allow only one start and stop position per index column */
732             if (currentStartPosition != thisIndexPosition)
733             {
734                 /*
735                 ** We're working on a new index column for the start position.
736                 ** Is it just one more than the previous position?
737                 */
738                 if ((thisIndexPosition - currentStartPosition) > 1)
739                 {
740                     /*
741                     ** There's a gap in the start positions.  Don't mark any
742                     ** more predicates as start predicates.
743                     */
744                     gapInStartPositions = true;
745                 }
746                 else if ((thisOperator == RelationalOperator.EQUALS_RELOP) ||
747                          (thisOperator == RelationalOperator.IS_NULL_RELOP))
748                 {
749                     /* Remember the last "=" or IS NULL predicate in the start
750                      * position.  (The sort on the predicates above has ensured
751                      * that these predicates appear 1st within the predicates on
752                      * a specific column.)
753                      */
754                     lastStartEqualsPosition = thisIndexPosition;
755                 }
756 
757                 if ( ! gapInStartPositions)
758                 {
759                     /*
760                     ** There is no gap in start positions.  Is this predicate
761                     ** useful as a start position?  This depends on the
762                     ** operator - for example, indexCol = <expr> is useful,
763                     ** while indexCol < <expr> is not useful with asc index
764                     ** we simply need to reverse the logic for desc indexes
765                     **
766                     ** The relop has to figure out whether the index column
767                     ** is on the left or the right, so pass the Optimizable
768                     ** table to help it.
769                     */
770                     if (! seenGT &&
771                         (isIn || ((relop.usefulStartKey(optTable) && isAscending[thisIndexPosition]) ||
772                         (relop.usefulStopKey(optTable) && ! isAscending[thisIndexPosition]))))
773                     {
774                         thisPred.markStartKey();
775                         currentStartPosition = thisIndexPosition;
776                         thisPredMarked = true;
777                         seenGT = (thisPred.getStartOperator(optTable) == ScanController.GT);
778                     }
779                 }
780             }
781 
782             /* Same as above, except for stop keys */
783             if (currentStopPosition != thisIndexPosition)
784             {
785                 if ((thisIndexPosition - currentStopPosition) > 1)
786                 {
787                     gapInStopPositions = true;
788                 }
789 
790                 if ( ! gapInStopPositions)
791                 {
792                     if (! seenGE &&
793                         (isIn || ((relop.usefulStopKey(optTable) && isAscending[thisIndexPosition]) ||
794                         (relop.usefulStartKey(optTable) && ! isAscending[thisIndexPosition]))))
795                     {
796                         thisPred.markStopKey();
797                         currentStopPosition = thisIndexPosition;
798                         thisPredMarked = true;
799                         seenGE = (thisPred.getStopOperator(optTable) == ScanController.GE);
800                     }
801                 }
802             }
803 
804             /* Mark this predicate as a qualifier if it is not a start/stop 
805              * position or if we have already seen a previous column whose 
806              * RELOPS do not include "=" or IS NULL.  For example, if
807              * the index is on (a, b, c) and the predicates are a > 1 and b = 1
808              * and c = 1, then b = 1 and c = 1 also need to be a qualifications,
809              * otherwise we may match on (2, 0, 3).
810              */
811             if ( (! isIn) &&    // store can never treat "in" as qualifier
812                  ((! thisPredMarked ) ||
813                   (seenNonEquals && thisIndexPosition != firstNonEqualsPosition)
814                  ) )
815             {
816                 thisPred.markQualifier();
817             }
818 
819             /* Remember if we have seen a column without an "=" */
820             if (lastStartEqualsPosition != thisIndexPosition &&
821                 firstNonEqualsPosition == -1 &&
822                 (thisOperator != RelationalOperator.EQUALS_RELOP) &&
823                 (thisOperator != RelationalOperator.IS_NULL_RELOP))
824             {
825                 seenNonEquals = true;
826                 /* Remember the column */
827                 firstNonEqualsPosition = thisIndexPosition;
828             }
829 
830             if (pushPreds)
831             {
832                 /* we only roughly detected that the predicate may be useful 
833                  * earlier, it may turn out that it's not actually start/stop 
834                  * key because another better predicate on the column is chosen.
835                  * We don't want to push "in" in this case, since it's not a 
836                  * qualifier.  Beetle 4316.
837                  */
838                 if (isIn && ! thisPredMarked)
839                     continue;
840 
841                 /*
842                 ** Push the predicate down.  They get pushed down in the
843                 ** order of the index.
844                 */
845 
846                 /* If this is an InListOperator predicate, make a copy of the
847                  * the predicate (including the AND node contained within it)
848                  * and then push the _copy_ (instead of the original) into
849                  * optTable.  We need to do this to avoid having the exact
850                  * same Predicate object (and in particular, the exact same
851                  * AndNode object) be referenced in both optTable and this.v,
852                  * which can lead to an infinite recursion loop when we get to
853                  * restorePredicates(), and thus to stack overflow
854                  * (beetle 4974).
855                  */
856                 Predicate predToPush;
857                 if (isIn) 
858                 {
859                     AndNode andCopy = (AndNode) getNodeFactory().getNode(
860                                         C_NodeTypes.AND_NODE,
861                                         thisPred.getAndNode().getLeftOperand(),
862                                         thisPred.getAndNode().getRightOperand(),
863                                         getContextManager());
864                     andCopy.copyFields(thisPred.getAndNode());
865                     Predicate predCopy = (Predicate) getNodeFactory().getNode(
866                                         C_NodeTypes.PREDICATE,
867                                         andCopy,
868                                         thisPred.getReferencedSet(),
869                                         getContextManager());
870                     predCopy.copyFields(thisPred);
871                     predToPush = predCopy;
872                 }
873                 else
874                 {
875                     predToPush = thisPred;
876                 }
877 
878                 if (optTable.pushOptPredicate(predToPush))
879                 {
880                     /* although we generated dynamic start and stop key for "in"
881                      * , we still need this predicate for further restriction
882                      */
883                     if (! isIn)
884                         removeOptPredicate(thisPred);
885                     // restore origin
886                 }
887                 else if (SanityManager.DEBUG)
888                 {
889                     SanityManager.ASSERT(false,
890                         "pushOptPredicate expected to be true");
891                 }
892             }
893             else
894             {
895                 /*
896                 ** We're not pushing the predicates down, so put them at the
897                 ** beginning of this predicate list in index order.
898                 */
899                 removeOptPredicate(thisPred);
900                 addOptPredicate(thisPred, i);
901             }
902         }
903     }
904 
905     /**
906      * Add a Predicate to the list.
907      *
908      * @param predicate A Predicate to add to the list
909      *
910      * @exception StandardException     Thrown on error
911      */
912 
913     public void addPredicate(Predicate predicate) throws StandardException
914     {
915         if (predicate.isStartKey())
916             numberOfStartPredicates++;
917         if (predicate.isStopKey())
918             numberOfStopPredicates++;
919         if (predicate.isQualifier())
920             numberOfQualifiers++;
921 
922         addElement(predicate);
923     }
924 
925     /**
926      * Transfer the non-qualifiers from this predicate list to the specified 
927      * predicate list.
928      * This is useful for arbitrary hash join, where we need to separate the 2 
929      * as the qualifiers get applied when probing the hash table and the 
930      * non-qualifiers get * applied afterwards.
931      *
932      * @param optTable  The optimizable that we want qualifiers for
933      * @param otherPL   ParameterList for non-qualifiers
934      *
935      * @exception StandardException     Thrown on error
936      */
937     protected void transferNonQualifiers(Optimizable optTable, PredicateList otherPL)
938         throws StandardException
939     {
940         /* Walk list backwards since we can delete while
941          * traversing the list.
942          */
943         for (int index = size() - 1; index >= 0; index--)
944         {
945             Predicate   pred = (Predicate) elementAt(index);
946 
947             RelationalOperator relop = pred.getRelop();
948             // Transfer each non-qualifier
949             if (relop == null || ! relop.isQualifier(optTable, false))
950             {
951                 pred.clearScanFlags();
952                 removeElementAt(index);
953                 otherPL.addElement(pred);
954             }
955         }
956 
957         // Mark all remaining predicates as qualifiers
958         markAllPredicatesQualifiers();
959     }
960 
961     /**
962      * Categorize the predicates in the list.  Initially, this means
963      * building a bit map of the referenced tables for each predicate.
964      *
965      * @exception StandardException         Thrown on error
966      */
967     public void categorize()
968         throws StandardException
969     {
970         int size = size();
971 
972         for (int index = 0; index < size; index++)
973         {
974             ((Predicate) elementAt(index)).categorize();
975         }
976     }
977 
978 
979     /**
980      * Prints the sub-nodes of this object.  See QueryTreeNode.java for
981      * how tree printing is supposed to work.
982      *
983      * @param depth     The depth of this node in the tree
984      */
985 
986     public void printSubNodes(int depth)
987     {
988         if (SanityManager.DEBUG)
989         {
990             Predicate       predicate;
991 
992             super.printSubNodes(depth);
993 
994             for (int index = 0; index < size(); index++)
995             {
996                 predicate = (Predicate) elementAt(index);
997                 predicate.treePrint(depth + 1);
998             }
999         }
1000    }
1001
1002    /**
1003     *  Eliminate predicates of the form:
1004     *                          AndNode
1005     *                          /      \
1006     *  true BooleanConstantNode        true BooleanConstantNode
1007     *  This is useful when checking for a NOP PRN as the
1008     *  Like transformation on c1 like 'ASDF%' can leave
1009     *  one of these predicates in the list.
1010     */
1011    public void eliminateBooleanTrueAndBooleanTrue()
1012    {
1013        /* Walk list backwards since we can delete while
1014         * traversing the list.
1015         */
1016        for (int index = size() - 1; index >= 0; index--)
1017        {
1018            AndNode         nextAnd;
1019            /* Look at the current predicate from the predicate list */
1020            nextAnd = ((Predicate) elementAt(index)).getAndNode();
1021
1022            if ((nextAnd.getLeftOperand().isBooleanTrue()) &&
1023                (nextAnd.getRightOperand().isBooleanTrue()))
1024            {
1025                removeElementAt(index);
1026            }
1027        }
1028
1029    }
1030
1031    /**
1032     * Rebuild a constant expression tree from the remaining constant 
1033     * predicates and delete those entries from the PredicateList.
1034     * The rightOperand of every top level AndNode is always a true 
1035     * BooleanConstantNode, so we can blindly overwrite that pointer.
1036     * Optimizations:
1037     *
1038     * We take this opportunity to eliminate:
1039     *                          AndNode
1040     *                       /         \
1041     *  true BooleanConstantNode    true BooleanConstantNode
1042     *
1043     * We remove the AndNode if the predicate list is a single AndNode:
1044     *                  AndNode
1045     *                 /       \
1046     *      LeftOperand         RightOperand
1047     *
1048     * becomes:
1049     *                  LeftOperand
1050     *
1051     * If the leftOperand of any AndNode is False, then the entire expression
1052     * will be False.  The expression simple becomes:
1053     *                  false BooleanConstantNode
1054     *
1055     * @return ValueNode    The rebuilt expression tree.
1056     */
1057    public ValueNode restoreConstantPredicates()
1058    throws StandardException
1059    {
1060        AndNode         nextAnd;
1061        AndNode         falseAnd = null;
1062        ValueNode       restriction = null;
1063
1064        /* Walk list backwards since we can delete while
1065         * traversing the list.
1066         */
1067        for (int index = size() - 1; index >= 0; index--)
1068        {
1069            /* Look at the current predicate from the predicate list */
1070            nextAnd = ((Predicate) elementAt(index)).getAndNode();
1071
1072            // Skip over the predicate if it is not a constant expression
1073            if (! nextAnd.isConstantExpression())
1074            {
1075                continue;
1076            }
1077
1078            // This node is a constant expression, so we can remove it from the list
1079            removeElementAt(index);
1080
1081            /* We can skip over TRUE AND TRUE */
1082            if ((nextAnd.getLeftOperand().isBooleanTrue()) &&
1083                (nextAnd.getRightOperand().isBooleanTrue()))
1084            {
1085                continue;
1086            }
1087
1088            /* Remember if we see a false BooleanConstantNode */
1089            if (nextAnd.getLeftOperand().isBooleanFalse())
1090            {
1091                falseAnd = nextAnd;
1092            }
1093
1094            if (restriction != null)
1095            {
1096                nextAnd.setRightOperand(restriction);
1097                /* If any of the predicates is nullable, then the resulting
1098                 * tree must be nullable.
1099                 */
1100                if (restriction.getTypeServices().isNullable())
1101                {
1102                    nextAnd.getTypeServices().setNullability(true);
1103                }
1104            }
1105            restriction = nextAnd;
1106        }
1107
1108        /* If restriction is a single AndNode, then it's rightOperand must be
1109         * a true BooleanConstantNode.  We simply chop out the AndNode and set 
1110         * restriction to AndNode.leftOperand.
1111         */
1112        if ((restriction != null) && 
1113            (((AndNode) restriction).getRightOperand().isBooleanTrue()))
1114        {
1115            restriction = ((AndNode) restriction).getLeftOperand();
1116        }
1117        else if (falseAnd != null)
1118        {
1119            /* Expression is ... AND FALSE AND ...
1120             * Replace the entire expression with a false BooleanConstantNode. 
1121             */
1122            restriction = falseAnd.getLeftOperand();
1123        }
1124
1125        return restriction;
1126    }
1127
1128    /**
1129     * Rebuild an expression tree from the remaining predicates and delete those
1130     * entries from the PredicateList.
1131     * The rightOperand of every top level AndNode is always a true 
1132     * BooleanConstantNode, so we can blindly overwrite that pointer.
1133     * Optimizations:
1134     *
1135     * We take this opportunity to eliminate:
1136     *                      AndNode
1137     *                     /       \
1138     *  true BooleanConstantNode    true BooleanConstantNode
1139     *
1140     * We remove the AndNode if the predicate list is a single AndNode:
1141     *                  AndNode
1142     *                 /       \
1143     *      LeftOperand         RightOperand
1144     *
1145     * becomes:
1146     *                  LeftOperand
1147     *
1148     * If the leftOperand of any AndNode is False, then the entire expression
1149     * will be False.  The expression simple becomes:
1150     *                  false BooleanConstantNode
1151     *
1152     * @return ValueNode    The rebuilt expression tree.
1153     */
1154    public ValueNode restorePredicates()
1155    throws StandardException
1156    {
1157        AndNode         nextAnd;
1158        AndNode         falseAnd = null;
1159        ValueNode       restriction = null;
1160
1161        int size = size();
1162        for (int index = 0; index < size; index++)
1163        {
1164            nextAnd = ((Predicate) elementAt(index)).getAndNode();
1165
1166            /* We can skip over TRUE AND TRUE */
1167            if ((nextAnd.getLeftOperand().isBooleanTrue()) &&
1168                (nextAnd.getRightOperand().isBooleanTrue()))
1169            {
1170                continue;
1171            }
1172
1173            /* Remember if we see a false BooleanConstantNode */
1174            if (nextAnd.getLeftOperand().isBooleanFalse())
1175            {
1176                falseAnd = nextAnd;
1177            }
1178
1179            if (restriction != null)
1180            {
1181                nextAnd.setRightOperand(restriction);
1182                /* If any of the predicates is nullable, then the resulting
1183                 * tree must be nullable.
1184                 */
1185                if (restriction.getTypeServices().isNullable())
1186                {
1187                    nextAnd.getTypeServices().setNullability(true);
1188                }
1189            }
1190            restriction = nextAnd;
1191        }
1192
1193        /* If restriction is a single AndNode, then it's rightOperand must be
1194         * a true BooleanConstantNode.  We simply chop out the AndNode and set 
1195         * restriction to AndNode.leftOperand.
1196         */
1197        if ((restriction != null) && 
1198            (((AndNode) restriction).getRightOperand().isBooleanTrue()))
1199        {
1200            restriction = ((AndNode) restriction).getLeftOperand();
1201        }
1202        else if (falseAnd != null)
1203        {
1204            /* Expression is ... AND FALSE AND ...
1205             * Replace the entire expression with a simple false 
1206             * BooleanConstantNode. 
1207             */
1208            restriction = falseAnd.getLeftOperand();
1209        }
1210
1211        /* Remove all predicates from the list */
1212        removeAllElements();
1213        return restriction;
1214    }
1215
1216    /**
1217     * Remap all ColumnReferences in this tree to be clones of the
1218     * underlying expression.
1219     *
1220     * @exception StandardException         Thrown on error
1221     */
1222    public void remapColumnReferencesToExpressions() throws StandardException
1223    {
1224        Predicate       pred;
1225
1226        int size = size();
1227        for (int index = 0; index < size; index++)
1228        {
1229            pred = (Predicate) elementAt(index);
1230
1231            pred.setAndNode((AndNode) 
1232                        pred.getAndNode().remapColumnReferencesToExpressions());
1233        }
1234    }
1235
1236    /**
1237     * Break apart the search clause into matching a PredicateList
1238     * where each top level predicate is a separate element in the list.
1239     * Build a bit map to represent the FromTables referenced within each
1240     * top level predicate.
1241     * NOTE: We want the rightOperand of every AndNode to be true, in order
1242     * to simplify the algorithm for putting the predicates back into the tree.
1243     * (As we put an AndNode back into the tree, we can ignore it's rightOperand.)
1244     *
1245     * @param numTables         Number of tables in the DML Statement
1246     * @param searchClause  The search clause to operate on.
1247     *
1248     * @exception StandardException     Thrown on error
1249     */
1250    void pullExpressions(int numTables,
1251                                 ValueNode searchClause)
1252                throws StandardException
1253    {
1254        AndNode     thisAnd;
1255        AndNode     topAnd;
1256        JBitSet     newJBitSet;
1257        Predicate   newPred;
1258        BooleanConstantNode trueNode = null;
1259
1260        if (searchClause != null)
1261        {
1262            topAnd = (AndNode) searchClause;
1263            searchClause = null;
1264            trueNode = (BooleanConstantNode) getNodeFactory().getNode(
1265                                            C_NodeTypes.BOOLEAN_CONSTANT_NODE,
1266                                            Boolean.TRUE,
1267                                            getContextManager());
1268            
1269            while (topAnd.getRightOperand() instanceof AndNode)
1270            {
1271                /* Break out the next top AndNode */
1272                thisAnd = topAnd;
1273                topAnd = (AndNode) topAnd.getRightOperand();
1274                thisAnd.setRightOperand(null);
1275
1276                /* Set the rightOperand to true */
1277                thisAnd.setRightOperand(trueNode);
1278
1279                /* Add the top AndNode to the PredicateList */
1280                newJBitSet = new JBitSet(numTables);
1281                newPred = (Predicate) getNodeFactory().getNode(
1282                                            C_NodeTypes.PREDICATE,
1283                                            thisAnd,
1284                                            newJBitSet,
1285                                            getContextManager());
1286                addPredicate(newPred);
1287            }
1288            
1289            /* Add the last top AndNode to the PredicateList */
1290            newJBitSet = new JBitSet(numTables);
1291            newPred = (Predicate) getNodeFactory().getNode(
1292                                            C_NodeTypes.PREDICATE,
1293                                            topAnd,
1294                                            newJBitSet,
1295                                            getContextManager());
1296            addPredicate(newPred);
1297        }
1298    }
1299
1300    /** 
1301     * XOR fromMap with the referenced table map in every remaining
1302     * Predicate in the list.  This is useful when pushing down 
1303     * multi-table predicates.
1304     * 
1305     * @param fromMap   The JBitSet to XOR with.
1306     */
1307    public void xorReferencedSet(JBitSet fromMap)
1308    {
1309        Predicate       predicate;
1310
1311        int size = size();
1312        for (int index = 0; index < size; index++)
1313        {
1314            predicate = (Predicate) elementAt(index);
1315
1316            if (SanityManager.DEBUG)
1317            {
1318                SanityManager.ASSERT(
1319                    fromMap.size() == predicate.getReferencedSet().size(),
1320                    "fromMap.size() (" + fromMap.size() + 
1321                    ") does not equal predicate.getReferencedSet().size() (" +
1322                    predicate.getReferencedSet().size());
1323            }
1324            
1325            predicate.getReferencedSet().xor(fromMap);
1326        }
1327    }
1328
1329    private void countScanFlags()
1330    {
1331        Predicate       predicate;
1332
1333        int size = size();
1334        for (int index = 0; index < size; index++)
1335        {
1336            predicate = (Predicate) elementAt(index);
1337            if (predicate.isStartKey())
1338                numberOfStartPredicates++;
1339            if (predicate.isStopKey())
1340                numberOfStopPredicates++;
1341            if (predicate.isQualifier())
1342                numberOfQualifiers++;
1343        }
1344    }
1345
1346    /**
1347     * Push all predicates, which can be pushed, into the underlying select.
1348     * A predicate can be pushed into an underlying select if the source of 
1349     * every ColumnReference in the predicate is itself a ColumnReference.
1350     *
1351     * This is useful when attempting to push predicates into non-flattenable
1352     * views or derived tables or into unions.
1353     *
1354     * @param select            The underlying SelectNode.
1355     * @param copyPredicate     Whether to make a copy of the predicate
1356     *                          before pushing
1357     *
1358     * @exception StandardException     Thrown on error
1359     */
1360    void pushExpressionsIntoSelect(SelectNode select, boolean copyPredicate)
1361        throws StandardException
1362    {
1363        /* Walk list backwards since we can delete while
1364         * traversing the list.
1365         */
1366        for (int index = size() - 1; index >= 0; index--)
1367        {
1368            Predicate   predicate;
1369            predicate = (Predicate) elementAt(index);
1370
1371            CollectNodesVisitor getCRs = 
1372                new CollectNodesVisitor(ColumnReference.class);
1373
1374            predicate.getAndNode().accept(getCRs);
1375            Vector   colRefs = getCRs.getList();
1376
1377            /* state doesn't become true until we find the 1st
1378             * ColumnReference.  (We probably will always find
1379             * at least 1 CR, but just to be safe, ...)
1380             */
1381            boolean state = colRefs.size() > 0;
1382            if (state)
1383            {
1384                for (Enumeration   e = colRefs.elements(); e.hasMoreElements(); )
1385                {
1386                    ColumnReference ref = (ColumnReference)e.nextElement();
1387                    if (!ref.pointsToColumnReference())
1388                    {
1389                        state = false;
1390                        break;
1391                    }
1392                }
1393            }
1394
1395            if (!state)
1396                continue;
1397
1398            if (copyPredicate)
1399            {
1400                // Copy this predicate and push this instead
1401                AndNode andNode = predicate.getAndNode();
1402                ValueNode leftOperand;
1403                ColumnReference crNode;
1404                BinaryRelationalOperatorNode opNode=null;
1405                InListOperatorNode inNode=null;
1406
1407                // Make sure we are only pushing binary relations and InList for
1408                // copyPredicate case. It should be benificial to push expressions that
1409                // can be pushed, so they can be applied closer to the data.
1410
1411                if (andNode.getLeftOperand() instanceof BinaryRelationalOperatorNode)
1412                {
1413                    opNode = (BinaryRelationalOperatorNode) andNode.getLeftOperand();
1414                    // Investigate using invariant interface to check rightOperand
1415                    if (! (opNode.getLeftOperand() instanceof ColumnReference) ||
1416                        ! (opNode.getRightOperand() instanceof ConstantNode ||
1417                             opNode.getRightOperand() instanceof ParameterNode))
1418                        continue;
1419
1420                    crNode = (ColumnReference) opNode.getLeftOperand();
1421                }
1422                else if (andNode.getLeftOperand() instanceof InListOperatorNode)
1423                {
1424                    inNode = (InListOperatorNode) andNode.getLeftOperand();
1425                    if (! (inNode.getRightOperandList().isConstantExpression()))
1426                        continue;
1427
1428                    crNode = (ColumnReference) inNode.getLeftOperand();
1429                }
1430                else
1431                    continue;
1432
1433                // Remap this crNode to underlying column reference in the select, if possible.
1434                ColumnReference newCRNode = select.findColumnReferenceInResult(crNode.columnName);
1435                if (newCRNode == null)
1436                    continue;
1437
1438                // Create a copy of the predicate to push down
1439                // <column> <relop> <value> AND TRUE
1440                if (andNode.getLeftOperand() instanceof BinaryRelationalOperatorNode)
1441                {
1442                    BinaryRelationalOperatorNode newRelop = (BinaryRelationalOperatorNode)
1443                            getNodeFactory().getNode(
1444                                        opNode.getNodeType(),
1445                                        newCRNode,
1446                                        opNode.getRightOperand(),
1447                                        getContextManager());
1448                    newRelop.bindComparisonOperator();
1449                    leftOperand = newRelop;
1450                }
1451                else
1452                {
1453                    InListOperatorNode newInNode = (InListOperatorNode)
1454                            getNodeFactory().getNode(
1455                                C_NodeTypes.IN_LIST_OPERATOR_NODE,
1456                                newCRNode,
1457                                inNode.getRightOperandList(),
1458                                getContextManager());
1459                    newInNode.setType(inNode.getTypeServices());
1460                    leftOperand = newInNode;
1461                }
1462
1463                // Convert the predicate into CNF form
1464                ValueNode trueNode = (ValueNode) getNodeFactory().getNode(
1465                                        C_NodeTypes.BOOLEAN_CONSTANT_NODE,
1466                                        Boolean.TRUE,
1467                                        getContextManager());
1468                AndNode newAnd = (AndNode) getNodeFactory().getNode(
1469                                                    C_NodeTypes.AND_NODE,
1470                                                    leftOperand,
1471                                                    trueNode,
1472                                                    getContextManager());
1473                newAnd.postBindFixup();
1474                JBitSet tableMap = new JBitSet(select.referencedTableMap.size());
1475
1476                // Use newly constructed predicate
1477                predicate = (Predicate) getNodeFactory().getNode(
1478                                                C_NodeTypes.PREDICATE,
1479                                                newAnd,
1480                                                tableMap,
1481                                                getContextManager());
1482            }
1483            else
1484            {
1485                // keep the counters up to date when removing a predicate
1486                if (predicate.isStartKey())
1487                    numberOfStartPredicates--;
1488                if (predicate.isStopKey())
1489                    numberOfStopPredicates--;
1490                if (predicate.isQualifier())
1491                    numberOfQualifiers--;
1492
1493                /* Clear all of the scan flags since they may be different
1494                 * due to the splitting of the list.
1495                 */
1496                predicate.clearScanFlags();
1497                // Remove this predicate from the list
1498                removeElementAt(index);
1499            }
1500
1501            // Push it into the select
1502            select.pushExpressionsIntoSelect(predicate);
1503        }       
1504    }
1505
1506    /**
1507     * Mark all of the RCs and the RCs in their RC/VCN chain
1508     * referenced in the predicate list as referenced.
1509     *
1510     * @exception StandardException     Thrown on error
1511     */
1512    void markReferencedColumns()
1513        throws StandardException
1514    {
1515        CollectNodesVisitor collectCRs = 
1516            new CollectNodesVisitor(ColumnReference.class);
1517
1518        int size = size();
1519        for (int index = 0; index < size; index++)
1520        {
1521            Predicate predicate = (Predicate) elementAt(index);
1522            predicate.getAndNode().accept(collectCRs);
1523        }
1524
1525        Vector   colRefs = collectCRs.getList();
1526        for (Enumeration   e = colRefs.elements(); e.hasMoreElements(); )
1527        {
1528            ColumnReference ref = (ColumnReference)e.nextElement();
1529            ref.getSource().markAllRCsInChainReferenced();
1530        }
1531    }
1532
1533    /**
1534     * Update the array of columns in = conditions with constants
1535     * or correlation or join columns.  This is useful when doing
1536     * subquery flattening on the basis of an equality condition.
1537     *
1538     * @param tableNumber   The tableNumber of the table from which
1539     *                      the columns of interest come from.
1540     * @param eqOuterCols   Array of booleans for noting which columns
1541     *                      are in = predicates with constants or
1542     *                      correlation columns.
1543     * @param tableNumbers  Array of table numbers in this query block.
1544     * @param resultColTable tableNumber is the table the result columns are
1545     *                      coming from
1546     *
1547     * @exception StandardException     Thrown on error
1548     */
1549    void checkTopPredicatesForEqualsConditions(
1550    int         tableNumber, 
1551    boolean[]   eqOuterCols, 
1552    int[]       tableNumbers, 
1553    JBitSet[]   tableColMap, 
1554    boolean     resultColTable)
1555        throws StandardException
1556    {
1557        int size = size();
1558        for (int index = 0; index < size; index++)
1559        {
1560            AndNode and = (AndNode) ((Predicate) elementAt(index)).getAndNode();
1561            and.checkTopPredicatesForEqualsConditions(
1562                tableNumber, eqOuterCols, tableNumbers, tableColMap,
1563                resultColTable);
1564        }
1565    }
1566
1567    /** 
1568     * Check if all of the predicates in the list are pushable.
1569     *
1570     * @return Whether or not all of the predicates in the list are pushable.
1571     */
1572     boolean allPushable()
1573    {
1574        int size = size();
1575        for (int index = 0; index < size; index++)
1576        {
1577            Predicate       predicate = (Predicate) elementAt(index);
1578            if (! predicate.getPushable())
1579            {
1580                return false;
1581            }
1582        }
1583        return true;
1584     }
1585
1586    /**
1587     * Build a list of pushable predicates, if any,
1588     * that satisfy the referencedTableMap.
1589     *
1590     * @param referencedTableMap    The referenced table map
1591     *
1592     * @return A list of pushable predicates, if any,
1593     * that satisfy the referencedTableMap.
1594     *
1595     * @exception StandardException     Thrown on error
1596     */
1597    PredicateList getPushablePredicates(JBitSet referencedTableMap)
1598        throws StandardException
1599    {
1600        PredicateList pushPList = null;
1601
1602        // Walk the list backwards because of possible deletes
1603        for (int index = size() - 1; index >= 0; index--)
1604        {
1605            Predicate predicate = (Predicate) elementAt(index);
1606            if (! predicate.getPushable())
1607            {
1608                continue;
1609            }
1610
1611            JBitSet curBitSet = predicate.getReferencedSet();
1612            
1613            /* Do we have a match? */
1614            if (referencedTableMap.contains(curBitSet))
1615            {
1616                /* Add the matching predicate to the push list */
1617                if (pushPList == null)
1618                {
1619                    pushPList = (PredicateList) getNodeFactory().getNode(
1620                                            C_NodeTypes.PREDICATE_LIST,
1621                                            getContextManager());
1622                }
1623                pushPList.addPredicate(predicate);
1624
1625                /* Remap all of the ColumnReferences to point to the
1626                 * source of the values.
1627                 */
1628                RemapCRsVisitor rcrv = new RemapCRsVisitor(true);
1629                predicate.getAndNode().accept(rcrv);
1630
1631                /* Remove the matching predicate from the outer list */
1632                removeElementAt(index);
1633            }
1634        }
1635        return pushPList;
1636    }
1637
1638    /**
1639     * Decrement the level of any CRs from the subquery's
1640     * FROM list that are interesting to transitive closure.
1641     * 
1642     * @param fromList  The subquery's FROM list.
1643     * @param decrement Decrement size.
1644     */
1645    void decrementLevel(FromList fromList, int decrement)
1646    {
1647        int[] tableNumbers = fromList.getTableNumbers();
1648
1649        /* For each top level relop, find all top level
1650         * CRs from the subquery and decrement their 
1651         * nesting level.
1652         */
1653        int size = size();
1654        for (int index = 0; index < size; index++)
1655        {
1656            ColumnReference cr1 = null;
1657            ColumnReference cr2 = null;
1658            Predicate predicate = (Predicate) elementAt(index);
1659            ValueNode vn = predicate.getAndNode().getLeftOperand();
1660
1661            if (vn instanceof BinaryOperatorNode)
1662            {
1663                    BinaryOperatorNode bon = (BinaryOperatorNode) vn;
1664                if (bon.getLeftOperand() instanceof ColumnReference)
1665                    {
1666                        cr1 = (ColumnReference) bon.getLeftOperand();
1667                    }
1668                    if (bon.getRightOperand() instanceof ColumnReference)
1669                    {
1670                        cr2 = (ColumnReference) bon.getRightOperand();
1671                    }
1672            }
1673            else if (vn instanceof UnaryOperatorNode)
1674            {
1675                UnaryOperatorNode uon = (UnaryOperatorNode) vn;
1676                if (uon.getOperand() instanceof ColumnReference)
1677                {
1678                    cr1 = (ColumnReference) uon.getOperand();
1679                }
1680            }
1681
1682            /* See if any of the CRs need to have their
1683             * source level decremented.
1684             */
1685            if (cr1 != null)
1686            {
1687                int sourceTable = cr1.getTableNumber();
1688                for (int inner = 0; inner < tableNumbers.length; inner++)
1689                if (tableNumbers[inner] == sourceTable)
1690                {
1691                    cr1.setSourceLevel(
1692                        cr1.getSourceLevel() - decrement);
1693                    break;
1694                }
1695            }
1696
1697            if (cr2 != null)
1698            {
1699                int sourceTable = cr2.getTableNumber();
1700                for (int inner = 0; inner < tableNumbers.length; inner++)
1701                if (tableNumbers[inner] == sourceTable)
1702                {
1703                    cr2.setSourceLevel(
1704                        cr2.getSourceLevel() - decrement);
1705                    break;
1706                }
1707            }
1708        }
1709    }
1710
1711    /**
1712     * Perform transitive closure on join clauses.  For each table in the query,
1713     * we build a list of equijoin clauses of the form:
1714     *      <ColumnReference> <=> <ColumnReference>
1715     * Each join clause is put on 2 lists since it joins 2 tables.
1716     * 
1717     * We then walk the array of lists.  We first walk it as the outer list.  
1718     * For each equijoin predicate, we assign an equivalence class if it does 
1719     * not yet have one.  We then walk the predicate list (as middle) for the 
1720     * other table, searching for other equijoins with the middle table number 
1721     * and column number.  All such predicates are assigned the same 
1722     * equivalence class. We then walk the predicate list (as inner) for the 
1723     * other side of the middle predicate to see if we can find an equijoin 
1724     * between outer and inner.  If so, then we simply assign it to the same 
1725     * equivalence class.  If not, then we add the new equijoin clause.
1726     *
1727     * @param numTables The number of tables in the query
1728     * @param fromList  The FromList in question.
1729     * @param cc        The CompilerContext to use
1730     *
1731     * @exception StandardException     Thrown on error
1732     */
1733    void joinClauseTransitiveClosure(int numTables, 
1734                                     FromList fromList, CompilerContext cc)
1735        throws StandardException
1736    {
1737        // Nothing to do if < 3 tables
1738        if (fromList.size() < 3)
1739        {
1740            return;
1741        }
1742
1743        /* Create an array of numTables PredicateLists to hold the join clauses. */
1744        PredicateList[] joinClauses = new PredicateList[numTables];
1745        for (int index = 0; index < numTables; index++)
1746        {
1747            joinClauses[index] = new PredicateList();
1748        }
1749
1750        /* Pull the equijoin clauses, putting each one in the list for
1751         * each of the tables being joined.
1752         */
1753        int size = size();
1754        for (int index = 0; index < size; index++)
1755        {
1756            Predicate predicate = (Predicate) elementAt(index);
1757            ValueNode vn = predicate.getAndNode().getLeftOperand();
1758
1759            if (! (vn.isBinaryEqualsOperatorNode()))
1760            {
1761                continue;
1762            }
1763
1764            /* Is this an equijoin clause between 2 ColumnReferences? */
1765            BinaryRelationalOperatorNode equals = 
1766                (BinaryRelationalOperatorNode) vn;
1767            ValueNode left = equals.getLeftOperand();
1768            ValueNode right = equals.getRightOperand();
1769
1770            if ((left  instanceof ColumnReference && 
1771                 right instanceof ColumnReference))
1772            {
1773                ColumnReference leftCR = (ColumnReference) left;
1774                ColumnReference rightCR = (ColumnReference) right;
1775                if (leftCR.getSourceLevel() == rightCR.getSourceLevel() &&
1776                    leftCR.getTableNumber() != rightCR.getTableNumber())
1777                {
1778                    // Add the equijoin clause to each of the lists
1779                    joinClauses[leftCR.getTableNumber()].addElement(predicate);
1780                    joinClauses[rightCR.getTableNumber()].addElement(predicate);
1781                }
1782                continue;
1783            }
1784        }
1785
1786        /* Walk each of the PredicateLists, using each 1 as the starting point 
1787         * of an equivalence class.
1788         */
1789        for (int index = 0; index < numTables; index++)
1790        {
1791            PredicateList outerJCL = joinClauses[index];
1792
1793            // Skip the empty lists
1794            if (outerJCL.size() == 0)
1795            {
1796                continue;
1797            }
1798
1799            /* Put all of the join clauses that already have an equivalence 
1800             * class at the head of the outer list to optimize search.
1801             */
1802            Vector   movePreds = new Vector  ();
1803            for (int jcIndex = outerJCL.size() - 1; jcIndex >= 0; jcIndex--)
1804            {
1805                Predicate predicate = (Predicate) outerJCL.elementAt(jcIndex);
1806                if (predicate.getEquivalenceClass() != -1)
1807                {
1808                    outerJCL.removeElementAt(jcIndex);
1809                    movePreds.addElement(predicate);
1810                }
1811            }
1812            for (int mpIndex = 0; mpIndex < movePreds.size(); mpIndex++)
1813            {
1814                outerJCL.insertElementAt(
1815                    (Predicate) movePreds.elementAt(mpIndex), 0);
1816            }
1817
1818            // Walk this list as the outer
1819            for (int outerIndex = 0; outerIndex < outerJCL.size(); outerIndex++)
1820            {
1821                ColumnReference innerCR = null;
1822                ColumnReference outerCR = null;
1823                int outerTableNumber = index;
1824                int middleTableNumber;
1825                int outerColumnNumber;
1826                int middleColumnNumber;
1827                int outerEC;
1828
1829                /* Assign an equivalence class to those Predicates 
1830                 * that have not already been assigned an equivalence class.
1831                 */
1832                Predicate outerP = (Predicate) outerJCL.elementAt(outerIndex);
1833                if (outerP.getEquivalenceClass() == -1)
1834                {
1835                    outerP.setEquivalenceClass(cc.getNextEquivalenceClass());
1836                }
1837                outerEC = outerP.getEquivalenceClass();
1838
1839                // Get the table and column numbers
1840                BinaryRelationalOperatorNode equals = 
1841                    (BinaryRelationalOperatorNode) outerP.getAndNode().getLeftOperand();
1842                ColumnReference leftCR = (ColumnReference) equals.getLeftOperand();
1843                ColumnReference rightCR = (ColumnReference) equals.getRightOperand();
1844
1845                if (leftCR.getTableNumber() == outerTableNumber)
1846                {
1847                    outerColumnNumber = leftCR.getColumnNumber();
1848                    middleTableNumber = rightCR.getTableNumber();
1849                    middleColumnNumber = rightCR.getColumnNumber();
1850                    outerCR = leftCR;
1851                }
1852                else
1853                {
1854                    outerColumnNumber = rightCR.getColumnNumber();
1855                    middleTableNumber = leftCR.getTableNumber();
1856                    middleColumnNumber = leftCR.getColumnNumber();
1857                    outerCR = rightCR;
1858                }
1859
1860                /* Walk the other list as the middle to find other join clauses
1861                 * in the chain/equivalence class
1862                 */
1863                PredicateList middleJCL = joinClauses[middleTableNumber];
1864                for (int middleIndex = 0; middleIndex < middleJCL.size(); middleIndex++)
1865                {
1866                    /* Skip those Predicates that have already been
1867                     * assigned a different equivalence class.
1868                     */
1869                    Predicate middleP = (Predicate) middleJCL.elementAt(middleIndex);
1870                    if (middleP.getEquivalenceClass() != -1 &&
1871                        middleP.getEquivalenceClass() != outerEC)
1872                    {
1873                        continue;
1874                    }
1875
1876                    int innerTableNumber;
1877                    int innerColumnNumber;
1878
1879                    // Get the table and column numbers
1880                    BinaryRelationalOperatorNode middleEquals = 
1881                        (BinaryRelationalOperatorNode) middleP.getAndNode().getLeftOperand();
1882                    ColumnReference mLeftCR = (ColumnReference) middleEquals.getLeftOperand();
1883                    ColumnReference mRightCR = (ColumnReference) middleEquals.getRightOperand();
1884
1885                    /* Find the other side of the equijoin, skipping this predicate if 
1886                     * not on middleColumnNumber.
1887                     */
1888                    if (mLeftCR.getTableNumber() == middleTableNumber) 
1889                    {
1890                        if (mLeftCR.getColumnNumber() != middleColumnNumber)
1891                        {
1892                            continue;
1893                        }
1894                        innerTableNumber = mRightCR.getTableNumber();
1895                        innerColumnNumber = mRightCR.getColumnNumber();
1896                    }
1897                    else
1898                    {
1899                        if (mRightCR.getColumnNumber() != middleColumnNumber)
1900                        {
1901                            continue;
1902                        }
1903                        innerTableNumber = mLeftCR.getTableNumber();
1904                        innerColumnNumber = mLeftCR.getColumnNumber();
1905                    }
1906
1907                    // Skip over outerTableNumber.outerColumnNumber = middleTableNumber.middleColumnNumber
1908                    if (outerTableNumber == innerTableNumber &&
1909                        outerColumnNumber == innerColumnNumber)
1910                    {
1911                        continue;
1912                    }
1913
1914                    // Put this predicate into the outer equivalence class
1915                    middleP.setEquivalenceClass(outerEC);
1916
1917                    /* Now go to the inner list and see if there is an equijoin
1918                     * between inner and outer on innerColumnNumber and outerColumnNumber.
1919                     * If so, then we continue our walk across middle, otherwise we
1920                     * add a new equijoin to both the inner and outer lists before
1921                     * continuing to walk across middle.
1922                     */
1923
1924                    int newTableNumber;
1925                    int newColumnNumber;
1926                    Predicate innerP = null;
1927                    PredicateList innerJCL = joinClauses[innerTableNumber];
1928                    int innerIndex = 0;
1929                    for ( ; innerIndex < innerJCL.size(); innerIndex++)
1930                    {
1931                        innerP = (Predicate) innerJCL.elementAt(innerIndex);
1932
1933                        // Skip over predicates with other equivalence classes
1934                        if (innerP.getEquivalenceClass() != -1 &&
1935                            innerP.getEquivalenceClass() != outerEC)
1936                        {
1937                            continue;
1938                        }
1939
1940                        /* Now we see if the inner predicate completes the loop.
1941                         * If so, then add it to the outer equivalence class
1942                         * and stop.
1943                         */
1944
1945                        // Get the table and column numbers
1946                        BinaryRelationalOperatorNode innerEquals = 
1947                            (BinaryRelationalOperatorNode) innerP.getAndNode().getLeftOperand();
1948                        ColumnReference iLeftCR = (ColumnReference) innerEquals.getLeftOperand();
1949                        ColumnReference iRightCR = (ColumnReference) innerEquals.getRightOperand();
1950
1951                        if (iLeftCR.getTableNumber() == innerTableNumber)
1952                        {
1953                            if (iLeftCR.getColumnNumber() != innerColumnNumber)
1954                            {
1955                                continue;
1956                            }
1957                            newTableNumber = iRightCR.getTableNumber();
1958                            newColumnNumber = iRightCR.getColumnNumber();
1959                            innerCR = iLeftCR;
1960                        }
1961                        else
1962                        {
1963                            if (iRightCR.getColumnNumber() != innerColumnNumber)
1964                            {
1965                                continue;
1966                            }
1967                            newTableNumber = iLeftCR.getTableNumber();
1968                            newColumnNumber = iLeftCR.getColumnNumber();
1969                            innerCR = iRightCR;
1970                        }
1971
1972                        // Did we find the equijoin between inner and outer
1973                        if (newTableNumber == outerTableNumber &&
1974                            newColumnNumber == outerColumnNumber)
1975                        {
1976                            break;
1977                        }
1978                    }
1979
1980                    // Did we find an equijoin on inner and outer
1981                    if (innerIndex != innerJCL.size())
1982                    {
1983                        // match found
1984                        // Put this predicate into the outer equivalence class
1985                        innerP.setEquivalenceClass(outerEC);
1986                        continue;
1987                    }
1988
1989                    // No match, add new equijoin
1990                    // Build a new predicate
1991                    BinaryRelationalOperatorNode newEquals = (BinaryRelationalOperatorNode)
1992                            getNodeFactory().getNode(
1993                                        C_NodeTypes.BINARY_EQUALS_OPERATOR_NODE,
1994                                        outerCR.getClone(),
1995                                        innerCR.getClone(),
1996                                        getContextManager());
1997                    newEquals.bindComparisonOperator();
1998                    /* Create the AND */
1999                    ValueNode trueNode = (ValueNode) getNodeFactory().getNode(
2000                                            C_NodeTypes.BOOLEAN_CONSTANT_NODE,
2001                                            Boolean.TRUE,
2002                                            getContextManager());
2003                    AndNode newAnd = (AndNode) getNodeFactory().getNode(
2004                                                        C_NodeTypes.AND_NODE,
2005                                                        newEquals,
2006                                                        trueNode,
2007                                                        getContextManager());
2008                    newAnd.postBindFixup();
2009                    // Add a new predicate to both the equijoin clauses and this list
2010                    JBitSet tableMap = new JBitSet(numTables);
2011                    newAnd.categorize(tableMap, false);
2012                    Predicate newPred = (Predicate) getNodeFactory().getNode(
2013                                                    C_NodeTypes.PREDICATE,
2014                                                    newAnd,
2015                                                    tableMap,
2016                                                    getContextManager());
2017                    newPred.setEquivalenceClass(outerEC);
2018                    addPredicate(newPred);
2019                    /* Add the new predicate right after the outer position
2020                     * so that we can follow all of the predicates in equivalence
2021                     * classes before those that do not yet have equivalence classes.
2022                     */
2023                    if (outerIndex != outerJCL.size() - 1)
2024                    {
2025                        outerJCL.insertElementAt(newPred, outerIndex + 1);
2026                    }
2027                    else
2028                    {
2029                        outerJCL.addElement(newPred);
2030                    }
2031                    innerJCL.addElement(newPred);
2032                }
2033            }
2034        }
2035    }
2036
2037     /**
2038      * Perform transitive closure on search clauses.  We build a
2039      * list of search clauses of the form:
2040      *     <ColumnReference> <RelationalOperator> [<ConstantNode>]
2041      * We also build a list of equijoin conditions of form:
2042      *     <ColumnReference1> = <ColumnReference2>
2043      * where both columns are from different tables in the same query block.
2044      * For each search clause in the list, we search the equijoin list to see
2045      * if there is an equijoin clause on the same column.  If so, then we 
2046      * search the search clause list for a search condition on the column 
2047      * being joined against with the same relation operator and constant.  If 
2048      * a match is found, then there is no need to add a new predicate.  
2049      * Otherwise, we add a new search condition on the column being joined 
2050      * with.  In either case, if the relational operator in the search
2051      * clause is an "=" then we mark the equijoin clause as being redundant.
2052      * Redundant equijoin clauses will be removed at the end of the search as 
2053      * they are * unnecessary.
2054      *
2055      * @param numTables            The number of tables in the query
2056      * @param hashJoinSpecified    Whether or not user specified a hash join
2057      *
2058      * @exception StandardException        Thrown on error
2059      */
2060     void searchClauseTransitiveClosure(int numTables, boolean hashJoinSpecified)
2061         throws StandardException
2062     {
2063        PredicateList   equijoinClauses = new PredicateList();
2064        PredicateList   searchClauses = new PredicateList();
2065        RelationalOperator  equalsNode = null;
2066
2067        int size = size();
2068        for (int index = 0; index < size; index++)
2069        {
2070            Predicate       predicate = (Predicate) elementAt(index);
2071            AndNode         andNode = predicate.getAndNode();
2072
2073            // Skip anything that's not a RelationalOperator
2074            if (! (andNode.getLeftOperand() instanceof RelationalOperator))
2075            {
2076                continue;
2077            }
2078
2079            RelationalOperator operator = (RelationalOperator) andNode.getLeftOperand();
2080            // Is this an equijoin?
2081            if (((ValueNode)operator).isBinaryEqualsOperatorNode())
2082            {
2083                BinaryRelationalOperatorNode equals = (BinaryRelationalOperatorNode) operator;
2084                // Remember any equals node for redundancy check at end
2085                equalsNode = equals;
2086                ValueNode left = equals.getLeftOperand();
2087                ValueNode right = equals.getRightOperand();
2088                if ((left instanceof ColumnReference && right instanceof ColumnReference))
2089                {
2090                    ColumnReference leftCR = (ColumnReference) left;
2091                    ColumnReference rightCR = (ColumnReference) right;
2092                    if (leftCR.getSourceLevel() == rightCR.getSourceLevel() &&
2093                        leftCR.getTableNumber() != rightCR.getTableNumber())
2094                    {
2095                        equijoinClauses.addElement(predicate);
2096                    }
2097                    continue;
2098                }
2099            }
2100
2101            // Is this a usable search clause?
2102            if (operator instanceof UnaryComparisonOperatorNode)
2103            {
2104                if (((UnaryComparisonOperatorNode) operator).getOperand() instanceof ColumnReference)
2105                {
2106                    searchClauses.addElement(predicate);
2107                }
2108                continue;
2109            }
2110            else if (operator instanceof BinaryComparisonOperatorNode)
2111            {
2112                BinaryComparisonOperatorNode bcon = (BinaryComparisonOperatorNode) operator;
2113                ValueNode left = bcon.getLeftOperand();
2114                ValueNode right = bcon.getRightOperand();
2115
2116                // RESOLVE: Consider using variant type of the expression, instead of
2117                // ConstantNode or ParameterNode in the future.
2118                if (left instanceof ColumnReference && 
2119                      (right instanceof ConstantNode || right instanceof ParameterNode))
2120                {
2121                    searchClauses.addElement(predicate);
2122                }
2123                else if (right instanceof ConstantNode && left instanceof ColumnReference)
2124                {
2125                    // put the ColumnReference on the left to simplify things
2126                    bcon.swapOperands();
2127                    searchClauses.addElement(predicate);
2128                }
2129                continue;
2130            }
2131        }
2132
2133        // Nothing to do if no search clauses or equijoin clauses
2134        if (equijoinClauses.size() == 0 || searchClauses.size() == 0)
2135        {
2136            return;
2137        }
2138
2139        /* Now we do the real work. 
2140         * NOTE: We can append to the searchClauses while walking
2141         * them, thus we cannot cache the value of size().
2142         */
2143        for (int scIndex = 0; scIndex < searchClauses.size(); scIndex++)
2144        {
2145            ColumnReference searchCR;
2146            DataValueDescriptor searchODV = null;
2147            RelationalOperator ro = (RelationalOperator)
2148                                        ((AndNode) 
2149                                            ((Predicate) searchClauses.elementAt(scIndex)).getAndNode()).getLeftOperand();
2150
2151            // Find the ColumnReference and constant value, if any, in the search clause
2152            if (ro instanceof UnaryComparisonOperatorNode)
2153            {
2154                searchCR = (ColumnReference) ((UnaryComparisonOperatorNode) ro).getOperand();
2155            }
2156            else
2157            {
2158                searchCR = (ColumnReference) ((BinaryComparisonOperatorNode) ro).getLeftOperand();
2159
2160                // Don't get value for parameterNode since not known yet.
2161                if (((BinaryComparisonOperatorNode) ro).getRightOperand() instanceof ConstantNode)
2162                {
2163                    ConstantNode currCN = (ConstantNode) ((BinaryComparisonOperatorNode) ro).getRightOperand();
2164                    searchODV = (DataValueDescriptor) currCN.getValue();
2165                }
2166                else searchODV = null;
2167            }
2168            // Cache the table and column numbers of searchCR
2169            int tableNumber = searchCR.getTableNumber();
2170            int colNumber = searchCR.getColumnNumber();
2171
2172            // Look for any equijoin clauses of interest
2173            int ejcSize = equijoinClauses.size();
2174            for (int ejcIndex = 0; ejcIndex < ejcSize; ejcIndex++)
2175            {
2176                /* Skip the current equijoin clause if it has already been used
2177                 * when adding a new search clause of the same type
2178                 * via transitive closure.
2179                 * NOTE: We check the type of the search clause instead of just the
2180                 * fact that a search clause was added because multiple search clauses
2181                 * can get added when preprocessing LIKE and BETWEEN.
2182                 */
2183                Predicate predicate = (Predicate) equijoinClauses.elementAt(ejcIndex);
2184                if (predicate.transitiveSearchClauseAdded(ro))
2185                {
2186                    continue;
2187                }
2188
2189                BinaryRelationalOperatorNode equals = (BinaryRelationalOperatorNode)
2190                                                    ((AndNode)
2191                                                        predicate.getAndNode()).getLeftOperand();
2192                ColumnReference leftCR = (ColumnReference) equals.getLeftOperand();
2193                ColumnReference rightCR = (ColumnReference) equals.getRightOperand();
2194                ColumnReference otherCR;
2195
2196                if (leftCR.getTableNumber() == tableNumber &&
2197                    leftCR.getColumnNumber() == colNumber)
2198                {
2199                    otherCR = rightCR;
2200                }
2201                else if (rightCR.getTableNumber() == tableNumber &&
2202                         rightCR.getColumnNumber() == colNumber)
2203                {
2204                    otherCR = leftCR;
2205                }
2206                else
2207                {
2208                    // this is not a matching equijoin clause
2209                    continue;
2210                }
2211
2212                /* At this point we've found a search clause and an equijoin that 
2213                 * are candidates for adding a new search clause via transitive
2214                 * closure.  Look to see if a matching search clause already
2215                 * exists on the other table.  If not, then add one.
2216                 * NOTE: In either case we mark the join clause has having added
2217                 * a search clause of this type to short circuit any future searches
2218                 */
2219                predicate.setTransitiveSearchClauseAdded(ro);
2220
2221                boolean match = false;
2222                ColumnReference searchCR2 = null;
2223                RelationalOperator ro2 = null;
2224                int scSize = searchClauses.size();
2225                for (int scIndex2 = 0; scIndex2 < scSize; scIndex2++)
2226                {
2227                    DataValueDescriptor currODV = null;
2228                    ro2 = (RelationalOperator)
2229                            ((AndNode) 
2230                                ((Predicate) searchClauses.elementAt(scIndex2)).getAndNode()).getLeftOperand();
2231
2232                    // Find the ColumnReference in the search clause
2233                    if (ro2 instanceof UnaryComparisonOperatorNode)
2234                    {
2235                        searchCR2 = (ColumnReference) ((UnaryComparisonOperatorNode) ro2).getOperand();
2236                    }
2237                    else
2238                    {
2239                        searchCR2 = (ColumnReference) ((BinaryComparisonOperatorNode) ro2).getLeftOperand();
2240                        if (((BinaryComparisonOperatorNode) ro2).getRightOperand() instanceof ConstantNode)
2241                        {
2242                            ConstantNode currCN = (ConstantNode) ((BinaryComparisonOperatorNode) ro2).getRightOperand();
2243                            currODV = (DataValueDescriptor) currCN.getValue();
2244                        }
2245                        else currODV = null;
2246                    }
2247
2248                    /* Is this a match? A match is a search clause with
2249                     * the same operator on the same column with a comparison against
2250                     * the same value.
2251                     */
2252                    if (searchCR2.getTableNumber() == otherCR.getTableNumber() &&
2253                        searchCR2.getColumnNumber() == otherCR.getColumnNumber() &&
2254                        ((currODV != null && searchODV != null && currODV.compare(searchODV) == 0) ||
2255                         (currODV == null && searchODV == null)) &&
2256                        ro2.getOperator() == ro.getOperator() &&
2257                        ro2.getClass().getName().equals(ro.getClass().getName()))
2258                    {
2259                        match = true;
2260                        break;
2261                    }
2262                }
2263
2264                // Add the new search clause if no match found
2265                if (! match)
2266                {
2267                    // Build a new predicate
2268                    RelationalOperator roClone = ro.getTransitiveSearchClause((ColumnReference) otherCR.getClone());
2269
2270                    /* Set type info for the operator node */
2271                    if (roClone instanceof BinaryComparisonOperatorNode)
2272                    {
2273                        ((BinaryComparisonOperatorNode) roClone).bindComparisonOperator();
2274                    }
2275                    else
2276                    {
2277                        ((UnaryComparisonOperatorNode) roClone).bindComparisonOperator();
2278                    }
2279
2280                    /* Create the AND */
2281                    ValueNode trueNode = (ValueNode) getNodeFactory().getNode(
2282                                            C_NodeTypes.BOOLEAN_CONSTANT_NODE,
2283                                            Boolean.TRUE,
2284                                            getContextManager());
2285                    AndNode newAnd = (AndNode) getNodeFactory().getNode(
2286                                                        C_NodeTypes.AND_NODE,
2287                                                        roClone,
2288                                                        trueNode,
2289                                                        getContextManager());
2290                    newAnd.postBindFixup();
2291                    // Add a new predicate to both the search clauses and this list
2292                    JBitSet tableMap = new JBitSet(numTables);
2293                    newAnd.categorize(tableMap, false);
2294                    Predicate newPred = (Predicate) getNodeFactory().getNode(
2295                                                        C_NodeTypes.PREDICATE,
2296                                                        newAnd,
2297                                                        tableMap,
2298                                                        getContextManager());
2299                    addPredicate(newPred);
2300                    searchClauses.addElement(newPred);
2301                }
2302            }
2303        }
2304
2305        /* Finally, we eliminate any equijoin clauses made redundant by 
2306         * transitive closure, but only if the user did not specify a hash join
2307         * in the current query block.
2308         */
2309        if (hashJoinSpecified)
2310        {
2311            return;
2312        }
2313
2314        /* Walk list backwards since we can delete while
2315         * traversing the list.
2316         */
2317        for (int index = size() - 1; index >= 0; index--)
2318        {
2319            Predicate predicate = (Predicate) elementAt(index);
2320
2321            if (predicate.transitiveSearchClauseAdded(equalsNode))
2322            {
2323                removeElementAt(index);
2324            }
2325        }
2326     }
2327
2328     /**
2329      * Remove redundant predicates.  A redundant predicate has an equivalence
2330      * class (!= -1) and there are other predicates in the same equivalence
2331      * class after it in the list.  (Actually, we remove all of the predicates
2332      * in the same equivalence class that appear after this one.)
2333      */
2334    void removeRedundantPredicates()
2335    {
2336        /* Walk backwards since we may remove 1 or more
2337         * elements for each predicate in the outer pass.
2338         */
2339        int outer = size() - 1;
2340        while (outer >= 0)
2341        {
2342            Predicate predicate = (Predicate) elementAt(outer);
2343            int equivalenceClass = predicate.getEquivalenceClass();
2344
2345            if (equivalenceClass == -1)
2346            {
2347                outer--;
2348                continue;
2349            }
2350
2351            // Walk the rest of the list backwards.
2352            for (int inner = outer - 1; inner >= 0; inner--)
2353            {
2354                Predicate innerPredicate = (Predicate) elementAt(inner);
2355                if (innerPredicate.getEquivalenceClass() == equivalenceClass)
2356                {
2357                    /* Only 1 predicate per column can be marked as a start
2358                     * and/or a stop position.
2359                     * When removing a redundant predicate, we need to make sure
2360                     * that the outer predicate gets marked as a start and/or
2361                     * stop key if the inner predicate is a start and/or stop
2362                     * key.  In this case, we are not changing the number of
2363                     * start and/or stop positions, so we leave that count alone.
2364                     */
2365                    if (innerPredicate.isStartKey())
2366                    {
2367                        predicate.markStartKey();
2368                    }
2369                    if (innerPredicate.isStopKey())
2370                    {
2371                        predicate.markStopKey();
2372                    }
2373                    if (innerPredicate.isStartKey() || innerPredicate.isStopKey())
2374                    {
2375                        if (innerPredicate.isQualifier())
2376                        {
2377                            // Bug 5868 - Query returns duplicate rows. In order to fix this,
2378                            // If the inner predicate is a qualifer along with being a start and/or stop,
2379                            // then mark the outer predicate as a qualifer too(along with marking it as a start
2380                            // and/or stop) if it is not already marked as qualifer and increment the qualifiers counter
2381                            // The reason we do this is that a start and/or stop key is not equivalent to
2382                            // a qualifier. In the orderUsefulPredicates method in this class(comment on line 786),
2383                            // we mark a start/stop as qualifier if we have already seen a previous column in composite
2384                            // index whose RELOPS do not include '=' or IS NULL. And hence we should not disregard
2385                            // the qualifier flag of inner predicate
2386                            if (!predicate.isQualifier())
2387                            {
2388                                predicate.markQualifier();
2389                                numberOfQualifiers++;
2390                            }
2391                        }
2392                    }
2393                    /* 
2394                     * If the redundant predicate is a qualifier, then we must
2395                     * decrement the qualifier count.  (Remaining predicate is
2396                     * already marked correctly.)
2397                     */
2398                    if (innerPredicate.isQualifier())
2399                    {
2400                        numberOfQualifiers--;
2401                    }
2402                    removeElementAt(inner);
2403                    outer--;
2404                }
2405            }
2406
2407            outer--;
2408        }
2409    }
2410
2411    /**
2412     * @see OptimizablePredicateList#transferPredicates
2413     *
2414     * @exception StandardException     Thrown on error
2415     */
2416    public void transferPredicates(OptimizablePredicateList otherList,
2417                                    JBitSet referencedTableMap,
2418                                    Optimizable table)
2419        throws StandardException
2420    {
2421        Predicate       predicate;
2422        PredicateList   theOtherList = (PredicateList) otherList;
2423
2424        /* Walk list backwards since we can delete while
2425         * traversing the list.
2426         */
2427        for (int index = size() - 1; index >= 0; index--)
2428        {
2429            predicate = (Predicate) elementAt(index);
2430
2431            if (SanityManager.DEBUG)
2432            {
2433                if (referencedTableMap.size() != predicate.getReferencedSet().size())
2434                {
2435                    SanityManager.THROWASSERT(
2436                        "referencedTableMap.size() (" + referencedTableMap.size() + 
2437                        ") does not equal predicate.getReferencedSet().size() (" +
2438                        predicate.getReferencedSet().size());
2439                }
2440            }
2441
2442            if (referencedTableMap.contains(predicate.getReferencedSet()))
2443            {
2444                // We need to keep the counters up to date when removing a predicate
2445                if (predicate.isStartKey())
2446                    numberOfStartPredicates--;
2447                if (predicate.isStopKey())
2448                    numberOfStopPredicates--;
2449                if (predicate.isQualifier())
2450                    numberOfQualifiers--;
2451
2452                /* Clear all of the scan flags since they may be different
2453                 * due to the splitting of the list.
2454                 */
2455                predicate.clearScanFlags();
2456                // Do the actual xfer
2457                theOtherList.addPredicate(predicate);
2458                removeElementAt(index);
2459            }
2460        }
2461
2462        // order the useful predicates on the other list
2463        AccessPath ap = table.getTrulyTheBestAccessPath();
2464        theOtherList.orderUsefulPredicates(
2465                                    table,
2466                                    ap.getConglomerateDescriptor(),
2467                                    false,
2468                                    ap.getNonMatchingIndexScan(),
2469                                    ap.getCoveringIndexScan());
2470
2471        // count the start/stop positions and qualifiers
2472        theOtherList.countScanFlags();
2473    }
2474
2475    /**
2476     * @see OptimizablePredicateList#transferAllPredicates
2477     *
2478     * @exception StandardException     Thrown on error
2479     */
2480    public void transferAllPredicates(OptimizablePredicateList otherList)
2481        throws StandardException
2482    {
2483        PredicateList   theOtherList = (PredicateList) otherList;
2484
2485        int size = size();
2486        for (int index = 0; index < size; index++)
2487        {
2488            Predicate predicate = (Predicate) elementAt(index);
2489
2490            /*
2491            ** Clear all of the scan flags since they may be different
2492            ** when the new list is re-classified
2493            */
2494            predicate.clearScanFlags();
2495
2496            // Add the predicate to the other list
2497            theOtherList.addPredicate(predicate);
2498        }
2499
2500        // Remove all of the predicates from this list
2501        removeAllElements();
2502
2503        /*
2504        ** This list is now empty, so there are no start predicates,
2505        ** stop predicates, or qualifiers.
2506        */
2507        numberOfStartPredicates = 0;
2508        numberOfStopPredicates = 0;
2509        numberOfQualifiers= 0;
2510    }
2511
2512    /**
2513     * @see OptimizablePredicateList#copyPredicatesToOtherList
2514     *
2515     * @exception StandardException     Thrown on error
2516     */
2517    public void copyPredicatesToOtherList(OptimizablePredicateList otherList)
2518        throws StandardException
2519    {
2520        for (int i = 0; i < size(); i++)
2521        {
2522            otherList.addOptPredicate(getOptPredicate(i));
2523        }
2524    }
2525
2526    /**
2527     * @see OptimizablePredicateList#isRedundantPredicate
2528     */
2529    public boolean isRedundantPredicate(int predNum)
2530    {
2531        Predicate pred = (Predicate) elementAt(predNum);
2532        if (pred.getEquivalenceClass() == -1)
2533        {
2534            return false;
2535        }
2536        for (int index = 0; index < predNum; index++)
2537        {
2538            if ( ((Predicate) elementAt(index)).getEquivalenceClass() == pred.getEquivalenceClass())
2539            {
2540                return true;
2541            }
2542        }
2543        return false;
2544    }
2545
2546    /**
2547     * @see OptimizablePredicateList#setPredicatesAndProperties
2548     *
2549     * @exception StandardException     Thrown on error
2550     */
2551    public void setPredicatesAndProperties(OptimizablePredicateList otherList)
2552        throws StandardException
2553    {
2554        PredicateList theOtherList = (PredicateList) otherList;
2555
2556        theOtherList.removeAllElements();
2557
2558        for (int i = 0; i < size(); i++)
2559        {
2560            theOtherList.addOptPredicate(getOptPredicate(i));
2561        }
2562
2563        theOtherList.numberOfStartPredicates = numberOfStartPredicates;
2564        theOtherList.numberOfStopPredicates = numberOfStopPredicates;
2565        theOtherList.numberOfQualifiers = numberOfQualifiers;
2566    }
2567
2568    /** @see OptimizablePredicateList#startOperator */
2569    public int startOperator(Optimizable optTable)
2570    {
2571        int startOperator;
2572
2573        /*
2574        ** This is the value we will use if there are no keys.  It doesn't
2575        ** matter what it is, as long as the operator is one of GT or GE
2576        ** (to match the openScan() interface).
2577        */
2578        startOperator = ScanController.GT;
2579
2580        int size = size();
2581        /* beetle 4572. start operator should be the last start key column's
2582         * start operator.  Note that all previous ones should be GE.
2583         */
2584        for (int index = size - 1; index >= 0; index--)
2585        {
2586            Predicate pred = ((Predicate) elementAt(index));
2587
2588            if ( ! pred.isStartKey() )
2589                continue;
2590
2591            startOperator = pred.getStartOperator(optTable);
2592            break;
2593        }
2594        return startOperator;
2595    }
2596
2597    /**
2598     * @see OptimizablePredicateList#generateStopKey
2599     *
2600     * @exception StandardException     Thrown on error
2601     */
2602    public void generateStopKey(ExpressionClassBuilderInterface acbi,
2603                                MethodBuilder mb,
2604                                Optimizable optTable)
2605                throws StandardException
2606    {
2607        ExpressionClassBuilder acb = (ExpressionClassBuilder) acbi;
2608
2609        /*
2610        ** To make the stop-key allocating function we cycle through
2611        ** the Predicates and generate the function and initializer:
2612        **
2613        ** private ExecIndexRow exprN()
2614        ** { ExecIndexRow r = getExecutionFactory().getIndexableRow(# stop keys);
2615        **   for (pred = each predicate in list)
2616        **   {
2617        **      if (pred.isStartKey())
2618        **      {
2619        **          pred.generateKey(acb);
2620        **      }
2621        **   }
2622        ** }
2623        **
2624        ** If there are no start predicates, we do not generate anything.
2625        */
2626
2627        if (numberOfStopPredicates != 0)
2628        {
2629            /* This sets up the method and the static field */
2630            MethodBuilder exprFun = acb.newExprFun();
2631
2632            /* Now we fill in the body of the method */
2633            LocalField rowField = 
2634                generateIndexableRow(acb, numberOfStopPredicates);
2635
2636            int colNum = 0;
2637            int size = size();
2638            for (int index = 0; index < size; index++)
2639            {
2640                Predicate pred = ((Predicate) elementAt(index));
2641
2642                if ( ! pred.isStopKey() )
2643                    continue;
2644
2645                generateSetColumn(acb, exprFun, colNum,
2646                                    pred, optTable, rowField, false);
2647
2648                colNum++;
2649            }
2650
2651            if (SanityManager.DEBUG)
2652            {
2653                SanityManager.ASSERT(colNum == numberOfStopPredicates,
2654                    "Number of stop predicates does not match");
2655            }
2656
2657            finishKey(acb, mb, exprFun, rowField);
2658            return;
2659        }
2660
2661        mb.pushNull(ClassName.GeneratedMethod);
2662    }
2663
2664    /** @see OptimizablePredicateList#stopOperator */
2665    public int stopOperator(Optimizable optTable)
2666    {
2667        int stopOperator;
2668
2669        /*
2670        ** This is the value we will use if there are no keys.  It doesn't
2671        ** matter what it is, as long as the operator is one of GT or GE
2672        ** (to match the openScan() interface).
2673        */
2674        stopOperator = ScanController.GT;
2675
2676        int size = size();
2677        /* beetle 4572. stop operator should be the last start key column's
2678         * stop operator.  Note that all previous ones should be GT.
2679         */
2680        for (int index = size - 1; index >= 0; index--)
2681        {
2682            Predicate pred = ((Predicate) elementAt(index));
2683
2684            if ( ! pred.isStopKey() )
2685                continue;
2686
2687            stopOperator = pred.getStopOperator(optTable);
2688            break;
2689        }
2690        return stopOperator;
2691    }
2692
2693    private void generateSingleQualifierCode(
2694    MethodBuilder           consMB,
2695    Optimizable             optTable,
2696    boolean                 absolute,
2697    ExpressionClassBuilder  acb,
2698    RelationalOperator      or_node,
2699    LocalField              qualField,
2700    int                     array_idx_1,
2701    int                     array_idx_2)
2702        throws StandardException
2703    {
2704        consMB.getField(qualField); // first arg for setQualifier
2705
2706        // get instance for getQualifier call
2707        consMB.pushThis();
2708        consMB.callMethod(
2709            VMOpcode.INVOKEVIRTUAL, 
2710            acb.getBaseClassName(), 
2711            "getExecutionFactory", ExecutionFactory.MODULE, 0);
2712        
2713        // Column Id - first arg
2714        if (absolute)
2715            or_node.generateAbsoluteColumnId(consMB, optTable); 
2716        else
2717            or_node.generateRelativeColumnId(consMB, optTable);
2718
2719        // Operator - second arg
2720        or_node.generateOperator(consMB, optTable);
2721
2722        // Method to evaluate qualifier -- third arg
2723        or_node.generateQualMethod(acb, consMB, optTable);
2724
2725        // Receiver for above method - fourth arg
2726        acb.pushThisAsActivation(consMB);
2727
2728        // Ordered Nulls? - fifth arg
2729        or_node.generateOrderedNulls(consMB);
2730
2731
2732        /*
2733        ** "Unknown" return value. For qualifiers,
2734        ** we never want to return rows where the
2735        ** result of a comparison is unknown.
2736        ** But we can't just generate false, because
2737        ** the comparison result could be negated.
2738        ** So, generate the same as the negation
2739        ** operand - that way, false will not be
2740        ** negated, and true will be negated to false.
2741        */
2742        or_node.generateNegate(consMB, optTable);
2743
2744        /* Negate comparison result? */
2745        or_node.generateNegate(consMB, optTable);
2746
2747        /* variantType for qualifier's orderable */
2748        consMB.push(or_node.getOrderableVariantType(optTable));
2749
2750        consMB.callMethod(
2751            VMOpcode.INVOKEINTERFACE, 
2752            ExecutionFactory.MODULE, 
2753            "getQualifier", ClassName.Qualifier, 8);
2754
2755        // result of getQualifier() is second arg for setQualifier
2756
2757        consMB.push(array_idx_1);       // third  arg for setQualifier
2758        consMB.push(array_idx_2);       // fourth arg for setQualifier
2759
2760        consMB.callMethod(
2761            VMOpcode.INVOKESTATIC, 
2762            acb.getBaseClassName(), 
2763            "setQualifier", "void", 4);
2764    }
2765
2766    /**
2767     * @see OptimizablePredicateList#generateQualifiers
2768     *
2769     * @exception StandardException     Thrown on error
2770     */
2771    public void generateQualifiers(
2772    ExpressionClassBuilderInterface acbi,
2773    MethodBuilder mb,
2774    Optimizable optTable,
2775    boolean absolute)
2776        throws StandardException
2777    {
2778        ExpressionClassBuilder  acb         = (ExpressionClassBuilder) acbi;
2779
2780        String                    retvalType  = ClassName.Qualifier + "[][]";
2781        MethodBuilder           consMB      = acb.getConstructor();
2782        MethodBuilder           executeMB   = acb.getExecuteMethod();
2783
2784        /* Create and initialize the array of Qualifiers */
2785        LocalField qualField = 
2786            acb.newFieldDeclaration(Modifier.PRIVATE, retvalType);
2787
2788
2789        /* 
2790        ** Stick a reinitialize of the Qualifier array in execute().
2791        ** Done because although we call Exec/Qualifier.clearOrderableCache() 
2792        ** before each query, we only clear the cache for VARIANT and
2793        ** SCAN_INVARIANT qualifiers.  However, each time the same
2794        ** statement is executed, even the QUERY_INVARIANT qualifiers
2795        ** need to be flushed.  For example:
2796        **  prepare select c1 from t where c1 = (select max(c1) from t) as p;
2797        **  execute p; -- we now have the materialized subquery result (1) 
2798        **             -- in our predicate
2799        **  insert into t values 666;
2800        **  execute p; -- we need to clear out 1 and recache the subq result
2801        */
2802
2803        // PUSHCOMPILER
2804//      if (mb == executeMB) {
2805//          System.out.println("adding code to method in two places");
2806//          new Throwable().printStackTrace();
2807//      }
2808//
2809
2810        // generate code to reinitializeQualifiers(Qualifier[][] qualifiers)
2811        executeMB.getField(qualField); // first arg to reinitializeQualifiers()
2812        executeMB.callMethod(
2813            VMOpcode.INVOKESTATIC, 
2814            acb.getBaseClassName(), "reinitializeQualifiers", "void", 1);
2815
2816        /*
2817        ** Initialize the Qualifier array to a new Qualifier[][] if
2818        ** there are any qualifiers.  It is automatically initialized to
2819        ** null if it isn't explicitly initialized.
2820        */
2821        if (numberOfQualifiers != 0)
2822        {
2823            if (SanityManager.DEBUG)
2824            {
2825                if (numberOfQualifiers > size())
2826                {
2827                    SanityManager.THROWASSERT(
2828                        "numberOfQualifiers(" + numberOfQualifiers + 
2829                        ") > size(" + size() + ")." + ":" +  this.hashCode());
2830                }
2831            }
2832
2833            // Determine number of leading AND qualifiers, and subsequent
2834            // trailing OR qualifiers.
2835            int num_of_or_conjunctions = 0;
2836            for (int i = 0; i < numberOfQualifiers; i++)
2837            {
2838                if (((Predicate) elementAt(i)).isOrList())
2839                {
2840                    num_of_or_conjunctions++;
2841                }
2842            }
2843
2844            
2845            /* Assign the initializer to the Qualifier[] field */
2846            consMB.pushNewArray(
2847                ClassName.Qualifier + "[]", (int) num_of_or_conjunctions + 1);
2848            consMB.setField(qualField);
2849
2850            // Allocate qualifiers[0] which is an entry for each of the leading
2851            // AND clauses.
2852
2853            consMB.getField(qualField);             // 1st arg allocateQualArray
2854            consMB.push((int) 0);                   // 2nd arg allocateQualArray
2855            consMB.push((int) numberOfQualifiers - num_of_or_conjunctions);  // 3rd arg allocateQualArray
2856
2857            consMB.callMethod(
2858                VMOpcode.INVOKESTATIC, 
2859                acb.getBaseClassName(), 
2860                "allocateQualArray", "void", 3);
2861        }
2862
2863        /* Sort the qualifiers by "selectivity" before generating.
2864         * We want the qualifiers ordered by selectivity with the
2865         * most selective ones first.  There are 3 groups of qualifiers:
2866         * = and IS NULL are the most selective,
2867         * <> and IS NOT NULL are the least selective and
2868         * all of the other RELOPs are in between.
2869         * We break the list into 4 parts (3 types of qualifiers and
2870         * then everything else) and then rebuild the ordered list.
2871         * RESOLVE - we will eventually want to order the qualifiers
2872         * by (column #, selectivity) once the store does just in time
2873         * instantiation.
2874         */
2875        if (numberOfQualifiers > 0)
2876        {
2877            orderQualifiers();
2878        }
2879
2880        /* Generate each of the qualifiers, if any */
2881
2882        // First generate the "leading" AND qualifiers.
2883        int qualNum = 0;
2884        int size = size();
2885        boolean gotOrQualifier = false;
2886
2887        for (int index = 0; index < size; index++)
2888        {
2889
2890            Predicate pred = ((Predicate) elementAt(index));
2891
2892            if (!pred.isQualifier())
2893            {
2894                continue;
2895            }
2896            else if (pred.isOrList())
2897            {
2898                gotOrQualifier = true;
2899
2900                // will generate the OR qualifiers below.
2901                break;
2902            }
2903            else
2904            {
2905                generateSingleQualifierCode(
2906                        consMB,
2907                        optTable,
2908                        absolute,
2909                        acb,
2910                        pred.getRelop(),
2911                        qualField,
2912                        0,
2913                        qualNum);
2914
2915                qualNum++;
2916            }
2917        }
2918
2919        if (gotOrQualifier)
2920        {
2921
2922            // process each set of or's into a list which are AND'd.  Each
2923            // predicate will become an array list in the qualifier array of
2924            // array's.
2925            //
2926            // The first list of And's went into qual[0][0...N]
2927            // Now each subquent predicate is actually a list of OR's so
2928            // will be passed as:
2929            //     1st OR predicate -> qual[1][0.. number of OR terms]
2930            //     2nd OR predicate -> qual[2][0.. number of OR terms]
2931            //     ...
2932            //
2933            int and_idx = 1;
2934
2935            // The remaining qualifiers must all be OR predicates, which
2936            // are pushed slightly differently than the leading AND qualifiers.
2937
2938            for (int index = qualNum; index < size; index++, and_idx++)
2939            {
2940
2941                Predicate pred = ((Predicate) elementAt(index));
2942
2943                if (SanityManager.DEBUG)
2944                {
2945                    SanityManager.ASSERT(pred.isOrList());
2946                }
2947
2948                // create an ArrayList of the OR nodes.  We need the count
2949                // of Or's in order to first generate the allocateQualArray()
2950                // call, then we walk the list assigning each of the OR's to
2951                // entries in the array in generateSingleQualifierCode().
2952                ArrayList   a_list = new ArrayList  ();
2953
2954                QueryTreeNode node = pred.getAndNode().getLeftOperand();
2955
2956                while (node instanceof OrNode)
2957                {
2958                    OrNode or_node = (OrNode) node;
2959
2960                    // The left operand of OR node is one of the terms, 
2961                    // (ie. A = 1)
2962                    if (or_node.getLeftOperand() instanceof RelationalOperator)
2963                    {
2964                        a_list.add(or_node.getLeftOperand());
2965                    }
2966
2967                    // The next OR node in the list if linked to the right.
2968                    node = or_node.getRightOperand();
2969                }
2970
2971                // Allocate an array to hold each of the terms of this OR, 
2972                // clause.  ie. (a = 1 or b = 2), will allocate a 2 entry array.
2973
2974                consMB.getField(qualField);        // 1st arg allocateQualArray
2975                consMB.push((int) and_idx);        // 2nd arg allocateQualArray
2976                consMB.push((int) a_list.size());  // 3rd arg allocateQualArray
2977
2978                consMB.callMethod(
2979                    VMOpcode.INVOKESTATIC, 
2980                    acb.getBaseClassName(), 
2981                    "allocateQualArray", "void", 3);
2982
2983                
2984                // finally transfer the nodes to the 2-d qualifier
2985                for (int i = 0; i < a_list.size(); i++)
2986                {
2987                    generateSingleQualifierCode(
2988                            consMB,
2989                            optTable,
2990                            absolute,
2991                            acb,
2992                            (RelationalOperator) a_list.get(i),
2993                            qualField,
2994                            and_idx,
2995                            i);
2996
2997                }
2998
2999                qualNum++;
3000            }
3001
3002        }
3003
3004        if (SanityManager.DEBUG)
3005        {
3006            SanityManager.ASSERT(qualNum == numberOfQualifiers,
3007                qualNum + " Qualifiers found, " +
3008                numberOfQualifiers + " expected.");
3009        }
3010
3011        /*
3012        ** Return a reference to the field that holds the initialized
3013        ** array of Qualifiers.
3014        */
3015        mb.getField(qualField);
3016    }
3017
3018
3019    /* Sort the qualifiers by "selectivity" before generating.
3020     * We want the qualifiers ordered by selectivity with the
3021     * most selective ones first.  There are 3 groups of qualifiers:
3022     * = and IS NULL are the most selective,
3023     * <> and IS NOT NULL are the least selective and
3024     * all of the other RELOPs are in between.
3025     * We break the list into 4 parts (3 types of qualifiers and
3026     * then everything else) and then rebuild the ordered list.
3027     * RESOLVE - we will eventually want to order the qualifiers
3028     * by (column #, selectivity) once the store does just in time
3029     * instantiation.
3030     */
3031    private static final int    QUALIFIER_ORDER_EQUALS      = 0;
3032    private static final int    QUALIFIER_ORDER_OTHER_RELOP = 1;
3033    private static final int    QUALIFIER_ORDER_NOT_EQUALS  = 2;
3034    private static final int    QUALIFIER_ORDER_NON_QUAL    = 3;
3035    private static final int    QUALIFIER_ORDER_OR_CLAUSE   = 4;
3036    private static final int    QUALIFIER_NUM_CATEGORIES    = 5;
3037    private void orderQualifiers()
3038    {
3039        // Sort the predicates into buckets, sortList[0] is the most 
3040        // selective, while sortList[4] is the least restrictive.
3041        //
3042        //     sortList[0]:  "= and IS NULL"
3043        //     sortList[1]:  "a set of OR'd conjunctions"
3044        //     sortList[2]:  "all other relop's"
3045        //     sortList[3]:  "<> and IS NOT NULL"
3046        //     sortList[4]:  "everything else"
3047        PredicateList[] sortList = new PredicateList[QUALIFIER_NUM_CATEGORIES];
3048
3049        for (int i = sortList.length - 1; i >= 0; i--)
3050            sortList[i] = new PredicateList();
3051
3052        int predIndex;
3053        int size = size();
3054        for (predIndex = 0; predIndex < size; predIndex++)
3055        {
3056            Predicate pred = (Predicate) elementAt(predIndex);
3057
3058            if (! pred.isQualifier())
3059            {
3060                sortList[QUALIFIER_ORDER_NON_QUAL].addElement(pred);
3061                continue;
3062            }
3063
3064            AndNode node = pred.getAndNode();
3065
3066            if (!(node.getLeftOperand() instanceof OrNode))
3067            {
3068                RelationalOperator relop = 
3069                    (RelationalOperator) node.getLeftOperand();
3070
3071                int op = relop.getOperator();
3072
3073                switch (op)
3074                {
3075                    case RelationalOperator.EQUALS_RELOP:
3076                    case RelationalOperator.IS_NULL_RELOP:
3077                        sortList[QUALIFIER_ORDER_EQUALS].addElement(pred);
3078                        break;
3079
3080                    case RelationalOperator.NOT_EQUALS_RELOP:
3081                    case RelationalOperator.IS_NOT_NULL_RELOP:
3082                        sortList[QUALIFIER_ORDER_NOT_EQUALS].addElement(pred);
3083                        break;
3084
3085                    default:
3086                        sortList[QUALIFIER_ORDER_OTHER_RELOP].addElement(pred);
3087                }
3088            }
3089            else
3090            {
3091                sortList[QUALIFIER_ORDER_OR_CLAUSE].addElement(pred);
3092            }
3093        }
3094
3095        /* Rebuild the list */
3096        predIndex = 0;
3097
3098        for (int index = 0; index < QUALIFIER_NUM_CATEGORIES; index++)
3099        {
3100            for (int items = 0; items < sortList[index].size(); items++)
3101            {
3102                setElementAt(sortList[index].elementAt(items), predIndex++);
3103            }
3104        }
3105    }
3106
3107    /**
3108     * @see OptimizablePredicateList#generateStartKey
3109     *
3110     * @exception StandardException     Thrown on error
3111     */
3112    public void generateStartKey(ExpressionClassBuilderInterface acbi,
3113                                MethodBuilder mb,
3114                                Optimizable optTable)
3115                throws StandardException
3116    {
3117        ExpressionClassBuilder acb = (ExpressionClassBuilder) acbi;
3118
3119        /*
3120        ** To make the start-key allocating function we cycle through
3121        ** the Predicates and generate the function and initializer:
3122        **
3123        ** private Object exprN()
3124        ** { ExecIndexRow r = getExecutionFactory().getIndexableRow(# start keys);
3125        **   for (pred = each predicate in list)
3126        **   {
3127        **      if (pred.isStartKey())
3128        **      {
3129        **          pred.generateKey(acb);
3130        **      }
3131        **   }
3132        ** }
3133        **
3134        ** If there are no start predicates, we do not generate anything.
3135        */
3136
3137        if (numberOfStartPredicates != 0)
3138        {
3139            /* This sets up the method and the static field */
3140            MethodBuilder exprFun = acb.newExprFun();
3141
3142            /* Now we fill in the body of the method */
3143            LocalField rowField = generateIndexableRow(acb, numberOfStartPredicates);
3144
3145            int colNum = 0;
3146            int size = size();
3147            for (int index = 0; index < size; index++)
3148            {
3149                Predicate pred = ((Predicate) elementAt(index));
3150
3151                if ( ! pred.isStartKey() )
3152                    continue;
3153
3154                generateSetColumn(acb, exprFun, colNum,
3155                                    pred, optTable, rowField, true);
3156
3157                colNum++;
3158            }
3159
3160            if (SanityManager.DEBUG)
3161            {
3162                SanityManager.ASSERT(colNum == numberOfStartPredicates,
3163                    "Number of start predicates does not match");
3164            }
3165
3166            finishKey(acb, mb, exprFun, rowField);
3167            return;
3168        }
3169
3170        mb.pushNull(ClassName.GeneratedMethod);
3171    }
3172
3173    /**
3174     * @see OptimizablePredicateList#sameStartStopPosition
3175     *
3176     * @exception StandardException     Thrown on error
3177     */
3178    public boolean sameStartStopPosition()
3179        throws StandardException
3180    {
3181        /* We can only use the same row for both the
3182         * start and stop positions if the number of
3183         * start and stop predicates are the same.
3184         */
3185        if (numberOfStartPredicates != numberOfStopPredicates)
3186        {
3187            return false;
3188        }
3189
3190        /* We can only use the same row for both the
3191         * start and stop positions when a predicate is
3192         * a start key iff it is a stop key.
3193         */
3194        int size = size();
3195        for (int index = 0; index < size; index++)
3196        {
3197            Predicate pred = ((Predicate) elementAt(index));
3198
3199            if ( (pred.isStartKey() && (! pred.isStopKey())) ||
3200                 (pred.isStopKey() && (! pred.isStartKey())))
3201            {
3202                return false;
3203            }
3204            /* "in"'s dynamic start and stop key are not the same, beetle 3858
3205             */
3206            if (pred.getAndNode().getLeftOperand() instanceof InListOperatorNode)
3207                return false;
3208        }
3209
3210        return true;
3211    }
3212
3213    /**
3214     * Generate the indexable row for a start key or stop key.
3215     *
3216     * @param acb   The ActivationClassBuilder for the class we're building
3217     * @param numberOfColumns   The number of columns in the key
3218     *
3219     * @return  The field that holds the indexable row
3220     */
3221    private LocalField generateIndexableRow(ExpressionClassBuilder acb, int numberOfColumns)
3222    {
3223        MethodBuilder mb = acb.getConstructor();
3224        /*
3225        ** Generate a call to get an indexable row
3226        ** with the given number of columns
3227        */
3228        acb.pushGetExecutionFactoryExpression(mb); // instance
3229        mb.push(numberOfColumns);
3230        mb.callMethod(VMOpcode.INVOKEINTERFACE, ClassName.ExecutionFactory, "getIndexableRow", ClassName.ExecIndexRow, 1);
3231
3232        /*
3233        ** Assign the indexable row to a field, and put this assignment into
3234        ** the constructor for the activation class.  This way, we only have
3235        ** to get the row once.
3236        */
3237        LocalField field =
3238            acb.newFieldDeclaration(Modifier.PRIVATE, ClassName.ExecIndexRow);
3239        
3240        mb.setField(field);
3241
3242        return field;
3243    }
3244
3245    /**
3246     * Generate the code to set the value from a predicate in an index column.
3247     *
3248     * @param acb   The ActivationClassBuilder for the class we're building
3249     * @param exprFun   The MethodBuilder for the method we're building
3250     * @param columnNumber  The position number of the column we're setting
3251     *                      the value in (zero-based)
3252     * @param pred  The Predicate with the value to put in the index column
3253     * @param optTable  The Optimizable table the column is in
3254     * @param rowField  The field that holds the indexable row
3255     * @param isStartKey Are we generating start or stop key?  This information
3256     *                   is useful for "in"'s dynamic start/stop key, bug 3858
3257     *
3258     * @exception StandardException     Thrown on error
3259     */
3260    private void generateSetColumn(ExpressionClassBuilder acb,
3261                                    MethodBuilder exprFun,
3262                                    int columnNumber,
3263                                    Predicate pred,
3264                                    Optimizable optTable,
3265                                    LocalField rowField,
3266                                    boolean isStartKey)
3267            throws StandardException
3268    {
3269        MethodBuilder mb;
3270        
3271        /* Code gets generated in constructor if comparison against
3272         * a constant, otherwise gets generated in the current
3273         * statement block.
3274         */
3275        boolean withKnownConstant = false;
3276        if (pred.compareWithKnownConstant(optTable, false))
3277        {
3278            withKnownConstant = true;
3279            mb = acb.getConstructor();
3280        }
3281        else
3282        {
3283            mb = exprFun;
3284        }
3285
3286        int[]   baseColumns = optTable.getTrulyTheBestAccessPath().
3287                                getConglomerateDescriptor().
3288                                    getIndexDescriptor().baseColumnPositions();
3289        boolean[]   isAscending = optTable.getTrulyTheBestAccessPath().
3290                                getConglomerateDescriptor().
3291                                    getIndexDescriptor().isAscending();
3292        boolean isIn = pred.getAndNode().getLeftOperand() instanceof InListOperatorNode;
3293
3294        /*
3295        ** Generate statements of the form
3296        **
3297        ** r.setColumn(columnNumber, columnExpression);
3298        **
3299        ** and put the generated statement in the allocator function.
3300        */
3301        mb.getField(rowField);
3302        mb.push(columnNumber + 1);
3303
3304        // second arg
3305        if (isIn)
3306        {
3307            InListOperatorNode inNode = (InListOperatorNode) pred.getAndNode().getLeftOperand();
3308            inNode.generateStartStopKey(isAscending[columnNumber], isStartKey, acb, mb);
3309        }
3310        else
3311            pred.generateExpressionOperand(optTable, baseColumns[columnNumber], acb, mb);
3312
3313        mb.upCast(ClassName.DataValueDescriptor);
3314
3315        mb.callMethod(VMOpcode.INVOKEINTERFACE, ClassName.Row, "setColumn", "void", 2);
3316
3317        /* Also tell the row if this column uses ordered null semantics */
3318        if (!isIn)
3319        {
3320            RelationalOperator relop = pred.getRelop();
3321            boolean setOrderedNulls = relop.orderedNulls();
3322
3323            /* beetle 4464, performance work.  If index column is not nullable 
3324             * (which is frequent), we should treat it as though nulls are 
3325             * ordered (indeed because they don't exist) so that we do not have
3326             * to check null at scan time for each row, each column.  This is 
3327             * an overload to "is null" operator, so that we have less overhead,
3328             * provided that they don't interfere.  It doesn't interfere if it 
3329             * doesn't overload if key is null.  If key is null, but operator
3330             * is not orderedNull type (is null), skipScan will use this flag 
3331             * (false) to skip scan.
3332             */
3333            if ((! setOrderedNulls) && 
3334                 ! relop.getColumnOperand(optTable).getTypeServices().isNullable())
3335            {
3336                if (withKnownConstant)
3337                    setOrderedNulls = true;
3338                else
3339                {
3340                    ValueNode keyExp = 
3341                        relop.getExpressionOperand(
3342                            optTable.getTableNumber(), 
3343                            baseColumns[columnNumber],
3344                            (FromTable)optTable);
3345
3346                    if (keyExp instanceof ColumnReference)
3347                        setOrderedNulls = 
3348                            ! ((ColumnReference) keyExp).getTypeServices().isNullable();
3349                }
3350            }
3351            if (setOrderedNulls)
3352            {
3353                mb.getField(rowField);
3354                mb.push(columnNumber);
3355                mb.callMethod(VMOpcode.INVOKEINTERFACE, ClassName.ExecIndexRow, "orderedNulls", "void", 1);
3356            }
3357        }
3358    }
3359
3360    /**
3361     * Finish generating a start or stop key
3362     *
3363     * @param acb   The ActivationClassBuilder for the class we're building
3364     * @param exprFun   The MethodBuilder for the method we're building
3365     * @param rowField  The name of the field that holds the indexable row
3366     */
3367    private void finishKey(ExpressionClassBuilder acb,
3368                                MethodBuilder mb,
3369                                MethodBuilder exprFun,
3370                                LocalField rowField)
3371    {
3372        /* Generate return statement and add to exprFun */
3373        exprFun.getField(rowField);
3374        exprFun.methodReturn();
3375        /* We are done putting stuff in exprFun */
3376        exprFun.complete();
3377
3378        /*
3379        ** What we use is the access of the static field,
3380        ** i.e. the pointer to the method.
3381        */
3382        acb.pushMethodReference(mb, exprFun);
3383    }
3384
3385    /* Class implementation */
3386    boolean constantColumn(ColumnReference colRef)
3387    {
3388        boolean retval = false;
3389
3390        /*
3391        ** Walk this list
3392        */
3393        int size = size();
3394        for (int index = 0; index < size; index++)
3395        {
3396            Predicate   pred = (Predicate) elementAt(index);
3397            RelationalOperator relop = pred.getRelop();
3398
3399            if (relop != null)
3400            {
3401                if (relop.getOperator() == RelationalOperator.EQUALS_RELOP)
3402                {
3403                    ValueNode exprOp = relop.getOperand(
3404                                    colRef,
3405                                    pred.getReferencedSet().size(),
3406                                    true
3407                                    );
3408
3409                    if (exprOp != null)
3410                    {
3411                        if (exprOp.isConstantExpression())
3412                        {
3413                            retval = true;
3414                            break;
3415                        }
3416                    }
3417                }
3418                else if (relop.getOperator() ==
3419                                            RelationalOperator.IS_NULL_RELOP)
3420                {
3421                    ColumnReference columnOp = 
3422                        (ColumnReference)relop.getOperand(
3423                                        colRef,
3424                                        pred.getReferencedSet().size(),
3425                                        false
3426                                        );
3427
3428                    if (columnOp != null)
3429                    {
3430                        retval = true;
3431                    }
3432                }
3433            }
3434        }
3435
3436        return retval;
3437    }
3438    
3439    /** 
3440     * @see OptimizablePredicateList#selectivity
3441     */
3442    public double selectivity(Optimizable optTable)
3443        throws StandardException
3444    {
3445        TableDescriptor td = optTable.getTableDescriptor();
3446        ConglomerateDescriptor[] conglomerates = td.getConglomerateDescriptors();
3447
3448        int numPredicates = size();
3449        int numConglomerates = conglomerates.length;
3450
3451        if (numConglomerates == 1)
3452            return -1.0d; // one conglomerate; must be heap.
3453
3454        if (numPredicates == 0)
3455            return -1.0d;       // no predicates why bother?
3456
3457        boolean nothingYet = true;
3458
3459        /* before we start, lets select non-redundant prediates into a working
3460         * list; we'll work with the workingPredicates list from now on in this
3461         * routine. 
3462         */
3463        PredicateList workingPredicates = new PredicateList();
3464
3465        for (int i = 0; i < numPredicates; i++)
3466        {
3467            if (isRedundantPredicate(i))
3468                continue;
3469
3470            /* to workingPredicates only add useful predicates... */
3471            workingPredicates.addOptPredicate((Predicate)elementAt(i));
3472        }
3473
3474        int numWorkingPredicates = workingPredicates.size();
3475
3476        /*--------------------------------------------------------------------
3477         * In the first phase, the routine initializes an array of
3478         * predicateWrapperLists-- one list for each conglomerate that has
3479         * statistics. 
3480         *
3481         * predsForConglomerates is an array of pwList. For each conglomerate we
3482         * keep a pwList of predicates that have an equals predicate on a column
3483         * in the conglomerate.
3484         *
3485         * As an example consider a table T, with indices on
3486         * T(c1)-->conglom_one, T(c2,c1)-->conglom_two.
3487         *
3488         * if we have the following predicates:
3489         *  T.c1=T1.x (p1) and T.c1=T2.y (p2) and T.c2=T1.z (p3), then we'll have the 
3490         * after the first loop is done, we'll have the following setup.
3491         *
3492         * conglom_one: pwList [p1,p2]
3493         * conglom_two: pwList [p1,p2,p3].
3494         *
3495         * Note that although p1,p2 appear on both conglomerates, the
3496         * indexPosition of p1 and p2 on the first list is 0 (first index
3497         * position) while the index position of p1,p2 on the second list is 1
3498         * (second index position).
3499         *
3500         * PredicateWrapper and PredicateWrapperLists are inner classes used
3501         * only in this file.
3502         * -------------------------------------------------------------------- */
3503        PredicateWrapperList[] 
3504            predsForConglomerates = new PredicateWrapperList[numConglomerates];
3505
3506        for (int i = 0; i < numConglomerates; i++)
3507        {
3508            ConglomerateDescriptor cd = conglomerates[i];
3509            
3510            if (!cd.isIndex())
3511                continue;
3512
3513            if (!td.statisticsExist(cd))
3514                continue;
3515
3516            int[] baseColumnList = 
3517                cd.getIndexDescriptor().baseColumnPositions();
3518
3519            for (int j = 0; j < numWorkingPredicates; j++)
3520            {
3521                Predicate pred = (Predicate)workingPredicates.elementAt(j);
3522
3523                int ip = pred.hasEqualOnColumnList(baseColumnList, 
3524                                                   optTable);
3525                
3526                if (ip < 0)
3527                    continue;   // look at the next predicate.
3528
3529                nothingYet = false;
3530                if (predsForConglomerates[i] == null)
3531                {
3532                    predsForConglomerates[i] = new PredicateWrapperList(numWorkingPredicates);
3533                }
3534                PredicateWrapper newpw = new PredicateWrapper(ip, pred, j);
3535                predsForConglomerates[i].insert(newpw);
3536            } // for (j = 0;
3537        } // for (i = 0; i < ...)
3538
3539        if (nothingYet)
3540        {
3541            return -1.0;
3542        }
3543
3544        /*------------------------------------------------------------------
3545         * In the second phase we,
3546         * walk the predsForConglomerateList again-- if we find
3547         * a break in the indexPositions we remove the predicates
3548         * after the gap. To clarify, if we have equal predicates on the first
3549         * and the third index positions, we can throw away the predicate on 
3550         * the 3rd index position-- it doesn't do us any good.
3551         *-------------------------------------------------------------------*/
3552
3553        int maxOverlap = -1;
3554        for (int i = 0; i < numConglomerates; i++)
3555        {
3556            if (predsForConglomerates[i] == null)
3557                continue;
3558            
3559            predsForConglomerates[i].retainLeadingContiguous();
3560        } // for (i = 0; i < ...)
3561        
3562
3563        calculateWeight(predsForConglomerates, numWorkingPredicates);
3564
3565        /*-------------------------------------------------------------------
3566         * In the third phase we loop through predsForConglomerates choosing the
3567         * best fit (chooseLongestMatch) of predicates. we use the statistics
3568         * for the set of predicates returned by chooseLongestMatch and then
3569         * loop until we can't find any more statistics or we have exhausted all
3570         * the predicates for which we are trying to find statistics.
3571         *--------------------------------------------------------------------*/
3572        Vector   statistics = new Vector  (numWorkingPredicates);
3573
3574        double selectivity = 1.0;
3575
3576        Vector   maxPreds = new Vector  ();
3577
3578        while (true)
3579        {
3580            maxPreds.removeAllElements();
3581            int conglomIndex = chooseLongestMatch(predsForConglomerates,
3582                                                  maxPreds, numWorkingPredicates);
3583            
3584            if (conglomIndex == -1)
3585                break;          // no more stats available.
3586
3587            selectivity *=
3588                td.selectivityForConglomerate(conglomerates[conglomIndex], maxPreds.size());
3589
3590            for (int i = 0; i < maxPreds.size(); i++)
3591            {
3592                /* remove the predicates that we've calculated the selectivity
3593                 * of, from workingPredicates.
3594                 */
3595                Predicate p =(Predicate) maxPreds.elementAt(i);
3596                workingPredicates.removeOptPredicate(p);
3597            }   
3598            
3599            if (workingPredicates.size() == 0)
3600                break;
3601        }
3602        
3603        if (workingPredicates.size() != 0)
3604        {
3605            selectivity *= workingPredicates.selectivityNoStatistics(optTable);
3606        }
3607
3608        return selectivity;
3609    }
3610    
3611    /* assign a weight to each predicate-- the maximum weight that a predicate
3612     * can have is numUsefulPredicates. If a predicate corresponds to the first
3613     * index position then its weight is numUsefulPredicates. The weight of a
3614     * pwlist is the sum of the weights of individual predicates.
3615     */
3616    private void calculateWeight(PredicateWrapperList[] pwList, int numUsefulPredicates)
3617    {
3618        int[] s = new int[numUsefulPredicates];
3619
3620        for (int i = 0; i < pwList.length; i++)
3621        {
3622            if (pwList[i] == null)
3623                continue;
3624            
3625            for (int j = 0; j < pwList[i].size(); j++)
3626            {
3627                s[pwList[i].elementAt(j).getPredicateID()] +=
3628                    (numUsefulPredicates - j);
3629            }
3630        }
3631        
3632        for (int i = 0; i < pwList.length; i++)
3633        {
3634            int w = 0;
3635
3636            if (pwList[i] == null)
3637                continue;
3638
3639            for (int j = 0; j < pwList[i].size(); j++)
3640            {
3641                w += s[pwList[i].elementAt(j).getPredicateID()];
3642            }
3643            pwList[i].setWeight(w);
3644        }
3645    }
3646    /** 
3647     * choose the statistic which has the maximum match with the predicates.
3648     * value is returned in ret.
3649     */
3650    private int chooseLongestMatch(PredicateWrapperList[] predArray, Vector   ret,
3651                                   int numWorkingPredicates)
3652    {
3653        int max = 0, maxWeight = 0;
3654        int position = -1;
3655        int weight;
3656
3657        for (int i = 0; i < predArray.length; i++)
3658        {
3659            if (predArray[i] == null)
3660                continue;
3661
3662            if (predArray[i].uniqueSize() == 0)
3663                continue;
3664
3665            if (predArray[i].uniqueSize() > max)
3666            {
3667                max = predArray[i].uniqueSize();
3668                position = i;
3669                maxWeight = predArray[i].getWeight();
3670            }
3671            
3672            if (predArray[i].uniqueSize() == max)
3673            {
3674                /* if the matching length is the same, choose the one with the
3675                 * lower weight.
3676                 */
3677                if (predArray[i].getWeight() > maxWeight)
3678                    continue;
3679                
3680                position = i;
3681                max = predArray[i].uniqueSize();
3682                maxWeight = predArray[i].getWeight();
3683            }
3684        }
3685        
3686        if (position == -1)
3687            return -1;
3688
3689        /* the problem here is that I might have more than one predicate
3690         * matching on the same index position; i.e
3691         * col_1 = .. [p1] AND col_1 = .. [p2] AND col_2 = ..[p3];
3692         * In that case that maximum matching predicate is [p1] and [p3] but
3693         * [p2] shuld be considered again later.
3694        */
3695        PredicateWrapperList pwl = predArray[position];
3696        Vector   uniquepreds = pwl.createLeadingUnique();
3697        
3698        /* uniqueprds is a vector of predicate (along with wrapper) that I'm
3699           going  to use to get statistics from-- we now have to delete these
3700           predicates from all the predicateWrapperLists!
3701        */
3702        for (int i = 0; i < uniquepreds.size(); i++)
3703        {
3704            Predicate p = 
3705                ((PredicateWrapper)uniquepreds.elementAt(i)).getPredicate();
3706            ret.addElement(p);
3707            for (int j = 0; j < predArray.length; j++)
3708            {
3709                if (predArray[j] == null)
3710                    continue;
3711
3712                pwl = predArray[j];
3713                /* note that we use object identity with the predicate and not
3714                 * the predicatewrapper to remove it from the prediate wrapper
3715                 * lists. 
3716                 */
3717                pwl.removeElement(p); 
3718            }
3719        }
3720
3721        /* if removing this predicate caused a gap, get rid of everything after
3722         * the gaps.
3723         */
3724        for (int i = 0; i < predArray.length; i++)
3725        {
3726            if (predArray[i] == null)
3727                continue;
3728            predArray[i].retainLeadingContiguous();
3729        }
3730
3731        /* recalculate the weights of the pwlists... */
3732        calculateWeight(predArray, numWorkingPredicates);
3733        return position;
3734    }
3735
3736    /** 
3737     * Compute selectivity the old fashioned way.
3738     */
3739    private double selectivityNoStatistics(Optimizable optTable)
3740    throws StandardException
3741    {
3742        double selectivity = 1.0;
3743
3744        for (int i = 0; i < size(); i++)
3745        {
3746            OptimizablePredicate pred = (OptimizablePredicate)elementAt(i);
3747            selectivity *= pred.selectivity((Optimizable)optTable);
3748        }
3749        
3750        return selectivity;
3751    }
3752
3753    /** 
3754     * Inner class which helps statistics routines do their work.
3755     * We need to keep track of the index position for each predicate for each
3756     * index while we're manipulating predicates and statistics. Each predicate
3757     * does have internal state for indexPosition, but this is a more permanent
3758     * sort of indexPosition, which keeps track of the position for the index
3759     * being considered in estimateCost. For us, each predicate can have
3760     * different index positions for different indices. 
3761     */
3762    private class PredicateWrapper 
3763    {
3764        int indexPosition;
3765        Predicate pred;
3766        int predicateID;
3767
3768        PredicateWrapper(int ip, Predicate p, int predicateID)
3769        {
3770            this.indexPosition = ip;
3771            this.pred = p;
3772            this.predicateID = predicateID;
3773        }
3774        
3775        int getIndexPosition() { return indexPosition; }
3776        Predicate getPredicate() { return pred; }
3777        int getPredicateID() { return predicateID; }
3778
3779        /* a predicatewrapper is BEFORE another predicate wrapper iff its index
3780         * position is less than the index position of the other.
3781         */
3782        boolean before(PredicateWrapper other)
3783        { 
3784            return (indexPosition < other.getIndexPosition());
3785        }
3786        
3787        /* for our purposes two predicates at the same index 
3788            position are contiguous. (have i spelled this right?)
3789        */
3790        boolean contiguous(PredicateWrapper other)
3791        {
3792            int otherIP = other.getIndexPosition();
3793            return ((indexPosition == otherIP) || (indexPosition - otherIP == 1)
3794                    || (indexPosition - otherIP == -1));
3795        }
3796        
3797    }
3798    
3799    /** Another inner class which is basically a List of Predicate Wrappers.
3800     */
3801    private class PredicateWrapperList
3802    {
3803        Vector   pwList;
3804        int numPreds;
3805        int numDuplicates;
3806        int weight;
3807
3808        PredicateWrapperList(int maxValue)
3809        {
3810            pwList = new Vector  (maxValue);
3811        }
3812        
3813        void removeElement(PredicateWrapper pw)
3814        {
3815            int index = pwList.indexOf(pw);
3816            if (index >= 0)
3817                removeElementAt(index);
3818        }
3819
3820        void removeElement(Predicate p)
3821        {
3822            for (int i = numPreds - 1; i >= 0; i--)
3823            {
3824                Predicate predOnList = elementAt(i).getPredicate();
3825                if (predOnList == p) // object equality is what we need
3826                    removeElementAt(i);
3827            }
3828        }
3829
3830        void removeElementAt(int index)
3831        {
3832            if (index < numPreds - 1)
3833            {
3834                PredicateWrapper nextPW = elementAt(index+1);
3835                if (nextPW.getIndexPosition() == index)
3836                    numDuplicates--;
3837            }
3838            pwList.removeElementAt(index);
3839            numPreds--;
3840        }
3841
3842        PredicateWrapper elementAt(int i)
3843        {
3844            return (PredicateWrapper)pwList.elementAt(i);
3845        }
3846
3847        void insert(PredicateWrapper pw)
3848        {
3849            int i;
3850            for (i = 0; i < pwList.size(); i++)
3851            {
3852                if (pw.getIndexPosition() == elementAt(i).getIndexPosition())
3853                    numDuplicates++;
3854
3855                if (pw.before(elementAt(i)))
3856                    break;
3857            }
3858            numPreds++;
3859            pwList.insertElementAt(pw, i);
3860        } 
3861        
3862        int size()
3863        {
3864            return numPreds;
3865        }
3866        
3867        /* number of unique references to a column; i.e two predicates which
3868         * refer to the same column in the table will give rise to duplicates.
3869         */
3870        int uniqueSize()
3871        {
3872            if (numPreds > 0)
3873                return numPreds - numDuplicates;
3874            return 0;
3875        }           
3876        
3877        /* From a list of PredicateWrappers, retain only contiguous ones. Get
3878         * rid of everything after the first gap.
3879         */
3880        void retainLeadingContiguous()
3881        {
3882            if (pwList == null)
3883                return;
3884
3885            if (pwList.size() == 0)
3886                return;
3887
3888            if (elementAt(0).getIndexPosition() != 0)
3889            {
3890                pwList.removeAllElements();
3891                numPreds = numDuplicates = 0;
3892                return;
3893            }
3894            
3895            int j;
3896            for (j = 0; j < numPreds - 1; j++)
3897            {
3898                if (!(elementAt(j).contiguous(elementAt(j+1))))
3899                    break;
3900            }
3901            
3902            /* j points to the last good one; i.e 
3903             *      0 1 1 2 4 4
3904             * j points to 2. remove 4 and everything after it.
3905             * Beetle 4321 - need to remove from back to front
3906             * to prevent array out of bounds problems
3907             *
3908             */
3909
3910            for (int k = numPreds - 1; k > j; k--)
3911            {
3912                if (elementAt(k).getIndexPosition() == 
3913                            elementAt(k-1).getIndexPosition())
3914                    numDuplicates--;
3915                pwList.removeElementAt(k);
3916            }
3917            numPreds = j + 1;
3918        }
3919        
3920        /* From a list of PW, extract the leading unique predicates; i.e if the
3921         * PW's with index positions are strung together like this:
3922         * 0 0 1 2 3 3
3923         * I need to extract out 0 1 2 3.
3924         * leaving 0 2 3 in there.
3925         */
3926        Vector   createLeadingUnique()
3927        {
3928            Vector   scratch = new Vector  ();
3929
3930            if (numPreds == 0)
3931                return null;
3932
3933            int lastIndexPosition = elementAt(0).getIndexPosition();
3934
3935            if (lastIndexPosition != 0)
3936                return null;
3937
3938            scratch.addElement(elementAt(0));   // always add 0.
3939
3940            for (int i = 1; i < numPreds; i++)
3941            {
3942                if (elementAt(i).getIndexPosition() == lastIndexPosition)
3943                    continue;
3944                lastIndexPosition = elementAt(i).getIndexPosition();
3945                scratch.addElement(elementAt(i));
3946            }
3947            return scratch;
3948        }
3949        
3950        void setWeight(int weight)
3951        {
3952            this.weight = weight;
3953        }
3954        
3955        int getWeight()
3956        {
3957            return weight;
3958        }
3959    }
3960}
3961
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags