KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*
2
3    Derby - Class org.apache.derby.impl.sql.compile.HashJoinStrategy
4
5    Licensed to the Apache Software Foundation (ASF) under one or more
6    contributor license agreements. See the NOTICE file distributed with
7    this work for additional information regarding copyright ownership.
8    The ASF licenses this file to you under the Apache License, Version 2.0
9    (the "License"); you may not use this file except in compliance with
10    the License. You may obtain a copy of the License at
11
12       http://www.apache.org/licenses/LICENSE-2.0
13
14    Unless required by applicable law or agreed to in writing, software
15    distributed under the License is distributed on an "AS IS" BASIS,
16    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17    See the License for the specific language governing permissions and
18    limitations under the License.
19
20  */
21
22 package org.apache.derby.impl.sql.compile;
23
24 import org.apache.derby.iapi.sql.compile.CostEstimate;
25 import org.apache.derby.iapi.sql.compile.ExpressionClassBuilderInterface;
26 import org.apache.derby.iapi.sql.compile.JoinStrategy;
27 import org.apache.derby.iapi.sql.compile.Optimizable;
28 import org.apache.derby.iapi.sql.compile.Optimizer;
29 import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
30 import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
31
32 import org.apache.derby.iapi.sql.dictionary.DataDictionary;
33 import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
34
35 import org.apache.derby.iapi.store.access.StoreCostController;
36 import org.apache.derby.iapi.store.access.TransactionController;
37
38 import org.apache.derby.iapi.services.compiler.MethodBuilder;
39
40 import org.apache.derby.impl.sql.compile.ExpressionClassBuilder;
41 import org.apache.derby.impl.sql.compile.ProjectRestrictNode;
42 import org.apache.derby.impl.sql.compile.Predicate;
43
44 import org.apache.derby.iapi.error.StandardException;
45
46 import org.apache.derby.iapi.reference.SQLState;
47
48 import org.apache.derby.iapi.services.cache.ClassSize;
49
50 import org.apache.derby.iapi.services.sanity.SanityManager;
51
52 import org.apache.derby.iapi.services.io.FormatableArrayHolder;
53 import org.apache.derby.iapi.services.io.FormatableIntHolder;
54
55 import org.apache.derby.iapi.util.JBitSet;
56
57 import java.util.Vector JavaDoc;
58
59 public class HashJoinStrategy extends BaseJoinStrategy {
60     public HashJoinStrategy() {
61     }
62
63     /**
64      * @see JoinStrategy#feasible
65      *
66      * @exception StandardException Thrown on error
67      */
68     public boolean feasible(Optimizable innerTable,
69                             OptimizablePredicateList predList,
70                             Optimizer optimizer
71                             )
72                     throws StandardException
73     {
74         int[] hashKeyColumns = null;
75
76         ConglomerateDescriptor cd = null;
77
78         /* If the innerTable is a VTI, then we
79          * must check to see if there are any
80          * join columns in the VTI's parameters.
81          * If so, then hash join is not feasible.
82          */
83         if (! innerTable.isMaterializable())
84         {
85
86             optimizer.trace(Optimizer.HJ_SKIP_NOT_MATERIALIZABLE, 0, 0, 0.0,
87                             null);
88             return false;
89         }
90
91         /* Don't consider hash join on the target table of an update/delete.
92          * RESOLVE - this is a temporary restriction. Problem is that we
93          * do not put RIDs into the row in the hash table when scanning
94          * the heap and we need them for a target table.
95          */
96         if (innerTable.isTargetTable())
97         {
98             return false;
99         }
100
101         /* If the predicate given by the user _directly_ references
102          * any of the base tables _beneath_ this node, then we
103          * cannot safely use the predicate for a hash because the
104          * predicate correlates two nodes at different nesting levels.
105          * If we did a hash join in this case, materialization of
106          * innerTable could lead to incorrect results--and in particular,
107          * results that are missing rows. We can check for this by
108          * looking at the predicates' reference maps, which are set based
109          * on the initial query (as part of pre-processing). Note that
110          * by the time we get here, it's possible that a predicate's
111          * reference map holds table numbers that do not agree with the
112          * table numbers of the column references used by the predicate.
113          * That's okay--this occurs as a result of "remapping" predicates
114          * that have been pushed down the query tree. And in fact
115          * it's a good thing because, by looking at the column reference's
116          * own table numbers instead of the predicate's referenced map,
117          * we are more readily able to find equijoin predicates that
118          * we otherwise would not have found.
119          *
120          * Note: do not perform this check if innerTable is a FromBaseTable
121          * because a base table does not have a "subtree" to speak of.
122          */
123         if ((predList != null) && (predList.size() > 0) &&
124             !(innerTable instanceof FromBaseTable))
125         {
126             FromTable ft = (FromTable)innerTable;
127
128             // First get a list of all of the base tables in the subtree
129 // below innerTable.
130 JBitSet tNums = new JBitSet(ft.getReferencedTableMap().size());
131             BaseTableNumbersVisitor btnVis = new BaseTableNumbersVisitor(tNums);
132             ft.accept(btnVis);
133
134             // Now get a list of all table numbers referenced by the
135 // join predicates that we'll be searching.
136 JBitSet pNums = new JBitSet(tNums.size());
137             Predicate pred = null;
138             for (int i = 0; i < predList.size(); i++)
139             {
140                 pred = (Predicate)predList.getOptPredicate(i);
141                 if (pred.isJoinPredicate())
142                     pNums.or(pred.getReferencedSet());
143             }
144
145             // If tNums and pNums have anything in common, then at
146 // least one predicate in the list refers directly to
147 // a base table beneath this node (as opposed to referring
148 // just to this node), which means it's not safe to do a
149 // hash join.
150 tNums.and(pNums);
151             if (tNums.getFirstSetBit() != -1)
152                 return false;
153         }
154
155         if (innerTable.isBaseTable())
156         {
157             /* Must have an equijoin on a column in the conglomerate */
158             cd = innerTable.getCurrentAccessPath().getConglomerateDescriptor();
159         }
160         
161         /* Look for equijoins in the predicate list */
162         hashKeyColumns = findHashKeyColumns(
163                                             innerTable,
164                                             cd,
165                                             predList);
166
167         if (SanityManager.DEBUG)
168         {
169             if (hashKeyColumns == null)
170             {
171                 optimizer.trace(Optimizer.HJ_SKIP_NO_JOIN_COLUMNS, 0, 0, 0.0, null);
172             }
173             else
174             {
175                 optimizer.trace(Optimizer.HJ_HASH_KEY_COLUMNS, 0, 0, 0.0, hashKeyColumns);
176             }
177         }
178
179         if (hashKeyColumns == null)
180         {
181             return false;
182         }
183
184         return true;
185     }
186
187     /** @see JoinStrategy#ignoreBulkFetch */
188     public boolean ignoreBulkFetch() {
189         return true;
190     }
191
192     /** @see JoinStrategy#multiplyBaseCostByOuterRows */
193     public boolean multiplyBaseCostByOuterRows() {
194         return false;
195     }
196
197     /**
198      * @see JoinStrategy#getBasePredicates
199      *
200      * @exception StandardException Thrown on error
201      */
202     public OptimizablePredicateList getBasePredicates(
203                                     OptimizablePredicateList predList,
204                                     OptimizablePredicateList basePredicates,
205                                     Optimizable innerTable)
206                             throws StandardException {
207         if (SanityManager.DEBUG) {
208             SanityManager.ASSERT(basePredicates.size() == 0,
209                 "The base predicate list should be empty.");
210         }
211
212         for (int i = predList.size() - 1; i >= 0; i--) {
213             OptimizablePredicate pred = predList.getOptPredicate(i);
214
215             if (innerTable.getReferencedTableMap().contains(pred.getReferencedMap()))
216             {
217                 basePredicates.addOptPredicate(pred);
218                 predList.removeOptPredicate(i);
219             }
220         }
221
222         basePredicates.classify(
223                 innerTable,
224                 innerTable.getCurrentAccessPath().getConglomerateDescriptor());
225
226         return basePredicates;
227     }
228
229     /** @see JoinStrategy#nonBasePredicateSelectivity */
230     public double nonBasePredicateSelectivity(
231                                         Optimizable innerTable,
232                                         OptimizablePredicateList predList)
233     throws StandardException {
234         double retval = 1.0;
235
236         if (predList != null) {
237             for (int i = 0; i < predList.size(); i++) {
238                 // Don't include redundant join predicates in selectivity calculations
239 if (predList.isRedundantPredicate(i))
240                 {
241                     continue;
242                 }
243
244                 retval *= predList.getOptPredicate(i).selectivity(innerTable);
245             }
246         }
247
248         return retval;
249     }
250     
251     /**
252      * @see JoinStrategy#putBasePredicates
253      *
254      * @exception StandardException Thrown on error
255      */
256     public void putBasePredicates(OptimizablePredicateList predList,
257                                     OptimizablePredicateList basePredicates)
258                         throws StandardException {
259         for (int i = basePredicates.size() - 1; i >= 0; i--) {
260             OptimizablePredicate pred = basePredicates.getOptPredicate(i);
261
262             predList.addOptPredicate(pred);
263             basePredicates.removeOptPredicate(i);
264         }
265     }
266
267     /** @see JoinStrategy#estimateCost */
268     public void estimateCost(Optimizable innerTable,
269                              OptimizablePredicateList predList,
270                              ConglomerateDescriptor cd,
271                              CostEstimate outerCost,
272                              Optimizer optimizer,
273                              CostEstimate costEstimate) {
274         /*
275         ** The cost of a hash join is the cost of building the hash table.
276         ** There is no extra cost per outer row, so don't do anything here.
277         */
278     }
279
280     /** @see JoinStrategy#maxCapacity */
281     public int maxCapacity( int userSpecifiedCapacity,
282                             int maxMemoryPerTable,
283                             double perRowUsage) {
284         if( userSpecifiedCapacity >= 0)
285             return userSpecifiedCapacity;
286         perRowUsage += ClassSize.estimateHashEntrySize();
287         if( perRowUsage <= 1)
288             return maxMemoryPerTable;
289         return (int)(maxMemoryPerTable/perRowUsage);
290     }
291
292     /** @see JoinStrategy#getName */
293     public String JavaDoc getName() {
294         return "HASH";
295     }
296
297     /** @see JoinStrategy#scanCostType */
298     public int scanCostType() {
299         return StoreCostController.STORECOST_SCAN_SET;
300     }
301
302     /** @see JoinStrategy#resultSetMethodName */
303     public String JavaDoc resultSetMethodName(boolean bulkFetch) {
304         return "getHashScanResultSet";
305     }
306
307     /** @see JoinStrategy#joinResultSetMethodName */
308     public String JavaDoc joinResultSetMethodName() {
309         return "getHashJoinResultSet";
310     }
311
312     /** @see JoinStrategy#halfOuterJoinResultSetMethodName */
313     public String JavaDoc halfOuterJoinResultSetMethodName() {
314         return "getHashLeftOuterJoinResultSet";
315     }
316
317     /**
318      * @see JoinStrategy#getScanArgs
319      *
320      * @exception StandardException Thrown on error
321      */
322     public int getScanArgs(
323                             TransactionController tc,
324                             MethodBuilder mb,
325                             Optimizable innerTable,
326                             OptimizablePredicateList storeRestrictionList,
327                             OptimizablePredicateList nonStoreRestrictionList,
328                             ExpressionClassBuilderInterface acbi,
329                             int bulkFetch,
330                             MethodBuilder resultRowAllocator,
331                             int colRefItem,
332                             int indexColItem,
333                             int lockMode,
334                             boolean tableLocked,
335                             int isolationLevel,
336                             int maxMemoryPerTable
337                             )
338                         throws StandardException {
339         ExpressionClassBuilder acb = (ExpressionClassBuilder) acbi;
340
341         fillInScanArgs1(tc,
342                                         mb,
343                                         innerTable,
344                                         storeRestrictionList,
345                                         acb,
346                                         resultRowAllocator);
347
348         nonStoreRestrictionList.generateQualifiers(acb, mb, innerTable, true);
349         mb.push(innerTable.initialCapacity());
350         mb.push(innerTable.loadFactor());
351         mb.push(innerTable.maxCapacity( (JoinStrategy) this, maxMemoryPerTable));
352         /* Get the hash key columns and wrap them in a formattable */
353         int[] hashKeyColumns = innerTable.hashKeyColumns();
354         FormatableIntHolder[] fihArray =
355                 FormatableIntHolder.getFormatableIntHolders(hashKeyColumns);
356         FormatableArrayHolder hashKeyHolder = new FormatableArrayHolder(fihArray);
357         int hashKeyItem = acb.addItem(hashKeyHolder);
358         mb.push(hashKeyItem);
359
360         fillInScanArgs2(mb,
361                         innerTable,
362                         bulkFetch,
363                         colRefItem,
364                         indexColItem,
365                         lockMode,
366                         tableLocked,
367                         isolationLevel);
368
369         return 28;
370     }
371
372     /**
373      * @see JoinStrategy#divideUpPredicateLists
374      *
375      * @exception StandardException Thrown on error
376      */
377     public void divideUpPredicateLists(
378                     Optimizable innerTable,
379                     OptimizablePredicateList originalRestrictionList,
380                     OptimizablePredicateList storeRestrictionList,
381                     OptimizablePredicateList nonStoreRestrictionList,
382                     OptimizablePredicateList requalificationRestrictionList,
383                     DataDictionary dd
384                     ) throws StandardException
385     {
386         /*
387         ** If we are walking a non-covering index, then all predicates that
388         ** get evaluated in the HashScanResultSet, whether during the building
389         ** or probing of the hash table, need to be evaluated at both the
390         ** IndexRowToBaseRowResultSet and the HashScanResultSet to ensure
391         ** that the rows materialized into the hash table still qualify when
392         ** we go to read the row from the heap. This also includes predicates
393         ** that are not qualifier/start/stop keys (hence not in store/non-store
394         ** list).
395         */
396         originalRestrictionList.copyPredicatesToOtherList(
397             requalificationRestrictionList);
398
399         ConglomerateDescriptor cd =
400             innerTable.getTrulyTheBestAccessPath().getConglomerateDescriptor();
401
402         /* For the inner table of a hash join, then divide up the predicates:
403          *
404          * o restrictionList - predicates that get applied when creating
405          * the hash table (single table clauses)
406          *
407          * o nonBaseTableRestrictionList
408          * - those that get applied when probing into the
409          * hash table (equijoin clauses on key columns,
410          * ordered by key column position first, followed
411          * by any other join predicates. (All predicates
412          * in this list are qualifiers which can be
413          * evaluated in the store).
414          *
415          * o baseTableRL - Only applicable if this is not a covering
416          * index. In that case, we will need to
417          * requalify the data page. Thus, this list
418          * will include all predicates.
419          */
420
421         // Build the list to be applied when creating the hash table
422 originalRestrictionList.transferPredicates(
423                                     storeRestrictionList,
424                                     innerTable.getReferencedTableMap(),
425                                     innerTable);
426
427         /*
428          * Eliminate any non-qualifiers that may have been pushed, but
429          * are redundant and not useful for hash join.
430          *
431          * For instance "in" (or other non-qualifier) was pushed down for
432          * start/stop key, * but for hash join, it may no longer be because
433          * previous key column may have been disqualified (eg., correlation).
434          * We simply remove
435          * such non-qualifier ("in") because we left it as residual predicate
436          * anyway. It's easier/safer to filter it out here than detect it
437          * ealier (and not push it down). Beetle 4316.
438          *
439          * Can't filter out OR list, as it is not a residual predicate,
440          */
441         for (int i = storeRestrictionList.size() - 1; i >= 0; i--)
442         {
443             Predicate p1 = (Predicate) storeRestrictionList.getOptPredicate(i);
444
445            
446             if (!p1.isStoreQualifier() && !p1.isStartKey() && !p1.isStopKey())
447             {
448                 storeRestrictionList.removeOptPredicate(i);
449             }
450         }
451
452         for (int i = originalRestrictionList.size() - 1; i >= 0; i--)
453         {
454             Predicate p1 =
455                 (Predicate) originalRestrictionList.getOptPredicate(i);
456
457             if (!p1.isStoreQualifier())
458                 originalRestrictionList.removeOptPredicate(i);
459         }
460
461         /* Copy the rest of the predicates to the non-store list */
462         originalRestrictionList.copyPredicatesToOtherList(
463                                                     nonStoreRestrictionList);
464
465         /* If innerTable is ProjectRestrictNode, we need to use its child
466          * to find hash key columns, this is because ProjectRestrictNode may
467          * not have underlying node's every result column as result column,
468          * and the predicate's column reference was bound to the underlying
469          * node's column position. Also we have to pass in the
470          * ProjectRestrictNode rather than the underlying node to this method
471          * because a predicate's referencedTableMap references the table number
472          * of the ProjectRestrictiveNode. And we need this info to see if
473          * a predicate is in storeRestrictionList that can be pushed down.
474          * Beetle 3458.
475          */
476         Optimizable hashTableFor = innerTable;
477         if (innerTable instanceof ProjectRestrictNode)
478         {
479             ProjectRestrictNode prn = (ProjectRestrictNode) innerTable;
480             if (prn.getChildResult() instanceof Optimizable)
481                 hashTableFor = (Optimizable) (prn.getChildResult());
482         }
483         int[] hashKeyColumns = findHashKeyColumns(hashTableFor,
484                                                 cd,
485                                                 nonStoreRestrictionList);
486         if (hashKeyColumns != null)
487         {
488             innerTable.setHashKeyColumns(hashKeyColumns);
489         }
490         else
491         {
492             String JavaDoc name;
493             if (cd != null && cd.isIndex())
494             {
495                 name = cd.getConglomerateName();
496             }
497             else
498             {
499                 name = innerTable.getBaseTableName();
500             }
501
502             throw StandardException.newException(SQLState.LANG_HASH_NO_EQUIJOIN_FOUND,
503                         name,
504                         innerTable.getBaseTableName());
505         }
506
507         // Mark all of the predicates in the probe list as qualifiers
508 nonStoreRestrictionList.markAllPredicatesQualifiers();
509
510         int[] conglomColumn = new int[hashKeyColumns.length];
511         if (cd != null && cd.isIndex())
512         {
513             /*
514             ** If the conglomerate is an index, get the column numbers of the
515             ** hash keys in the base heap.
516             */
517             for (int index = 0; index < hashKeyColumns.length; index++)
518             {
519                 conglomColumn[index] =
520                   cd.getIndexDescriptor().baseColumnPositions()[hashKeyColumns[index]];
521             }
522         }
523         else
524         {
525             /*
526             ** If the conglomerate is a heap, the column numbers of the hash
527             ** key are the column numbers returned by findHashKeyColumns().
528             **
529             ** NOTE: Must switch from zero-based to one-based
530             */
531             for (int index = 0; index < hashKeyColumns.length; index++)
532             {
533                 conglomColumn[index] = hashKeyColumns[index] + 1;
534             }
535         }
536
537         /* Put the equality predicates on the key columns for the hash first.
538          * (Column # is columns[colCtr] from above.)
539          */
540         for (int index = hashKeyColumns.length - 1; index >= 0; index--)
541         {
542             nonStoreRestrictionList.putOptimizableEqualityPredicateFirst(
543                     innerTable,
544                     conglomColumn[index]);
545         }
546     }
547
548     /**
549      * @see JoinStrategy#isHashJoin
550      */
551     public boolean isHashJoin()
552     {
553         return true;
554     }
555
556     /**
557      * @see JoinStrategy#doesMaterialization
558      */
559     public boolean doesMaterialization()
560     {
561         return true;
562     }
563
564     /**
565      * Find the hash key columns, if any, to use with this join.
566      *
567      * @param innerTable The inner table of the join
568      * @param cd The conglomerate descriptor to use on inner table
569      * @param predList The predicate list to look for the equijoin in
570      *
571      * @return the numbers of the hash key columns, or null if no hash key column
572      *
573      * @exception StandardException Thrown on error
574      */
575     private int[] findHashKeyColumns(Optimizable innerTable,
576                                     ConglomerateDescriptor cd,
577                                     OptimizablePredicateList predList)
578                 throws StandardException
579     {
580         if (predList == null)
581             return (int[]) null;
582
583         /* Find the column to use as the hash key.
584          * (There must be an equijoin condition on this column.)
585          * If cd is null, then Optimizable is not a scan.
586          * For indexes, we start at the first column in the key
587          * and walk the key columns until we find the first one with
588          * an equijoin condition on it. We do essentially the same
589          * for heaps. (From column 1 through column n.)
590          */
591         int[] columns = null;
592         if (cd == null)
593         {
594             columns = new int[innerTable.getNumColumnsReturned()];
595             for (int j = 0; j < columns.length; j++)
596             {
597                 columns[j] = j + 1;
598             }
599         }
600         else if (cd.isIndex())
601         {
602             columns = cd.getIndexDescriptor().baseColumnPositions();
603         }
604         else
605         {
606             columns =
607                 new int[innerTable.getTableDescriptor().getNumberOfColumns()];
608             for (int j = 0; j < columns.length; j++)
609             {
610                 columns[j] = j + 1;
611             }
612         }
613
614         // Build a Vector of all the hash key columns
615 int colCtr;
616         Vector JavaDoc hashKeyVector = new Vector JavaDoc();
617         for (colCtr = 0; colCtr < columns.length; colCtr++)
618         {
619             // Is there an equijoin condition on this column?
620 if (predList.hasOptimizableEquijoin(innerTable, columns[colCtr]))
621             {
622                 hashKeyVector.addElement(new Integer JavaDoc(colCtr));
623             }
624         }
625
626         // Convert the Vector into an int[], if there are hash key columns
627 if (hashKeyVector.size() > 0)
628         {
629             int[] keyCols = new int[hashKeyVector.size()];
630             for (int index = 0; index < keyCols.length; index++)
631             {
632                 keyCols[index] = ((Integer JavaDoc) hashKeyVector.elementAt(index)).intValue();
633             }
634             return keyCols;
635         }
636         else
637             return (int[]) null;
638     }
639
640     public String JavaDoc toString() {
641         return getName();
642     }
643 }
644
Popular Tags