001: /*
002:
003: Derby - Class org.apache.derby.impl.sql.compile.Level2OptimizerImpl
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.impl.sql.compile;
023:
024: import org.apache.derby.iapi.services.sanity.SanityManager;
025:
026: import org.apache.derby.iapi.error.StandardException;
027:
028: import org.apache.derby.iapi.sql.compile.JoinStrategy;
029: import org.apache.derby.iapi.sql.compile.Optimizable;
030: import org.apache.derby.iapi.sql.compile.OptimizableList;
031: import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
032: import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
033: import org.apache.derby.iapi.sql.compile.Optimizer;
034: import org.apache.derby.iapi.sql.compile.CostEstimate;
035: import org.apache.derby.iapi.sql.compile.RequiredRowOrdering;
036: import org.apache.derby.iapi.sql.compile.RowOrdering;
037: import org.apache.derby.iapi.sql.compile.AccessPath;
038:
039: import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
040:
041: import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
042: import org.apache.derby.iapi.sql.dictionary.DataDictionary;
043: import org.apache.derby.iapi.sql.dictionary.IndexRowGenerator;
044: import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
045:
046: import org.apache.derby.iapi.reference.SQLState;
047:
048: import org.apache.derby.iapi.util.JBitSet;
049:
050: import org.apache.derby.impl.sql.compile.OptimizerImpl;
051: import org.apache.derby.impl.sql.compile.CostEstimateImpl;
052:
053: import java.util.Properties;
054:
055: /**
056: * This is the Level 2 Optimizer.
057: */
058:
059: public class Level2OptimizerImpl extends OptimizerImpl {
060: private LanguageConnectionContext lcc;
061:
062: Level2OptimizerImpl(OptimizableList optimizableList,
063: OptimizablePredicateList predicateList,
064: DataDictionary dDictionary, boolean ruleBasedOptimization,
065: boolean noTimeout, boolean useStatistics,
066: int maxMemoryPerTable, JoinStrategy[] joinStrategies,
067: int tableLockThreshold,
068: RequiredRowOrdering requiredRowOrdering,
069: int numTablesInQuery, LanguageConnectionContext lcc)
070: throws StandardException {
071: super (optimizableList, predicateList, dDictionary,
072: ruleBasedOptimization, noTimeout, useStatistics,
073: maxMemoryPerTable, joinStrategies, tableLockThreshold,
074: requiredRowOrdering, numTablesInQuery);
075:
076: // Remember whether or not optimizer trace is on;
077: optimizerTrace = lcc.getOptimizerTrace();
078: optimizerTraceHtml = lcc.getOptimizerTraceHtml();
079: this .lcc = lcc;
080:
081: // Optimization started
082: if (optimizerTrace) {
083: trace(STARTED, 0, 0, 0.0, null);
084: }
085: }
086:
087: /** @see Optimizer#getLevel */
088: public int getLevel() {
089: return 2;
090: }
091:
092: /** @see Optimizer#newCostEstimate */
093: public CostEstimate newCostEstimate() {
094: return new Level2CostEstimateImpl();
095: }
096:
097: public CostEstimateImpl getNewCostEstimate(double theCost,
098: double theRowCount, double theSingleScanRowCount) {
099: return new Level2CostEstimateImpl(theCost, theRowCount,
100: theSingleScanRowCount);
101: }
102:
103: // Optimzer trace
104: public void trace(int traceFlag, int intParam1, int intParam2,
105: double doubleParam, Object objectParam1) {
106: ConglomerateDescriptor cd;
107: String cdString;
108: String traceString = null;
109:
110: // We can get called from outside optimizer when tracing is off
111: if (!optimizerTrace) {
112: return;
113: }
114:
115: switch (traceFlag) {
116: case STARTED:
117: traceString = "Optimization started at time "
118: + timeOptimizationStarted + " using optimizer "
119: + this .hashCode();
120: break;
121:
122: case TIME_EXCEEDED:
123: traceString = "Optimization time exceeded at time "
124: + currentTime + "\n" + bestCost();
125: break;
126:
127: case NO_TABLES:
128: traceString = "No tables to optimize.";
129: break;
130:
131: case COMPLETE_JOIN_ORDER:
132: traceString = "We have a complete join order.";
133: break;
134:
135: case COST_OF_SORTING:
136: traceString = "Cost of sorting is " + sortCost;
137: break;
138:
139: case NO_BEST_PLAN:
140: traceString = "No best plan found.";
141: break;
142:
143: case MODIFYING_ACCESS_PATHS:
144: traceString = "Modifying access paths using optimizer "
145: + this .hashCode();
146: break;
147:
148: case SHORT_CIRCUITING:
149: String basis = (timeExceeded) ? "time exceeded" : "cost";
150: Optimizable this Opt = optimizableList
151: .getOptimizable(proposedJoinOrder[joinPosition]);
152: if (this Opt.getBestAccessPath().getCostEstimate() == null)
153: basis = "no best plan found";
154: traceString = "Short circuiting based on " + basis
155: + " at join position " + joinPosition;
156: break;
157:
158: case SKIPPING_JOIN_ORDER:
159: traceString = buildJoinOrder("\n\nSkipping join order: ",
160: true, intParam1, proposedJoinOrder);
161: break;
162:
163: case ILLEGAL_USER_JOIN_ORDER:
164: traceString = "User specified join order is not legal.";
165: break;
166:
167: case USER_JOIN_ORDER_OPTIMIZED:
168: traceString = "User-specified join order has now been optimized.";
169: break;
170:
171: case CONSIDERING_JOIN_ORDER:
172: traceString = buildJoinOrder(
173: "\n\nConsidering join order: ", false, intParam1,
174: proposedJoinOrder);
175: break;
176:
177: case TOTAL_COST_NON_SA_PLAN:
178: traceString = "Total cost of non-sort-avoidance plan is "
179: + currentCost;
180: break;
181:
182: case TOTAL_COST_SA_PLAN:
183: traceString = "Total cost of sort avoidance plan is "
184: + currentSortAvoidanceCost;
185: break;
186:
187: case TOTAL_COST_WITH_SORTING:
188: traceString = "Total cost of non-sort-avoidance plan with sort cost added is "
189: + currentCost;
190: break;
191:
192: case CURRENT_PLAN_IS_SA_PLAN:
193: traceString = "Current plan is a sort avoidance plan."
194: + "\n\tBest cost is : " + bestCost
195: + "\n\tThis cost is : " + currentSortAvoidanceCost;
196: break;
197:
198: case CHEAPEST_PLAN_SO_FAR:
199: traceString = "This is the cheapest plan so far.";
200: break;
201:
202: case PLAN_TYPE:
203: traceString = "Plan is a "
204: + (intParam1 == Optimizer.NORMAL_PLAN ? "normal"
205: : "sort avoidance") + " plan.";
206: break;
207:
208: case COST_OF_CHEAPEST_PLAN_SO_FAR:
209: traceString = "Cost of cheapest plan is " + currentCost;
210: break;
211:
212: case SORT_NEEDED_FOR_ORDERING:
213: traceString = "Sort needed for ordering: "
214: + (intParam1 != Optimizer.SORT_AVOIDANCE_PLAN)
215: + "\n\tRow ordering: " + requiredRowOrdering;
216: break;
217:
218: case REMEMBERING_BEST_JOIN_ORDER:
219: traceString = buildJoinOrder(
220: "\n\nRemembering join order as best: ", false,
221: intParam1, bestJoinOrder);
222: break;
223:
224: case SKIPPING_DUE_TO_EXCESS_MEMORY:
225: traceString = "Skipping access path due to excess memory usage, maximum is "
226: + maxMemoryPerTable;
227: break;
228:
229: case COST_OF_N_SCANS:
230: traceString = "Cost of " + doubleParam + " scans is: "
231: + objectParam1 + " for table " + intParam1;
232: break;
233:
234: case HJ_SKIP_NOT_MATERIALIZABLE:
235: traceString = "Skipping HASH JOIN because optimizable is not materializable";
236: break;
237:
238: case HJ_SKIP_NO_JOIN_COLUMNS:
239: traceString = "Skipping HASH JOIN because there are no hash key columns";
240: break;
241:
242: case HJ_HASH_KEY_COLUMNS:
243: int[] hashKeyColumns = (int[]) objectParam1;
244: traceString = "# hash key columns = "
245: + hashKeyColumns.length;
246: for (int index = 0; index < hashKeyColumns.length; index++) {
247: traceString = "\n" + traceString + "hashKeyColumns["
248: + index + "] = " + hashKeyColumns[index];
249: }
250: break;
251:
252: case CALLING_ON_JOIN_NODE:
253: traceString = "Calling optimizeIt() for join node";
254: break;
255:
256: case CONSIDERING_JOIN_STRATEGY:
257: JoinStrategy js = (JoinStrategy) objectParam1;
258: traceString = "\nConsidering join strategy " + js
259: + " for table " + intParam1;
260: break;
261:
262: case REMEMBERING_BEST_ACCESS_PATH:
263: traceString = "Remembering access path "
264: + objectParam1
265: + " as truly the best for table "
266: + intParam1
267: + " for plan type "
268: + (intParam2 == Optimizer.NORMAL_PLAN ? " normal "
269: : "sort avoidance") + "\n";
270: break;
271:
272: case NO_MORE_CONGLOMERATES:
273: traceString = "No more conglomerates to consider for table "
274: + intParam1;
275: break;
276:
277: case CONSIDERING_CONGLOMERATE:
278: cd = (ConglomerateDescriptor) objectParam1;
279: cdString = dumpConglomerateDescriptor(cd);
280: traceString = "\nConsidering conglomerate " + cdString
281: + " for table " + intParam1;
282: break;
283:
284: case SCANNING_HEAP_FULL_MATCH_ON_UNIQUE_KEY:
285: traceString = "Scanning heap, but we have a full match on a unique key.";
286: break;
287:
288: case ADDING_UNORDERED_OPTIMIZABLE:
289: traceString = "Adding unordered optimizable, # of predicates = "
290: + intParam1;
291: break;
292:
293: case CHANGING_ACCESS_PATH_FOR_TABLE:
294: traceString = "Changing access path for table " + intParam1;
295: break;
296:
297: case TABLE_LOCK_NO_START_STOP:
298: traceString = "Lock mode set to MODE_TABLE because no start or stop position";
299: break;
300:
301: case NON_COVERING_INDEX_COST:
302: traceString = "Index does not cover query - cost including base row fetch is: "
303: + doubleParam + " for table " + intParam1;
304: break;
305:
306: case ROW_LOCK_ALL_CONSTANT_START_STOP:
307: traceString = "Lock mode set to MODE_RECORD because all start and stop positions are constant";
308: break;
309:
310: case ESTIMATING_COST_OF_CONGLOMERATE:
311: cd = (ConglomerateDescriptor) objectParam1;
312: cdString = dumpConglomerateDescriptor(cd);
313: traceString = "Estimating cost of conglomerate: "
314: + costForTable(cdString, intParam1);
315: break;
316:
317: case LOOKING_FOR_SPECIFIED_INDEX:
318: traceString = "Looking for user-specified index: "
319: + objectParam1 + " for table " + intParam1;
320: break;
321:
322: case MATCH_SINGLE_ROW_COST:
323: traceString = "Guaranteed to match a single row - cost is: "
324: + doubleParam + " for table " + intParam1;
325: break;
326:
327: case COST_INCLUDING_EXTRA_1ST_COL_SELECTIVITY:
328: traceString = costIncluding("1st column", objectParam1,
329: intParam1);
330: traceString = "Cost including extra first column selectivity is : "
331: + objectParam1 + " for table " + intParam1;
332: break;
333:
334: case CALLING_NEXT_ACCESS_PATH:
335: traceString = "Calling nextAccessPath() for base table "
336: + objectParam1 + " with " + intParam1
337: + " predicates.";
338: break;
339:
340: case TABLE_LOCK_OVER_THRESHOLD:
341: traceString = lockModeThreshold("MODE_TABLE", "greater",
342: doubleParam, intParam1);
343: break;
344:
345: case ROW_LOCK_UNDER_THRESHOLD:
346: traceString = lockModeThreshold("MODE_RECORD", "less",
347: doubleParam, intParam1);
348: break;
349:
350: case COST_INCLUDING_EXTRA_START_STOP:
351: traceString = costIncluding("start/stop", objectParam1,
352: intParam1);
353: break;
354:
355: case COST_INCLUDING_EXTRA_QUALIFIER_SELECTIVITY:
356: traceString = costIncluding("qualifier", objectParam1,
357: intParam1);
358: break;
359:
360: case COST_INCLUDING_EXTRA_NONQUALIFIER_SELECTIVITY:
361: traceString = costIncluding("non-qualifier", objectParam1,
362: intParam1);
363: break;
364:
365: case COST_INCLUDING_COMPOSITE_SEL_FROM_STATS:
366: traceString = costIncluding("selectivity from statistics",
367: objectParam1, intParam1);
368: break;
369:
370: case COST_INCLUDING_STATS_FOR_INDEX:
371: traceString = costIncluding(
372: "statistics for index being considered",
373: objectParam1, intParam1);
374: break;
375: case COMPOSITE_SEL_FROM_STATS:
376: traceString = "Selectivity from statistics found. It is "
377: + doubleParam;
378: break;
379:
380: case COST_OF_NONCOVERING_INDEX:
381: traceString = "Index does not cover query: cost including row fetch is: "
382: + costForTable(objectParam1, intParam1);
383: break;
384:
385: case REMEMBERING_JOIN_STRATEGY:
386: traceString = "\nRemembering join strategy " + objectParam1
387: + " as best for table " + intParam1;
388: break;
389:
390: case REMEMBERING_BEST_ACCESS_PATH_SUBSTRING:
391: traceString = "in best access path";
392: break;
393:
394: case REMEMBERING_BEST_SORT_AVOIDANCE_ACCESS_PATH_SUBSTRING:
395: traceString = "in best sort avoidance access path";
396: break;
397:
398: case REMEMBERING_BEST_UNKNOWN_ACCESS_PATH_SUBSTRING:
399: traceString = "in best unknown access path";
400: break;
401:
402: case COST_OF_CONGLOMERATE_SCAN1:
403: cd = (ConglomerateDescriptor) objectParam1;
404: cdString = dumpConglomerateDescriptor(cd);
405: traceString = "Cost of conglomerate " + cdString
406: + " scan for table number " + intParam1 + " is : ";
407: break;
408:
409: case COST_OF_CONGLOMERATE_SCAN2:
410: traceString = objectParam1.toString();
411: break;
412:
413: case COST_OF_CONGLOMERATE_SCAN3:
414: traceString = "\tNumber of extra first column predicates is : "
415: + intParam1
416: + ", extra first column selectivity is : "
417: + doubleParam;
418: break;
419:
420: case COST_OF_CONGLOMERATE_SCAN4:
421: traceString = "\tNumber of extra start/stop predicates is : "
422: + intParam1
423: + ", extra start/stop selectivity is : "
424: + doubleParam;
425: break;
426:
427: case COST_OF_CONGLOMERATE_SCAN5:
428: traceString = "\tNumber of extra qualifiers is : "
429: + intParam1 + ", extra qualifier selectivity is : "
430: + doubleParam;
431: break;
432:
433: case COST_OF_CONGLOMERATE_SCAN6:
434: traceString = "\tNumber of extra non-qualifiers is : "
435: + intParam1
436: + ", extra non-qualifier selectivity is : "
437: + doubleParam;
438: break;
439:
440: case COST_OF_CONGLOMERATE_SCAN7:
441: traceString = "\tNumber of start/stop statistics predicates is : "
442: + intParam1
443: + ", statistics start/stop selectivity is : "
444: + doubleParam;
445: break;
446: }
447: if (SanityManager.DEBUG) {
448: if (traceString == null) {
449: SanityManager
450: .THROWASSERT("traceString expected to be non-null");
451: }
452: }
453: lcc.appendOptimizerTraceOutput(traceString + "\n");
454: }
455:
456: private String costForTable(Object cost, int tableNumber) {
457: return cost + " for table " + tableNumber;
458: }
459:
460: private String bestCost() {
461: return "Best cost = " + bestCost + "\n";
462: }
463:
464: private String buildJoinOrder(String prefix,
465: boolean addJoinOrderNumber, int joinOrderNumber,
466: int[] joinOrder) {
467: String joinOrderString = prefix;
468:
469: for (int i = 0; i <= joinPosition; i++) {
470: joinOrderString = joinOrderString + " " + joinOrder[i];
471: }
472: if (addJoinOrderNumber) {
473: joinOrderString = joinOrderString + " " + joinOrderNumber;
474: }
475:
476: return joinOrderString + " with assignedTableMap = "
477: + assignedTableMap + "\n\n";
478: }
479:
480: private String lockModeThreshold(String lockMode, String relop,
481: double rowCount, int threshold) {
482: return "Lock mode set to " + lockMode
483: + " because estimated row count of " + rowCount + " "
484: + relop + " than threshold of " + threshold;
485: }
486:
487: private String costIncluding(String selectivityType,
488: Object objectParam1, int intParam1) {
489: return "Cost including extra " + selectivityType
490: + " start/stop selectivity is : "
491: + costForTable(objectParam1, intParam1);
492: }
493:
494: private String dumpConglomerateDescriptor(ConglomerateDescriptor cd) {
495: if (SanityManager.DEBUG) {
496: return cd.toString();
497: }
498:
499: String keyString = "";
500: String[] columnNames = cd.getColumnNames();
501:
502: if (cd.isIndex() && columnNames != null) {
503: IndexRowGenerator irg = cd.getIndexDescriptor();
504:
505: int[] keyColumns = irg.baseColumnPositions();
506:
507: keyString = ", key columns = {"
508: + columnNames[keyColumns[0] - 1];
509: for (int index = 1; index < keyColumns.length; index++) {
510: keyString = keyString + ", "
511: + columnNames[keyColumns[index] - 1];
512: }
513: keyString = keyString + "}";
514: }
515:
516: return "CD: conglomerateNumber = " + cd.getConglomerateNumber()
517: + " name = " + cd.getConglomerateName() + " uuid = "
518: + cd.getUUID() + " indexable = " + cd.isIndex()
519: + keyString;
520: }
521: }
|