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