KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > derby > impl > sql > compile > OrderByList


1 /*
2
3    Derby - Class org.apache.derby.impl.sql.compile.OrderByList
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.compile;
23
24 import org.apache.derby.iapi.sql.compile.CompilerContext;
25 import org.apache.derby.iapi.sql.compile.CostEstimate;
26 import org.apache.derby.iapi.sql.compile.RequiredRowOrdering;
27 import org.apache.derby.iapi.sql.compile.RowOrdering;
28 import org.apache.derby.iapi.sql.compile.C_NodeTypes;
29
30 import org.apache.derby.iapi.error.StandardException;
31 import org.apache.derby.iapi.services.sanity.SanityManager;
32
33 import org.apache.derby.impl.sql.compile.ActivationClassBuilder;
34
35 import org.apache.derby.iapi.sql.Activation;
36 import org.apache.derby.iapi.sql.ResultSet;
37
38 import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
39
40 import org.apache.derby.iapi.services.compiler.MethodBuilder;
41
42 import org.apache.derby.iapi.services.loader.GeneratedMethod;
43
44 import org.apache.derby.iapi.store.access.ColumnOrdering;
45 import org.apache.derby.iapi.store.access.SortCostController;
46 import org.apache.derby.iapi.store.access.TransactionController;
47
48 import org.apache.derby.iapi.types.DataValueDescriptor;
49
50 import org.apache.derby.iapi.reference.ClassName;
51 import org.apache.derby.iapi.reference.Limits;
52 import org.apache.derby.iapi.reference.SQLState;
53
54 import org.apache.derby.iapi.util.JBitSet;
55 import org.apache.derby.iapi.services.classfile.VMOpcode;
56
57 import java.util.Properties JavaDoc;
58
59 /**
60  * An OrderByList is an ordered list of columns in the ORDER BY clause.
61  * That is, the order of columns in this list is significant - the
62  * first column in the list is the most significant in the ordering,
63  * and the last column in the list is the least significant.
64  *
65     @author ames
66  */
67 public class OrderByList extends OrderedColumnList
68                         implements RequiredRowOrdering {
69
70     private boolean allAscending = true;
71     private boolean alwaysSort;
72     private ResultSetNode resultToSort;
73     private SortCostController scc;
74     private Object JavaDoc[] resultRow;
75     private ColumnOrdering[] columnOrdering;
76     private int estimatedRowSize;
77     private boolean sortNeeded = true;
78
79     /**
80         Add a column to the list
81     
82         @param column The column to add to the list
83      */
84     public void addOrderByColumn(OrderByColumn column)
85     {
86         addElement(column);
87
88         if (! column.isAscending())
89             allAscending = false;
90     }
91
92     /**
93      * Are all columns in the list ascending.
94      *
95      * @return Whether or not all columns in the list ascending.
96      */
97     boolean allAscending()
98     {
99         return allAscending;
100     }
101
102     /**
103         Get a column from the list
104     
105         @param position The column to get from the list
106      */
107     public OrderByColumn getOrderByColumn(int position) {
108         if (SanityManager.DEBUG)
109         SanityManager.ASSERT(position >=0 && position < size());
110         return (OrderByColumn) elementAt(position);
111     }
112
113     /**
114         Print the list.
115     
116         @param depth The depth at which to indent the sub-nodes
117      */
118     public void printSubNodes(int depth) {
119
120         if (SanityManager.DEBUG)
121         {
122             for (int index = 0; index < size(); index++)
123             {
124                 ( (OrderByColumn) (elementAt(index)) ).treePrint(depth);
125             }
126         }
127     }
128
129     /**
130         Bind the update columns by their names to the target resultset
131         of the cursor specification.
132
133         @param target The underlying result set
134     
135         @exception StandardException Thrown on error
136      */
137     public void bindOrderByColumns(ResultSetNode target)
138                     throws StandardException {
139
140         /* Remember the target for use in optimization */
141         resultToSort = target;
142
143         int size = size();
144
145         /* Only 1012 columns allowed in ORDER BY clause */
146         if (size > Limits.DB2_MAX_ELEMENTS_IN_ORDER_BY)
147         {
148             throw StandardException.newException(SQLState.LANG_TOO_MANY_ELEMENTS);
149         }
150
151         for (int index = 0; index < size; index++)
152         {
153             OrderByColumn obc = (OrderByColumn) elementAt(index);
154             obc.bindOrderByColumn(target);
155
156             /*
157             ** Always sort if we are ordering on an expression, and not
158             ** just a column.
159             */
160             if ( !
161              (obc.getResultColumn().getExpression() instanceof ColumnReference))
162             {
163                 alwaysSort = true;
164             }
165         }
166     }
167
168     /**
169         Pull up Order By columns by their names to the target resultset
170         of the cursor specification.
171
172         @param target The underlying result set
173     
174      */
175     public void pullUpOrderByColumns(ResultSetNode target)
176                     throws StandardException {
177
178         /* Remember the target for use in optimization */
179         resultToSort = target;
180
181         int size = size();
182         for (int index = 0; index < size; index++)
183         {
184             OrderByColumn obc = (OrderByColumn) elementAt(index);
185             obc.pullUpOrderByColumn(target);
186         }
187
188     }
189
190     /**
191      * Is this order by list an in order prefix of the specified RCL.
192      * This is useful when deciding if an order by list can be eliminated
193      * due to a sort from an underlying distinct or union.
194      *
195      * @param sourceRCL The source RCL.
196      *
197      * @return Whether or not this order by list an in order prefix of the specified RCL.
198      */
199     boolean isInOrderPrefix(ResultColumnList sourceRCL)
200     {
201         boolean inOrderPrefix = true;
202         int rclSize = sourceRCL.size();
203
204         if (SanityManager.DEBUG)
205         {
206             if (size() > sourceRCL.size())
207             {
208                 SanityManager.THROWASSERT(
209                     "size() (" + size() +
210                     ") expected to be <= sourceRCL.size() (" +
211                     sourceRCL.size() + ")");
212             }
213         }
214
215         int size = size();
216         for (int index = 0; index < size; index++)
217         {
218             if (((OrderByColumn) elementAt(index)).getResultColumn() !=
219                 (ResultColumn) sourceRCL.elementAt(index))
220             {
221                 return false;
222             }
223         }
224         return true;
225     }
226
227     /**
228      * Order by columns now point to the PRN above the node of interest.
229      * We need them to point to the RCL under that one. This is useful
230      * when combining sorts where we need to reorder the sorting
231      * columns.
232      */
233     void resetToSourceRCs()
234     {
235         int size = size();
236         for (int index = 0; index < size; index++)
237         {
238             OrderByColumn obc = (OrderByColumn) elementAt(index);
239             obc.resetToSourceRC();
240         }
241     }
242
243     /**
244      * Build a new RCL with the same RCs as the passed in RCL
245      * but in an order that matches the ordering columns.
246      *
247      * @param resultColumns The RCL to reorder.
248      *
249      * @exception StandardException Thrown on error
250      */
251     ResultColumnList reorderRCL(ResultColumnList resultColumns)
252         throws StandardException
253     {
254         ResultColumnList newRCL = (ResultColumnList) getNodeFactory().getNode(
255                                                 C_NodeTypes.RESULT_COLUMN_LIST,
256                                                 getContextManager());
257
258         /* The new RCL starts with the ordering columns */
259         int size = size();
260         for (int index = 0; index < size; index++)
261         {
262             OrderByColumn obc = (OrderByColumn) elementAt(index);
263             newRCL.addElement(obc.getResultColumn());
264             resultColumns.removeElement(obc.getResultColumn());
265         }
266
267         /* And ends with the non-ordering columns */
268         newRCL.destructiveAppend(resultColumns);
269         newRCL.resetVirtualColumnIds();
270         return newRCL;
271     }
272
273     /**
274         Remove any constant columns from this order by list.
275         Constant columns are ones where all of the column references
276         are equal to constant expressions according to the given
277         predicate list.
278      */
279     void removeConstantColumns(PredicateList whereClause)
280     {
281         /* Walk the list backwards so we can remove elements safely */
282         for (int loc = size() - 1;
283              loc >= 0;
284              loc--)
285         {
286             OrderByColumn obc = (OrderByColumn) elementAt(loc);
287
288             if (obc.constantColumn(whereClause))
289             {
290                 removeElementAt(loc);
291             }
292         }
293     }
294
295     /**
296         Remove any duplicate columns from this order by list.
297         For example, one may "ORDER BY 1, 1, 2" can be reduced
298         to "ORDER BY 1, 2".
299         Beetle 5401.
300      */
301     void removeDupColumns()
302     {
303         /* Walk the list backwards so we can remove elements safely */
304         for (int loc = size() - 1; loc > 0; loc--)
305         {
306             OrderByColumn obc = (OrderByColumn) elementAt(loc);
307             int colPosition = obc.getColumnPosition();
308
309             for (int inner = 0; inner < loc; inner++)
310             {
311                 OrderByColumn prev_obc = (OrderByColumn) elementAt(inner);
312                 if (colPosition == prev_obc.getColumnPosition())
313                 {
314                     removeElementAt(loc);
315                     break;
316                 }
317             }
318         }
319     }
320
321     /**
322         generate the sort result set operating over the source
323         expression.
324
325         @param acb the tool for building the class
326         @param mb the method the generated code is to go into
327         @exception StandardException thrown on failure
328      */
329     public void generate(ActivationClassBuilder acb,
330                                 MethodBuilder mb,
331                                 ResultSetNode child)
332                             throws StandardException
333     {
334         /*
335         ** If sorting is not required, don't generate a sort result set -
336         ** just return the child result set.
337         */
338         if ( ! sortNeeded) {
339             child.generate(acb, mb);
340             return;
341         }
342
343         /* Get the next ResultSet#, so we can number this ResultSetNode, its
344          * ResultColumnList and ResultSet.
345          *
346          * REMIND: to do this properly (if order bys can live throughout
347          * the tree) there ought to be an OrderByNode that holds its own
348          * ResultColumnList that is a lsit of virtual column nodes pointing
349          * to the source's result columns. But since we know it is outermost,
350          * we just gloss over that and get ourselves a resultSetNumber
351          * directly.
352          */
353         CompilerContext cc = getCompilerContext();
354
355
356         /*
357             create the orderItem and stuff it in.
358          */
359         int orderItem = acb.addItem(acb.getColumnOrdering(this));
360
361
362         /* Generate the SortResultSet:
363          * arg1: childExpress - Expression for childResultSet
364          * arg2: distinct - always false, we have a separate node
365          * for distincts
366          * arg3: isInSortedOrder - is the source result set in sorted order
367          * arg4: orderItem - entry in saved objects for the ordering
368          * arg5: rowAllocator - method to construct rows for fetching
369          * from the sort
370          * arg6: row size
371          * arg7: resultSetNumber
372          * arg8: estimated row count
373          * arg9: estimated cost
374          */
375
376         acb.pushGetResultSetFactoryExpression(mb);
377
378         child.generate(acb, mb);
379
380         int resultSetNumber = cc.getNextResultSetNumber();
381
382         // is a distinct query
383 mb.push(false);
384
385         // not in sorted order
386 mb.push(false);
387
388         mb.push(orderItem);
389
390         // row allocator
391 child.getResultColumns().generateHolder(acb, mb);
392
393         mb.push(child.getResultColumns().getTotalColumnSize());
394
395         mb.push(resultSetNumber);
396
397         // Get the cost estimate for the child
398 // RESOLVE - we will eventually include the cost of the sort
399 CostEstimate costEstimate = child.getFinalCostEstimate();
400
401         mb.push(costEstimate.rowCount());
402         mb.push(costEstimate.getEstimatedCost());
403
404         mb.callMethod(VMOpcode.INVOKEINTERFACE, (String JavaDoc) null, "getSortResultSet",
405                             ClassName.NoPutResultSet, 9);
406
407     }
408
409     /* RequiredRowOrdering interface */
410
411     /**
412      * @see RequiredRowOrdering#sortRequired
413      *
414      * @exception StandardException Thrown on error
415      */
416     public int sortRequired(RowOrdering rowOrdering) throws StandardException
417     {
418         return sortRequired(rowOrdering, (JBitSet) null);
419     }
420
421     /**
422      * @see RequiredRowOrdering#sortRequired
423      *
424      * @exception StandardException Thrown on error
425      */
426     public int sortRequired(RowOrdering rowOrdering, JBitSet tableMap)
427                 throws StandardException
428     {
429         /*
430         ** Currently, all indexes are ordered ascending, so a descending
431         ** ORDER BY always requires a sort.
432         */
433         if (alwaysSort)
434         {
435             return RequiredRowOrdering.SORT_REQUIRED;
436         }
437
438         /*
439         ** Step through the columns in this list, and ask the
440         ** row ordering whether it is ordered on each column.
441         */
442         int position = 0;
443         int size = size();
444         for (int loc = 0; loc < size; loc++)
445         {
446             OrderByColumn obc = getOrderByColumn(loc);
447
448             // ResultColumn rc = obc.getResultColumn();
449
450             /*
451             ** This presumes that the OrderByColumn refers directly to
452             ** the base column, i.e. there is no intervening VirtualColumnNode.
453             */
454             // ValueNode expr = obc.getNonRedundantExpression();
455 ValueNode expr = obc.getResultColumn().getExpression();
456
457             if ( ! (expr instanceof ColumnReference))
458             {
459                 return RequiredRowOrdering.SORT_REQUIRED;
460             }
461
462             ColumnReference cr = (ColumnReference) expr;
463
464             /*
465             ** Check whether the table referred to is in the table map (if any).
466             ** If it isn't, we may have an ordering that does not require
467             ** sorting for the tables in a partial join order. Look for
468             ** columns beyond this column to see whether a referenced table
469             ** is found - if so, sorting is required (for example, in a
470             ** case like ORDER BY S.A, T.B, S.C, sorting is required).
471             */
472             if (tableMap != null)
473             {
474                 if ( ! tableMap.get(cr.getTableNumber()))
475                 {
476                     /* Table not in partial join order */
477                     for (int remainingPosition = loc + 1;
478                          remainingPosition < size();
479                          remainingPosition++)
480                     {
481                         OrderByColumn remainingobc = getOrderByColumn(loc);
482
483                         ResultColumn remainingrc =
484                                                 remainingobc.getResultColumn();
485
486                         ValueNode remainingexpr = remainingrc.getExpression();
487
488                         if (remainingexpr instanceof ColumnReference)
489                         {
490                             ColumnReference remainingcr =
491                                             (ColumnReference) remainingexpr;
492                             if (tableMap.get(remainingcr.getTableNumber()))
493                             {
494                                 return RequiredRowOrdering.SORT_REQUIRED;
495                             }
496                         }
497                     }
498
499                     return RequiredRowOrdering.NOTHING_REQUIRED;
500                 }
501             }
502
503             if ( ! rowOrdering.alwaysOrdered(cr.getTableNumber()))
504             {
505                 /*
506                 ** Check whether the ordering is ordered on this column in
507                 ** this position.
508                 */
509                 if ( ! rowOrdering.orderedOnColumn(
510                     obc.isAscending() ?
511                                 RowOrdering.ASCENDING : RowOrdering.DESCENDING,
512                     position,
513                     cr.getTableNumber(),
514                     cr.getColumnNumber()
515                     ))
516                 {
517                     return RequiredRowOrdering.SORT_REQUIRED;
518                 }
519
520                 /*
521                 ** The position to ask about is for the columns in tables
522                 ** that are *not* always ordered. The always-ordered tables
523                 ** are not counted as part of the list of ordered columns
524                 */
525                 position++;
526             }
527         }
528
529         return RequiredRowOrdering.NOTHING_REQUIRED;
530     }
531
532     /**
533      * @see RequiredRowOrdering#estimateCost
534      *
535      * @exception StandardException Thrown on error
536      */
537     public void estimateCost(double estimatedInputRows,
538                                 RowOrdering rowOrdering,
539                                 CostEstimate resultCost)
540                     throws StandardException
541     {
542         /*
543         ** Do a bunch of set-up the first time: get the SortCostController,
544         ** the template row, the ColumnOrdering array, and the estimated
545         ** row size.
546         */
547         if (scc == null)
548         {
549             scc = getCompilerContext().getSortCostController();
550
551             resultRow =
552                 resultToSort.getResultColumns().buildEmptyRow().getRowArray();
553             columnOrdering = getColumnOrdering();
554             estimatedRowSize =
555                         resultToSort.getResultColumns().getTotalColumnSize();
556         }
557
558         long inputRows = (long) estimatedInputRows;
559         long exportRows = inputRows;
560         double sortCost;
561
562         sortCost = scc.getSortCost(
563                                     (DataValueDescriptor[]) resultRow,
564                                     columnOrdering,
565                                     false,
566                                     inputRows,
567                                     exportRows,
568                                     estimatedRowSize
569                                     );
570
571         resultCost.setCost(sortCost, estimatedInputRows, estimatedInputRows);
572     }
573
574     /** @see RequiredRowOrdering#sortNeeded */
575     public void sortNeeded()
576     {
577         sortNeeded = true;
578     }
579
580     /** @see RequiredRowOrdering#sortNotNeeded */
581     public void sortNotNeeded()
582     {
583         sortNeeded = false;
584     }
585
586     /**
587      * Remap all ColumnReferences in this tree to be clones of the
588      * underlying expression.
589      *
590      * @exception StandardException Thrown on error
591      */
592     void remapColumnReferencesToExpressions() throws StandardException
593     {
594     }
595
596     /**
597      * Get whether or not a sort is needed.
598      *
599      * @return Whether or not a sort is needed.
600      */
601     public boolean getSortNeeded()
602     {
603         return sortNeeded;
604     }
605 }
606
Popular Tags