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


1 /*
2
3    Derby - Class org.apache.derby.impl.sql.compile.Predicate
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.impl.sql.compile.ExpressionClassBuilder;
25 import org.apache.derby.impl.sql.compile.ActivationClassBuilder;
26
27 import org.apache.derby.iapi.sql.compile.C_NodeTypes;
28 import org.apache.derby.iapi.sql.compile.Visitable;
29 import org.apache.derby.iapi.sql.compile.Visitor;
30 import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
31 import org.apache.derby.iapi.sql.compile.Optimizable;
32
33 import org.apache.derby.iapi.sql.dictionary.DataDictionary;
34
35 import org.apache.derby.iapi.store.access.ScanController;
36
37 import org.apache.derby.iapi.error.StandardException;
38
39 import org.apache.derby.iapi.services.compiler.MethodBuilder;
40
41 import org.apache.derby.iapi.services.sanity.SanityManager;
42
43 import org.apache.derby.iapi.types.DataValueDescriptor;
44
45 import org.apache.derby.iapi.util.JBitSet;
46
47 import java.util.ArrayList ;
48 import java.util.Hashtable ;
49
50 /**
51  * A Predicate represents a top level predicate.
52  *
53  * @author Jerry Brenner
54  */
55
56 public final class Predicate extends QueryTreeNode implements OptimizablePredicate,
57                                                         Comparable
58 {
59     /* Top of the predicate */
60     AndNode andNode;
61     boolean pushable;
62     /* Bit map of referenced tables */
63     JBitSet referencedSet;
64     /* Join clauses are placed into equivalence classes when applying transitive
65      * closure for join clauses. This is useful for eliminating redundant predicates.
66      */
67     int equivalenceClass = -1;
68     int indexPosition;
69     protected boolean startKey;
70     protected boolean stopKey;
71     protected boolean isQualifier;
72
73     /* Hashtable used for tracking the search clause types that have been
74      * pushed through this predicate (if an equijoin) via transitive closure.
75      */
76     private Hashtable searchClauseHT;
77
78     // Whether or not this predicate has been scoped; see the
79 // getPredScopedForResultSet() method of this class for more.
80 private boolean scoped;
81
82     /**
83      * Initializer.
84      *
85      * @param andNode The top of the predicate
86      * @param referencedSet Bit map of referenced tables
87      */
88
89     public void init(Object andNode, Object referencedSet)
90     {
91         this.andNode = (AndNode) andNode;
92         pushable = false;
93         this.referencedSet = (JBitSet) referencedSet;
94         scoped = false;
95     }
96
97     /*
98      * Optimizable interface
99      */
100
101     /**
102      * @see org.apache.derby.iapi.sql.compile.OptimizablePredicate#getReferencedMap
103      */
104     public JBitSet getReferencedMap()
105     {
106         return referencedSet;
107     }
108
109     /**
110      * @see org.apache.derby.iapi.sql.compile.OptimizablePredicate#hasSubquery
111      */
112     public boolean hasSubquery()
113     {
114         /* RESOLVE - Currently, we record whether or not a predicate is pushable based
115          * on whether or not it contains a subquery or method call, but we do not
116          * record the underlying info.
117          */
118         return ! pushable;
119     }
120
121     /**
122      * @see org.apache.derby.iapi.sql.compile.OptimizablePredicate#hasMethodCall
123      */
124     public boolean hasMethodCall()
125     {
126         /* RESOLVE - Currently, we record whether or not a predicate is pushable based
127          * on whether or not it contains a subquery or method call, but we do not
128          * record the underlying info.
129          */
130         return ! pushable;
131     }
132
133     /** @see OptimizablePredicate#markStartKey */
134     public void markStartKey()
135     {
136         startKey = true;
137     }
138
139     /** @see OptimizablePredicate#isStartKey */
140     public boolean isStartKey()
141     {
142         return startKey;
143     }
144
145     /** @see OptimizablePredicate#markStopKey */
146     public void markStopKey()
147     {
148         stopKey = true;
149     }
150
151     /** @see OptimizablePredicate#isStopKey */
152     public boolean isStopKey()
153     {
154         return stopKey;
155     }
156
157     /** @see OptimizablePredicate#markQualifier */
158     public void markQualifier()
159     {
160         isQualifier = true;
161     }
162
163     /** @see OptimizablePredicate#isQualifier */
164     public boolean isQualifier()
165     {
166         return isQualifier;
167     }
168
169     /** @see OptimizablePredicate#compareWithKnownConstant */
170     public boolean compareWithKnownConstant(Optimizable optTable, boolean considerParameters)
171     {
172         boolean retval = false;
173         RelationalOperator relop = getRelop();
174
175         /* if this is for "in" operator node's dynamic start/stop key, relop is
176          * null, and it's not comparing with constant, beetle 3858
177          */
178         if (relop == null)
179             return false;
180
181         if (relop.compareWithKnownConstant(optTable, considerParameters))
182             retval = true;
183
184         return retval;
185     }
186
187     public int hasEqualOnColumnList(int[] baseColumnPositions,
188                                         Optimizable optTable)
189         throws StandardException
190     {
191         RelationalOperator relop = getRelop();
192
193         if (relop == null)
194             return -1;
195         
196         if (!(relop.getOperator() == RelationalOperator.EQUALS_RELOP))
197             return -1;
198             
199         for (int i = 0; i < baseColumnPositions.length; i++)
200         {
201             ColumnReference cr = relop.getColumnOperand(optTable,
202                                                         baseColumnPositions[i]);
203         
204             if (cr == null)
205                 continue;
206             
207             if (relop.selfComparison(cr))
208                 continue;
209
210             // If I made it thus far in the loop, we've found
211 // something.
212 return i;
213         }
214         
215         return -1;
216     }
217
218     /**
219      * @see OptimizablePredicate#getCompareValue
220      *
221      * @exception StandardException Thrown on error
222      */
223     public DataValueDescriptor getCompareValue(Optimizable optTable)
224         throws StandardException
225     {
226         if (SanityManager.DEBUG)
227         {
228             SanityManager.ASSERT(compareWithKnownConstant(optTable, true),
229                 "Cannot get the compare value if not comparing with a known constant.");
230         }
231
232         RelationalOperator relop = getRelop();
233
234         return relop.getCompareValue(optTable);
235     }
236
237     /** @see OptimizablePredicate#equalsComparisonWithConstantExpression */
238     public boolean equalsComparisonWithConstantExpression(Optimizable optTable)
239     {
240         RelationalOperator relop = getRelop();
241         boolean retval = false;
242
243         if (relop != null)
244         {
245             retval = relop.equalsComparisonWithConstantExpression(optTable);
246         }
247
248         return retval;
249     }
250
251     /** @see OptimizablePredicate#selectivity */
252     public double selectivity(Optimizable optTable)
253     throws StandardException
254     {
255         return andNode.getLeftOperand().selectivity(optTable);
256     }
257
258     /** @see OptimizablePredicate#getIndexPosition */
259     public int getIndexPosition()
260     {
261         return indexPosition;
262     }
263
264
265     /* Comparable interface */
266
267     public int compareTo(Object other)
268     {
269         Predicate otherPred = (Predicate) other;
270
271         /* Not all operators are "equal". If the predicates are on the
272          * same key column, then a "=" opertor takes precedence over all
273          * other operators. This ensures that the "=" will be both the start
274          * and stop predicates. Otherwise, we could end up with it being one
275          * but not the other and get incorrect results.
276          *
277          * Also, we want "<>" to come after all the other operators.
278          * Other parts of the optimizer use the first predicate on an index
279          * column to determine the cost of using the index, so we want the
280          * "<>" to come last because it's not useful for limiting the scan.
281          *
282          * In other words, P1 is before() P2 if:
283          * o The P1.indexPosition < P2.indexPosition
284          * or o P1.indexPosition == P2.indexPosition and
285          * P1's operator is ("=" or IS NULL) and
286          * P2's operator is not ("=" or IS NULL)
287          * or o P1.indexPosition == P2.indexPosition and
288          * P1's operator is not ("<>" or IS NOT NULL) and
289          * P2's operator is ("<>" or IS NOT NULL)
290          *
291          * (We have to impose an arbitrary, but reproducible ordering
292          * on the the "=" predicates on the same column, otherwise an
293          * ASSERTion, that after the predicates are order, Pn+1 is not
294          * before() Pn, will be violated.
295          */
296
297         int otherIndexPosition = otherPred.getIndexPosition();
298
299         if (indexPosition < otherIndexPosition)
300             return -1;
301
302         if (indexPosition > otherIndexPosition)
303             return 1;
304
305         // initialize these flags as if they are for "in" operator, then
306 // change them if they are not
307 //
308 boolean thisIsEquals = false, otherIsEquals = false;
309         boolean thisIsNotEquals = true, otherIsNotEquals = true;
310
311         if (getRelop() != null) // this is not "in"
312 {
313             int thisOperator = ((RelationalOperator)andNode.getLeftOperand()).getOperator();
314             thisIsEquals = (thisOperator == RelationalOperator.EQUALS_RELOP ||
315                                 thisOperator == RelationalOperator.IS_NULL_RELOP);
316             thisIsNotEquals = (thisOperator == RelationalOperator.NOT_EQUALS_RELOP ||
317                                    thisOperator == RelationalOperator.IS_NOT_NULL_RELOP);
318         }
319         if (otherPred.getRelop() != null) // other is not "in"
320 {
321             int otherOperator = ((RelationalOperator)(otherPred.getAndNode().getLeftOperand())).getOperator();
322             otherIsEquals = (otherOperator == RelationalOperator.EQUALS_RELOP ||
323                                  otherOperator == RelationalOperator.IS_NULL_RELOP);
324             otherIsNotEquals = (otherOperator == RelationalOperator.NOT_EQUALS_RELOP ||
325                                  otherOperator == RelationalOperator.IS_NOT_NULL_RELOP);
326         }
327
328         boolean thisIsBefore = (thisIsEquals && ! otherIsEquals) || ( ! thisIsNotEquals && otherIsNotEquals);
329         if (thisIsBefore)
330             return -1;
331
332         boolean otherIsBefore = (otherIsEquals && ! thisIsEquals) || ( ! otherIsNotEquals && thisIsNotEquals);
333         if (otherIsBefore)
334             return 1;
335         return 0;
336     }
337
338     /**
339      * Return the andNode.
340      *
341      * @return AndNode The andNode.
342      */
343     public AndNode getAndNode()
344     {
345         return andNode;
346     }
347
348     /**
349      * Set the andNode.
350      *
351      * @param andNode The new andNode.
352      */
353     public void setAndNode(AndNode andNode)
354     {
355         this.andNode = andNode;
356     }
357
358     /**
359      * Return the pushable.
360      *
361      * @return boolean Whether or not the predicate is pushable.
362      */
363     public boolean getPushable()
364     {
365         return pushable;
366     }
367
368     /**
369      * Set whether or not this predicate is pushable. This method
370      * is intended for use when creating a copy of the predicate, ex
371      * for predicate pushdown. We choose not to add this assignment
372      * to copyFields() because the comments for that method say that
373      * it should copy all fields _except_ the two specified at init
374      * time; "pushable" is one of the two specified at init time.
375      *
376      * @param pushable Whether or not the predicate is pushable.
377      */
378     public void setPushable(boolean pushable) {
379         this.pushable = pushable;
380     }
381
382     /**
383      * Return the referencedSet.
384      *
385      * @return JBitSet The referencedSet.
386      */
387     public JBitSet getReferencedSet()
388     {
389         return referencedSet;
390     }
391
392     /**
393      * Set the equivalence class, if any, for this predicate.
394      *
395      * @param equivalenceClass The equivalence class for this predicate.
396      */
397     void setEquivalenceClass(int equivalenceClass)
398     {
399         this.equivalenceClass = equivalenceClass;
400     }
401
402     /**
403      * Get the equivalenceClass for this predicate.
404      *
405      * @return The equivalenceClass for this predicate.
406      */
407     int getEquivalenceClass()
408     {
409         return equivalenceClass;
410     }
411
412     /**
413      * Categorize this predicate. Initially, this means
414      * building a bit map of the referenced tables for each predicate.
415      *
416      * @exception StandardException Thrown on error
417      */
418     public void categorize() throws StandardException
419     {
420         pushable = andNode.categorize(referencedSet, false);
421     }
422
423     /**
424      * Get the RelationalOperator on the left side of the AND node, if
425      * there is one. If the left side is not a RelationalOperator, return
426      * null.
427      *
428      * @return The RelationalOperator on the left side of the AND node,
429      * if any.
430      */
431     public RelationalOperator getRelop()
432     {
433         
434         if (andNode.getLeftOperand() instanceof RelationalOperator)
435         {
436             return (RelationalOperator) andNode.getLeftOperand();
437         }
438         else
439         {
440             return null;
441         }
442     }
443
444     public final boolean isOrList()
445     {
446         return(andNode.getLeftOperand() instanceof OrNode);
447     }
448
449     /**
450      * Is this predicate a possible Qualifier for store?
451      * <p>
452      * Current 2 types of predicates can be pushed to store:
453      * 1) RelationalOperator -
454      * represented with by left operand as instance of RelationalOperator.
455      * 2) A single And'd term of a list of OR terms
456      * represented by left operand as instance of OrNode.
457      *
458      * More checking specific operator's terms to see if they are finally
459      * pushable to store. In the final push at execution each term of the AND
460      * or OR must be a Relational operator with a column reference on one side
461      * and a constant on the other.
462      *
463      *
464      * @return true if term is wither a AND of a RelationalOperator, or an
465      * OR of one or more Relational Operators.
466      *
467      *
468      * @exception StandardException Standard exception policy.
469      **/
470     public final boolean isStoreQualifier()
471     {
472         if ((andNode.getLeftOperand() instanceof RelationalOperator) ||
473             (andNode.getLeftOperand() instanceof OrNode))
474         {
475             return(true);
476         }
477         else
478         {
479             return(false);
480         }
481     }
482
483     /**
484      * Is this predicate an pushable OR list?
485      * <p>
486      * Does the predicate represent a AND'd list of OR term's, all of which
487      * are pushable. To be pushable each of OR terms must be a legal
488      * qualifier, which is a column reference on one side of a Relational
489      * operator and a constant on the other.
490      *
491      * @return true if the predicate is a pushable set of OR clauses.
492      *
493      *
494      * @exception StandardException Standard exception policy.
495      **/
496     public final boolean isPushableOrClause(Optimizable optTable)
497         throws StandardException
498     {
499         boolean ret_val = true;
500
501         if (andNode.getLeftOperand() instanceof OrNode)
502         {
503             QueryTreeNode node = andNode.getLeftOperand();
504
505             while (node instanceof OrNode)
506             {
507                 OrNode or_node = (OrNode) node;
508
509                 if (or_node.getLeftOperand() instanceof RelationalOperator)
510                 {
511                     // if any term of the OR clause is not a qualifier, then
512 // reject the entire OR clause.
513 if (!((RelationalOperator) or_node.getLeftOperand()).
514                         isQualifier(optTable, true))
515                     {
516                         // one of the terms is not a pushable Qualifier.
517 return(false);
518                     }
519
520                     node = or_node.getRightOperand();
521                 }
522                 else
523                 {
524                     // one of the terms is not a RelationalOperator
525
526                     return(false);
527                 }
528             }
529
530             return(true);
531         }
532         else
533         {
534             // Not an OR list
535 return(false);
536         }
537     }
538
539     /**
540      * Return whether or not this predicate has been used
541      * to add a new search clause of the specified type via transitive closure.
542      * NOTE: This can only be true if this is an equijoin
543      * between 2 column references.
544      *
545      * @param ro The search clause that we are currently considering
546      * as the source for transitive closure
547      *
548      * @return Whether or not this predicate has been used
549      * to add a new search clause of the specified type via transitive
550      * closure.
551      */
552     boolean transitiveSearchClauseAdded(RelationalOperator ro)
553     {
554         if (searchClauseHT == null ||
555             searchClauseHT.get(new Integer (ro.getOperator())) == null)
556         {
557             return false;
558         }
559         else
560         {
561             return true;
562         }
563     }
564
565     /**
566      * Mark this predicate as having been used to add a new predicate
567      * of the specified type via transitive closure on search clauses.
568      *
569      * @param ro The search clause that we are currently considering
570      * as the source for transitive closure
571      *
572      */
573     void setTransitiveSearchClauseAdded(RelationalOperator ro)
574     {
575         if (searchClauseHT == null)
576         {
577             searchClauseHT = new Hashtable ();
578         }
579         /* I have to remember that this ro has been added to this predicate as a
580          * transitive search clause.
581          */
582         Integer i = new Integer (ro.getOperator());
583         searchClauseHT.put(i, i);
584     }
585
586     /**
587      * Get the start operator for this predicate for a scan.
588      *
589      * @param optTable The optimizable table, so we can tell which side of
590      * the operator the search column is on.
591      *
592      * @return The start operator for a start key on this column.
593      */
594     int getStartOperator(Optimizable optTable)
595     {
596         if (SanityManager.DEBUG)
597         {
598             SanityManager.ASSERT(startKey, "Getting a start operator from a Predicate that's not a start key.");
599         }
600
601         /* if it's for "in" operator's dynamic start key, operator is GE,
602          * beetle 3858
603          */
604         if (andNode.getLeftOperand() instanceof InListOperatorNode)
605             return ScanController.GE;
606
607         return getRelop().getStartOperator(optTable);
608     }
609
610     int getStopOperator(Optimizable optTable)
611     {
612         if (SanityManager.DEBUG)
613         {
614             SanityManager.ASSERT(stopKey, "Getting a stop operator from a Predicate that's not a stop key.");
615         }
616
617          /* if it's for "in" operator's dynamic stop key, operator is GT,
618           * beetle 3858
619           */
620         if (andNode.getLeftOperand() instanceof InListOperatorNode)
621             return ScanController.GT;
622
623         return getRelop().getStopOperator(optTable);
624     }
625
626     /**
627      * Set the position of the index column that this predicate restricts
628      *
629      * @param indexPosition The position of the index column that this
630      * predicate restricts.
631      */
632     void setIndexPosition(int indexPosition)
633     {
634         this.indexPosition = indexPosition;
635     }
636
637     /**
638      * Clear the start/stop position and qualifier flags
639      */
640     void clearScanFlags()
641     {
642         startKey = false;
643         stopKey = false;
644         isQualifier = false;
645     }
646
647     /**
648      * Clear the qualifier flag.
649      */
650     void clearQualifierFlag()
651     {
652         isQualifier = false;
653     }
654
655     void generateExpressionOperand(Optimizable optTable,
656                                         int columnPosition,
657                                         ExpressionClassBuilder acb,
658                                         MethodBuilder mb)
659                 throws StandardException
660     {
661         getRelop().generateExpressionOperand(optTable,
662                                                     columnPosition,
663                                                     acb,
664                                                     mb);
665     }
666
667     void generateAbsoluteColumnId(MethodBuilder mb,
668                                         Optimizable optTable)
669     {
670         getRelop().generateAbsoluteColumnId(mb, optTable);
671     }
672
673     void generateRelativeColumnId(MethodBuilder mb,
674                                         Optimizable optTable)
675     {
676         getRelop().generateRelativeColumnId(mb, optTable);
677     }
678
679     void generateOperator(MethodBuilder mb,
680                                 Optimizable optTable)
681     {
682         getRelop().generateOperator(mb, optTable);
683     }
684
685     void generateQualMethod(ExpressionClassBuilder acb,
686                                 MethodBuilder mb,
687                                 Optimizable optTable)
688                     throws StandardException
689     {
690         getRelop().generateQualMethod(acb, mb, optTable);
691     }
692
693     void generateOrderedNulls(MethodBuilder mb)
694     {
695         getRelop().generateOrderedNulls(mb);
696     }
697
698     void generateNegate(MethodBuilder mb,
699                                 Optimizable optTable)
700     {
701         getRelop().generateNegate(mb, optTable);
702     }
703
704     void generateOrderableVariantType(MethodBuilder mb,
705                                 Optimizable optTable)
706                     throws StandardException
707     {
708         int variantType = getRelop().getOrderableVariantType(optTable);
709         mb.push(variantType);
710
711     }
712     /**
713      * Convert this object to a String. See comments in QueryTreeNode.java
714      * for how this should be done for tree printing.
715      *
716      * @return This object as a String
717      */
718
719     public String toString()
720     {
721         if (SanityManager.DEBUG)
722         {
723             return binaryRelOpColRefsToString() + "\nreferencedSet: " +
724                 referencedSet + "\n" + "pushable: " + pushable + "\n" +
725                 super.toString();
726         }
727         else
728         {
729             return "";
730         }
731     }
732
733     /**
734      * Get a string version of the column references for this predicate
735      * IF it's a binary relational operator. We only print out the
736      * names of the operands if they are column references; otherwise
737      * we just print a dummy value. This is for debugging purposes
738      * only--it's a convenient way to see what columns the predicate
739      * is referencing, especially when tracing through code and printing
740      * assert failure.
741      */
742     public String binaryRelOpColRefsToString()
743     {
744         // We only consider binary relational operators here.
745 if (!(getAndNode().getLeftOperand()
746             instanceof BinaryRelationalOperatorNode))
747         {
748             return "";
749         }
750
751         final String DUMMY_VAL = "<expr>";
752         java.lang.StringBuffer sBuf = new java.lang.StringBuffer ();
753         BinaryRelationalOperatorNode opNode =
754             (BinaryRelationalOperatorNode)getAndNode().getLeftOperand();
755
756         // Get left operand's name.
757 if (opNode.getLeftOperand() instanceof ColumnReference)
758         {
759             sBuf.append(
760                 ((ColumnReference)opNode.getLeftOperand()).getTableName() +
761                 "." +
762                 ((ColumnReference)opNode.getLeftOperand()).getColumnName()
763             );
764         }
765         else
766             sBuf.append(DUMMY_VAL);
767
768         // Get the operator type.
769 sBuf.append(" " + opNode.operator + " ");
770
771         // Get right operand's name.
772 if (opNode.getRightOperand() instanceof ColumnReference) {
773             sBuf.append(
774                 ((ColumnReference)opNode.getRightOperand()).getTableName() +
775                 "." +
776                 ((ColumnReference)opNode.getRightOperand()).getColumnName()
777             );
778         }
779         else
780             sBuf.append(DUMMY_VAL);
781
782         return sBuf.toString();
783     }
784
785     /**
786      * Prints the sub-nodes of this object. See QueryTreeNode.java for
787      * how tree printing is supposed to work.
788      *
789      * @param depth The depth of this node in the tree
790      */
791
792     public void printSubNodes(int depth)
793     {
794         if (SanityManager.DEBUG)
795         {
796             printLabel(depth, "andNode: ");
797             andNode.treePrint(depth + 1);
798             super.printSubNodes(depth);
799         }
800     }
801
802     /**
803      * Accept a visitor, and call v.visit()
804      * on child nodes as necessary.
805      *
806      * @param v the visitor
807      *
808      * @exception StandardException on error
809      */
810     public Visitable accept(Visitor v)
811         throws StandardException
812     {
813         if (v.skipChildren(this))
814         {
815             return v.visit(this);
816         }
817
818         Visitable returnNode = super.accept(v);
819
820         if (andNode != null && !v.stopTraversal())
821         {
822             andNode = (AndNode)andNode.accept(v);
823         }
824
825         return returnNode;
826     }
827
828     /**
829      * Copy all fields of this Predicate (except the two that
830      * are set from 'init').
831      *
832      */
833
834     public void copyFields(Predicate otherPred) {
835
836         this.equivalenceClass = otherPred.getEquivalenceClass();
837         this.indexPosition = otherPred.getIndexPosition();
838         this.startKey = otherPred.isStartKey();
839         this.stopKey = otherPred.isStopKey();
840         this.isQualifier = otherPred.isQualifier();
841         this.searchClauseHT = otherPred.getSearchClauseHT();
842
843     }
844
845     /**
846      * Get the search clause Hash Table.
847      */
848
849     public Hashtable getSearchClauseHT() {
850         return searchClauseHT;
851     }
852
853     /**
854      * Determine whether or not this predicate is eligible for
855      * push-down into subqueries. Right now the only predicates
856      * we consider to be eligible are those which 1) are Binary
857      * Relational operator nodes and 2) have a column reference
858      * on BOTH sides, each of which has a reference to a base
859      * table somewhere beneath it.
860      *
861      * @return Whether or not this predicate is eligible to be
862      * pushed into subqueries.
863      */
864     protected boolean pushableToSubqueries()
865         throws StandardException
866     {
867         if (!isJoinPredicate())
868             return false;
869
870         // Make sure both column references ultimately point to base
871 // tables. If, for example, either column reference points to a
872 // a literal or an aggregate, then we do not push the predicate.
873 // This is because pushing involves remapping the references--
874 // but if the reference doesn't have a base table beneath it,
875 // the notion of "remapping" it doesn't (seem to) apply. RESOLVE:
876 // it might be okay to make the "remap" operation a no-op for
877 // such column references, but it's not clear whether that's
878 // always a safe option; further investigation required.
879
880         BinaryRelationalOperatorNode opNode =
881             (BinaryRelationalOperatorNode)getAndNode().getLeftOperand();
882
883         JBitSet tNums = new JBitSet(getReferencedSet().size());
884         BaseTableNumbersVisitor btnVis = new BaseTableNumbersVisitor(tNums);
885         opNode.getLeftOperand().accept(btnVis);
886         if (tNums.getFirstSetBit() == -1)
887             return false;
888
889         tNums.clearAll();
890         opNode.getRightOperand().accept(btnVis);
891         if (tNums.getFirstSetBit() == -1)
892             return false;
893
894         return true;
895     }
896
897     /**
898      * Is this predicate a join predicate? In order to be so,
899      * it must be a binary relational operator node that has
900      * a column reference on both sides.
901      *
902      * @return Whether or not this is a join predicate.
903      */
904     protected boolean isJoinPredicate()
905     {
906         // If the predicate isn't a binary relational operator,
907 // then it's not a join predicate.
908 if (!(getAndNode().getLeftOperand()
909             instanceof BinaryRelationalOperatorNode))
910         {
911             return false;
912         }
913
914         BinaryRelationalOperatorNode opNode =
915             (BinaryRelationalOperatorNode)getAndNode().getLeftOperand();
916
917         // If both sides are column references AND they point to different
918 // tables, then this is a join pred.
919 return ((opNode.getLeftOperand() instanceof ColumnReference) &&
920             (opNode.getRightOperand() instanceof ColumnReference) &&
921             (((ColumnReference)opNode.getLeftOperand()).getTableNumber() !=
922             ((ColumnReference)opNode.getRightOperand()).getTableNumber()));
923     }
924
925     /**
926      * If this predicate's operator is a BinaryRelationalOperatorNode,
927      * then look at the operands and return a new, equivalent predicate
928      * that is "scoped" to the received ResultSetNode. By "scoped" we
929      * mean that the operands, which shold be column references, have been
930      * mapped to the appropriate result columns in the received RSN.
931      * This is useful for pushing predicates from outer queries down
932      * into inner queries, in which case the column references need
933      * to be remapped.
934      *
935      * For example, let V1 represent
936      *
937      * select i,j from t1 UNION select i,j from t2
938      *
939      * and V2 represent
940      *
941      * select a,b from t3 UNION select a,b from t4
942      *
943      * Then assume we have the following query:
944      *
945      * select * from V1, V2 where V1.j = V2.b
946      *
947      * Let's further assume that this Predicate object represents the
948      * "V1.j = V2.b" operator and that the childRSN we received
949      * as a parameter represents one of the subqueries to which we
950      * want to push the predicate; let's say it's:
951      *
952      * select i,j from t1
953      *
954      * Then this method will return a new predicate whose binary
955      * operator represents the expression "T1.j = V2.b" (that is, V1.j
956      * will be mapped to the corresponding column in T1). For more on
957      * how that mapping is made, see the "getScopedOperand()" method
958      * in BinaryRelationalOperatorNode.java.
959      *
960      * ASSUMPTION: We should only get to this method if we know that
961      * at least one operand in this predicate can and should be mapped
962      * to the received childRSN. For an example of where that check is
963      * made, see the pushOptPredicate() method in SetOperatorNode.java.
964      *
965      * @param parentRSNsTables Set of all table numbers referenced by
966      * the ResultSetNode that is _parent_ to the received childRSN.
967      * We need this to make sure we don't scope the operands to a
968      * ResultSetNode to which they don't apply.
969      * @param childRSN The result set node for which we want to create
970      * a scoped predicate.
971      * @param whichRC If not -1 then this tells us which ResultColumn
972      * in the received childRSN we need to use for the scoped predicate;
973      * if -1 then the column position of the scoped column reference
974      * will be stored in this array and passed back to the caller.
975      * @return A new predicate whose operands have been scoped to the
976      * received childRSN.
977      */
978     protected Predicate getPredScopedForResultSet(
979         JBitSet parentRSNsTables, ResultSetNode childRSN,
980         int [] whichRC) throws StandardException
981     {
982         // We only deal with binary relational operators here.
983 if (!(getAndNode().getLeftOperand()
984             instanceof BinaryRelationalOperatorNode))
985         {
986             return this;
987         }
988
989         // The predicate must have an AndNode in CNF, so we
990 // need to create an AndNode representing:
991 // <scoped_bin_rel_op> AND TRUE
992 // First create the boolean constant for TRUE.
993 ValueNode trueNode = (ValueNode) getNodeFactory().getNode(
994             C_NodeTypes.BOOLEAN_CONSTANT_NODE,
995             Boolean.TRUE,
996             getContextManager());
997
998         BinaryRelationalOperatorNode opNode =
999             (BinaryRelationalOperatorNode)getAndNode().getLeftOperand();
1000
1001        // Create a new op node with left and right operands that point
1002 // to the received result set's columns as appropriate.
1003 BinaryRelationalOperatorNode newOpNode =
1004            (BinaryRelationalOperatorNode) getNodeFactory().getNode(
1005                opNode.getNodeType(),
1006                opNode.getScopedOperand(
1007                    BinaryRelationalOperatorNode.LEFT,
1008                    parentRSNsTables,
1009                    childRSN,
1010                    whichRC),
1011                opNode.getScopedOperand(
1012                    BinaryRelationalOperatorNode.RIGHT,
1013                    parentRSNsTables,
1014                    childRSN,
1015                    whichRC),
1016                getContextManager());
1017
1018        // Bind the new op node.
1019 newOpNode.bindComparisonOperator();
1020
1021        // Create and bind a new AND node in CNF form,
1022 // i.e. "<newOpNode> AND TRUE".
1023 AndNode newAnd = (AndNode) getNodeFactory().getNode(
1024            C_NodeTypes.AND_NODE,
1025            newOpNode,
1026            trueNode,
1027            getContextManager());
1028        newAnd.postBindFixup();
1029
1030        // Categorize the new AND node; among other things, this
1031 // call sets up the new operators's referenced table map,
1032 // which is important for correct pushing of the new
1033 // predicate.
1034 JBitSet tableMap = new JBitSet(
1035            childRSN.getReferencedTableMap().size());
1036        newAnd.categorize(tableMap, false);
1037
1038        // Now put the pieces together to get a new predicate.
1039 Predicate newPred = (Predicate) getNodeFactory().getNode(
1040            C_NodeTypes.PREDICATE,
1041            newAnd,
1042            tableMap,
1043            getContextManager());
1044
1045        // Copy all of this predicates other fields into the new predicate.
1046 newPred.clearScanFlags();
1047        newPred.copyFields(this);
1048        newPred.setPushable(getPushable());
1049
1050        // Take note of the fact that the new predicate is scoped for
1051 // the sake of pushing; we need this information during optimization
1052 // to figure out what we should and should not "pull" back up.
1053 newPred.markAsScopedForPush();
1054        return newPred;
1055    }
1056
1057    /**
1058     * Indicate that this predicate is a scoped copy of some other
1059     * predicate (i.e. it was created as the result of a call to
1060     * getPredScopedForResultSet() on some other predicate).
1061     */
1062    protected void markAsScopedForPush() {
1063        this.scoped = true;
1064    }
1065
1066    /**
1067     * Return whether or not this predicate is a scoped copy of
1068     * another predicate.
1069     */
1070    protected boolean isScopedForPush() {
1071        return scoped;
1072    }
1073
1074    /**
1075     * When remapping a "normal" (i.e. non-scoped) predicate both
1076     * of the predicate's operands are remapped and that's it.
1077     * But when remapping a scoped predicate, things are slightly
1078     * different. This method handles remapping of scoped predicates.
1079     *
1080     * We know that, for a scoped predicate, exactly one operand has
1081     * been scoped for a specific target result set; the other operand
1082     * is pointing to some other instance of FromTable with which the
1083     * target result set is to be joined (see getScopedOperand() in
1084     * BinaryRelationalOperatorNode.java). For every level of the
1085     * query through which the scoped predicate is pushed, we have
1086     * to perform a remap operation of the scoped operand. We do
1087     * *not*, however, remap the non-scoped operand. The reason
1088     * is that the non-scoped operand is already pointing to the
1089     * result set against which it must be evaluated. As the scoped
1090     * predicate is pushed down the query tree, the non-scoped
1091     * operand should not change where it's pointing and thus should
1092     * not be remapped. For example, assume we have a query whose
1093     * tree has the following form:
1094     *
1095     * SELECT[0]
1096     * / \
1097     * PRN PRN
1098     * | |
1099     * SELECT[4] UNION
1100     * | / \
1101     * PRN SELECT[1] SELECT[2]
1102     * | | |
1103     * <FBT:T1> PRN PRN
1104     * | |
1105     * SELECT[3] <FromBaseTable:T2>
1106     * |
1107     * PRN
1108     * |
1109     * <FromBaseTable:T3>
1110     *
1111     * Assume also that we have some predicate "SELECT[4].i = <UNION>.j".
1112     * If the optimizer decides to push the predicate to the UNION
1113     * node, it (the predicate) will be scoped to the UNION's children,
1114     * yielding something like "SELECT[4].i = SELECT[1].j" for the
1115     * left child and "SELECT[4].i = SELECT[2].j" for the right child.
1116     * These scoped predicates will then be pushed to the PRNs above
1117     * SELECT[3] and T2, respectively. As part of that pushing
1118     * process a call to PRN.pushOptPredicate() will occur, which
1119     * brings us to this method. So let's assume we're here for
1120     * the scoped predicate "SELECT[4].i = SELECT[1].j". Then we want
1121     * to remap the scoped operand, "SELECT[1].j", so that it will
1122     * point to the correct column in "SELECT[3]". We do NOT, however,
1123     * want to remap the non-scoped operand "SELECT[4].i" because that
1124     * operand is already pointing to the correct result set--namely,
1125     * to a column in SELECT[4]. That non-scoped operand should not
1126     * change regardless of how far down the UNION subtree the scoped
1127     * predicate is pushed.
1128     *
1129     * If we did try to remap the non-scoped operand, it would end up
1130     * pointing to result sets too low in the tree, which could lead to
1131     * execution-time errors. So when we remap a scoped predicate, we
1132     * have to make sure we only remap the scoped operand. That's what
1133     * this method does.
1134     *
1135     * @return True if this predicate is a scoped predicate, in which
1136     * case we performed a one-sided remap. False if the predicate is
1137     * not scoped; the caller can then make the calls to perform a
1138     * "normal" remap on this predicate.
1139     */
1140    protected boolean remapScopedPred()
1141    {
1142        if (!scoped)
1143            return false;
1144
1145        /* Note: right now the only predicates we scope are those
1146         * which are join predicates and all scoped predicates will
1147         * have the same relational operator as the predicates from
1148         * which they were scoped. Thus if we get here, we know
1149         * that andNode's leftOperand must be an instance of
1150         * BinaryRelationalOperatorNode (and therefore the following
1151         * cast is safe).
1152         */
1153        BinaryRelationalOperatorNode binRelOp =
1154            (BinaryRelationalOperatorNode)andNode.getLeftOperand();
1155
1156        ValueNode operand = null;
1157
1158        if (SanityManager.DEBUG)
1159        {
1160            /* If this predicate is scoped then one (and only one) of
1161             * its operands should be scoped. Note that it's possible
1162             * for an operand to be scoped to a non-ColumnReference
1163             * value; if either operand is not a ColumnReference, then
1164             * that operand must be the scoped operand.
1165             */
1166            operand = binRelOp.getLeftOperand();
1167            boolean leftIsScoped =
1168                !(operand instanceof ColumnReference) ||
1169                    ((ColumnReference)operand).isScoped();
1170
1171            operand = binRelOp.getRightOperand();
1172            boolean rightIsScoped =
1173                !(operand instanceof ColumnReference) ||
1174                    ((ColumnReference)operand).isScoped();
1175
1176            SanityManager.ASSERT(leftIsScoped ^ rightIsScoped,
1177                "All scoped predicates should have exactly one scoped " +
1178                "operand, but '" + binaryRelOpColRefsToString() +
1179                "' has " + (leftIsScoped ? "TWO" : "NONE") + ".");
1180        }
1181
1182        // Find the scoped operand and remap it.
1183 operand = binRelOp.getLeftOperand();
1184        if ((operand instanceof ColumnReference) &&
1185            ((ColumnReference)operand).isScoped())
1186        {
1187            // Left operand is the scoped operand.
1188 ((ColumnReference)operand).remapColumnReferences();
1189        }
1190        else
1191        {
1192            operand = binRelOp.getRightOperand();
1193            if ((operand instanceof ColumnReference) &&
1194                ((ColumnReference)operand).isScoped())
1195            {
1196                // Right operand is the scoped operand.
1197 ((ColumnReference)operand).remapColumnReferences();
1198            }
1199
1200            // Else scoped operand is not a ColumnReference, which
1201 // means it can't (and doesn't need to) be remapped. So
1202 // just fall through and return.
1203 }
1204
1205        return true;
1206    }
1207
1208    /**
1209     * Return true if this predicate is scoped AND the scoped
1210     * operand is a ColumnReference that points to a source result
1211     * set. If the scoped operand is not a ColumnReference that
1212     * points to a source result set then it must be pointing to
1213     * some kind of expression, such as a literal (ex. 'strlit'),
1214     * an aggregate value (ex. "count(*)"), or the result of a
1215     * function (ex. "sin(i)") or operator (ex. "i+1").
1216     *
1217     * This method is used when pushing predicates to determine how
1218     * far down the query tree a scoped predicate needs to be pushed
1219     * to allow for successful evaluation of the scoped operand. If
1220     * the scoped operand is not pointing to a source result set
1221     * then it should not be pushed any further down tree. The reason
1222     * is that evaluation of the expression to which the operand is
1223     * pointing may depend on other values from the current level
1224     * in the tree (ex. "sin(i)" depends on the value of "i", which
1225     * could be a column at the predicate's current level). If we
1226     * pushed the predicate further down, those values could become
1227     * inaccessible, leading to execution-time errors.
1228     *
1229     * If, on the other hand, the scoped operand *is* pointing to
1230     * a source result set, then we want to push it further down
1231     * the tree until it reaches that result set, which allows
1232     * evaluation of this predicate to occur as close to store as
1233     * possible. This method doesn't actually do the push, it just
1234     * returns "true" and then the caller can push as appropriate.
1235     */
1236    protected boolean isScopedToSourceResultSet()
1237        throws StandardException
1238    {
1239        if (!scoped)
1240            return false;
1241
1242        /* Note: right now the only predicates we scope are those
1243         * which are join predicates and all scoped predicates will
1244         * have the same relational operator as the predicates from
1245         * which they were scoped. Thus if we get here, we know
1246         * that andNode's leftOperand must be an instance of
1247         * BinaryRelationalOperatorNode (and therefore the following
1248         * cast is safe).
1249         */
1250        BinaryRelationalOperatorNode binRelOp =
1251            (BinaryRelationalOperatorNode)andNode.getLeftOperand();
1252
1253        ValueNode operand = binRelOp.getLeftOperand();
1254
1255        /* If operand isn't a ColumnReference then is must be the
1256         * scoped operand. This is because both operands have to
1257         * be column references in order for scoping to occur (as
1258         * per pushableToSubqueries()) and only the scoped operand
1259         * can change (esp. can become a non-ColumnReference) as
1260         * part of the scoping process. And since it's not a
1261         * ColumnReference it can't be "a ColumnReference that
1262         * points to a source result set", so return false.
1263         */
1264        if (!(operand instanceof ColumnReference))
1265            return false;
1266
1267        /* If the operand is a ColumnReference and is scoped,
1268         * then see if it is pointing to a ResultColumn whose
1269         * expression is either another a CR or a Virtual
1270         * ColumnNode. If it is then that operand applies
1271         * to a source result set further down the tree and
1272         * thus we return true.
1273         */
1274        ValueNode exp = null;
1275        ColumnReference cRef = (ColumnReference)operand;
1276        if (cRef.isScoped())
1277        {
1278            exp = cRef.getSource().getExpression();
1279            return ((exp instanceof VirtualColumnNode) ||
1280                (exp instanceof ColumnReference));
1281        }
1282
1283        operand = binRelOp.getRightOperand();
1284        if (!(operand instanceof ColumnReference))
1285            return false;
1286
1287        cRef = (ColumnReference)operand;
1288        if (SanityManager.DEBUG)
1289        {
1290            // If we got here then the left operand was NOT the scoped
1291 // operand; make sure the right one is scoped, then.
1292 SanityManager.ASSERT(cRef.isScoped(),
1293                "All scoped predicates should have exactly one scoped " +
1294                "operand, but '" + binaryRelOpColRefsToString() +
1295                "has NONE.");
1296        }
1297
1298        exp = cRef.getSource().getExpression();
1299        return ((exp instanceof VirtualColumnNode) ||
1300            (exp instanceof ColumnReference));
1301    }
1302}
1303

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags