001: /*
002:
003: Derby - Class org.apache.derby.impl.store.access.btree.BTreeCostController
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.store.access.btree;
023:
024: import org.apache.derby.iapi.reference.Property;
025: import org.apache.derby.iapi.reference.SQLState;
026:
027: import org.apache.derby.iapi.services.sanity.SanityManager;
028:
029: import org.apache.derby.iapi.error.StandardException;
030:
031: import org.apache.derby.iapi.store.access.conglomerate.Conglomerate;
032: import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;
033: import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;
034:
035: import org.apache.derby.iapi.store.access.DynamicCompiledOpenConglomInfo;
036: import org.apache.derby.iapi.store.access.RowUtil;
037: import org.apache.derby.iapi.store.access.ScanController;
038: import org.apache.derby.iapi.store.access.StoreCostController;
039: import org.apache.derby.iapi.store.access.StoreCostResult;
040: import org.apache.derby.iapi.store.access.TransactionController;
041:
042: import org.apache.derby.iapi.store.raw.ContainerHandle;
043: import org.apache.derby.iapi.store.raw.LockingPolicy;
044: import org.apache.derby.iapi.store.raw.RawStoreFactory;
045: import org.apache.derby.iapi.store.raw.Transaction;
046:
047: import org.apache.derby.iapi.types.DataValueDescriptor;
048:
049: import org.apache.derby.iapi.types.RowLocation;
050:
051: import org.apache.derby.iapi.services.io.FormatableBitSet;
052: import java.util.Properties;
053:
054: /**
055:
056: The StoreCostController interface provides methods that an access client
057: (most likely the system optimizer) can use to get store's estimated cost of
058: various operations on the conglomerate the StoreCostController was opened
059: for.
060: <p>
061: It is likely that the implementation of StoreCostController will open
062: the conglomerate and will leave the conglomerate open until the
063: StoreCostController is closed. This represents a significant amount of
064: work, so the caller if possible should attempt to open the StoreCostController
065: once per unit of work and rather than close and reopen the controller. For
066: instance if the optimizer needs to cost 2 different scans against a single
067: conglomerate, it should use one instance of the StoreCostController.
068: <p>
069: The locking behavior of the implementation of a StoreCostController is
070: undefined, it may or may not get locks on the underlying conglomerate. It
071: may or may not hold locks until end of transaction.
072: An optimal implementation will not get any locks on the underlying
073: conglomerate, thus allowing concurrent access to the table by a executing
074: query while another query is optimizing.
075: <p>
076: @see TransactionController#openStoreCost
077:
078: **/
079:
080: public class BTreeCostController extends OpenBTree implements
081: StoreCostController {
082:
083: // 1.5 numbers on mikem old machine:
084: //
085: // The magic numbers are based on the following benchmark results:
086: //
087: // no col one int col all cols
088: // ------ ----------- --------
089: //100 byte heap fetch by row loc, cached 0.3625 0.5098 0.6629
090: //100 byte heap fetch by row loc, uncached 1.3605769 1.5168269 1.5769231
091: //4 byte heap fetch by row loc, cached 0.3745 0.4016 0.3766
092: //4 byte heap fetch by row loc, uncached 4.1938777 3.5714285 4.4897957
093: //
094: // no col one int col all cols
095: // ------ ----------- --------
096: //Int col one level btree
097: // fetch by exact key, cached 0.781 1.012 0.42
098: // fetch by exact key, sort merge 1.081 1.221 0.851
099: // fetch by exact key, uncached 0.0 0.0 0.0
100: //Int col two level btree
101: // fetch by exact key, cached 1.062 1.342 0.871
102: // fetch by exact key, sort merge 1.893 2.273 1.633
103: // fetch by exact key, uncached 5.7238097 5.3428574 4.7714286
104: //String key one level btree
105: // fetch by exact key, cached 1.082 0.811 0.781
106: // fetch by exact key, sort merge 1.572 1.683 1.141
107: // fetch by exact key, uncached 0.0 0.0 0.0
108: //String key two level btree
109: // fetch by exact key, cached 2.143 2.664 1.953
110: // fetch by exact key, sort merge 3.775 4.116 3.505
111: // fetch by exact key, uncached 4.639474 5.0052633 4.4289474
112:
113: // mikem new machine - insane, codeline, non-jit 1.1.7 numbers
114: //
115: // no col one int col all cols
116: // ------ ----------- --------
117: //100 byte heap fetch by row loc, cached 0.1662 0.4597 0.5618
118: //100 byte heap fetch by row loc, uncached 0.7565947 1.2601918 1.6690648
119: //4 byte heap fetch by row loc, cached 0.1702 0.1983 0.1903
120: //4 byte heap fetch by row loc, uncached 1.5068493 1.3013699 1.6438357
121: //
122: // no col one int col all cols
123: // ------ ----------- --------
124: // Int col one level btree
125: // fetch by exact key, cached 0.271 0.511 0.33
126: // fetch by exact key, sort merge 0.691 0.921 0.771
127: // fetch by exact key, uncached 0.0 0.0 0.0
128: // Int col two level btree
129: // fetch by exact key, cached 0.541 0.711 0.561
130: // fetch by exact key, sort merge 1.432 1.682 1.533
131: // fetch by exact key, uncached 3.142857 3.6285715 3.2380953
132: // String key one level btree
133: // fetch by exact key, cached 0.611 0.851 0.701
134: // fetch by exact key, sort merge 1.051 1.272 1.122
135: // fetch by exact key, uncached 0.0 0.0 0.0
136: // String key two level btree
137: // fetch by exact key, cached 1.532 1.843 1.622
138: // fetch by exact key, sort merge 2.844 3.155 2.984
139: // fetch by exact key, uncached 3.4 3.636842 3.531579
140: //
141:
142: // The following costs are search costs to find a row on a leaf, use
143: // the heap costs to determine scan costs, for now ignore qualifier
144: // application and stop comparisons.
145: // I used the int key, 2 level numbers divided by 2 to get per level.
146:
147: private static final double BTREE_CACHED_FETCH_BY_KEY_PER_LEVEL = (0.541 / 2);
148:
149: private static final double BTREE_SORTMERGE_FETCH_BY_KEY_PER_LEVEL = (1.432 / 2);
150:
151: private static final double BTREE_UNCACHED_FETCH_BY_KEY_PER_LEVEL = (3.143 / 2);
152:
153: // saved values passed to init().
154: TransactionManager init_xact_manager;
155: Transaction init_rawtran;
156: Conglomerate init_conglomerate;
157:
158: /**
159: * Only lookup these estimates from raw store once.
160: **/
161: long num_pages;
162: long num_rows;
163: long page_size;
164: int tree_height;
165:
166: /* Constructors for This class: */
167:
168: public BTreeCostController() {
169: }
170:
171: /* Private/Protected methods of This class: */
172:
173: /**
174: * Initialize the cost controller.
175: * <p>
176: * Save initialize parameters away, and open the underlying container.
177: * <p>
178: *
179: * @param xact_manager access manager transaction.
180: * @param rawtran Raw store transaction.
181: *
182: * @exception StandardException Standard exception policy.
183: **/
184: public void init(TransactionManager xact_manager,
185: BTree conglomerate, Transaction rawtran)
186: throws StandardException {
187: super .init(xact_manager,
188: xact_manager,
189: (ContainerHandle) null, // open the btree.
190: rawtran, false, ContainerHandle.MODE_READONLY,
191: TransactionManager.MODE_NONE,
192: (BTreeLockingPolicy) null, // RESOLVE (mikem) - this means
193: // no locks during costing - will
194: // that work?????
195: conglomerate, (LogicalUndo) null, // read only, so no undo necessary
196: (DynamicCompiledOpenConglomInfo) null);
197:
198: // look up costs from raw store. For btrees these numbers are out
199: // of whack as they want to be leaf specific numbers but they include
200: // every page branch and leafs.
201: num_pages = this .container
202: .getEstimatedPageCount(/* unused flag */0);
203:
204: // subtract one row for every page to account for internal control row
205: // which exists on every page.
206: num_rows = this .container
207: .getEstimatedRowCount(/*unused flag*/0)
208: - num_pages;
209:
210: Properties prop = new Properties();
211: prop.put(Property.PAGE_SIZE_PARAMETER, "");
212: this .container.getContainerProperties(prop);
213: page_size = Integer.parseInt(prop
214: .getProperty(Property.PAGE_SIZE_PARAMETER));
215:
216: tree_height = getHeight();
217:
218: return;
219: }
220:
221: /* Public Methods of This class: */
222:
223: /**
224: * Close the controller.
225: * <p>
226: * Close the open controller. This method always succeeds, and never
227: * throws any exceptions. Callers must not use the StoreCostController
228: * Cost controller after closing it; they are strongly advised to clear
229: * out the scan controller reference after closing.
230: * <p>
231: **/
232: public void close() throws StandardException {
233: super .close();
234: }
235:
236: /**
237: * Return the cost of calling ConglomerateController.fetch().
238: * <p>
239: * Return the estimated cost of calling ConglomerateController.fetch()
240: * on the current conglomerate. This gives the cost of finding a record
241: * in the conglomerate given the exact RowLocation of the record in
242: * question.
243: * <p>
244: * The validColumns parameter describes what kind of row
245: * is being fetched, ie. it may be cheaper to fetch a partial row than a
246: * complete row.
247: * <p>
248: *
249: *
250: * @param validColumns A description of which columns to return from
251: * row on the page into "templateRow." templateRow,
252: * and validColumns work together to
253: * describe the row to be returned by the fetch -
254: * see RowUtil for description of how these three
255: * parameters work together to describe a fetched
256: * "row".
257: *
258: * @param access_type Describe the type of access the query will be
259: * performing to the ConglomerateController.
260: *
261: * STORECOST_CLUSTERED - The location of one fetch
262: * is likely clustered "close" to the next
263: * fetch. For instance if the query plan were
264: * to sort the RowLocations of a heap and then
265: * use those RowLocations sequentially to
266: * probe into the heap, then this flag should
267: * be specified. If this flag is not set then
268: * access to the table is assumed to be
269: * random - ie. the type of access one gets
270: * if you scan an index and probe each row
271: * in turn into the base table is "random".
272: *
273: *
274: * @return The cost of the fetch.
275: *
276: * @exception StandardException Standard exception policy.
277: *
278: * @see RowUtil
279: **/
280: public double getFetchFromRowLocationCost(
281: FormatableBitSet validColumns, int access_type)
282: throws StandardException {
283: throw StandardException
284: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE);
285: }
286:
287: /**
288: * Return the cost of exact key lookup.
289: * <p>
290: * Return the estimated cost of calling ScanController.fetch()
291: * on the current conglomerate, with start and stop positions set such
292: * that an exact match is expected.
293: * <p>
294: * This call returns the cost of a fetchNext() performed on a scan which
295: * has been positioned with a start position which specifies exact match
296: * on all keys in the row.
297: * <p>
298: * Example:
299: * <p>
300: * In the case of a btree this call can be used to determine the cost of
301: * doing an exact probe into btree, giving all key columns. This cost
302: * can be used if the client knows it will be doing an exact key probe
303: * but does not have the key's at optimize time to use to make a call to
304: * getScanCost()
305: * <p>
306: *
307: *
308: * @param validColumns A description of which columns to return from
309: * row on the page into "templateRow." templateRow,
310: * and validColumns work together to
311: * describe the row to be returned by the fetch -
312: * see RowUtil for description of how these three
313: * parameters work together to describe a fetched
314: * "row".
315: *
316: * @param access_type Describe the type of access the query will be
317: * performing to the ScanController.
318: *
319: * STORECOST_CLUSTERED - The location of one scan
320: * is likely clustered "close" to the previous
321: * scan. For instance if the query plan were
322: * to used repeated "reopenScan()'s" to probe
323: * for the next key in an index, then this flag
324: * should be be specified. If this flag is not
325: * set then each scan will be costed independant
326: * of any other predicted scan access.
327: *
328: * @return The cost of the fetch.
329: *
330: * @exception StandardException Standard exception policy.
331: *
332: * @see RowUtil
333: **/
334: public double getFetchFromFullKeyCost(
335: FormatableBitSet validColumns, int access_type)
336: throws StandardException {
337: double ret_cost;
338:
339: if ((access_type & StoreCostController.STORECOST_CLUSTERED) == 0) {
340: // uncached fetch
341: ret_cost = BTREE_UNCACHED_FETCH_BY_KEY_PER_LEVEL;
342: } else {
343: ret_cost = BTREE_SORTMERGE_FETCH_BY_KEY_PER_LEVEL;
344: }
345: ret_cost *= tree_height;
346:
347: return (ret_cost);
348: }
349:
350: /**
351: * Calculate the cost of a scan.
352: * <p>
353: * Cause this object to calculate the cost of performing the described
354: * scan. The interface is setup such that first a call is made to
355: * calcualteScanCost(), and then subsequent calls to accessor routines
356: * are made to get various pieces of information about the cost of
357: * the scan.
358: * <p>
359: * For the purposes of costing this routine is going to assume that
360: * a page will remain in cache between the time one next()/fetchNext()
361: * call and a subsequent next()/fetchNext() call is made within a scan.
362: * <p>
363: * The result of costing the scan is placed in the "cost_result".
364: * The cost of the scan is stored by calling
365: * cost_result.setEstimatedCost(cost).
366: * The estimated row count is stored by calling
367: * cost_result.setEstimatedRowCount(row_count).
368: * <p>
369: * The estimated cost of the scan assumes the caller will
370: * execute a fetchNext() loop for every row that qualifies between
371: * start and stop position. Note that this cost is different than
372: * execution a next(),fetch() loop; or if the scan is going to be
373: * terminated by client prior to reaching the stop condition.
374: * <p>
375: * The estimated number of rows returned from the scan
376: * assumes the caller will execute a fetchNext() loop for every
377: * row that qualifies between start and stop position.
378: * <p>
379: *
380: *
381: * @param scan_type The type of scan that will be executed. There
382: * are currently 2 types:
383: * STORECOST_SCAN_NORMAL - scans will be executed
384: * using the standard next/fetch, where each fetch
385: * can retrieve 1 or many rows (if fetchNextGroup()
386: * interface is used).
387: *
388: * STORECOST_SCAN_SET - The entire result set will
389: * be retrieved using the the fetchSet() interface.
390: *
391: * @param row_count Estimated total row count of the table. The
392: * current system tracks row counts in heaps better
393: * than btree's (btree's have "rows" which are not
394: * user rows - branch rows, control rows), so
395: * if available the client should
396: * pass in the base table's row count into this
397: * routine to be used as the index's row count.
398: * If the caller has no idea, pass in -1.
399: *
400: * @param group_size The number of rows to be returned by a single
401: * fetch call for STORECOST_SCAN_NORMAL scans.
402: *
403: * @param forUpdate Should be true if the caller intends to update
404: * through the scan.
405: *
406: * @param scanColumnList A description of which columns to return from
407: * every fetch in the scan. template,
408: * and scanColumnList work together
409: * to describe the row to be returned by the scan -
410: * see RowUtil for description of how these three
411: * parameters work together to describe a "row".
412: *
413: * @param template A prototypical row which the scan may use to
414: * maintain its position in the conglomerate. Not
415: * all access method scan types will require this,
416: * if they don't it's ok to pass in null.
417: * In order to scan a conglomerate one must
418: * allocate 2 separate "row" templates. The "row"
419: * template passed into openScan is for the private
420: * use of the scan itself, and no access to it
421: * should be made by the caller while the scan is
422: * still open. Because of this the scanner must
423: * allocate another "row" template to hold the
424: * values returned from fetch(). Note that this
425: * template must be for the full row, whether a
426: * partial row scan is being executed or not.
427: *
428: * @param startKeyValue An indexable row which holds a (partial) key
429: * value which, in combination with the
430: * startSearchOperator, defines the starting
431: * position of the scan. If null, the starting
432: * position of the scan is the first row of the
433: * conglomerate. The startKeyValue must only
434: * reference columns included in the scanColumnList.
435: *
436: * @param startSearchOperator
437: * an operator which defines how the startKeyValue
438: * is to be searched for. If startSearchOperation
439: * is ScanController.GE, the scan starts on the
440: * first row which is greater than or equal to the
441: * startKeyValue. If startSearchOperation is
442: * ScanController.GT, the scan starts on the first
443: * row whose key is greater than startKeyValue. The
444: * startSearchOperation parameter is ignored if the
445: * startKeyValue parameter is null.
446: *
447: * @param stopKeyValue An indexable row which holds a (partial) key
448: * value which, in combination with the
449: * stopSearchOperator, defines the ending position
450: * of the scan. If null, the ending position of the
451: * scan is the last row of the conglomerate. The
452: * stopKeyValue must only reference columns included
453: * in the scanColumnList.
454: *
455: * @param stopSearchOperator
456: * an operator which defines how the stopKeyValue
457: * is used to determine the scan stopping position.
458: * If stopSearchOperation is ScanController.GE, the
459: * scan stops just before the first row which is
460: * greater than or equal to the stopKeyValue. If
461: * stopSearchOperation is ScanController.GT, the
462: * scan stops just before the first row whose key
463: * is greater than startKeyValue. The
464: * stopSearchOperation parameter is ignored if the
465: * stopKeyValue parameter is null.
466: *
467: *
468: * @param access_type Describe the type of access the query will be
469: * performing to the ScanController.
470: *
471: * STORECOST_CLUSTERED - The location of one scan
472: * is likely clustered "close" to the previous
473: * scan. For instance if the query plan were
474: * to used repeated "reopenScan()'s" to probe
475: * for the next key in an index, then this flag
476: * should be be specified. If this flag is not
477: * set then each scan will be costed independant
478: * of any other predicted scan access.
479: *
480: *
481: * @exception StandardException Standard exception policy.
482: *
483: * @see RowUtil
484: **/
485: public void getScanCost(int scan_type, long row_count,
486: int group_size, boolean forUpdate,
487: FormatableBitSet scanColumnList,
488: DataValueDescriptor[] template,
489: DataValueDescriptor[] startKeyValue,
490: int startSearchOperator,
491: DataValueDescriptor[] stopKeyValue, int stopSearchOperator,
492: boolean reopen_scan, int access_type,
493: StoreCostResult cost_result) throws StandardException {
494: float left_of_start;
495: float left_of_stop;
496: ControlRow control_row = null;
497: long input_row_count = (row_count < 0 ? num_rows : row_count);
498:
499: try {
500: // Find the starting page and row slot.
501: if (startKeyValue == null) {
502: left_of_start = 0;
503: } else {
504: // Search for the starting row.
505:
506: SearchParameters sp = new SearchParameters(
507: startKeyValue,
508: ((startSearchOperator == ScanController.GE) ? SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH
509: : SearchParameters.POSITION_RIGHT_OF_PARTIAL_KEY_MATCH),
510: template, this , true);
511:
512: control_row = ControlRow.Get(this , BTree.ROOTPAGEID)
513: .search(sp);
514:
515: control_row.release();
516: control_row = null;
517:
518: left_of_start = sp.left_fraction;
519: }
520:
521: if (stopKeyValue == null) {
522: left_of_stop = 1;
523: } else {
524: // Search for the stopping row.
525:
526: SearchParameters sp = new SearchParameters(
527: stopKeyValue,
528: ((stopSearchOperator == ScanController.GE) ? SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH
529: : SearchParameters.POSITION_RIGHT_OF_PARTIAL_KEY_MATCH),
530: template, this , true);
531:
532: control_row = ControlRow.Get(this , BTree.ROOTPAGEID)
533: .search(sp);
534:
535: control_row.release();
536: control_row = null;
537:
538: left_of_stop = sp.left_fraction;
539: }
540:
541: // System.out.println(
542: // "\n\tleft_of_start = " + left_of_start +
543: // "\n\tleft_of_stop = " + left_of_stop);
544:
545: // what percentage of rows are between start and stop?
546:
547: float ret_fraction = left_of_stop - left_of_start;
548:
549: // If for some reason the stop position comes before the start
550: // position, assume 0 rows will return from query.
551: if (ret_fraction < 0)
552: ret_fraction = 0;
553:
554: // Never return estimate of more rows than exist, sometimes
555: // the recursive estimation through the btree may return a number
556: // like 1.00001.
557: if (ret_fraction > 1)
558: ret_fraction = 1;
559:
560: float estimated_row_count = input_row_count * ret_fraction;
561:
562: // first the base cost of positioning on the first row in the scan.
563: double cost = getFetchFromFullKeyCost(scanColumnList,
564: access_type);
565:
566: // add the base cost of bringing each page for the first time into
567: // the cache. This is basically the cost of bringing each leaf
568: // uncached into the cache and reading the control row off of it.:
569: cost += (num_pages * ret_fraction)
570: * BASE_UNCACHED_ROW_FETCH_COST;
571:
572: // Now some magic to try and figure out the cost of doing a
573: // scan along the leaf level of the tree. Mostly just assume
574: // the costs are the same as the heap, and ignore qualifier
575: // processing and stop row comparisons for now.
576:
577: // the base cost of getting each of the rows from a page assumed
578: // to already be cached (by the scan fetch) - this is only for all
579: // rows after the initial row on the page has been accounted for
580: // under the BASE_UNCACHED_ROW_FETCH_COST cost.:
581: long cached_row_count = ((long) estimated_row_count)
582: - num_pages;
583: if (cached_row_count < 0)
584: cached_row_count = 0;
585:
586: if (scan_type == StoreCostController.STORECOST_SCAN_NORMAL)
587: cost += cached_row_count * BASE_GROUPSCAN_ROW_COST;
588: else
589: cost += cached_row_count * BASE_HASHSCAN_ROW_FETCH_COST;
590:
591: // finally add the cost associated with the number of bytes in row:
592: long row_size = (input_row_count == 0) ? 4
593: : (num_pages * page_size) / input_row_count;
594:
595: cost += (estimated_row_count * row_size)
596: * BASE_ROW_PER_BYTECOST;
597:
598: if (SanityManager.DEBUG) {
599: if (cost < 0)
600: SanityManager.THROWASSERT("cost " + cost);
601:
602: if (estimated_row_count < 0)
603: SanityManager.THROWASSERT("estimated_row_count = "
604: + estimated_row_count);
605: }
606:
607: // return the cost
608: cost_result.setEstimatedCost(cost);
609:
610: // RESOLVE - should we make sure this number is > 0?
611: cost_result.setEstimatedRowCount(Math
612: .round(estimated_row_count));
613: } finally {
614: if (control_row != null)
615: control_row.release();
616: }
617:
618: // System.out.println("BTreeCostController.getScanCost():" +
619: // "\n\t cost = " + cost_result.getEstimatedCost() +
620: // "\n\t rows = " + cost_result.getEstimatedRowCount());
621:
622: return;
623: }
624:
625: /**
626: * Return an "empty" row location object of the correct type.
627: * <p>
628: *
629: * @return The empty Rowlocation.
630: *
631: * @exception StandardException Standard exception policy.
632: **/
633: public RowLocation newRowLocationTemplate()
634: throws StandardException {
635: throw StandardException
636: .newException(SQLState.BTREE_UNIMPLEMENTED_FEATURE);
637: }
638: }
|