001: /*
002:
003: Derby - Class org.apache.derby.impl.sql.execute.SortResultSet
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.execute;
023:
024: import org.apache.derby.iapi.services.monitor.Monitor;
025:
026: import org.apache.derby.iapi.services.sanity.SanityManager;
027:
028: import org.apache.derby.iapi.services.stream.HeaderPrintWriter;
029: import org.apache.derby.iapi.services.stream.InfoStreams;
030:
031: import org.apache.derby.iapi.services.io.Formatable;
032:
033: import org.apache.derby.iapi.sql.execute.CursorResultSet;
034: import org.apache.derby.iapi.sql.ResultSet;
035: import org.apache.derby.iapi.sql.execute.ExecRow;
036: import org.apache.derby.iapi.sql.execute.NoPutResultSet;
037:
038: import org.apache.derby.iapi.sql.Activation;
039:
040: import org.apache.derby.iapi.store.access.ColumnOrdering;
041: import org.apache.derby.iapi.types.DataValueDescriptor;
042: import org.apache.derby.iapi.store.access.SortObserver;
043: import org.apache.derby.iapi.store.access.TransactionController;
044: import org.apache.derby.iapi.store.access.SortController;
045: import org.apache.derby.iapi.store.access.ScanController;
046:
047: import org.apache.derby.iapi.services.loader.GeneratedMethod;
048:
049: import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
050:
051: import org.apache.derby.iapi.error.StandardException;
052:
053: import org.apache.derby.iapi.types.RowLocation;
054:
055: import org.apache.derby.iapi.services.io.FormatableArrayHolder;
056:
057: import java.util.Properties;
058: import java.util.Vector;
059: import java.util.Enumeration;
060:
061: /**
062: * Takes a source result set, sends it to the sorter,
063: * and returns the results. If distinct is true, removes
064: * all but one copy of duplicate rows using DistinctAggregator,
065: * which really doesn't aggregate anything at all -- the sorter
066: * assumes that the presence of an aggregator means that
067: * it should return a single row for each set with identical
068: * ordering columns.
069: * <p>
070: * If aggregate is true, then it feeds any number of aggregates
071: * to the sorter. Each aggregate is an instance of GenericAggregator
072: * which knows which Aggregator to call to perform the
073: * aggregation.
074: * <p>
075: * Brief background on the sorter and aggregates: the sorter
076: * has some rudimentary knowledge about aggregates. If
077: * it is passed aggregates, it will eliminate duplicates
078: * on the ordering columns. In the process it will call the
079: * aggregator on each row that is discarded.
080: * <p>
081: * Note that a DISTINCT on the SELECT list and an aggregate cannot
082: * be processed by the same SortResultSet(), if there are both
083: * aggregates (distinct or otherwise) and a DISTINCT on the select
084: * list, then 2 separate SortResultSets are required (the DISTINCT
085: * is a sort on the output of the sort with the aggregation).
086: * <p>
087: * Currently, all rows are fed through the sorter. This is
088: * true even if there is no sorting needed. In this case
089: * we feed every row in and just pull every row out (this is
090: * an obvious area for a performance improvement). We'll
091: * need to know if the rows are sorted before we can make
092: * any optimizations in this area.
093: * <p>
094: * <B>CLONING</B>: Cloning and sorts are an important topic.
095: * Currently we do a lot of cloning. We clone the following: <UL>
096: * <LI> every row that is inserted into the sorter. We
097: * need to clone the rows because the source result set might
098: * be reusing rows, and we need to be able to accumulate the
099: * entire result set in the sorter. </LI>
100: * <p>
101: * There are two cloning APIs: cloning by the sorter on
102: * rows that are not discarded as duplicates or cloning
103: * in the SortResultSet prior to inserting into the sorter.
104: * If we have any aggregates at all we always clone prior
105: * to inserting into the sorter. We need to do this
106: * because we have to set up the aggregators before passing
107: * them into the sorter. When we don't have aggregates
108: * we let the sorter to the cloning to avoid unnecessary
109: * clones on duplicate rows that are going to be discarded
110: * anyway.
111: *
112: * @author ames, rewrite for aggregates by jamie, aggregate removal by jerry
113: */
114: class SortResultSet extends NoPutResultSetImpl implements
115: CursorResultSet {
116:
117: /* Run time statistics variables */
118: public int rowsInput;
119: public int rowsReturned;
120: public boolean distinct;
121:
122: // set in constructor and not altered during
123: // life of object.
124: public NoPutResultSet source;
125: private GeneratedMethod rowAllocator;
126: private ColumnOrdering[] order;
127: private ColumnOrdering[] savedOrder;
128: private SortObserver observer;
129: private ExecRow sortTemplateRow;
130: public boolean isInSortedOrder; // true if source results in sorted order
131: private NoPutResultSet originalSource; // used for run time stats only
132: private int maxRowSize;
133:
134: // set in open and not modified thereafter
135: private ScanController scanController;
136:
137: // argument to getNextRowFromRS()
138:
139: private ExecRow sortResultRow;
140:
141: // In order distincts
142: private ExecRow currSortedRow;
143: private boolean nextCalled;
144: private int numColumns;
145:
146: // used to track and close sorts
147: private long genericSortId;
148: private boolean dropGenericSort;
149:
150: // remember whether or not any sort was performed
151: private boolean sorted;
152:
153: // RTS
154: public Properties sortProperties = new Properties();
155:
156: /**
157: * Constructor
158: *
159: * @param s input result set
160: * @param distinct if this is a DISTINCT select list.
161: * Also set to true for a GROUP BY w/o aggretates
162: * @param isInSortedOrder true if the source results are in sorted order
163: * @param orderingItem indicates the number of the
164: * SavedObject off of the PreparedStatement that holds the
165: * ColumOrdering array used by this routine
166: * @param a activation
167: * @param ra generated method to build an empty
168: * output row
169: * @param maxRowSize approx row size, passed to sorter
170: * @param resultSetNumber The resultSetNumber for this result set
171: *
172: * @exception StandardException Thrown on error
173: */
174: public SortResultSet(NoPutResultSet s, boolean distinct,
175: boolean isInSortedOrder, int orderingItem, Activation a,
176: GeneratedMethod ra, int maxRowSize, int resultSetNumber,
177: double optimizerEstimatedRowCount,
178: double optimizerEstimatedCost) throws StandardException {
179: super (a, resultSetNumber, optimizerEstimatedRowCount,
180: optimizerEstimatedCost);
181: this .distinct = distinct;
182: this .isInSortedOrder = isInSortedOrder;
183: source = s;
184: originalSource = s;
185: rowAllocator = ra;
186: this .maxRowSize = maxRowSize;
187: sortTemplateRow = (ExecRow) rowAllocator.invoke(activation);
188: order = (ColumnOrdering[]) ((FormatableArrayHolder) (a
189: .getPreparedStatement().getSavedObject(orderingItem)))
190: .getArray(ColumnOrdering.class);
191:
192: /* NOTE: We need to save order to another variable
193: * in the constructor and reset it on every open.
194: * This is important because order can get reset in the
195: * guts of execution below. Subsequent sorts could get
196: * the wrong result without this logic.
197: */
198: savedOrder = order;
199:
200: /*
201: ** Create a sort observer that are retained by the
202: ** sort.
203: */
204: observer = new BasicSortObserver(true, distinct,
205: sortTemplateRow, true);
206:
207: constructorTime += getElapsedMillis(beginTime);
208: }
209:
210: ///////////////////////////////////////////////////////////////////////////////
211: //
212: // ResultSet interface (leftover from NoPutResultSet)
213: //
214: ///////////////////////////////////////////////////////////////////////////////
215:
216: /**
217: * Open the scan. Load the sorter and prepare to get
218: * rows from it.
219: *
220: * @exception StandardException thrown if cursor finished.
221: */
222: public void openCore() throws StandardException {
223: nextCalled = false;
224: beginTime = getCurrentTimeMillis();
225: // REVISIT: through the direct DB API, this needs to be an
226: // error, not an ASSERT; users can open twice. Only through JDBC
227: // is access to open controlled and ensured valid.
228: if (SanityManager.DEBUG)
229: SanityManager.ASSERT(!isOpen, "SortResultSet already open");
230:
231: /* NOTE: We need to save order to another variable
232: * in the constructor and reset it on every open.
233: * This is important because order can get reset in the
234: * guts of execution below. Subsequent sorts could get
235: * the wrong result without this logic.
236: */
237: order = savedOrder;
238:
239: sortResultRow = sortTemplateRow.getClone();
240:
241: source.openCore();
242:
243: /* If this is an in-order distinct then we do not need the sorter.
244: * (We filter out the duplicate rows ourselves.)
245: * We save a clone of the first row so that subsequent next()s
246: * do not overwrite the saved row.
247: */
248: if (isInSortedOrder && distinct) {
249: currSortedRow = getNextRowFromRS();
250: if (currSortedRow != null) {
251: currSortedRow = (ExecRow) currSortedRow.getClone();
252: }
253: } else {
254: /*
255: ** Load up the sorter.
256: */
257: scanController = loadSorter();
258: sorted = true;
259: }
260:
261: isOpen = true;
262: numOpens++;
263:
264: openTime += getElapsedMillis(beginTime);
265: }
266:
267: /**
268: * Load up the sorter. Feed it every row from the
269: * source scan. When done, close
270: * the source scan and open the sort. Return the sort
271: * scan controller.
272: *
273: * @exception StandardException thrown on failure.
274: *
275: * @return the sort controller
276: */
277: private ScanController loadSorter() throws StandardException {
278: SortController sorter;
279: long sortId;
280: ExecRow sourceRow;
281: ExecRow inputRow;
282: boolean inOrder = (order.length == 0 || isInSortedOrder);
283: int inputRowCountEstimate = (int) optimizerEstimatedRowCount;
284:
285: // find the language context and
286: // Get the current transaction controller
287: TransactionController tc = getTransactionController();
288: sortId = tc.createSort((Properties) null, sortTemplateRow
289: .getRowArray(), order, observer, inOrder,
290: inputRowCountEstimate, // est rows
291: maxRowSize // est rowsize
292: );
293: sorter = tc.openSort(sortId);
294: genericSortId = sortId;
295: dropGenericSort = true;
296:
297: /* The sorter is responsible for doing the cloning */
298: while ((inputRow = getNextRowFromRS()) != null) {
299: /* The sorter is responsible for doing the cloning */
300: sorter.insert(inputRow.getRowArray());
301: }
302: source.close();
303: sortProperties = sorter.getSortInfo().getAllSortInfo(
304: sortProperties);
305: sorter.close();
306:
307: return tc.openSortScan(sortId, activation
308: .getResultSetHoldability());
309: }
310:
311: /**
312: * Return the next row.
313: *
314: * @exception StandardException thrown on failure.
315: * @exception StandardException ResultSetNotOpen thrown if not yet open.
316: *
317: * @return the next row in the result
318: */
319: public ExecRow getNextRowCore() throws StandardException {
320: if (!isOpen) {
321: return null;
322: }
323:
324: beginTime = getCurrentTimeMillis();
325:
326: // In order distinct
327: if (isInSortedOrder && distinct) {
328: // No rows, no work to do
329: if (currSortedRow == null) {
330: nextTime += getElapsedMillis(beginTime);
331: return null;
332: }
333:
334: /* If this is the 1st next, then simply return the 1st row
335: * (which we got on the open()).
336: */
337: if (!nextCalled) {
338: nextCalled = true;
339: numColumns = currSortedRow.getRowArray().length;
340: nextTime += getElapsedMillis(beginTime);
341: rowsReturned++;
342: setCurrentRow(currSortedRow);
343: return currSortedRow;
344: }
345:
346: ExecRow sortResult = getNextRowFromRS();
347:
348: /* Drain and throw away rows until we find a new distinct row. */
349: while (sortResult != null) {
350: /* We found a new row. Update the current row and return this one. */
351: if (!filterRow(currSortedRow, sortResult)) {
352: /* Save a clone of the new row so that it doesn't get overwritten */
353: currSortedRow = (ExecRow) sortResult.getClone();
354: setCurrentRow(currSortedRow);
355: nextTime += getElapsedMillis(beginTime);
356: rowsReturned++;
357: return currSortedRow;
358: }
359:
360: // Get the next row
361: sortResult = getNextRowFromRS();
362: }
363:
364: // We've drained the source, so no more rows to return
365: currSortedRow = null;
366: nextTime += getElapsedMillis(beginTime);
367: return null;
368: } else {
369: ExecRow sortResult = getNextRowFromRS();
370:
371: if (sortResult != null) {
372: setCurrentRow(sortResult);
373: rowsReturned++;
374: }
375: nextTime += getElapsedMillis(beginTime);
376: return sortResult;
377: }
378: }
379:
380: /**
381: * Filter out the new row if it has the same contents as
382: * the current row. (This allows us to process in-order
383: * distincts without a sorter.)
384: *
385: * @param currRow The current row.
386: * @param newRow The new row.
387: *
388: * @return Whether or not to filter out the new row.
389: *
390: * @exception StandardException thrown on failure to get row location
391: */
392: private boolean filterRow(ExecRow currRow, ExecRow newRow)
393: throws StandardException {
394: for (int index = 1; index <= numColumns; index++) {
395: DataValueDescriptor currOrderable = currRow
396: .getColumn(index);
397: DataValueDescriptor newOrderable = newRow.getColumn(index);
398: if (!(currOrderable.compare(
399: DataValueDescriptor.ORDER_OP_EQUALS, newOrderable,
400: true, true))) {
401: return false;
402: }
403: }
404: return true;
405: }
406:
407: /**
408: * If the result set has been opened,
409: * close the open scan.
410: *
411: * @exception StandardException thrown on error
412: */
413: public void close() throws StandardException {
414: beginTime = getCurrentTimeMillis();
415: if (isOpen) {
416: // we don't want to keep around a pointer to the
417: // row ... so it can be thrown away.
418: // REVISIT: does this need to be in a finally
419: // block, to ensure that it is executed?
420: clearCurrentRow();
421:
422: sortResultRow = null;
423: closeSource();
424:
425: if (dropGenericSort) {
426: getTransactionController().dropSort(genericSortId);
427: dropGenericSort = false;
428: }
429: super .close();
430: } else if (SanityManager.DEBUG)
431: SanityManager.DEBUG("CloseRepeatInfo",
432: "Close of SortResultSet repeated");
433:
434: closeTime += getElapsedMillis(beginTime);
435:
436: isOpen = false;
437: }
438:
439: public void finish() throws StandardException {
440: source.finish();
441: finishAndRTS();
442: }
443:
444: /**
445: * Return the total amount of time spent in this ResultSet
446: *
447: * @param type CURRENT_RESULTSET_ONLY - time spent only in this ResultSet
448: * ENTIRE_RESULTSET_TREE - time spent in this ResultSet and below.
449: *
450: * @return long The total amount of time spent (in milliseconds).
451: */
452: public long getTimeSpent(int type) {
453: long totTime = constructorTime + openTime + nextTime
454: + closeTime;
455:
456: if (type == NoPutResultSet.CURRENT_RESULTSET_ONLY) {
457: return totTime
458: - originalSource
459: .getTimeSpent(ENTIRE_RESULTSET_TREE);
460: } else {
461: return totTime;
462: }
463: }
464:
465: ///////////////////////////////////////////////////////////////////////////////
466: //
467: // CursorResultSet interface
468: //
469: ///////////////////////////////////////////////////////////////////////////////
470:
471: /**
472: * This result set has its row location from
473: * the last fetch done. If the cursor is closed,
474: * a null is returned.
475: *
476: * @see CursorResultSet
477: *
478: * @return the row location of the current cursor row.
479: * @exception StandardException thrown on failure to get row location
480: */
481: public RowLocation getRowLocation() throws StandardException {
482: if (!isOpen)
483: return null;
484:
485: // REVISIT: could we reuse the same rowlocation object
486: // across several calls?
487: RowLocation rl;
488: rl = scanController.newRowLocationTemplate();
489: scanController.fetchLocation(rl);
490: return rl;
491: }
492:
493: /**
494: * This result set has its row from the last fetch done.
495: * If the cursor is closed, a null is returned.
496: *
497: * @see CursorResultSet
498: *
499: * @return the last row returned;
500: * @exception StandardException thrown on failure.
501: */
502: /* RESOLVE - this should return activation.getCurrentRow(resultSetNumber),
503: * once there is such a method. (currentRow is redundant)
504: */
505: public ExecRow getCurrentRow() throws StandardException {
506: if (SanityManager.DEBUG)
507: SanityManager.ASSERT(isOpen,
508: "SortResultSet expected to be open");
509:
510: /*
511: DISTINCT assumes the currentRow is good, since it
512: is the only one with access to its sort scan result
513: */
514: return currentRow;
515: }
516:
517: ///////////////////////////////////////////////////////////////////////////////
518: //
519: // SCAN ABSTRACTION UTILITIES
520: //
521: ///////////////////////////////////////////////////////////////////////////////
522: /**
523: * Get the next output row for processing
524: */
525: private ExecRow getNextRowFromRS() throws StandardException {
526: return (scanController == null) ? getRowFromResultSet()
527: : getRowFromSorter();
528: }
529:
530: /**
531: * Get a row from the input result set.
532: */
533: private ExecRow getRowFromResultSet() throws StandardException {
534: ExecRow sourceRow;
535: ExecRow inputRow = null;
536:
537: if ((sourceRow = source.getNextRowCore()) != null) {
538: rowsInput++;
539: inputRow = sourceRow;
540: }
541:
542: return inputRow;
543: }
544:
545: /**
546: * Get a row from the sorter. Side effects:
547: * sets currentRow.
548: */
549: private ExecRow getRowFromSorter() throws StandardException {
550: ExecRow inputRow = null;
551:
552: if (scanController.next()) {
553: // REMIND: HACKALERT we are assuming that result will
554: // point to what sortResult is manipulating when
555: // we complete the fetch.
556: currentRow = sortResultRow;
557:
558: inputRow = sortResultRow;
559:
560: scanController.fetch(inputRow.getRowArray());
561: }
562: return inputRow;
563: }
564:
565: /**
566: * Close the source of whatever we have been scanning.
567: */
568: private void closeSource() throws StandardException {
569: if (scanController == null) {
570: /*
571: ** NOTE: do not null out source, we
572: ** may be opened again, in which case
573: ** we will open source again.
574: */
575: source.close();
576: } else {
577: scanController.close();
578: scanController = null;
579: }
580: }
581: }
|