001: /*
002:
003: Derby - Class org.apache.derby.iapi.sql.compile.JoinStrategy
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.iapi.sql.compile;
023:
024: import org.apache.derby.iapi.sql.dictionary.DataDictionary;
025: import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
026:
027: import org.apache.derby.iapi.store.access.TransactionController;
028:
029: import org.apache.derby.iapi.services.compiler.MethodBuilder;
030:
031: import org.apache.derby.iapi.error.StandardException;
032:
033: /**
034: * A JoinStrategy represents a strategy like nested loop, hash join,
035: * merge join, etc. It tells the optimizer whether the strategy is
036: * feasible in a given situation, how much the strategy costs, whether
037: * the strategy requires the data from the source result sets to be ordered,
038: * etc.
039: */
040:
041: public interface JoinStrategy {
042: /**
043: * Is this join strategy feasible under the circumstances?
044: *
045: * @param innerTable The inner table of the join
046: * @param predList The predicateList for the join
047: * @param optimizer The optimizer to use
048: *
049: * @return true means the strategy is feasible, false means it isn't
050: *
051: * @exception StandardException Thrown on error
052: */
053: boolean feasible(Optimizable innerTable,
054: OptimizablePredicateList predList, Optimizer optimizer)
055: throws StandardException;
056:
057: /**
058: * Is it OK to use bulk fetch with this join strategy?
059: */
060: boolean bulkFetchOK();
061:
062: /**
063: * Should we just ignore bulk fetch with this join strategy?
064: */
065: boolean ignoreBulkFetch();
066:
067: /**
068: * Returns true if the base cost of scanning the conglomerate should be
069: * multiplied by the number of outer rows.
070: */
071: boolean multiplyBaseCostByOuterRows();
072:
073: /**
074: * Get the base predicates for this join strategy. The base predicates
075: * are the ones that can be used while scanning the table. For some
076: * join strategies (for example, nested loop), all predicates are base
077: * predicates. For other join strategies (for example, hash join),
078: * the base predicates are those that involve comparisons with constant
079: * expressions.
080: *
081: * Also, order the base predicates according to the order in the
082: * proposed conglomerate descriptor for the inner table.
083: *
084: * @param predList The predicate list to pull from.
085: * @param basePredicates The list to put the base predicates in.
086: * @param innerTable The inner table of the join
087: *
088: * @return The base predicate list. If no predicates are pulled,
089: * it may return the source predList without doing anything.
090: *
091: * @exception StandardException Thrown on error
092: */
093: OptimizablePredicateList getBasePredicates(
094: OptimizablePredicateList predList,
095: OptimizablePredicateList basePredicates,
096: Optimizable innerTable) throws StandardException;
097:
098: /**
099: * Get the extra selectivity of the non-base predicates (those that were
100: * left in the predicate list by getBasePredicates() that are not
101: * applied to the scan of the base conglomerate.
102: *
103: * NOTE: For some types of join strategy, it may not remove any predicates
104: * from the original predicate list. The join strategy is expected to
105: * know when it does this, and to return 1.0 as the extra selectivity
106: * in these cases.
107: *
108: * @param innerTable The inner table of the join.
109: * @param predList The original predicate list that was passed to
110: * getBasePredicates(), from which some base predicates
111: * may have been pulled.
112: *
113: * @return The extra selectivity due to non-base predicates
114: */
115: double nonBasePredicateSelectivity(Optimizable innerTable,
116: OptimizablePredicateList predList) throws StandardException;
117:
118: /**
119: * Put back and base predicates that were removed from the list by
120: * getBasePredicates (see above).
121: *
122: * NOTE: Those join strategies that treat all predicates as base
123: * predicates may treat the get and put methods as no-ops.
124: *
125: * @param predList The list of predicates to put the base predicates
126: * back in.
127: * @param basePredicates The base predicates to put back in the list.
128: *
129: * @exception StandardException Thrown on error
130: */
131: void putBasePredicates(OptimizablePredicateList predList,
132: OptimizablePredicateList basePredicates)
133: throws StandardException;
134:
135: /**
136: * Get the estimated cost for the join.
137: *
138: * @param predList The predicate list for the join
139: * @param innerTable The inner table to join with
140: * @param cd The conglomerate descriptor (if appropriate) to get
141: * the cost of
142: * @param outerCost The estimated cost of the part of the plan outer
143: * to the inner table
144: * @param optimizer The optimizer to use to help estimate the cost
145: * @param costEstimate The estimated cost of doing a single scan of the
146: * inner table, to be filled in with the cost of
147: * doing the join.
148: *
149: * @exception StandardException Thrown on error
150: */
151: void estimateCost(Optimizable innerTable,
152: OptimizablePredicateList predList,
153: ConglomerateDescriptor cd, CostEstimate outerCost,
154: Optimizer optimizer, CostEstimate costEstimate)
155: throws StandardException;
156:
157: /**
158: * @param userSpecifiedCapacity
159: * @param maxMemoryPerTable maximum number of bytes per table
160: * @param perRowUsage number of bytes per row
161: *
162: * @return The maximum number of rows that can be handled by this join strategy
163: */
164: public int maxCapacity(int userSpecifiedCapacity,
165: int maxMemoryPerTable, double perRowUsage);
166:
167: /** Get the name of this join strategy */
168: String getName();
169:
170: /** Get the costing type, for use with StoreCostController.getScanCost */
171: int scanCostType();
172:
173: /**
174: * Get the name of the result set method for base table scans
175: *
176: * @param bulkFetch True means bulk fetch is being done on the inner
177: * table
178: */
179: String resultSetMethodName(boolean bulkFetch);
180:
181: /**
182: * Get the name of the join result set method for the join
183: */
184: String joinResultSetMethodName();
185:
186: /**
187: * Get the name of the join result set method for the half outerjoin
188: */
189: String halfOuterJoinResultSetMethodName();
190:
191: /**
192: * Get the appropriate arguments to the scan for this type of join.
193: *
194: * @param tc The TransactionController
195: * @param mb The method to generate the arguments in
196: * @param innerTable The inner table of the join
197: * @param storeRestrictionList The predicate list to be evaluated in the
198: * store
199: * @param nonStoreRestrictionList The predicate list to be evaluated
200: * outside of the store
201: * @param acb The expression class builder for the activation class
202: * we're building
203: * @param bulkFetch The amount of bulk fetch to do
204: * @param resultRowAllocator A completed method to allocate the result row
205: * @param colRefItem The item number of the column reference bit map
206: * @param lockMode The lock mode to use when scanning the table
207: * (see TransactionController).
208: * @param tableLocked Whether or not the table is marked (in sys.systables)
209: * as always using table locking
210: * @param isolationLevel Isolation level specified (or not) for scans
211: * @param maxMemoryPerTable Max memory per table
212: *
213: * @return Count of the expressions pushed to use as the parameters to the
214: * result set for the inner table
215: *
216: * @exception StandardException Thrown on error
217: */
218: int getScanArgs(TransactionController tc, MethodBuilder mb,
219: Optimizable innerTable,
220: OptimizablePredicateList storeRestrictionList,
221: OptimizablePredicateList nonStoreRestrictionList,
222: ExpressionClassBuilderInterface acb, int bulkFetch,
223: MethodBuilder resultRowAllocator, int colRefItem,
224: int indexColItem, int lockMode, boolean tableLocked,
225: int isolationLevel, int maxMemoryPerTable)
226: throws StandardException;
227:
228: /**
229: * Divide up the predicates into different lists for different phases
230: * of the operation. When this method is called, all of the predicates
231: * will be in restrictionList. The effect of this method is to
232: * remove all of the predicates from restrictionList except those that
233: * will be pushed down to the store as start/stop predicates or
234: * Qualifiers. The remaining predicates will be put into
235: * nonBaseTableRestrictionList.
236: *
237: * All predicate lists will be ordered as necessary for use with
238: * the conglomerate.
239: *
240: * Some operations (like hash join) materialize results, and so
241: * require requalification of rows when doing a non-covering index
242: * scan. The predicates to use for requalification are copied into
243: * baseTableRestrictionList.
244: *
245: * @param innerTable The inner table of the join
246: * @param originalRestrictionList Initially contains all predicates.
247: * This method removes predicates from
248: * this list and moves them to other
249: * lists, as appropriate.
250: * @param storeRestrictionList To be filled in with predicates to
251: * be pushed down to store.
252: * @param nonStoreRestrictionList To be filled in with predicates
253: * that are not pushed down to the
254: * store.
255: * @param requalificationRestrictionList Copy of predicates used to
256: * re-qualify rows, if necessary.
257: * @param dd The DataDictionary
258: *
259: * @exception StandardException Thrown on error
260: */
261: void divideUpPredicateLists(Optimizable innerTable,
262: OptimizablePredicateList originalRestrictionList,
263: OptimizablePredicateList storeRestrictionList,
264: OptimizablePredicateList nonStoreRestrictionList,
265: OptimizablePredicateList requalificationRestrictionList,
266: DataDictionary dd) throws StandardException;
267:
268: /**
269: * Is this a form of hash join?
270: *
271: * @return Whether or not this strategy is a form
272: * of hash join.
273: */
274: public boolean isHashJoin();
275:
276: /**
277: * Is materialization built in to the join strategy?
278: *
279: * @return Whether or not materialization is built in to the join strategy
280: */
281: public boolean doesMaterialization();
282: }
|