001: /*
002:
003: Derby - Class org.apache.derby.impl.sql.compile.RowOrderingImpl
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.RowOrdering;
025: import org.apache.derby.iapi.sql.compile.Optimizable;
026:
027: import org.apache.derby.iapi.services.sanity.SanityManager;
028:
029: import org.apache.derby.iapi.error.StandardException;
030:
031: import java.util.Vector;
032:
033: class RowOrderingImpl implements RowOrdering {
034:
035: /* This vector contains ColumnOrderings */
036: Vector ordering;
037:
038: /*
039: ** This ColumnOrdering represents the columns that can be considered
040: ** ordered no matter what. For example, columns that are compared to
041: ** constants with = are always ordered. Also, all columns in a one-row
042: ** result set are ordered.
043: */
044: ColumnOrdering columnsAlwaysOrdered;
045:
046: /*
047: ** This vector contains table numbers for tables that are always ordered.
048: ** This happens for one-row tables.
049: */
050: Vector alwaysOrderedOptimizables;
051:
052: ColumnOrdering currentColumnOrdering;
053:
054: /* This vector contains unordered Optimizables */
055: Vector unorderedOptimizables;
056:
057: RowOrderingImpl() {
058: ordering = new Vector();
059: unorderedOptimizables = new Vector();
060: columnsAlwaysOrdered = new ColumnOrdering(RowOrdering.DONTCARE);
061: alwaysOrderedOptimizables = new Vector();
062: }
063:
064: /**
065: * @see RowOrdering#orderedOnColumn
066: *
067: * @exception StandardException Thrown on error
068: */
069: public boolean orderedOnColumn(int direction, int orderPosition,
070: int tableNumber, int columnNumber) throws StandardException {
071:
072: /*
073: ** Return true if the table is always ordered.
074: */
075: if (vectorContainsOptimizable(tableNumber,
076: alwaysOrderedOptimizables)) {
077: return true;
078: }
079:
080: /*
081: ** Return true if the column is always ordered.
082: */
083: if (columnsAlwaysOrdered.contains(tableNumber, columnNumber)) {
084: return true;
085: }
086:
087: /*
088: ** Return false if we're looking for an ordering position that isn't
089: ** in this ordering.
090: */
091: if (orderPosition >= ordering.size())
092: return false;
093:
094: ColumnOrdering co = (ColumnOrdering) ordering
095: .elementAt(orderPosition);
096:
097: /*
098: ** Is the column in question ordered with the given direction at
099: ** this position?
100: */
101: return co.ordered(direction, tableNumber, columnNumber);
102: }
103:
104: /**
105: * @see RowOrdering#orderedOnColumn
106: *
107: * @exception StandardException Thrown on error
108: */
109: public boolean orderedOnColumn(int direction, int tableNumber,
110: int columnNumber) throws StandardException {
111:
112: /*
113: ** Return true if the table is always ordered.
114: */
115: if (vectorContainsOptimizable(tableNumber,
116: alwaysOrderedOptimizables)) {
117: return true;
118: }
119:
120: /*
121: ** Return true if the column is always ordered.
122: */
123: if (columnsAlwaysOrdered.contains(tableNumber, columnNumber)) {
124: return true;
125: }
126:
127: boolean ordered = false;
128:
129: for (int i = 0; i < ordering.size(); i++) {
130: ColumnOrdering co = (ColumnOrdering) ordering.elementAt(i);
131:
132: /*
133: ** Is the column in question ordered with the given direction at
134: ** this position?
135: */
136: boolean this Ordered = co.ordered(direction, tableNumber,
137: columnNumber);
138:
139: if (this Ordered) {
140: ordered = true;
141: break;
142: }
143: }
144:
145: return ordered;
146: }
147:
148: /**
149: * Return true if the given vector of Optimizables contains an Optimizable
150: * with the given table number.
151: */
152: private boolean vectorContainsOptimizable(int tableNumber,
153: Vector vec) {
154: int i;
155:
156: for (i = vec.size() - 1; i >= 0; i--) {
157: Optimizable optTable = (Optimizable) vec.elementAt(i);
158:
159: if (optTable.hasTableNumber()) {
160: if (optTable.getTableNumber() == tableNumber) {
161: return true;
162: }
163: }
164: }
165:
166: return false;
167: }
168:
169: /** @see RowOrdering#addOrderedColumn */
170: public void addOrderedColumn(int direction, int tableNumber,
171: int columnNumber) {
172: if (unorderedOptimizables.size() > 0)
173: return;
174:
175: ColumnOrdering currentColumnOrdering;
176:
177: if (ordering.size() == 0) {
178: currentColumnOrdering = new ColumnOrdering(direction);
179: ordering.addElement(currentColumnOrdering);
180: } else {
181: currentColumnOrdering = (ColumnOrdering) ordering
182: .elementAt(ordering.size() - 1);
183: }
184:
185: if (SanityManager.DEBUG) {
186: if (currentColumnOrdering.direction() != direction) {
187: SanityManager.THROWASSERT("direction == " + direction
188: + ", currentColumnOrdering.direction() == "
189: + currentColumnOrdering.direction());
190: }
191: }
192:
193: currentColumnOrdering.addColumn(tableNumber, columnNumber);
194: }
195:
196: /** @see RowOrdering#nextOrderPosition */
197: public void nextOrderPosition(int direction) {
198: if (unorderedOptimizables.size() > 0)
199: return;
200:
201: currentColumnOrdering = new ColumnOrdering(direction);
202: ordering.addElement(currentColumnOrdering);
203: }
204:
205: public void optimizableAlwaysOrdered(Optimizable optimizable) {
206: // A table can't be ordered if there is an outer unordered table
207: if (unorderedOptimizablesOtherThan(optimizable)) {
208: return;
209: }
210:
211: /*
212: ** A table is not "always ordered" if any of the other ordered tables
213: ** in the join order are not also "always ordered". In other words,
214: ** if any outer table is not a one-row table, this table is not
215: ** always ordered.
216: **
217: ** The table that was passed in as a parameter may have already been
218: ** added as a table with ordered columns. If it is the first table
219: ** in the list of ordered columns, then there should be no other
220: ** tables in this list, so we remove it from the list and add it
221: ** to the list of always-ordered tables.
222: */
223: boolean hasTableNumber = optimizable.hasTableNumber();
224: int tableNumber = (hasTableNumber ? optimizable
225: .getTableNumber() : 0);
226: if (((ordering.size() == 0) || (hasTableNumber && ((ColumnOrdering) ordering
227: .elementAt(0)).hasTable(tableNumber)))
228: && (hasTableNumber && !columnsAlwaysOrdered
229: .hasAnyOtherTable(tableNumber))) {
230: if (optimizable.hasTableNumber())
231: removeOptimizable(optimizable.getTableNumber());
232:
233: alwaysOrderedOptimizables.addElement(optimizable);
234: }
235: }
236:
237: /** @see RowOrdering#columnAlwaysOrdered */
238: public void columnAlwaysOrdered(Optimizable optimizable,
239: int columnNumber) {
240: columnsAlwaysOrdered.addColumn(optimizable.getTableNumber(),
241: columnNumber);
242: }
243:
244: /** @see RowOrdering#alwaysOrdered */
245: public boolean alwaysOrdered(int tableNumber) {
246: return vectorContainsOptimizable(tableNumber,
247: alwaysOrderedOptimizables);
248: }
249:
250: /** @see RowOrdering#removeOptimizable */
251: public void removeOptimizable(int tableNumber) {
252: int i;
253:
254: /*
255: ** Walk the list backwards, so we can remove elements
256: ** by position.
257: */
258: for (i = ordering.size() - 1; i >= 0; i--) {
259: /*
260: ** First, remove the table from all the ColumnOrderings
261: */
262: ColumnOrdering ord = (ColumnOrdering) ordering.elementAt(i);
263: ord.removeColumns(tableNumber);
264: if (ord.empty())
265: ordering.removeElementAt(i);
266: }
267:
268: /* Remove from list of always-ordered columns */
269: columnsAlwaysOrdered.removeColumns(tableNumber);
270:
271: /* Also remove from list of unordered optimizables */
272: removeOptimizableFromVector(tableNumber, unorderedOptimizables);
273:
274: /* Also remove from list of always ordered optimizables */
275: removeOptimizableFromVector(tableNumber,
276: alwaysOrderedOptimizables);
277: }
278:
279: /**
280: * Remove all optimizables with the given table number from the
281: * given vector of optimizables.
282: */
283: private void removeOptimizableFromVector(int tableNumber, Vector vec) {
284: int i;
285:
286: for (i = vec.size() - 1; i >= 0; i--) {
287: Optimizable optTable = (Optimizable) vec.elementAt(i);
288:
289: if (optTable.hasTableNumber()) {
290: if (optTable.getTableNumber() == tableNumber) {
291: vec.removeElementAt(i);
292: }
293: }
294: }
295: }
296:
297: /** @see RowOrdering#addUnorderedOptimizable */
298: public void addUnorderedOptimizable(Optimizable optimizable) {
299: unorderedOptimizables.addElement(optimizable);
300: }
301:
302: /** @see RowOrdering#copy */
303: public void copy(RowOrdering copyTo) {
304: if (SanityManager.DEBUG) {
305: if (!(copyTo instanceof RowOrderingImpl)) {
306: SanityManager
307: .THROWASSERT("copyTo should be a RowOrderingImpl, is a "
308: + copyTo.getClass().getName());
309: }
310: }
311:
312: RowOrderingImpl dest = (RowOrderingImpl) copyTo;
313:
314: /* Clear the ordering of what we're copying to */
315: dest.ordering.removeAllElements();
316: dest.currentColumnOrdering = null;
317:
318: dest.unorderedOptimizables.removeAllElements();
319: for (int i = 0; i < unorderedOptimizables.size(); i++) {
320: dest.unorderedOptimizables.addElement(unorderedOptimizables
321: .elementAt(i));
322: }
323:
324: dest.alwaysOrderedOptimizables.removeAllElements();
325: for (int i = 0; i < alwaysOrderedOptimizables.size(); i++) {
326: dest.alwaysOrderedOptimizables
327: .addElement(alwaysOrderedOptimizables.elementAt(i));
328: }
329:
330: for (int i = 0; i < ordering.size(); i++) {
331: ColumnOrdering co = (ColumnOrdering) ordering.elementAt(i);
332:
333: dest.ordering.addElement(co.cloneMe());
334:
335: if (co == currentColumnOrdering)
336: dest.rememberCurrentColumnOrdering(i);
337: }
338:
339: dest.columnsAlwaysOrdered = null;
340: if (columnsAlwaysOrdered != null)
341: dest.columnsAlwaysOrdered = columnsAlwaysOrdered.cloneMe();
342: }
343:
344: private void rememberCurrentColumnOrdering(int posn) {
345: currentColumnOrdering = (ColumnOrdering) ordering
346: .elementAt(posn);
347: }
348:
349: public String toString() {
350: String retval = null;
351:
352: if (SanityManager.DEBUG) {
353: int i;
354:
355: retval = "Unordered optimizables: ";
356:
357: for (i = 0; i < unorderedOptimizables.size(); i++) {
358: Optimizable opt = (Optimizable) unorderedOptimizables
359: .elementAt(i);
360: if (opt.getBaseTableName() != null) {
361: retval += opt.getBaseTableName();
362: } else {
363: retval += unorderedOptimizables.elementAt(i)
364: .toString();
365: }
366: retval += " ";
367: }
368: retval += "\n";
369:
370: retval += "\nAlways ordered optimizables: ";
371:
372: for (i = 0; i < alwaysOrderedOptimizables.size(); i++) {
373: Optimizable opt = (Optimizable) alwaysOrderedOptimizables
374: .elementAt(i);
375: if (opt.getBaseTableName() != null) {
376: retval += opt.getBaseTableName();
377: } else {
378: retval += alwaysOrderedOptimizables.elementAt(i)
379: .toString();
380: }
381: retval += " ";
382: }
383: retval += "\n";
384:
385: for (i = 0; i < ordering.size(); i++) {
386: retval += " ColumnOrdering " + i + ": "
387: + ordering.elementAt(i);
388: }
389: }
390:
391: return retval;
392: }
393:
394: /**
395: * Returns true if there are unordered optimizables in the join order
396: * other than the given one.
397: */
398: private boolean unorderedOptimizablesOtherThan(
399: Optimizable optimizable) {
400: for (int i = 0; i < unorderedOptimizables.size(); i++) {
401: Optimizable this Opt = (Optimizable) unorderedOptimizables
402: .elementAt(i);
403:
404: if (this Opt != optimizable)
405: return true;
406: }
407:
408: return false;
409: }
410: }
|