Optimizer


1   /*
2   
3      Derby - Class org.apache.derby.iapi.sql.compile.Optimizer
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.iapi.sql.compile;
23  
24  import org.apache.derby.iapi.sql.dictionary.DataDictionary;
25  import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
26  import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
27  
28  import org.apache.derby.iapi.error.StandardException;
29  
30  import org.apache.derby.iapi.util.JBitSet;
31  
32  /**
33   * Optimizer provides services for optimizing a query.
34   * RESOLVE:
35   *  o  Need to figure out what to do about subqueries, figuring out
36   *     their attachment points and how to communicate them back to the
37   *     caller.
38   */
39  
40  public interface Optimizer {
41      /**
42          Module name for the monitor's module locating system.
43       */
44      String   MODULE = "org.apache.derby.iapi.sql.compile.Optimizer";
45  
46      /**
47          Property name for controlling whether to do join order optimization.
48       */
49      String   JOIN_ORDER_OPTIMIZATION = "derby.optimizer.optimizeJoinOrder";
50  
51      /**
52          Property name for controlling whether to do rule-based optimization,
53          as opposed to cost-based optimization.
54       */
55      String   RULE_BASED_OPTIMIZATION =
56                          "derby.optimizer.ruleBasedOptimization";
57  
58      /**
59          Property name for controlling whether the optimizer ever times out
60          while optimizing a query and goes with the best plan so far.
61       */
62      String   NO_TIMEOUT = "derby.optimizer.noTimeout";
63  
64      /**
65          Property name for controlling the maximum size of memory (in KB)
66          the optimizer can use for each table.  If an access path takes
67          memory larger than that size for a table, the access path is skipped.
68          Default is 1024 (KB).
69       */
70      String   MAX_MEMORY_PER_TABLE = "derby.language.maxMemoryPerTable";
71  
72      /**
73          Maximum size of dynamically created materialized rows. Caching large results
74          use lot of memory and can cause stack overflow. See DERBY-634
75      */
76      int MAX_DYNAMIC_MATERIALIZED_ROWS = 512;
77  
78      /**
79         Property name for disabling statistics use for all queries.
80      */
81      String   USE_STATISTICS = "derby.language.useStatistics";
82  
83      /** Indicates a "normal" plan that is not optimized to do sort avoidance */
84      int NORMAL_PLAN = 1;
85  
86      /** Indicates a sort-avoidance plan */
87      int SORT_AVOIDANCE_PLAN = 2;
88  
89      // optimizer trace
90      public static final int STARTED = 1;
91      public static final int TIME_EXCEEDED =2;
92      public static final int NO_TABLES = 3;
93      public static final int COMPLETE_JOIN_ORDER = 4;
94      public static final int COST_OF_SORTING = 5;
95      public static final int NO_BEST_PLAN = 6;
96      public static final int MODIFYING_ACCESS_PATHS = 7;
97      public static final int SHORT_CIRCUITING = 8;
98      public static final int SKIPPING_JOIN_ORDER = 9;
99      public static final int ILLEGAL_USER_JOIN_ORDER = 10;
100     public static final int USER_JOIN_ORDER_OPTIMIZED = 11;
101     public static final int CONSIDERING_JOIN_ORDER = 12;
102     public static final int TOTAL_COST_NON_SA_PLAN = 13;
103     public static final int TOTAL_COST_SA_PLAN = 14;
104     public static final int TOTAL_COST_WITH_SORTING = 15;
105     public static final int CURRENT_PLAN_IS_SA_PLAN = 16;
106     public static final int CHEAPEST_PLAN_SO_FAR = 17;
107     public static final int PLAN_TYPE = 18;
108     public static final int COST_OF_CHEAPEST_PLAN_SO_FAR = 19;
109     public static final int SORT_NEEDED_FOR_ORDERING = 20;
110     public static final int REMEMBERING_BEST_JOIN_ORDER = 21;
111     public static final int SKIPPING_DUE_TO_EXCESS_MEMORY = 22;
112     public static final int COST_OF_N_SCANS = 23;
113     public static final int HJ_SKIP_NOT_MATERIALIZABLE = 24;
114     public static final int HJ_SKIP_NO_JOIN_COLUMNS = 25;
115     public static final int HJ_HASH_KEY_COLUMNS = 26;
116     public static final int CALLING_ON_JOIN_NODE = 27;
117     public static final int CONSIDERING_JOIN_STRATEGY = 28;
118     public static final int REMEMBERING_BEST_ACCESS_PATH = 29;
119     public static final int NO_MORE_CONGLOMERATES = 30;
120     public static final int CONSIDERING_CONGLOMERATE = 31;
121     public static final int SCANNING_HEAP_FULL_MATCH_ON_UNIQUE_KEY = 32;
122     public static final int ADDING_UNORDERED_OPTIMIZABLE = 33;
123     public static final int CHANGING_ACCESS_PATH_FOR_TABLE = 34;
124     public static final int TABLE_LOCK_NO_START_STOP = 35;
125     public static final int NON_COVERING_INDEX_COST = 36;
126     public static final int ROW_LOCK_ALL_CONSTANT_START_STOP = 37;
127     public static final int ESTIMATING_COST_OF_CONGLOMERATE = 38;
128     public static final int LOOKING_FOR_SPECIFIED_INDEX = 39;
129     public static final int MATCH_SINGLE_ROW_COST = 40;
130     public static final int COST_INCLUDING_EXTRA_1ST_COL_SELECTIVITY = 41;
131     public static final int CALLING_NEXT_ACCESS_PATH = 42;
132     public static final int TABLE_LOCK_OVER_THRESHOLD = 43;
133     public static final int ROW_LOCK_UNDER_THRESHOLD = 44;
134     public static final int COST_INCLUDING_EXTRA_START_STOP = 45;
135     public static final int COST_INCLUDING_EXTRA_QUALIFIER_SELECTIVITY = 46;
136     public static final int COST_INCLUDING_EXTRA_NONQUALIFIER_SELECTIVITY = 47;
137     public static final int COST_OF_NONCOVERING_INDEX = 48;
138     public static final int REMEMBERING_JOIN_STRATEGY = 49;
139     public static final int REMEMBERING_BEST_ACCESS_PATH_SUBSTRING = 50;
140     public static final int REMEMBERING_BEST_SORT_AVOIDANCE_ACCESS_PATH_SUBSTRING = 51;
141     public static final int REMEMBERING_BEST_UNKNOWN_ACCESS_PATH_SUBSTRING = 52;
142     public static final int COST_OF_CONGLOMERATE_SCAN1 = 53;
143     public static final int COST_OF_CONGLOMERATE_SCAN2 = 54;
144     public static final int COST_OF_CONGLOMERATE_SCAN3 = 55;
145     public static final int COST_OF_CONGLOMERATE_SCAN4 = 56;
146     public static final int COST_OF_CONGLOMERATE_SCAN5 = 57;
147     public static final int COST_OF_CONGLOMERATE_SCAN6 = 58;
148     public static final int COST_OF_CONGLOMERATE_SCAN7 = 59;
149     public static final int COST_INCLUDING_COMPOSITE_SEL_FROM_STATS= 60;
150     public static final int COMPOSITE_SEL_FROM_STATS = 61;
151     public static final int COST_INCLUDING_STATS_FOR_INDEX = 62;
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() throws StandardException;
177 
178     /**
179      * Cost the current permutation.
180      * Caller is responsible for pushing all predicates which can be evaluated 
181      * prior to costing.
182      *
183      * @exception StandardException     Thrown on error
184      */
185     public void costPermutation() throws StandardException;
186 
187     /**
188      * Cost the current Optimizable with the specified OPL.
189      * Caller is responsible for pushing all predicates which can be evaluated 
190      * prior to costing.
191      *
192      * @param optimizable   The Optimizable
193      * @param td            TableDescriptor of the Optimizable
194      * @param cd            The ConglomerateDescriptor for the conglom to cost
195      *                      (This should change to an object to represent
196      *                      access paths, but for now this is OK).
197      * @param predList      The OptimizablePredicateList to apply
198      * @param outerCost     The cost of the tables outer to the one being
199      *                      optimizer - tells how many outer rows there are.
200      *
201      * @exception StandardException     Thrown on error
202      */
203     public void costOptimizable(Optimizable optimizable,
204                                 TableDescriptor td, 
205                                 ConglomerateDescriptor cd,
206                                 OptimizablePredicateList predList,
207                                 CostEstimate outerCost)
208             throws StandardException;
209 
210     /**
211      * Consider the cost of the given optimizable.  This method is like
212      * costOptimizable, above, but it is used when the Optimizable does
213      * not need help from the optimizer in costing the Optimizable (in practice,
214      * all Optimizables except FromBaseTable use this method.
215      *
216      * Caller is responsible for pushing all predicates which can be evaluated 
217      * prior to costing.
218      *
219      * @param optimizable   The Optimizable
220      * @param predList      The OptimizablePredicateList to apply
221      * @param estimatedCost The estimated cost of the given optimizable
222      * @param outerCost     The cost of the tables outer to the one being
223      *                      optimizer - tells how many outer rows there are.
224      *
225      * @exception StandardException     Thrown on error
226      */
227     public void considerCost(Optimizable optimizable,
228                             OptimizablePredicateList predList,
229                             CostEstimate estimatedCost,
230                             CostEstimate outerCost)
231             throws StandardException;
232 
233     /**
234      * Return the DataDictionary that the Optimizer is using.
235      * This is useful when an Optimizable needs to call optimize() on
236      * a child ResultSetNode.
237      * 
238      * @return DataDictionary   DataDictionary that the Optimizer is using.
239      */
240     public DataDictionary getDataDictionary();
241 
242     /**
243      * Modify the access path for each Optimizable, as necessary.  This includes
244      * things like adding result sets to translate from index rows to base rows.
245      *
246      * @exception StandardException     Thrown on error
247      */
248     public void modifyAccessPaths() throws StandardException;
249 
250     /** Get a new CostEstimate object */
251     public CostEstimate newCostEstimate();
252 
253     /** Get the estimated cost of the optimized query */
254     public CostEstimate getOptimizedCost();
255 
256     /**
257      * Get the final estimated cost of the optimized query.  This
258      * should be the cost that corresponds to the best overall join
259      * order chosen by the optimizer, and thus this method should
260      * only be called after optimization is complete (i.e. when
261      * modifying access paths).
262      */
263     public CostEstimate getFinalCost();
264 
265     /**
266      * Prepare for another round of optimization.
267      *
268      * This method is called before every "round" of optimization, where
269      * we define a "round" to be the period between the last time a call to
270      * getOptimizer() (on either a ResultSetNode or an OptimizerFactory)
271      * returned _this_ Optimizer and the time a call to this Optimizer's
272      * getNextPermutation() method returns FALSE.  Any re-initialization
273      * of state that is required before each round should be done in this
274      * method.
275      */
276     public void prepForNextRound();
277 
278     /**
279      * Set the estimated number of outer rows - good for optimizing nested
280      * optimizables like subqueries and join nodes.
281      */
282     public void setOuterRows(double outerRowCount);
283 
284     /**
285      * Get the number of join strategies supported by this optimizer.
286      */
287     public int getNumberOfJoinStrategies();
288 
289     /**
290      * Get the maximum number of estimated rows touched in a table before
291      * we decide to open the table with table locking (as opposed to row
292      * locking.
293      */
294     public int tableLockThreshold();
295 
296     /**
297      * Gets a join strategy by number (zero-based).
298      */
299     JoinStrategy getJoinStrategy(int whichStrategy);
300 
301     /**
302      * Gets a join strategy by name.  Returns null if not found.
303      * The look-up is case-insensitive.
304      */
305     JoinStrategy getJoinStrategy(String   whichStrategy);
306 
307     /**
308      * Optimizer trace.
309      */
310     public void trace(int traceFlag, int intParam1, int intParam2,
311                       double doubleParam, Object   objectParam1);
312 
313     /**
314      * Get the level of this optimizer.
315      *
316      * @return The level of this optimizer.
317      */
318     public int getLevel();
319 
320     /**
321      * Tells whether any of the tables outer to the current one
322      * has a uniqueness condition on the given predicate list,
323      * and if so, how many times each unique key can be seen by
324      * the current table.
325      *
326      * @param predList      The predicate list to check
327      *
328      * @return  <= 0 means there is no uniqueness condition
329      *          > 0 means there is a uniqueness condition on an
330      *          outer table, and the return value is the reciprocal of
331      *          the maximum number of times the optimizer estimates that each
332      *          unique key will be returned. For example, 0.5 means the
333      *          optimizer thinks each distinct join key will be returned
334      *          at most twice.
335      *
336      * @exception StandardException     Thrown on error
337      */
338     double uniqueJoinWithOuterTable(OptimizablePredicateList predList)
339             throws StandardException;
340     
341     /** 
342      * If statistics should be considered by the optimizer while optimizing 
343      * a query. The user may disable the use of statistics by setting the
344      * property derby.optimizer.useStatistics or by using the property
345      * useStatistics in a query.
346      *
347      * @see #USE_STATISTICS
348      */
349     public boolean useStatistics();
350 
351     /**
352      * @return the maximum number of bytes to be used per table.
353      */
354     public int getMaxMemoryPerTable();
355 }
356
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags