001: /*
002:
003: Derby - Class org.apache.derby.iapi.sql.compile.Optimizer
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.TableDescriptor;
026: import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
027:
028: import org.apache.derby.iapi.error.StandardException;
029:
030: import org.apache.derby.iapi.util.JBitSet;
031:
032: /**
033: * Optimizer provides services for optimizing a query.
034: * RESOLVE:
035: * o Need to figure out what to do about subqueries, figuring out
036: * their attachment points and how to communicate them back to the
037: * caller.
038: */
039:
040: public interface Optimizer {
041: /**
042: Module name for the monitor's module locating system.
043: */
044: String MODULE = "org.apache.derby.iapi.sql.compile.Optimizer";
045:
046: /**
047: Property name for controlling whether to do join order optimization.
048: */
049: String JOIN_ORDER_OPTIMIZATION = "derby.optimizer.optimizeJoinOrder";
050:
051: /**
052: Property name for controlling whether to do rule-based optimization,
053: as opposed to cost-based optimization.
054: */
055: String RULE_BASED_OPTIMIZATION = "derby.optimizer.ruleBasedOptimization";
056:
057: /**
058: Property name for controlling whether the optimizer ever times out
059: while optimizing a query and goes with the best plan so far.
060: */
061: String NO_TIMEOUT = "derby.optimizer.noTimeout";
062:
063: /**
064: Property name for controlling the maximum size of memory (in KB)
065: the optimizer can use for each table. If an access path takes
066: memory larger than that size for a table, the access path is skipped.
067: Default is 1024 (KB).
068: */
069: String MAX_MEMORY_PER_TABLE = "derby.language.maxMemoryPerTable";
070:
071: /**
072: Maximum size of dynamically created materialized rows. Caching large results
073: use lot of memory and can cause stack overflow. See DERBY-634
074: */
075: int MAX_DYNAMIC_MATERIALIZED_ROWS = 512;
076:
077: /**
078: Property name for disabling statistics use for all queries.
079: */
080: String USE_STATISTICS = "derby.language.useStatistics";
081:
082: /** Indicates a "normal" plan that is not optimized to do sort avoidance */
083: int NORMAL_PLAN = 1;
084:
085: /** Indicates a sort-avoidance plan */
086: int SORT_AVOIDANCE_PLAN = 2;
087:
088: // optimizer trace
089: public static final int STARTED = 1;
090: public static final int TIME_EXCEEDED = 2;
091: public static final int NO_TABLES = 3;
092: public static final int COMPLETE_JOIN_ORDER = 4;
093: public static final int COST_OF_SORTING = 5;
094: public static final int NO_BEST_PLAN = 6;
095: public static final int MODIFYING_ACCESS_PATHS = 7;
096: public static final int SHORT_CIRCUITING = 8;
097: public static final int SKIPPING_JOIN_ORDER = 9;
098: public static final int ILLEGAL_USER_JOIN_ORDER = 10;
099: public static final int USER_JOIN_ORDER_OPTIMIZED = 11;
100: public static final int CONSIDERING_JOIN_ORDER = 12;
101: public static final int TOTAL_COST_NON_SA_PLAN = 13;
102: public static final int TOTAL_COST_SA_PLAN = 14;
103: public static final int TOTAL_COST_WITH_SORTING = 15;
104: public static final int CURRENT_PLAN_IS_SA_PLAN = 16;
105: public static final int CHEAPEST_PLAN_SO_FAR = 17;
106: public static final int PLAN_TYPE = 18;
107: public static final int COST_OF_CHEAPEST_PLAN_SO_FAR = 19;
108: public static final int SORT_NEEDED_FOR_ORDERING = 20;
109: public static final int REMEMBERING_BEST_JOIN_ORDER = 21;
110: public static final int SKIPPING_DUE_TO_EXCESS_MEMORY = 22;
111: public static final int COST_OF_N_SCANS = 23;
112: public static final int HJ_SKIP_NOT_MATERIALIZABLE = 24;
113: public static final int HJ_SKIP_NO_JOIN_COLUMNS = 25;
114: public static final int HJ_HASH_KEY_COLUMNS = 26;
115: public static final int CALLING_ON_JOIN_NODE = 27;
116: public static final int CONSIDERING_JOIN_STRATEGY = 28;
117: public static final int REMEMBERING_BEST_ACCESS_PATH = 29;
118: public static final int NO_MORE_CONGLOMERATES = 30;
119: public static final int CONSIDERING_CONGLOMERATE = 31;
120: public static final int SCANNING_HEAP_FULL_MATCH_ON_UNIQUE_KEY = 32;
121: public static final int ADDING_UNORDERED_OPTIMIZABLE = 33;
122: public static final int CHANGING_ACCESS_PATH_FOR_TABLE = 34;
123: public static final int TABLE_LOCK_NO_START_STOP = 35;
124: public static final int NON_COVERING_INDEX_COST = 36;
125: public static final int ROW_LOCK_ALL_CONSTANT_START_STOP = 37;
126: public static final int ESTIMATING_COST_OF_CONGLOMERATE = 38;
127: public static final int LOOKING_FOR_SPECIFIED_INDEX = 39;
128: public static final int MATCH_SINGLE_ROW_COST = 40;
129: public static final int COST_INCLUDING_EXTRA_1ST_COL_SELECTIVITY = 41;
130: public static final int CALLING_NEXT_ACCESS_PATH = 42;
131: public static final int TABLE_LOCK_OVER_THRESHOLD = 43;
132: public static final int ROW_LOCK_UNDER_THRESHOLD = 44;
133: public static final int COST_INCLUDING_EXTRA_START_STOP = 45;
134: public static final int COST_INCLUDING_EXTRA_QUALIFIER_SELECTIVITY = 46;
135: public static final int COST_INCLUDING_EXTRA_NONQUALIFIER_SELECTIVITY = 47;
136: public static final int COST_OF_NONCOVERING_INDEX = 48;
137: public static final int REMEMBERING_JOIN_STRATEGY = 49;
138: public static final int REMEMBERING_BEST_ACCESS_PATH_SUBSTRING = 50;
139: public static final int REMEMBERING_BEST_SORT_AVOIDANCE_ACCESS_PATH_SUBSTRING = 51;
140: public static final int REMEMBERING_BEST_UNKNOWN_ACCESS_PATH_SUBSTRING = 52;
141: public static final int COST_OF_CONGLOMERATE_SCAN1 = 53;
142: public static final int COST_OF_CONGLOMERATE_SCAN2 = 54;
143: public static final int COST_OF_CONGLOMERATE_SCAN3 = 55;
144: public static final int COST_OF_CONGLOMERATE_SCAN4 = 56;
145: public static final int COST_OF_CONGLOMERATE_SCAN5 = 57;
146: public static final int COST_OF_CONGLOMERATE_SCAN6 = 58;
147: public static final int COST_OF_CONGLOMERATE_SCAN7 = 59;
148: public static final int COST_INCLUDING_COMPOSITE_SEL_FROM_STATS = 60;
149: public static final int COMPOSITE_SEL_FROM_STATS = 61;
150: public static final int COST_INCLUDING_STATS_FOR_INDEX = 62;
151:
152: /**
153: * Iterate through the permutations, returning false when the permutations
154: * are exhausted.
155: * NOTE - Implementers are responsible for hiding tree pruning of permutations
156: * behind this method call.
157: *
158: * @return boolean True - An optimizable permutation remains.
159: * False - Permutations are exhausted.
160: *
161: * @exception StandardException Thrown on error
162: */
163: public boolean getNextPermutation() throws StandardException;
164:
165: /**
166: * Iterate through the "decorated permutations", returning false when they
167: * are exhausted.
168: * NOTE - Implementers are responsible for hiding tree pruning of access
169: * methods behind this method call.
170: *
171: * @return boolean True - An optimizable decorated permutation remains.
172: * False - Decorated permutations are exhausted.
173: *
174: * @exception StandardException Thrown on error
175: */
176: public boolean getNextDecoratedPermutation()
177: throws StandardException;
178:
179: /**
180: * Cost the current permutation.
181: * Caller is responsible for pushing all predicates which can be evaluated
182: * prior to costing.
183: *
184: * @exception StandardException Thrown on error
185: */
186: public void costPermutation() throws StandardException;
187:
188: /**
189: * Cost the current Optimizable with the specified OPL.
190: * Caller is responsible for pushing all predicates which can be evaluated
191: * prior to costing.
192: *
193: * @param optimizable The Optimizable
194: * @param td TableDescriptor of the Optimizable
195: * @param cd The ConglomerateDescriptor for the conglom to cost
196: * (This should change to an object to represent
197: * access paths, but for now this is OK).
198: * @param predList The OptimizablePredicateList to apply
199: * @param outerCost The cost of the tables outer to the one being
200: * optimizer - tells how many outer rows there are.
201: *
202: * @exception StandardException Thrown on error
203: */
204: public void costOptimizable(Optimizable optimizable,
205: TableDescriptor td, ConglomerateDescriptor cd,
206: OptimizablePredicateList predList, CostEstimate outerCost)
207: throws StandardException;
208:
209: /**
210: * Consider the cost of the given optimizable. This method is like
211: * costOptimizable, above, but it is used when the Optimizable does
212: * not need help from the optimizer in costing the Optimizable (in practice,
213: * all Optimizables except FromBaseTable use this method.
214: *
215: * Caller is responsible for pushing all predicates which can be evaluated
216: * prior to costing.
217: *
218: * @param optimizable The Optimizable
219: * @param predList The OptimizablePredicateList to apply
220: * @param estimatedCost The estimated cost of the given optimizable
221: * @param outerCost The cost of the tables outer to the one being
222: * optimizer - tells how many outer rows there are.
223: *
224: * @exception StandardException Thrown on error
225: */
226: public void considerCost(Optimizable optimizable,
227: OptimizablePredicateList predList,
228: CostEstimate estimatedCost, CostEstimate outerCost)
229: throws StandardException;
230:
231: /**
232: * Return the DataDictionary that the Optimizer is using.
233: * This is useful when an Optimizable needs to call optimize() on
234: * a child ResultSetNode.
235: *
236: * @return DataDictionary DataDictionary that the Optimizer is using.
237: */
238: public DataDictionary getDataDictionary();
239:
240: /**
241: * Modify the access path for each Optimizable, as necessary. This includes
242: * things like adding result sets to translate from index rows to base rows.
243: *
244: * @exception StandardException Thrown on error
245: */
246: public void modifyAccessPaths() throws StandardException;
247:
248: /** Get a new CostEstimate object */
249: public CostEstimate newCostEstimate();
250:
251: /** Get the estimated cost of the optimized query */
252: public CostEstimate getOptimizedCost();
253:
254: /**
255: * Get the final estimated cost of the optimized query. This
256: * should be the cost that corresponds to the best overall join
257: * order chosen by the optimizer, and thus this method should
258: * only be called after optimization is complete (i.e. when
259: * modifying access paths).
260: */
261: public CostEstimate getFinalCost();
262:
263: /**
264: * Prepare for another round of optimization.
265: *
266: * This method is called before every "round" of optimization, where
267: * we define a "round" to be the period between the last time a call to
268: * getOptimizer() (on either a ResultSetNode or an OptimizerFactory)
269: * returned _this_ Optimizer and the time a call to this Optimizer's
270: * getNextPermutation() method returns FALSE. Any re-initialization
271: * of state that is required before each round should be done in this
272: * method.
273: */
274: public void prepForNextRound();
275:
276: /**
277: * Set the estimated number of outer rows - good for optimizing nested
278: * optimizables like subqueries and join nodes.
279: */
280: public void setOuterRows(double outerRowCount);
281:
282: /**
283: * Get the number of join strategies supported by this optimizer.
284: */
285: public int getNumberOfJoinStrategies();
286:
287: /**
288: * Get the maximum number of estimated rows touched in a table before
289: * we decide to open the table with table locking (as opposed to row
290: * locking.
291: */
292: public int tableLockThreshold();
293:
294: /**
295: * Gets a join strategy by number (zero-based).
296: */
297: JoinStrategy getJoinStrategy(int whichStrategy);
298:
299: /**
300: * Gets a join strategy by name. Returns null if not found.
301: * The look-up is case-insensitive.
302: */
303: JoinStrategy getJoinStrategy(String whichStrategy);
304:
305: /**
306: * Optimizer trace.
307: */
308: public void trace(int traceFlag, int intParam1, int intParam2,
309: double doubleParam, Object objectParam1);
310:
311: /**
312: * Get the level of this optimizer.
313: *
314: * @return The level of this optimizer.
315: */
316: public int getLevel();
317:
318: /**
319: * Tells whether any of the tables outer to the current one
320: * has a uniqueness condition on the given predicate list,
321: * and if so, how many times each unique key can be seen by
322: * the current table.
323: *
324: * @param predList The predicate list to check
325: *
326: * @return <= 0 means there is no uniqueness condition
327: * > 0 means there is a uniqueness condition on an
328: * outer table, and the return value is the reciprocal of
329: * the maximum number of times the optimizer estimates that each
330: * unique key will be returned. For example, 0.5 means the
331: * optimizer thinks each distinct join key will be returned
332: * at most twice.
333: *
334: * @exception StandardException Thrown on error
335: */
336: double uniqueJoinWithOuterTable(OptimizablePredicateList predList)
337: throws StandardException;
338:
339: /**
340: * If statistics should be considered by the optimizer while optimizing
341: * a query. The user may disable the use of statistics by setting the
342: * property derby.optimizer.useStatistics or by using the property
343: * useStatistics in a query.
344: *
345: * @see #USE_STATISTICS
346: */
347: public boolean useStatistics();
348:
349: /**
350: * @return the maximum number of bytes to be used per table.
351: */
352: public int getMaxMemoryPerTable();
353: }
|