001: /*
002: * $Id: AxionQueryOptimizer.java,v 1.20 2005/12/22 09:02:29 ahimanikya Exp $
003: * =======================================================================
004: * Copyright (c) 2004-2005 Axion Development Team. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * 1. Redistributions of source code must retain the above
011: * copyright notice, this list of conditions and the following
012: * disclaimer.
013: *
014: * 2. Redistributions in binary form must reproduce the above copyright
015: * notice, this list of conditions and the following disclaimer in
016: * the documentation and/or other materials provided with the
017: * distribution.
018: *
019: * 3. The names "Tigris", "Axion", nor the names of its contributors may
020: * not be used to endorse or promote products derived from this
021: * software without specific prior written permission.
022: *
023: * 4. Products derived from this software may not be called "Axion", nor
024: * may "Tigris" or "Axion" appear in their names without specific prior
025: * written permission.
026: *
027: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
028: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
029: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
030: * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
031: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
032: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
033: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
034: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
035: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
036: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
037: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
038: * =======================================================================
039: */
040: package org.axiondb.engine.commands;
041:
042: import java.util.Iterator;
043: import java.util.LinkedHashSet;
044: import java.util.Set;
045:
046: import org.axiondb.AxionException;
047: import org.axiondb.ColumnIdentifier;
048: import org.axiondb.FromNode;
049: import org.axiondb.Function;
050: import org.axiondb.FunctionFactory;
051: import org.axiondb.Selectable;
052: import org.axiondb.Table;
053: import org.axiondb.TableIdentifier;
054: import org.axiondb.engine.visitors.FlattenWhereNodeVisitor;
055: import org.axiondb.engine.visitors.ReferencesOtherTablesWhereNodeVisitor;
056: import org.axiondb.functions.AndFunction;
057: import org.axiondb.functions.ComparisonFunction;
058: import org.axiondb.functions.EqualFunction;
059: import org.axiondb.functions.IsNotNullFunction;
060: import org.axiondb.functions.IsNullFunction;
061:
062: /**
063: * Axion Query Optimizer
064: *
065: * @author Rodney Waldhoff
066: * @author Chuck Burdick
067: * @author Ahimanikya Satapathy
068: * @author Ritesh Adval
069: */
070: public class AxionQueryOptimizer {
071:
072: // TODO: Removal of unnecessary parentheses in WHERE Node:
073: // given: ((a AND b) AND c OR (((a AND b) AND (c AND d))))
074: // production: (a AND b AND c) OR (a AND b AND c AND d)
075:
076: // TODO: Constant folding in WHERE Node:
077: // given: (a<b AND b=c) AND a=5
078: // production: b>5 AND b=c AND a=5
079:
080: // TODO: Constant condition removal (needed because of constant folding):
081: // given: (B>=5 AND B=5) OR (B=6 AND 5=5) OR (B=7 AND 5=6)
082: // production: B=5 OR B=6
083:
084: // TODO: Apply Demorgan's law to simply the expression/where node tree.
085:
086: // TODO : Implement normalize() that will flip the comparison functions, if required.
087: /**
088: * Compose back the decomposed condition into a single condition tree.
089: *
090: * @param conditions decomposed condition set
091: * @return Single condition tree composed with AndFunction
092: */
093: public static Selectable createOneRootFunction(Set conditions) {
094: if (conditions == null || conditions.size() == 0) {
095: return null;
096: } else if (conditions.size() == 1) {
097: return (Selectable) conditions.iterator().next();
098: } else {
099: // "AND"ing all condition nodes to create one root "AND" function
100: AndFunction previousAnd = new AndFunction();
101: for (Iterator iter = conditions.iterator(); iter.hasNext();) {
102: Selectable function = (Selectable) iter.next();
103: if (previousAnd.getArgumentCount() != 2) {
104: previousAnd.addArgument(function);
105: } else {
106: AndFunction andFunction = new AndFunction();
107: andFunction.addArgument(previousAnd);
108: andFunction.addArgument(function);
109: previousAnd = andFunction;
110: }
111: }
112: return previousAnd;
113: }
114: }
115:
116: /**
117: * Decomose a where/join condition into three part: (1) column-column comparision
118: * function (2) column-literal conditions. column-literal conditions can be applied
119: * earlier at table level than at join level. (3) and all remaining conditions: any
120: * other function, these will be applied after join.
121: *
122: * @param flattenConditionSet Flatten Condition Set, created from the where/join
123: * condition, or combined where and join condition set
124: * @return Array of Set 0: column-column set, 1: column-literal set, 2: other
125: */
126: public static Set[] decomposeWhereConditionNodes(
127: Set flattenConditionSet, boolean isAllInnerJoin) {
128: Set columnColumnConditons = new LinkedHashSet();
129: Set columnLiteralConditions = new LinkedHashSet();
130: Set remaingConditionNodes = new LinkedHashSet();
131:
132: for (Iterator it = flattenConditionSet.iterator(); it.hasNext();) {
133: Object condition = it.next();
134: if (condition instanceof ComparisonFunction) {
135: ComparisonFunction fn = (ComparisonFunction) condition;
136: if (fn.isColumnColumn()) {
137: columnColumnConditons.add(fn);
138: } else if (fn.isColumnLiteral()) {
139: columnLiteralConditions.add(fn);
140: } else {
141: remaingConditionNodes.add(fn);
142: }
143: } else if (isAllInnerJoin
144: && (condition instanceof IsNotNullFunction || condition instanceof IsNullFunction)) {
145: columnLiteralConditions.add(condition);
146: } else {
147: remaingConditionNodes.add(condition);
148: }
149: }
150: return new Set[] { columnColumnConditons,
151: columnLiteralConditions, remaingConditionNodes };
152: }
153:
154: public static boolean hasTableReference(ComparisonFunction fn,
155: TableIdentifier tid) {
156: return getColumnRefersTable(fn, tid) != null;
157: }
158:
159: public static Selectable getColumnRefersTable(
160: ComparisonFunction fn, TableIdentifier tid) {
161: Selectable searchColumn = null;
162: Selectable leftColumn = fn.getArgument(0);
163: Selectable rightColumn = fn.getArgument(1);
164:
165: if (hasColumnForTable(leftColumn, tid)) {
166: searchColumn = leftColumn;
167: } else if (hasColumnForTable(rightColumn, tid)) {
168: searchColumn = rightColumn;
169: }
170: return searchColumn;
171: }
172:
173: private static boolean hasColumnForTable(Selectable column,
174: TableIdentifier tid) {
175: if (column instanceof ColumnIdentifier) {
176: ColumnIdentifier col = (ColumnIdentifier) column;
177: if (tid.equals(col.getTableIdentifier())) {
178: return true;
179: }
180: }
181: return false;
182: }
183:
184: /**
185: * Decomposes the given {@link WhereNode}into a {@link Set}of nodes that were
186: * originally joined by ANDs, and adds to this set predicates that are implied by the
187: * original tree (for example, given <tt>A = 1</tt> and <tt>A = B</tt>, we can
188: * infer <tt>B = 1</tt>.)
189: *
190: * @param flattenConditions
191: * @return derived condition set
192: * @throws AxionException
193: */
194: public static Set deriveTableFilter(Set flattenConditions,
195: boolean isAllInnerJoin) throws AxionException {
196: Set[] splitConditions = decomposeWhereConditionNodes(
197: flattenConditions, isAllInnerJoin);
198: Set columnColumns = splitConditions[0];
199: Set columnLiterals = splitConditions[1];
200:
201: for (Iterator iter = columnColumns.iterator(); iter.hasNext();) {
202: Function columnColumn = (Function) (iter.next());
203: if (columnColumn instanceof EqualFunction) {
204: for (Iterator aiter = columnLiterals.iterator(); aiter
205: .hasNext();) {
206: Function columnLiteral = (Function) (aiter.next());
207: FunctionFactory fnFactory = (FunctionFactory) columnLiteral;
208: Function derivedFunction = fnFactory
209: .makeNewInstance();
210: addDerivedFunction(flattenConditions, columnColumn,
211: columnLiteral, derivedFunction);
212: }
213: }
214: }
215: return flattenConditions;
216: }
217:
218: /**
219: * Find column-literal comparision function for a given table. This function then can
220: * be applied first to restrict the number of rows returned by an iterator. We do this
221: * at the index level also. Give preference to EqualFunction
222: *
223: * @param tid TableIdentifier
224: * @param conditions decomposed condition set
225: * @return column-literal function if found, null if not found
226: */
227: public static Function findColumnLiteralFunction(
228: TableIdentifier tid, Table table, Set conditions,
229: boolean mustCheckForIndex) {
230: Function result = null;
231: for (Iterator it = conditions.iterator(); it.hasNext();) {
232: Selectable condition = (Selectable) it.next();
233: Function fn = isColumnIndexed(tid, table, condition,
234: mustCheckForIndex);
235: if (fn != null) {
236: if (fn instanceof EqualFunction) {
237: return fn;
238: }
239: if (result == null) {
240: result = fn;
241: }
242: }
243: }
244: return result;
245: }
246:
247: public static Function findColumnLiteralEqualFunction(
248: TableIdentifier tid, Table table, Set conditions,
249: boolean mustCheckForIndex) {
250: Function result = null;
251: for (Iterator it = conditions.iterator(); it.hasNext();) {
252: Selectable condition = (Selectable) it.next();
253: Function fn = isColumnIndexed(tid, table, condition,
254: mustCheckForIndex);
255: if (fn != null && fn instanceof EqualFunction) {
256: return fn;
257: }
258: }
259: return result;
260: }
261:
262: public static Function isColumnIndexed(TableIdentifier tid,
263: Table table, Selectable condition, boolean mustCheckForIndex) {
264: if (condition instanceof ComparisonFunction) {
265: ComparisonFunction fn = (ComparisonFunction) condition;
266: if (fn.isColumnLiteral() && onlyReferencesTable(tid, fn)) {
267: Selectable searchColumn = getColumnRefersTable(fn, tid);
268: if (isColumnIndexed(mustCheckForIndex, table,
269: searchColumn)) {
270: return fn;
271: }
272: }
273: } else if (condition instanceof IsNotNullFunction
274: || condition instanceof IsNullFunction) {
275: Function fn = (Function) condition;
276: if (onlyReferencesTable(tid, fn)) {
277: Selectable searchColumn = fn.getArgument(0);
278: if (isColumnIndexed(mustCheckForIndex, table,
279: searchColumn)) {
280: return fn;
281: }
282: }
283: }
284: return null;
285: }
286:
287: private static boolean isColumnIndexed(boolean mustCheckForIndex,
288: Table table, Selectable searchColumn) {
289: if (mustCheckForIndex) { // if one column is indexed
290: if (searchColumn != null
291: && table.isColumnIndexed(table
292: .getColumn(searchColumn.getName()))) {
293: return true;
294: }
295: }
296: return !mustCheckForIndex;
297: }
298:
299: // If we have a column-column equal function for the given table, then give prefernce
300: // to that as that will be best fit for the join condition.
301: public static ComparisonFunction findFirstColumnColumnComparisonFunction(
302: Set columnColumnConditions, TableIdentifier tid,
303: Table table, boolean mustCheckForIndex)
304: throws AxionException {
305:
306: ComparisonFunction result = null;
307: for (Iterator iter = columnColumnConditions.iterator(); iter
308: .hasNext();) {
309: Object condition = iter.next();
310: if (condition instanceof ComparisonFunction) {
311: ComparisonFunction fn = (ComparisonFunction) condition;
312: if (isColumnColumnComparisonFunction(fn,
313: columnColumnConditions, tid, table,
314: mustCheckForIndex)) {
315: if (fn instanceof EqualFunction) {
316: return fn;
317: } else if (result == null) {
318: result = fn;
319: }
320: }
321: }
322: }
323: return result;
324: }
325:
326: public static EqualFunction findFirstEqualFunction(
327: Set columnColumnConditions, TableIdentifier tid,
328: Table table, boolean mustCheckForIndex)
329: throws AxionException {
330:
331: for (Iterator iter = columnColumnConditions.iterator(); iter
332: .hasNext();) {
333: Object condition = iter.next();
334: if (condition instanceof EqualFunction) {
335: EqualFunction fn = (EqualFunction) condition;
336: if (isColumnColumnComparisonFunction(fn,
337: columnColumnConditions, tid, table,
338: mustCheckForIndex)) {
339: return fn;
340: }
341: }
342: }
343: return null;
344: }
345:
346: /**
347: * Flatten the given condition tree into an ANDed set
348: *
349: * @param conditionTree condition tree
350: * @return flat set of functions which are anded together
351: */
352: public static Set flatConditionTree(Selectable conditionTree) {
353: if (null == conditionTree) {
354: return new LinkedHashSet(1);
355: }
356: return new FlattenWhereNodeVisitor().getNodes(conditionTree);
357: }
358:
359: /**
360: * Check if the given table is the only table refernce in the condition
361: *
362: * @param table TableIdentifier
363: * @param conditionNode
364: * @return true if match, otherwise false.
365: */
366: public static boolean onlyReferencesTable(TableIdentifier table,
367: Selectable conditionNode) {
368: ReferencesOtherTablesWhereNodeVisitor v = new ReferencesOtherTablesWhereNodeVisitor(
369: table);
370: v.visit(conditionNode);
371: return v.getResult();
372: }
373:
374: private static void addDerivedFunction(Set flattenConditions,
375: Function columnColumn, Function columnLiteral,
376: Function derivedFunction) {
377: if (columnLiteral.getArgumentCount() == 2) {
378: if (columnColumn.getArgument(0).equals(
379: columnLiteral.getArgument(0))) {
380: derivedFunction
381: .addArgument(columnColumn.getArgument(1));
382: derivedFunction.addArgument(columnLiteral
383: .getArgument(1));
384: } else if (columnColumn.getArgument(0).equals(
385: columnLiteral.getArgument(1))) {
386: derivedFunction.addArgument(columnLiteral
387: .getArgument(0));
388: derivedFunction
389: .addArgument(columnColumn.getArgument(1));
390: } else if (columnColumn.getArgument(1).equals(
391: columnLiteral.getArgument(0))) {
392: derivedFunction
393: .addArgument(columnColumn.getArgument(0));
394: derivedFunction.addArgument(columnLiteral
395: .getArgument(1));
396: } else if (columnColumn.getArgument(1).equals(
397: columnLiteral.getArgument(1))) {
398: derivedFunction.addArgument(columnLiteral
399: .getArgument(0));
400: derivedFunction
401: .addArgument(columnColumn.getArgument(0));
402: }
403: } else {
404: if (columnColumn.getArgument(0).equals(
405: columnLiteral.getArgument(0))) {
406: derivedFunction
407: .addArgument(columnColumn.getArgument(1));
408: } else if (columnColumn.getArgument(1).equals(
409: columnLiteral.getArgument(0))) {
410: derivedFunction
411: .addArgument(columnColumn.getArgument(0));
412: }
413: }
414:
415: if (derivedFunction.getArgumentCount() > 0) {
416: flattenConditions.add(derivedFunction);
417: }
418: }
419:
420: private static boolean isColumnColumnComparisonFunction(
421: ComparisonFunction fn, Set columnColumnConditions,
422: TableIdentifier tid, Table table, boolean mustCheckForIndex) {
423:
424: if (fn.isColumnColumn()) {
425: if (mustCheckForIndex) { // if one column is indexed
426: Selectable searchColumn = getColumnRefersTable(fn, tid);
427: if (searchColumn != null
428: && table.isColumnIndexed(table
429: .getColumn(searchColumn.getName()))) {
430: return true;
431: }
432: } else if (hasTableReference(fn, tid)) {
433: return true;
434: }
435: }
436: return false;
437: }
438:
439: public static boolean isAllInnerJoin(Object node) {
440: FromNode from = (FromNode) node;
441: if (from.isInnerJoin()) {
442: if (from.getRight() instanceof FromNode
443: && !isAllInnerJoin(from.getRight())) {
444: return false;
445: }
446:
447: if (from.getLeft() instanceof FromNode
448: && !isAllInnerJoin(from.getLeft())) {
449: return false;
450: }
451: return true;
452: }
453: return false;
454: }
455:
456: }
|