KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > derby > impl > sql > execute > SortResultSet


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