Source code: org/apache/derby/iapi/sql/compile/Optimizer.java
1 /*
2
3 Derby - Class org.apache.derby.iapi.sql.compile.Optimizer
4
5 Copyright 1997, 2004 The Apache Software Foundation or its licensors, as applicable.
6
7 Licensed under the Apache License, Version 2.0 (the "License");
8 you may not use this file except in compliance with the License.
9 You may obtain a copy of the License at
10
11 http://www.apache.org/licenses/LICENSE-2.0
12
13 Unless required by applicable law or agreed to in writing, software
14 distributed under the License is distributed on an "AS IS" BASIS,
15 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 See the License for the specific language governing permissions and
17 limitations under the License.
18
19 */
20
21 package org.apache.derby.iapi.sql.compile;
22
23 import org.apache.derby.iapi.sql.dictionary.DataDictionary;
24 import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
25 import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
26
27 import org.apache.derby.iapi.error.StandardException;
28
29 import org.apache.derby.iapi.util.JBitSet;
30
31 /**
32 * Optimizer provides services for optimizing a query.
33 * RESOLVE:
34 * o Need to figure out what to do about subqueries, figuring out
35 * their attachment points and how to communicate them back to the
36 * caller.
37 */
38
39 public interface Optimizer {
40 /**
41 Module name for the monitor's module locating system.
42 */
43 String MODULE = "org.apache.derby.iapi.sql.compile.Optimizer";
44
45 /**
46 Property name for controlling whether to do join order optimization.
47 */
48 String JOIN_ORDER_OPTIMIZATION = "derby.optimizer.optimizeJoinOrder";
49
50 /**
51 Property name for controlling whether to do rule-based optimization,
52 as opposed to cost-based optimization.
53 */
54 String RULE_BASED_OPTIMIZATION =
55 "derby.optimizer.ruleBasedOptimization";
56
57 /**
58 Property name for controlling whether the optimizer ever times out
59 while optimizing a query and goes with the best plan so far.
60 */
61 String NO_TIMEOUT = "derby.optimizer.noTimeout";
62
63 /**
64 Property name for controlling the maximum size of memory (in KB)
65 the optimizer can use for each table. If an access path takes
66 memory larger than that size for a table, the access path is skipped.
67 Default is 1024 (KB).
68 */
69 String MAX_MEMORY_PER_TABLE = "derby.language.maxMemoryPerTable";
70
71 /**
72 Property name for disabling statistics use for all queries.
73 */
74 String USE_STATISTICS = "derby.language.useStatistics";
75
76 /** Indicates a "normal" plan that is not optimized to do sort avoidance */
77 int NORMAL_PLAN = 1;
78
79 /** Indicates a sort-avoidance plan */
80 int SORT_AVOIDANCE_PLAN = 2;
81
82 // optimizer trace
83 public static final int STARTED = 1;
84 public static final int TIME_EXCEEDED =2;
85 public static final int NO_TABLES = 3;
86 public static final int COMPLETE_JOIN_ORDER = 4;
87 public static final int COST_OF_SORTING = 5;
88 public static final int NO_BEST_PLAN = 6;
89 public static final int MODIFYING_ACCESS_PATHS = 7;
90 public static final int SHORT_CIRCUITING = 8;
91 public static final int SKIPPING_JOIN_ORDER = 9;
92 public static final int ILLEGAL_USER_JOIN_ORDER = 10;
93 public static final int USER_JOIN_ORDER_OPTIMIZED = 11;
94 public static final int CONSIDERING_JOIN_ORDER = 12;
95 public static final int TOTAL_COST_NON_SA_PLAN = 13;
96 public static final int TOTAL_COST_SA_PLAN = 14;
97 public static final int TOTAL_COST_WITH_SORTING = 15;
98 public static final int CURRENT_PLAN_IS_SA_PLAN = 16;
99 public static final int CHEAPEST_PLAN_SO_FAR = 17;
100 public static final int PLAN_TYPE = 18;
101 public static final int COST_OF_CHEAPEST_PLAN_SO_FAR = 19;
102 public static final int SORT_NEEDED_FOR_ORDERING = 20;
103 public static final int REMEMBERING_BEST_JOIN_ORDER = 21;
104 public static final int SKIPPING_DUE_TO_EXCESS_MEMORY = 22;
105 public static final int COST_OF_N_SCANS = 23;
106 public static final int HJ_SKIP_NOT_MATERIALIZABLE = 24;
107 public static final int HJ_SKIP_NO_JOIN_COLUMNS = 25;
108 public static final int HJ_HASH_KEY_COLUMNS = 26;
109 public static final int CALLING_ON_JOIN_NODE = 27;
110 public static final int CONSIDERING_JOIN_STRATEGY = 28;
111 public static final int REMEMBERING_BEST_ACCESS_PATH = 29;
112 public static final int NO_MORE_CONGLOMERATES = 30;
113 public static final int CONSIDERING_CONGLOMERATE = 31;
114 public static final int SCANNING_HEAP_FULL_MATCH_ON_UNIQUE_KEY = 32;
115 public static final int ADDING_UNORDERED_OPTIMIZABLE = 33;
116 public static final int CHANGING_ACCESS_PATH_FOR_TABLE = 34;
117 public static final int TABLE_LOCK_NO_START_STOP = 35;
118 public static final int NON_COVERING_INDEX_COST = 36;
119 public static final int ROW_LOCK_ALL_CONSTANT_START_STOP = 37;
120 public static final int ESTIMATING_COST_OF_CONGLOMERATE = 38;
121 public static final int LOOKING_FOR_SPECIFIED_INDEX = 39;
122 public static final int MATCH_SINGLE_ROW_COST = 40;
123 public static final int COST_INCLUDING_EXTRA_1ST_COL_SELECTIVITY = 41;
124 public static final int CALLING_NEXT_ACCESS_PATH = 42;
125 public static final int TABLE_LOCK_OVER_THRESHOLD = 43;
126 public static final int ROW_LOCK_UNDER_THRESHOLD = 44;
127 public static final int COST_INCLUDING_EXTRA_START_STOP = 45;
128 public static final int COST_INCLUDING_EXTRA_QUALIFIER_SELECTIVITY = 46;
129 public static final int COST_INCLUDING_EXTRA_NONQUALIFIER_SELECTIVITY = 47;
130 public static final int COST_OF_NONCOVERING_INDEX = 48;
131 public static final int REMEMBERING_JOIN_STRATEGY = 49;
132 public static final int REMEMBERING_BEST_ACCESS_PATH_SUBSTRING = 50;
133 public static final int REMEMBERING_BEST_SORT_AVOIDANCE_ACCESS_PATH_SUBSTRING = 51;
134 public static final int REMEMBERING_BEST_UNKNOWN_ACCESS_PATH_SUBSTRING = 52;
135 public static final int COST_OF_CONGLOMERATE_SCAN1 = 53;
136 public static final int COST_OF_CONGLOMERATE_SCAN2 = 54;
137 public static final int COST_OF_CONGLOMERATE_SCAN3 = 55;
138 public static final int COST_OF_CONGLOMERATE_SCAN4 = 56;
139 public static final int COST_OF_CONGLOMERATE_SCAN5 = 57;
140 public static final int COST_OF_CONGLOMERATE_SCAN6 = 58;
141 public static final int COST_OF_CONGLOMERATE_SCAN7 = 59;
142 public static final int COST_INCLUDING_COMPOSITE_SEL_FROM_STATS= 60;
143 public static final int COMPOSITE_SEL_FROM_STATS = 61;
144 public static final int COST_INCLUDING_STATS_FOR_INDEX = 62;
145 /**
146 * Iterate through the permutations, returning false when the permutations
147 * are exhausted.
148 * NOTE - Implementers are responsible for hiding tree pruning of permutations
149 * behind this method call.
150 *
151 * @return boolean True - An optimizable permutation remains.
152 * False - Permutations are exhausted.
153 *
154 * @exception StandardException Thrown on error
155 */
156 public boolean getNextPermutation() throws StandardException;
157
158 /**
159 * Iterate through the "decorated permutations", returning false when they
160 * are exhausted.
161 * NOTE - Implementers are responsible for hiding tree pruning of access
162 * methods behind this method call.
163 *
164 * @return boolean True - An optimizable decorated permutation remains.
165 * False - Decorated permutations are exhausted.
166 *
167 * @exception StandardException Thrown on error
168 */
169 public boolean getNextDecoratedPermutation() throws StandardException;
170
171 /**
172 * Cost the current permutation.
173 * Caller is responsible for pushing all predicates which can be evaluated
174 * prior to costing.
175 *
176 * @return Nothing.
177 *
178 * @exception StandardException Thrown on error
179 */
180 public void costPermutation() throws StandardException;
181
182 /**
183 * Cost the current Optimizable with the specified OPL.
184 * Caller is responsible for pushing all predicates which can be evaluated
185 * prior to costing.
186 *
187 * @param optimizable The Optimizable
188 * @param td TableDescriptor of the Optimizable
189 * @param cd The ConglomerateDescriptor for the conglom to cost
190 * (This should change to an object to represent
191 * access paths, but for now this is OK).
192 * @param predList The OptimizablePredicateList to apply
193 * @param outerCost The cost of the tables outer to the one being
194 * optimizer - tells how many outer rows there are.
195 * @return Nothing.
196 *
197 * @exception StandardException Thrown on error
198 */
199 public void costOptimizable(Optimizable optimizable,
200 TableDescriptor td,
201 ConglomerateDescriptor cd,
202 OptimizablePredicateList predList,
203 CostEstimate outerCost)
204 throws StandardException;
205
206 /**
207 * Consider the cost of the given optimizable. This method is like
208 * costOptimizable, above, but it is used when the Optimizable does
209 * not need help from the optimizer in costing the Optimizable (in practice,
210 * all Optimizables except FromBaseTable use this method.
211 *
212 * Caller is responsible for pushing all predicates which can be evaluated
213 * prior to costing.
214 *
215 * @param optimizable The Optimizable
216 * @param predList The OptimizablePredicateList to apply
217 * @param estimatedCost The estimated cost of the given optimizable
218 * @param outerCost The cost of the tables outer to the one being
219 * optimizer - tells how many outer rows there are.
220 * @return Nothing.
221 *
222 * @exception StandardException Thrown on error
223 */
224 public void considerCost(Optimizable optimizable,
225 OptimizablePredicateList predList,
226 CostEstimate estimatedCost,
227 CostEstimate outerCost)
228 throws StandardException;
229
230 /**
231 * Return the DataDictionary that the Optimizer is using.
232 * This is useful when an Optimizable needs to call optimize() on
233 * a child ResultSetNode.
234 *
235 * @return DataDictionary DataDictionary that the Optimizer is using.
236 */
237 public DataDictionary getDataDictionary();
238
239 /**
240 * Modify the access path for each Optimizable, as necessary. This includes
241 * things like adding result sets to translate from index rows to base rows.
242 *
243 * @exception StandardException Thrown on error
244 */
245 public void modifyAccessPaths() throws StandardException;
246
247 /** Get a new CostEstimate object */
248 public CostEstimate newCostEstimate();
249
250 /** Get the estimated cost of the optimized query */
251 public CostEstimate getOptimizedCost();
252
253 /**
254 * Set the estimated number of outer rows - good for optimizing nested
255 * optimizables like subqueries and join nodes.
256 */
257 public void setOuterRows(double outerRowCount);
258
259 /**
260 * Get the number of join strategies supported by this optimizer.
261 */
262 public int getNumberOfJoinStrategies();
263
264 /**
265 * Get the maximum number of estimated rows touched in a table before
266 * we decide to open the table with table locking (as opposed to row
267 * locking.
268 */
269 public int tableLockThreshold();
270
271 /**
272 * Gets a join strategy by number (zero-based).
273 */
274 JoinStrategy getJoinStrategy(int whichStrategy);
275
276 /**
277 * Gets a join strategy by name. Returns null if not found.
278 * The look-up is case-insensitive.
279 */
280 JoinStrategy getJoinStrategy(String whichStrategy);
281
282 /**
283 * Optimizer trace.
284 */
285 public void trace(int traceFlag, int intParam1, int intParam2,
286 double doubleParam, Object objectParam1);
287
288 /**
289 * Get the level of this optimizer.
290 *
291 * @return The level of this optimizer.
292 */
293 public int getLevel();
294
295 /**
296 * Tells whether any of the tables outer to the current one
297 * has a uniqueness condition on the given predicate list,
298 * and if so, how many times each unique key can be seen by
299 * the current table.
300 *
301 * @param predList The predicate list to check
302 *
303 * @return <= 0 means there is no uniqueness condition
304 * > 0 means there is a uniqueness condition on an
305 * outer table, and the return value is the reciprocal of
306 * the maximum number of times the optimizer estimates that each
307 * unique key will be returned. For example, 0.5 means the
308 * optimizer thinks each distinct join key will be returned
309 * at most twice.
310 *
311 * @exception StandardException Thrown on error
312 */
313 double uniqueJoinWithOuterTable(OptimizablePredicateList predList)
314 throws StandardException;
315
316 /**
317 * If statistics should be considered by the optimizer while optimizing
318 * a query. The user may disable the use of statistics by setting the
319 * property derby.optimizer.useStatistics or by using the property
320 * useStatistics in a query.
321 *
322 * @see #USE_STATISTICS
323 */
324 public boolean useStatistics();
325
326 /**
327 * @return the maximum number of bytes to be used per table.
328 */
329 public int getMaxMemoryPerTable();
330 }