0001: /*
0002: * $Id: AxionQueryPlanner.java,v 1.61 2006/01/10 21:02:37 ahimanikya Exp $
0003: * =======================================================================
0004: * Copyright (c) 2002-2005 Axion Development Team. All rights reserved.
0005: *
0006: * Redistribution and use in source and binary forms, with or without
0007: * modification, are permitted provided that the following conditions
0008: * are met:
0009: *
0010: * 1. Redistributions of source code must retain the above
0011: * copyright notice, this list of conditions and the following
0012: * disclaimer.
0013: *
0014: * 2. Redistributions in binary form must reproduce the above copyright
0015: * notice, this list of conditions and the following disclaimer in
0016: * the documentation and/or other materials provided with the
0017: * distribution.
0018: *
0019: * 3. The names "Tigris", "Axion", nor the names of its contributors may
0020: * not be used to endorse or promote products derived from this
0021: * software without specific prior written permission.
0022: *
0023: * 4. Products derived from this software may not be called "Axion", nor
0024: * may "Tigris" or "Axion" appear in their names without specific prior
0025: * written permission.
0026: *
0027: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
0028: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
0029: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
0030: * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
0031: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
0032: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
0033: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
0034: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
0035: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0036: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
0037: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0038: * =======================================================================
0039: */
0040:
0041: package org.axiondb.engine.commands;
0042:
0043: import java.util.ArrayList;
0044: import java.util.Arrays;
0045: import java.util.Collections;
0046: import java.util.HashMap;
0047: import java.util.Iterator;
0048: import java.util.LinkedHashSet;
0049: import java.util.List;
0050: import java.util.Map;
0051: import java.util.Set;
0052:
0053: import org.axiondb.AxionException;
0054: import org.axiondb.Column;
0055: import org.axiondb.ColumnIdentifier;
0056: import org.axiondb.Database;
0057: import org.axiondb.FromNode;
0058: import org.axiondb.Function;
0059: import org.axiondb.Index;
0060: import org.axiondb.Literal;
0061: import org.axiondb.OrderNode;
0062: import org.axiondb.Row;
0063: import org.axiondb.RowDecorator;
0064: import org.axiondb.RowIterator;
0065: import org.axiondb.Selectable;
0066: import org.axiondb.Table;
0067: import org.axiondb.TableIdentifier;
0068: import org.axiondb.engine.TransactableTableImpl;
0069: import org.axiondb.engine.rowiterators.ChangingIndexedRowIterator;
0070: import org.axiondb.engine.rowiterators.DistinctRowIterator;
0071: import org.axiondb.engine.rowiterators.FilteringChangingIndexedRowIterator;
0072: import org.axiondb.engine.rowiterators.FilteringRowIterator;
0073: import org.axiondb.engine.rowiterators.GroupedRowIterator;
0074: import org.axiondb.engine.rowiterators.IndexNestedLoopJoinedRowIterator;
0075: import org.axiondb.engine.rowiterators.LimitingRowIterator;
0076: import org.axiondb.engine.rowiterators.ListRowIterator;
0077: import org.axiondb.engine.rowiterators.MutableIndexedRowIterator;
0078: import org.axiondb.engine.rowiterators.NestedLoopJoinedRowIterator;
0079: import org.axiondb.engine.rowiterators.ReverseSortedRowIterator;
0080: import org.axiondb.engine.rowiterators.SingleRowIterator;
0081: import org.axiondb.engine.rowiterators.SortedRowIterator;
0082: import org.axiondb.engine.rows.SimpleRow;
0083: import org.axiondb.engine.tables.ExternalDatabaseTable;
0084: import org.axiondb.engine.tables.TableView;
0085: import org.axiondb.functions.ComparisonFunction;
0086: import org.axiondb.functions.EqualFunction;
0087: import org.axiondb.util.ValuePool;
0088:
0089: /**
0090: * Query Planner used in select and sub-select Query. I use Rule-based analysis and
0091: * decision-making – rules expressing proven, efficient statement execution methods
0092: * determine how operations and their attributes are built and combined.
0093: * <p>
0094: * One of the important components is the Query Optimizer. Its goal, for every SQL
0095: * statement, is to answer this question: What is the quickest way to execute the
0096: * statement, to produce exactly the data requested by the statement in the shortest
0097: * possible time?
0098: * <p>
0099: * The query processor makes extensive use of a relational algebra tree representation to
0100: * model and manipulate SQL queries. These trees can be thought of as a series of pipes,
0101: * valves, and other components through which data flows, entering through the bottom from
0102: * one or more tables, and leaving through the top as a result set. At various points
0103: * within the tree, the data are operated on as needed to produce the desired result. Each
0104: * operation is represented as a node in the tree. Nodes may have one or more expressions
0105: * associated with them to specify columns, conditions, and calculations associated with
0106: * the operation. In Axion in most cases these trees are represented as RowIterators.
0107: * <p>
0108: * Some of the operators that may be present in the tree are:
0109: * <li>Restrict – reduces the number of output rows by eliminating those that fail to
0110: * satisfy some condition applied to the input. Restrict operators appear in the tree from
0111: * WHERE clauses and JOINs. example: FilteringRowIterator
0112: * <li>Join – combines two input tables into a single output table that contains some
0113: * combination of rows from the inputs. Joins appear in the tree from the use of FROM
0114: * clauses and from JOIN clauses. example: NestedLoopJoinRowIterator.
0115: * <li>Sort – changes the ordering of rows in an input table to produce an output table
0116: * in the desired order. example: SortedRowIterator
0117: * <li>Table – represents a Table scan or an Index scan, reading data from a given table
0118: * by either its default index (table scan) or a specific index (index scan). Leaf nodes
0119: * of the tree are always references to database tables.
0120: * <p>
0121: * Current Axion SQL parser does not build a formal query tree, instead it builds a
0122: * AxionQueryContext object, which hold the query tree, that includes selectables, where
0123: * node, from node, oder by and group by node. FromNode is nested and represet a from
0124: * tree, the subqueries are nested in the context object. Then I apply rule bases analysis
0125: * to optimize the query.
0126: * <p>
0127: * The Axion query optimizer divides the optimization process into several phases. Some of
0128: * the phases deal with very significant rule based cost factors and are straightforward
0129: * to understand. Each phase, listed below, addresses a specific type of optimization:
0130: * <p>
0131: * <li>Pushing restrictions as far down the tree as possible
0132: * <li>Derive restrictions
0133: * <li>Using indexes for restrictions
0134: * <li>Join optimization
0135: * <li>Sort optimization
0136: * <li>Using index for NULL Check
0137: * <li>Count Rows Optimization
0138: * <p>
0139: * <b>Pushing Restrict Operations Close to the Data Origin: </b> This optimization stage
0140: * consists of moving restrict operators as far down the query tree as possible. This
0141: * reduces the number of tuples moving up the tree for further processing and minimizes
0142: * the amount of data handled. When restrict operations on a join node cannot be moved
0143: * below the join node, they are set as join conditions. When multiple predicates are
0144: * moved down the tree to the same relative position, they are reassembled into a single
0145: * Restrict operation. Consider the SQL clause:
0146: * <p>
0147: * <code>
0148: * SELECT EMP.NAME FROM EMP, DEPT
0149: * WHERE EMP.SAL > 4000
0150: * AND EMP.SAL <= 6000
0151: * AND EMP.DEPTNO = DEPT.DEPTNO
0152: * </code>
0153: * <p>
0154: * The optimizer apply restrictions <code> EMP.SAL > 4000 </code> and
0155: * <code> EMP.SAL <= 6000 </code> are moved down the tree, below the join node, since they
0156: * apply to a single table. The restriction EMP.DEPTNO = DEPT.DEPTNO, applying to two
0157: * tables, stays in the join node.
0158: * <p>
0159: * <b>Derive restrictions: </b> This optimization stage consists of deriving restrict
0160: * operators based on the current current restriction and join condition. Consider the
0161: * following SQL clause:
0162: * <p>
0163: * <code>
0164: * SELECT EMP.NAME FROM EMP, DEPT
0165: * WHERE EMP.DEPTNO = DEPT.DEPTNO AND EMP.DEPTNO = 10
0166: * </code>
0167: * <p>
0168: * In this stage, the Optimizer can derive <code> DEPT.DEPTNO = 10 </code> and push that
0169: * down the tree, below the join node, since they apply to a single table. The restriction
0170: * EMP.DEPTNO = DEPT.DEPTNO, applying to two tables, stays in the join node.
0171: * <p>
0172: * <b>Using Indexes for Restrictions: </b> This optimization phase consists of recognizing
0173: * those cases where an existing index can be used to evaluate a restriction and
0174: * converting a table scan into an index bracket or set of contiguous index entries. An
0175: * index bracket is extremely effective in limiting the number of rows that must be
0176: * processed. Consider the following SQL clause:
0177: * <p>
0178: * <code>
0179: * SELECT EMP.NAME FROM EMP WHERE EMP.SAL > 6000 AND EMP.DEPTNO = 10
0180: * </code>
0181: * <p>
0182: * Instead of a separate restrict operation, the output tree uses the index EmpIdx on the
0183: * DEPTNO column table EMP to evaluate the restriction DEPTNO = 10.
0184: * <p>
0185: * <b>Choosing the Join Algorithm: </b> Currently Axion support Augmented nested loop
0186: * (ANL) or Index Nested Loop join and Nested loop join.
0187: * <p>
0188: * The <b>Index Nested Loop Join or Augmented Nested Loop Join (ANL) </b> is by far the
0189: * most common join method and is the classic Axion join method. An augmented nested loop
0190: * join is performed by doing a scan over the left subtree and for each row in it,
0191: * performing an index bracket scan on a portion of the right subtree. The right subtree
0192: * is read as many times as there are rows in the left subtree. To be a candidate for an
0193: * ANL join, the subtree pair for a join node must meet the following criteria:
0194: * <p>
0195: * <li>There must be an index(es) defined on the join column(s) for the table in the
0196: * right subtree.
0197: * <li>No other scan on that index has already been set.
0198: * <p>
0199: * When there is an index defined on the left subtree’s table instead of on the right, the
0200: * optimizer swaps the subtrees to make an ANL join possible. When neither subtree’s table
0201: * has an index defined on the join column, the optimizer creats a dynamic index on one of
0202: * the subtree.
0203: * <p>
0204: * A <b>Nested Loop Join </b> is performed by doing a scan over the left subtree and for
0205: * each row in it performing a full scan of the right subtree. This is the default join
0206: * algorithm, which can be used for any join. However, it is usually less efficient than
0207: * the other methods. Usually, either an existing index, or a dynamic index, used in an
0208: * ANL join, will cost much less. Occasionally, when subtree cardinalities are very low
0209: * (possibly because of index bracketing), nested loop will be the method with the least
0210: * cost.
0211: * <p>
0212: * <b>Count Rows Optimization: </b> If we are coutinig the leaf nodes, axion will use
0213: * table row count instead of table scan. If index was used to scan the table, count will
0214: * use the index count. e.g <code>select count(*) from emp</code> will get the row count
0215: * from table emp, instead of making a full table scan, but
0216: * <code>select count(*) from emp where emp.id > 100 </code> require a full table scan
0217: * unless optimizer can take advantage of index, if index is scanned then, index count
0218: * will be used.
0219: * <p>
0220: * <b>Sort Optimization: </b> The optimizer/planner performs two separate optimizations
0221: * designed to avoid sort operations whenever possible: eliminating redundant sorts and
0222: * converting table scans followed by sorts into index bracket scans.
0223: * <p>
0224: * <li><b>Eliminating Redundant Sorts: </b> The optimizer/planner checks whether the
0225: * query tree contains unnecessary sort nodes. For example, when an SQL statement contains
0226: * both a GROUP BY and an ORDER BY clause that refers to the same column, at most one sort
0227: * is needed. A sort node is also redundant when the immediate descendant node of the sort
0228: * node is an index bracket scan on the sort column. That is, the sort is redundant when
0229: * the data input to the sort was read using an index with the needed sort order.
0230: * <p>
0231: * <li><b>Converting Table Scans to Index Bracket Scans: </b> When a leaf node of a
0232: * subtree is a table scan, the optimizer/planner checks whether any indexes that exist on
0233: * the table match the sort column(s). If so, the optimizer converts the table scan to the
0234: * index bracket scan and removes the sort node.
0235: *
0236: * @version $Revision: 1.61 $ $Date: 2006/01/10 21:02:37 $
0237: * @author Morgan Delagrange
0238: * @author Rodney Waldhoff
0239: * @author Chuck Burdick
0240: * @author Amrish Lal
0241: * @author Dave Pekarek Krohn
0242: * @author Rahul Dwivedi
0243: * @author Ahimanikya Satapathy
0244: * @author Ritesh Adval
0245: */
0246: public class AxionQueryPlanner {
0247:
0248: // TODO: Take advantage of Index for MIN/MAX - The first and last values represent MIN
0249: // and MAX values respectively for asending indexes.
0250:
0251: // TODO: Take advantage of Index for LIKE operator.
0252:
0253: // TODO: Reducing Multi-Block queries to Single Block - Folding correlated sub-query
0254: // to outer query where possible or use SemiJoin like technique for optimizing
0255: // Muti-Block queries. See: http://www-db.stanford.edu/~widom/cs346/chaudhuri.pdf
0256:
0257: // TODO: Handle situation where we have mutiple index avaiable for the join condition;
0258: // once we have multi column index this will make sence.
0259:
0260: // TODO: Use Index and Cardinal statistics to estimate cost, we could maintain system
0261: // table for this. Generate multiple join path and based on the cost choose the best
0262: // fit.
0263:
0264: // TODO: Use System-R Join Optimization ?
0265:
0266: public AxionQueryPlanner(AxionQueryContext context) {
0267: _context = context;
0268: }
0269:
0270: public Map getColumnIdToFieldMap() {
0271: return _colIdToFieldMap;
0272: }
0273:
0274: public RowIterator getPlanNodeRowIterator() {
0275: return _planNode.getRowIterator();
0276: }
0277:
0278: /**
0279: * Makes appropriate {@link RowIterator}for the current query/subquery.
0280: *
0281: * @param db the current database.
0282: * @param readOnly when <code>true</code>, the caller does not expect to be able to
0283: * modify (i.e., call {@link RowIterator#set}or {@link RowIterator#remove}on)
0284: * the returned {@link RowIterator}, the returned iterator <i>may </i> be
0285: * unmodifiable.
0286: * @return retunrs the top most RowIterator that may wrap other underlaying
0287: * RowIterator based on the specific query.
0288: */
0289: public RowIterator makeRowIterator(Database db, boolean readOnly)
0290: throws AxionException {
0291: if (db.isReadOnly()) {
0292: readOnly = true;
0293: }
0294:
0295: RowIterator rows = null;
0296: AxionQueryContext context = getContext();
0297: _literals = context.createLiteralList();
0298: _parentRow = context.getParentRow();
0299:
0300: try {
0301: if (context.getTableCount() == 0) { // *** NO from node *** //
0302: rows = processQueryWithNoTable(context);
0303: } else if (context.getTableCount() == 1) { // *** Only one table *** //
0304: rows = processQueryForSingleTable(db, readOnly, context);
0305: } else { // *** Traditional or ANSI Join *** //
0306: rows = processQuery(db, readOnly, context);
0307: }
0308:
0309: rows = makeGroupedRowIterator(db, rows, context,
0310: getColumnIdToFieldMap());
0311: if (context.foundAggregateFunction()) {
0312: resolveSelectedAfterGrouping(context,
0313: getColumnIdToFieldMap());
0314: }
0315:
0316: rows = makeDistinctRowIterator(rows, context);
0317: rows = makeOrderedRowIterator(db, rows,
0318: getColumnIdToFieldMap(), context);
0319: rows = makeLimitingRowIterator(rows, context,
0320: getColumnIdToFieldMap());
0321:
0322: } finally {
0323: dropViewIfSubQuery(context.getFrom(), db);
0324: }
0325: return rows;
0326: }
0327:
0328: private void addExplainRow(RowIterator rows) {
0329: if (_context.isExplain()) {
0330: _planNode.addExplainRow(rows.toString());
0331: }
0332: }
0333:
0334: private Map clearAndGetColumnIdToFieldMap() {
0335: _colIdToFieldMap.clear();
0336: return _colIdToFieldMap;
0337: }
0338:
0339: // Note: Assume index available for the given column of a table so create a new Index
0340: // Caller need to make sure no existing available index for this column
0341: private RowIterator createDynamicIndex(Database db, Table table,
0342: ColumnIdentifier columnId) throws AxionException {
0343: Column column = table.getColumn(columnId.getName());
0344: if (table.getIndexForColumn(column) == null) {
0345: Index index = db.getIndexFactory("default")
0346: .makeNewSystemInstance(table, column,
0347: db.getDBDirectory() == null);
0348: db.addIndex(index, table, true);
0349: if (table instanceof ExternalDatabaseTable) {
0350: // External DB Table's indices are different and are not maintained by Axion.
0351: index = table.getIndexForColumn(column);
0352: }
0353: return new ChangingIndexedRowIterator(index, table,
0354: new EqualFunction());
0355: }
0356: return null;
0357: }
0358:
0359: private void createDynamicIndex(FromNode from,
0360: JoinCondition joinCondition,
0361: QueryPlannerJoinContext joinContext, Database db)
0362: throws AxionException {
0363: // If either left and right are physical tables, then create index with the
0364: // following exception
0365: // Rule1: If right outer join , I will not create index on right table
0366: // Rule2: If left outer join , I will not create index on left table
0367: if (!from.isRightJoin()
0368: && from.getRight() instanceof TableIdentifier
0369: && !joinContext.swapRightToLeft()) {
0370: TableIdentifier rtid = (TableIdentifier) from.getRight();
0371: Table rightTable = db.getTable(rtid);
0372: if (!isTableView(rightTable)) {
0373: createDynamicIndexOnRightTable(from, rtid,
0374: joinCondition, joinContext, db, rightTable);
0375: }
0376: } else if (!from.isLeftJoin()
0377: && from.getLeft() instanceof TableIdentifier) {
0378: TableIdentifier ltid = (TableIdentifier) from.getLeft();
0379: Table leftTable = db.getTable(ltid);
0380: if (!isTableView(leftTable)) {
0381: createDynamicIndexOnLeftTable(from, ltid,
0382: joinCondition, joinContext, db, leftTable);
0383: }
0384: }
0385: }
0386:
0387: private void createDynamicIndexOnLeftTable(FromNode from,
0388: TableIdentifier ltid, JoinCondition joinCondition,
0389: QueryPlannerJoinContext joinContext, Database db,
0390: Table table) throws AxionException {
0391:
0392: EqualFunction fn = AxionQueryOptimizer.findFirstEqualFunction(
0393: joinCondition.getNodes(), ltid, table, false);
0394: if (fn != null && !fn.getArgument(0).equals(fn.getArgument(1))) {
0395: // Assume that left argument of function is from left table
0396: joinContext.setLeftTableKey((ColumnIdentifier) fn
0397: .getArgument(0));
0398: joinContext.setRightTablekey((ColumnIdentifier) fn
0399: .getArgument(1));
0400:
0401: // Left argument of function is not from left table so flip it
0402: if (!ltid.equals(joinContext.getLeftTableKey()
0403: .getTableIdentifier())) {
0404: joinContext.flipKey();
0405: }
0406:
0407: // Now create index
0408: ColumnIdentifier columnId = joinContext.getLeftTableKey();
0409: RowIterator leftIter = createDynamicIndex(db, table,
0410: columnId);
0411: if (leftIter != null) {
0412: addExplainRow(leftIter);
0413: joinContext.setLeftIterator(leftIter);
0414: swapKeyForSortingIfUSedInOrderByOrGroupBy(joinContext
0415: .getLeftTableKey(), joinContext
0416: .getRightTablekey());
0417: joinContext.setRowsAreSortedByJoinKey(true);
0418: joinCondition.getNodes().remove(fn);
0419: pushUnwantedConditions(from, joinCondition, ltid);
0420: }
0421: }
0422: }
0423:
0424: private void createDynamicIndexOnRightTable(FromNode from,
0425: TableIdentifier rtid, JoinCondition joinCondition,
0426: QueryPlannerJoinContext joinContext, Database db,
0427: Table table) throws AxionException {
0428:
0429: EqualFunction fn = AxionQueryOptimizer.findFirstEqualFunction(
0430: joinCondition.getNodes(), rtid, table, false);
0431: if (fn != null && !fn.getArgument(0).equals(fn.getArgument(1))) {
0432: // Assume that right argument of function is from right table
0433: joinContext.setLeftTableKey((ColumnIdentifier) fn
0434: .getArgument(0));
0435: joinContext.setRightTablekey((ColumnIdentifier) fn
0436: .getArgument(1));
0437:
0438: // Right argument of function is not from right table so flip it
0439: if (!rtid.equals(joinContext.getRightTablekey()
0440: .getTableIdentifier())) {
0441: joinContext.flipKey();
0442: }
0443:
0444: // Now create index
0445: ColumnIdentifier columnId = joinContext.getRightTablekey();
0446: RowIterator rightIter = createDynamicIndex(db, table,
0447: columnId);
0448: if (rightIter != null) {
0449: addExplainRow(rightIter);
0450: joinContext.setRightIterator(rightIter);
0451: swapKeyForSortingIfUSedInOrderByOrGroupBy(joinContext
0452: .getRightTablekey(), joinContext
0453: .getLeftTableKey());
0454: joinContext.setRowsAreSortedByJoinKey(true);
0455: joinCondition.getNodes().remove(fn);
0456: pushUnwantedConditions(from, joinCondition, rtid);
0457: }
0458: }
0459: }
0460:
0461: private void dropViewIfSubQuery(FromNode from, Database db)
0462: throws AxionException {
0463: if (from == null) {
0464: return;
0465: }
0466: dropViewIfSubQuery(from.getLeft(), db);
0467: dropViewIfSubQuery(from.getRight(), db);
0468: }
0469:
0470: private void dropViewIfSubQuery(Object child, Database db)
0471: throws AxionException {
0472: if (child instanceof TableIdentifier) {
0473: TableIdentifier tid = (TableIdentifier) child;
0474: Table view = db.getTable(tid);
0475: if (view instanceof TransactableTableImpl) {
0476: view = ((TransactableTableImpl) view).getTable();
0477: }
0478: if (view instanceof TableView) {
0479: if (((TableView) view).getType().equals(
0480: TableView.SUBQUERY)) {
0481: db.dropTable(tid.getTableName());
0482: }
0483: }
0484: } else if (child instanceof FromNode) {
0485: dropViewIfSubQuery((FromNode) child, db);
0486: }
0487: }
0488:
0489: private AxionQueryContext getContext() {
0490: return _context;
0491: }
0492:
0493: private RowIterator getIndexedRows(Set conditions,
0494: ColumnIdentifier cid, Table table, boolean readOnly)
0495: throws AxionException {
0496: RowIterator rows = null;
0497: Function fn = AxionQueryOptimizer.findColumnLiteralFunction(cid
0498: .getTableIdentifier(), table, conditions, true);
0499:
0500: if (fn != null) {
0501: rows = table.getIndexedRows(fn, readOnly);
0502: }
0503: if (rows == null) {
0504: rows = table.getIndexedRows(cid, readOnly);
0505: }
0506: return rows;
0507: }
0508:
0509: private RowIterator getIndexedRowsIfSortingRequired(
0510: RowIterator rows, AxionQueryContext context, Table table,
0511: boolean readOnly, Set conditions) throws AxionException {
0512: // Attempt to get Index based row iterator, if group column is from this table
0513: if (null == rows && context.getGroupByCount() == 1) {
0514: ColumnIdentifier grpCol = (ColumnIdentifier) context
0515: .getGroupBy(0);
0516: rows = getIndexedRows(conditions, grpCol, table, readOnly);
0517: if (rows != null) {
0518: setIndexUsedForGroupBy(true);
0519: addExplainRow(rows);
0520: }
0521: }
0522:
0523: // Attempt to get Index based row iterator, if order column is from this table
0524: if (null == rows && context.getOrderByCount() == 1) {
0525: OrderNode node = context.getOrderBy(0);
0526: Selectable ordCol = node.getSelectable();
0527: if (ordCol instanceof ColumnIdentifier) {
0528: rows = getIndexedRows(conditions,
0529: (ColumnIdentifier) ordCol, table, readOnly);
0530: if (rows != null) {
0531: setSkipSorting(true);
0532: addExplainRow(rows);
0533: }
0534: }
0535: }
0536: return rows;
0537: }
0538:
0539: private RowIterator getRowIteratorFromTable(Database db,
0540: TableIdentifier tid, Table table, RowIterator rows,
0541: boolean readOnly, Set conditions) throws AxionException {
0542: if (rows != null) {
0543: return rows;
0544: }
0545:
0546: Function fn = AxionQueryOptimizer.findColumnLiteralFunction(
0547: tid, table, conditions, true);
0548:
0549: // First try to apply column literal equal function or other comaprision
0550: // function, this is very fast in case of comparison function this will result in
0551: // subset which contains less rows which improves performance
0552: if (fn != null) {
0553: // ...then try to find an index for this node.
0554: rows = table.getIndexedRows(fn, readOnly);
0555: if (rows != null) {
0556: conditions.remove(fn);
0557: addExplainRow(rows);
0558: }
0559: }
0560:
0561: // If we still don't have a RowIterator for this table, then we'll use a full
0562: // table scan.
0563: if (null == rows) {
0564: rows = table.getRowIterator(readOnly);
0565: addExplainRow(rows);
0566: }
0567: return rows;
0568: }
0569:
0570: private boolean wasSortedWhileGrouping(List groupByColumns,
0571: List orderByColumns, boolean isDescending)
0572: throws AxionException {
0573: int groupByCount = groupByColumns.size();
0574: int orderByCount = orderByColumns.size();
0575:
0576: if (groupByCount == 0 || groupByCount < orderByCount) {
0577: return false;
0578: }
0579:
0580: if (wasIndexUsedForGroupBy() && isDescending) {
0581: _doReverseSorting = true;
0582: }
0583:
0584: if (!groupByColumns.equals(orderByColumns)) {
0585: return false;
0586: }
0587: return true;
0588: }
0589:
0590: /**
0591: * Detemines whether we can eliminate sorting by checking whether or not the
0592: * RowIterrator has been already sorted.
0593: * <p>
0594: * If ORDER BY has less or equal number of nodes (say n) as GROUP BY nodes (say m)
0595: * then, then we eliminate sorting if they order node(n) matches first n nodes of
0596: * group by nodes. If one or more ORDER BY nodes order is desending then, we can
0597: * eliminate sorting only if GroupedRowIterator did not use index based row iterators.
0598: */
0599: private boolean isSortingRequired(AxionQueryContext context)
0600: throws AxionException {
0601: int orderByCount = context.getOrderByCount();
0602: int groupByCount = context.getGroupByCount();
0603:
0604: if (orderByCount == 0) {
0605: _doReverseSorting = false;
0606: return false;
0607: }
0608:
0609: List orderByColumns = new ArrayList();
0610: boolean isDescending = true;
0611: for (int i = 0; i < orderByCount; i++) {
0612: OrderNode node = context.getOrderBy(i);
0613: isDescending = (node.isDescending() && isDescending) ? true
0614: : false;
0615: orderByColumns.add(node.getSelectable());
0616: }
0617:
0618: if (skipSorting() && isDescending) {
0619: _doReverseSorting = true;
0620: }
0621:
0622: List groupByColumns = Collections.EMPTY_LIST;
0623: if (groupByCount > orderByCount) {
0624: groupByColumns = new ArrayList(context.getGroupBy()
0625: .subList(0, context.getOrderByCount()));
0626: } else if (groupByCount > 0) {
0627: groupByColumns = context.getGroupBy();
0628: }
0629:
0630: if (skipSorting()
0631: || wasSortedWhileGrouping(groupByColumns,
0632: orderByColumns, isDescending)) {
0633: return false;
0634: }
0635:
0636: return true;
0637: }
0638:
0639: private boolean isTableView(Table table) {
0640: if (table instanceof TransactableTableImpl) {
0641: table = ((TransactableTableImpl) table).getTable();
0642: }
0643:
0644: if (table instanceof TableView) {
0645: return true;
0646: }
0647: return false;
0648: }
0649:
0650: private RowIterator makeChangingIndexedRowIterator(Table table,
0651: Index index) throws AxionException {
0652: RowIterator iter = new ChangingIndexedRowIterator(index, table,
0653: new EqualFunction());
0654: addExplainRow(iter);
0655: return iter;
0656: }
0657:
0658: private RowIterator makeDistinctRowIterator(RowIterator rows,
0659: AxionQueryContext context) {
0660: // Apply distinct, if needed
0661: if (context.getDistinct()) {
0662: rows = new DistinctRowIterator(rows,
0663: getColumnIdToFieldMap(), context.getSelected());
0664: addExplainRow(rows);
0665: }
0666: return rows;
0667: }
0668:
0669: private RowIterator makeFilteringRowIterator(TableIdentifier tid,
0670: Table table, RowIterator rows, AxionQueryContext context,
0671: Set conditions) throws AxionException {
0672: // Apply any unapplied whereNodesForTable.
0673: Iterator tableFilterIt = conditions.iterator();
0674: while (tableFilterIt.hasNext()) {
0675: Map localmap = new HashMap();
0676: List columns = new ArrayList();
0677: populateColumnList(columns, tid, table, context);
0678: populateColumnIdToFieldMap(columns, localmap);
0679: Selectable node = (Selectable) (tableFilterIt.next());
0680: // If the node only references this table...
0681: if (AxionQueryOptimizer.onlyReferencesTable(tid, node)) {
0682: if (rows instanceof MutableIndexedRowIterator) {
0683: rows = new FilteringChangingIndexedRowIterator(
0684: (MutableIndexedRowIterator) rows,
0685: new RowDecorator(localmap), node);
0686: } else {
0687: rows = new FilteringRowIterator(rows,
0688: new RowDecorator(localmap), node);
0689: }
0690: tableFilterIt.remove();
0691: addExplainRow(rows);
0692: }
0693: }
0694: return (rows);
0695: }
0696:
0697: // Take advantage of index in group by if group by used on a single column and single
0698: // table.
0699: private RowIterator makeGroupedIndexBasedRowIterator(
0700: boolean readOnly, AxionQueryContext context, Table table)
0701: throws AxionException {
0702: ColumnIdentifier cid = (ColumnIdentifier) context.getGroupBy(0);
0703: RowIterator rows = table.getIndexedRows(cid, readOnly);
0704: if (rows != null) {
0705: setIndexUsedForGroupBy(true);
0706: addExplainRow(rows);
0707: rows = new GroupedRowIterator(false, rows,
0708: getColumnIdToFieldMap(), context.getGroupBy(),
0709: context.getSelect(), context.getHaving(), context
0710: .getWhere(), context.getOrderBy());
0711: addExplainRow(rows);
0712: }
0713: return rows;
0714: }
0715:
0716: // If we have any join and single column is used for group by then, we check if the
0717: // Index based Joined RowIterator key of the table is matching with group by column,
0718: // and has been scanned using index on the group by column.
0719: private RowIterator makeGroupedRowIterator(Database db,
0720: RowIterator rows, AxionQueryContext context,
0721: Map colIdToFieldMap) throws AxionException {
0722: // Apply group by if any
0723: RowIterator grpRows = null;
0724: if (context.foundAggregateFunction()) {
0725: // Check if the rows has been already sorted for the group by column
0726: if (wasIndexUsedForGroupBy()) {
0727: grpRows = new GroupedRowIterator(false, rows,
0728: colIdToFieldMap, context.getGroupBy(), context
0729: .getSelect(), context.getHaving(),
0730: null, context.getOrderBy());
0731: addExplainRow(grpRows);
0732: return grpRows;
0733: } else {
0734: grpRows = new GroupedRowIterator(rows, colIdToFieldMap,
0735: context.getGroupBy(), context.getSelect(),
0736: context.getHaving(), context.getOrderBy());
0737: addExplainRow(grpRows);
0738: return grpRows;
0739: }
0740: }
0741: return rows;
0742: }
0743:
0744: private void makeIndexNestedLoopJoinedRowIterator(FromNode from,
0745: JoinCondition joinCondition,
0746: QueryPlannerJoinContext joinContext) throws AxionException {
0747: IndexNestedLoopJoinedRowIterator joinedRowIterator = null;
0748: if (joinContext.getRightIterator() instanceof MutableIndexedRowIterator
0749: && !from.isRightJoin()
0750: && !joinContext.swapRightToLeft()) {
0751: joinedRowIterator = new IndexNestedLoopJoinedRowIterator(
0752: joinContext.getLeftIterator(), joinContext
0753: .getLeftColumnPosition(),
0754: (MutableIndexedRowIterator) (joinContext
0755: .getRightIterator()), joinContext
0756: .getRightColumnCount(),
0757: !from.isInnerJoin(), from.isRightJoin());
0758: } else if (joinContext.getLeftIterator() instanceof MutableIndexedRowIterator
0759: && !from.isLeftJoin()) {
0760: joinedRowIterator = new IndexNestedLoopJoinedRowIterator(
0761: joinContext.getRightIterator(), joinContext
0762: .getRightColumnPosition(),
0763: (MutableIndexedRowIterator) (joinContext
0764: .getLeftIterator()), joinContext
0765: .getLeftColumnCount(), !from.isInnerJoin(),
0766: true);
0767: }
0768:
0769: if (joinedRowIterator != null) {
0770: if (!joinCondition.isEmpty()) {
0771: joinedRowIterator.setJoinCondition(joinCondition
0772: .stitchAll(), new RowDecorator(joinContext
0773: .getColumnIdToFieldMap()));
0774: _unappliedWhereNodes
0775: .removeAll(joinCondition.getNodes());
0776: }
0777: joinContext.setRowIterator(joinedRowIterator);
0778: addExplainRow(joinedRowIterator);
0779: }
0780: }
0781:
0782: private void makeLeftChangingIndexedRowIterator(FromNode from,
0783: JoinCondition joinCondition, Database db,
0784: QueryPlannerJoinContext joinContext) throws AxionException {
0785:
0786: if (joinContext.getRightIterator() == null
0787: && from.getLeft() instanceof TableIdentifier) {
0788: TableIdentifier ltid = (TableIdentifier) from.getLeft();
0789: Table table = db.getTable(ltid);
0790: ComparisonFunction fn = AxionQueryOptimizer
0791: .findFirstColumnColumnComparisonFunction(
0792: joinCondition.getNodes(), ltid, table, true);
0793: if (fn != null
0794: && !fn.getArgument(0).equals(fn.getArgument(1))) {
0795: // Assume that left argument of function is from left table
0796: joinContext.setLeftTableKey((ColumnIdentifier) fn
0797: .getArgument(0));
0798: joinContext.setRightTablekey((ColumnIdentifier) fn
0799: .getArgument(1));
0800:
0801: // If left argument of function is not from left table then flip it
0802: if (!ltid.equals(joinContext.getLeftTableKey()
0803: .getTableIdentifier())) {
0804: joinContext.flipKey();
0805: }
0806:
0807: // Check if we can use index
0808: if (joinContext.getLeftTableKey() != null
0809: && !from.isLeftJoin()) {
0810: Index index = table.getIndexForColumn(table
0811: .getColumn(joinContext.getLeftTableKey()
0812: .getName()));
0813: joinContext
0814: .setLeftIterator(makeChangingIndexedRowIterator(
0815: table, index));
0816:
0817: if (fn instanceof EqualFunction) {
0818: swapKeyForSortingIfUSedInOrderByOrGroupBy(
0819: joinContext.getLeftTableKey(),
0820: joinContext.getRightTablekey());
0821: joinContext.setRowsAreSortedByJoinKey(true);
0822: }
0823: joinCondition.getNodes().remove(fn);
0824: pushUnwantedConditions(from, joinCondition, ltid);
0825: } else {
0826: joinContext.setLeftTableKey(null);
0827: joinContext.setRightTablekey(null);
0828: }
0829: }
0830: }
0831: }
0832:
0833: private void makeLeftRowIterator(FromNode from,
0834: JoinCondition joinCondition, Database db,
0835: QueryPlannerJoinContext joinContext, ColumnIdentifier lcol,
0836: AxionQueryContext context, boolean readOnly)
0837: throws AxionException {
0838:
0839: Object leftChild = from.getLeft();
0840: if (leftChild instanceof FromNode) {
0841: QueryPlannerJoinContext nestedJoinContext = processFromTree(
0842: (FromNode) leftChild, db, context, readOnly);
0843: joinContext.setLeftIterator(nestedJoinContext
0844: .getRowIterator());
0845: joinContext.addColumnIdentifiers(nestedJoinContext
0846: .getColumnIdentifiers());
0847: joinContext.setLeftColumnCount(nestedJoinContext
0848: .getTotalColumnCount());
0849:
0850: if (lcol != null) {
0851: Integer colPos = (Integer) nestedJoinContext
0852: .getColumnIdToFieldMap().get(
0853: lcol.getCanonicalIdentifier());
0854: if (colPos != null) {
0855: joinContext
0856: .setLeftColumnPosition(colPos.intValue());
0857: }
0858: }
0859: } else {
0860: TableIdentifier tid = (TableIdentifier) leftChild;
0861: Table left = db.getTable(tid);
0862: if (lcol != null) {
0863: joinContext.setLeftColumnPosition(left
0864: .getColumnIndex(lcol.getName()));
0865: }
0866:
0867: RowIterator rows = joinContext.getLeftIterator();
0868: if (joinContext.isRowsAreSortedByJoinKey()) {
0869: rows = getIndexedRowsIfSortingRequired(rows, context,
0870: left, readOnly, _unappliedTableFilters);
0871: }
0872: rows = getRowIteratorFromTable(db, tid, left, rows,
0873: readOnly, _unappliedTableFilters);
0874: rows = makeFilteringRowIterator(tid, left, rows, context,
0875: _unappliedTableFilters);
0876:
0877: populateColumnList(joinContext.getColumnIdentifiers(), tid,
0878: left, context);
0879: joinContext.setLeftIterator(rows);
0880: joinContext.setLeftColumnCount(left.getColumnCount());
0881:
0882: pushUnwantedConditions(from, joinCondition, tid);
0883: }
0884: }
0885:
0886: private void pushUnwantedConditions(FromNode from,
0887: JoinCondition joinCondition, TableIdentifier tid) {
0888: if (from.isInnerJoin() && !joinCondition.isEmpty()) {
0889: Set conditions = new LinkedHashSet();
0890: for (Iterator iter = joinCondition.getNodes().iterator(); iter
0891: .hasNext();) {
0892: ComparisonFunction fn = (ComparisonFunction) iter
0893: .next();
0894: if (!AxionQueryOptimizer.hasTableReference(fn, tid)) {
0895: _unappliedWhereNodes.add(fn);
0896: } else {
0897: conditions.add(fn);
0898: }
0899: }
0900: joinCondition.setNodes(conditions);
0901: }
0902: }
0903:
0904: private RowIterator makeLimitingRowIterator(RowIterator rows,
0905: AxionQueryContext context, Map colIdToFieldMap)
0906: throws AxionException {
0907: // If there's a limit, apply it
0908: if (null != context.getLimit() || null != context.getOffset()) {
0909: rows = new LimitingRowIterator(rows, context.getLimit(),
0910: context.getOffset());
0911: addExplainRow(rows);
0912: }
0913: return rows;
0914: }
0915:
0916: private RowIterator makeLiteralRowIterator(List columns)
0917: throws AxionException {
0918: RowIterator literaliter = null;
0919:
0920: if (null != _literals || _parentRow != null) {
0921: int ltRowSize = ((null != _literals) ? _literals.size() : 0);
0922: ltRowSize += ((null != _parentRow) ? _parentRow.getRow()
0923: .size() : 0);
0924: Row litrow = new SimpleRow(ltRowSize);
0925:
0926: Iterator iter;
0927: int pos = 0;
0928: if (null != _literals) {
0929: iter = _literals.iterator();
0930: for (int i = 0; iter.hasNext(); i++) {
0931: Literal literal = (Literal) iter.next();
0932: columns.add(literal);
0933: litrow.set(pos++, literal);
0934: }
0935: }
0936:
0937: if (null != _parentRow) {
0938: iter = _parentRow.getSelectableIterator();
0939: for (int i = 0; iter.hasNext(); i++) {
0940: ColumnIdentifier parentCol = (ColumnIdentifier) iter
0941: .next();
0942: // Give prefernce to the inner select if the name exists
0943: // in both inner and outer select
0944: if (!columns.contains(parentCol)) {
0945: columns.add(parentCol);
0946: litrow.set(pos++, _parentRow.get(parentCol));
0947: }
0948: }
0949: }
0950:
0951: literaliter = new SingleRowIterator(litrow);
0952: addExplainRow(literaliter);
0953:
0954: // Set to null, so that they are processed only once.
0955: _literals = null;
0956: _parentRow = null;
0957: }
0958: return literaliter;
0959: }
0960:
0961: private void makeNestedLoopJoinedIterator(FromNode from,
0962: JoinCondition joinCondition,
0963: QueryPlannerJoinContext joinContext) throws AxionException {
0964: // NOTE: Join is carried out using nested loop algorithm; hence, in case of
0965: // of right outer join, we make the right table as the outer table of
0966: // the nested loop algorithm. Note that no change is made to _colIdToFieldmap.
0967:
0968: NestedLoopJoinedRowIterator joinedRowIter = null;
0969: if (!from.isRightJoin() && !joinContext.swapRightToLeft()) {
0970: joinedRowIter = new NestedLoopJoinedRowIterator(joinContext
0971: .getLeftIterator(), joinContext.getRightIterator(),
0972: joinContext.getRightColumnCount(), !from
0973: .isInnerJoin(), from.isRightJoin());
0974: } else {
0975: joinedRowIter = new NestedLoopJoinedRowIterator(joinContext
0976: .getRightIterator(), joinContext.getLeftIterator(),
0977: joinContext.getLeftColumnCount(), !from
0978: .isInnerJoin(), true);
0979: }
0980:
0981: // Note: if RootJoinCondition is null or empty, it will be a Cross Product join.
0982: if (!joinCondition.isEmpty()) {
0983: joinedRowIter.setJoinCondition(joinCondition.stitchAll(),
0984: new RowDecorator(joinContext
0985: .getColumnIdToFieldMap()));
0986: _unappliedWhereNodes.removeAll(joinCondition.getNodes());
0987: }
0988: joinContext.setRowIterator(joinedRowIter);
0989: addExplainRow(joinedRowIter);
0990: }
0991:
0992: private RowIterator makeOrderedIndexBasedRowIterator(
0993: boolean readOnly, AxionQueryContext context, Table table)
0994: throws AxionException {
0995: // Check if we can use index for order by; only supported for single table
0996: RowIterator orderedRows = null;
0997: OrderNode node = context.getOrderBy(0);
0998: ColumnIdentifier cid = null;
0999: Selectable where = context.getWhere();
1000:
1001: // Index keep data row pointer is ascending order
1002: if (node.getSelectable() instanceof ColumnIdentifier) {
1003: cid = (ColumnIdentifier) node.getSelectable();
1004: Set conditions = AxionQueryOptimizer
1005: .flatConditionTree(where);
1006: orderedRows = getIndexedRows(conditions, cid, table,
1007: readOnly);
1008: }
1009:
1010: if (orderedRows != null) {
1011: setSkipSorting(true);
1012: addExplainRow(orderedRows);
1013: if (where != null) {
1014: orderedRows = new FilteringRowIterator(orderedRows,
1015: new RowDecorator(getColumnIdToFieldMap()),
1016: where);
1017: addExplainRow(orderedRows);
1018: }
1019: }
1020: return orderedRows;
1021: }
1022:
1023: private RowIterator makeOrderedRowIterator(Database db,
1024: RowIterator rows, Map colIdToFieldMap,
1025: AxionQueryContext context) throws AxionException {
1026: if (isSortingRequired(context)) {
1027: rows = new SortedRowIterator.MergeSort(rows, context
1028: .getOrderBy(), new RowDecorator(colIdToFieldMap));
1029: addExplainRow(rows);
1030: } else if (_doReverseSorting) {
1031: rows = new ReverseSortedRowIterator(rows);
1032: addExplainRow(rows);
1033: }
1034: return rows;
1035: }
1036:
1037: private void makeRightChangingIndexedRowIterator(FromNode from,
1038: JoinCondition joinCondition, Database db,
1039: QueryPlannerJoinContext joinContext) throws AxionException {
1040:
1041: if (joinContext.getLeftIterator() == null
1042: && from.getRight() instanceof TableIdentifier) {
1043: TableIdentifier rtid = (TableIdentifier) from.getRight();
1044: Table table = db.getTable(rtid);
1045: ComparisonFunction fn = AxionQueryOptimizer
1046: .findFirstColumnColumnComparisonFunction(
1047: joinCondition.getNodes(), rtid, table, true);
1048: if (fn != null
1049: && !fn.getArgument(0).equals(fn.getArgument(1))) {
1050: // Assume that right argument of function is from right table
1051: joinContext.setLeftTableKey((ColumnIdentifier) fn
1052: .getArgument(0));
1053: joinContext.setRightTablekey((ColumnIdentifier) fn
1054: .getArgument(1));
1055:
1056: // Right argument of function is not from right table so flip it
1057: if (!rtid.equals(joinContext.getRightTablekey()
1058: .getTableIdentifier())) {
1059: joinContext.flipKey();
1060: }
1061:
1062: // Check in we can use index
1063: if (joinContext.getRightTablekey() != null
1064: && !from.isRightJoin()) {
1065: Index index = table.getIndexForColumn(table
1066: .getColumn(joinContext.getRightTablekey()
1067: .getName()));
1068: joinContext
1069: .setRightIterator(makeChangingIndexedRowIterator(
1070: table, index));
1071: if (fn instanceof EqualFunction) {
1072: swapKeyForSortingIfUSedInOrderByOrGroupBy(
1073: joinContext.getRightTablekey(),
1074: joinContext.getLeftTableKey());
1075: joinContext.setRowsAreSortedByJoinKey(true);
1076: }
1077: joinCondition.getNodes().remove(fn);
1078: pushUnwantedConditions(from, joinCondition, rtid);
1079: } else {
1080: joinContext.setLeftTableKey(null);
1081: joinContext.setRightTablekey(null);
1082: }
1083: }
1084: }
1085: }
1086:
1087: private void makeRightRowIterator(FromNode from,
1088: JoinCondition joinCondition, Database db,
1089: QueryPlannerJoinContext joinContext, ColumnIdentifier rcol,
1090: AxionQueryContext context, boolean readOnly)
1091: throws AxionException {
1092: Object rightChild = from.getRight();
1093: if (rightChild instanceof FromNode) {
1094: QueryPlannerJoinContext nestedJoinContext = processFromTree(
1095: (FromNode) rightChild, db, context, readOnly);
1096: joinContext.setRightIterator(nestedJoinContext
1097: .getRowIterator());
1098: joinContext.addColumnIdentifiers(nestedJoinContext
1099: .getColumnIdentifiers());
1100: joinContext.setRightColumnCount(nestedJoinContext
1101: .getTotalColumnCount());
1102:
1103: if (rcol != null) {
1104: Integer colPos = (Integer) nestedJoinContext
1105: .getColumnIdToFieldMap().get(
1106: rcol.getCanonicalIdentifier());
1107: if (colPos != null) {
1108: joinContext.setRightColumnPosition(colPos
1109: .intValue());
1110: }
1111: }
1112: } else {
1113: TableIdentifier tid = (TableIdentifier) rightChild;
1114: Table right = db.getTable(tid);
1115: if (rcol != null) {
1116: joinContext.setRightColumnPosition(right
1117: .getColumnIndex(rcol.getName()));
1118: }
1119:
1120: RowIterator rows = joinContext.getRightIterator();
1121: if (joinContext.isRowsAreSortedByJoinKey()) {
1122: rows = getIndexedRowsIfSortingRequired(rows, context,
1123: right, readOnly, _unappliedTableFilters);
1124: }
1125: rows = getRowIteratorFromTable(db, tid, right, rows,
1126: readOnly, _unappliedTableFilters);
1127: rows = makeFilteringRowIterator(tid, right, rows, context,
1128: _unappliedTableFilters);
1129:
1130: populateColumnList(joinContext.getColumnIdentifiers(), tid,
1131: right, context);
1132: joinContext.setRightIterator(rows);
1133: joinContext.setRightColumnCount(right.getColumnCount());
1134:
1135: pushUnwantedConditions(from, joinCondition, tid);
1136: }
1137: }
1138:
1139: private void populateColumnIdToFieldMap(List columnList,
1140: Map colIdToFieldMap) {
1141: for (int i = 0, I = columnList.size(); i < I; i++) {
1142: colIdToFieldMap.put(columnList.get(i), ValuePool.getInt(i));
1143: }
1144: }
1145:
1146: private void populateColumnList(List colList,
1147: TableIdentifier tableIdent, Table table,
1148: AxionQueryContext context) throws AxionException {
1149: for (int j = 0, J = table.getColumnCount(); j < J; j++) {
1150: ColumnIdentifier id = null;
1151: // Determine which selected column id matches, if any
1152: for (int k = 0, K = context.getSelectCount(); k < K; k++) {
1153: Selectable sel = context.getSelect(k);
1154: if (sel instanceof ColumnIdentifier) {
1155: ColumnIdentifier cSel = (ColumnIdentifier) sel;
1156: if (tableIdent.equals(cSel.getTableIdentifier())
1157: && cSel.getName().equals(
1158: table.getColumn(j).getName())) {
1159: id = cSel.getCanonicalIdentifier();
1160: break;
1161: }
1162: }
1163: }
1164:
1165: if (null == id) {
1166: id = new ColumnIdentifier(tableIdent, table
1167: .getColumn(j).getName());
1168: }
1169: colList.add(id);
1170: }
1171: }
1172:
1173: private QueryPlannerJoinContext processFromTree(FromNode from,
1174: Database db, AxionQueryContext context, boolean readOnly)
1175: throws AxionException {
1176:
1177: QueryPlannerJoinContext joinContext = new QueryPlannerJoinContext();
1178:
1179: // Process join on and where conditions
1180: JoinCondition joinCondition = processJoinConditionTree(from);
1181:
1182: // NO Join, may be a correlated-subquery or right nested join
1183: if (!from.hasRight()) {
1184: makeLeftRowIterator(from, joinCondition, db, joinContext,
1185: joinContext.getLeftTableKey(), context, readOnly);
1186: joinContext.setRowIterator(joinContext.getLeftIterator());
1187: return joinContext;
1188: }
1189:
1190: if (!findFilterOnIndexColumnForRightTable(from, db,
1191: joinContext, joinCondition)) {
1192: // If index found for the join column in right table create
1193: // ChangingIndexedRowIterator on right table
1194: makeRightChangingIndexedRowIterator(from, joinCondition,
1195: db, joinContext);
1196: }
1197:
1198: // If index found for the join column in left table create
1199: // ChangingIndexedRowIterator on the left table
1200: makeLeftChangingIndexedRowIterator(from, joinCondition, db,
1201: joinContext);
1202:
1203: // If no index found then we may create dynamic index
1204: if (from.getTableCount() > 1
1205: && joinContext.getLeftIterator() == null
1206: && joinContext.getRightIterator() == null) {
1207: createDynamicIndex(from, joinCondition, joinContext, db);
1208: }
1209:
1210: // Get RowIterator from left subtree.
1211: makeLeftRowIterator(from, joinCondition, db, joinContext,
1212: joinContext.getLeftTableKey(), context, readOnly);
1213: joinContext
1214: .setIteratorCount(joinContext.getIteratorCount() + 1);
1215:
1216: // Get RowIterator from right subtree.
1217: makeRightRowIterator(from, joinCondition, db, joinContext,
1218: joinContext.getRightTablekey(), context, readOnly);
1219: joinContext
1220: .setIteratorCount(joinContext.getIteratorCount() + 1);
1221:
1222: // If index found or created for the outer table then use
1223: // IndexNestedLoopRowIterator.
1224: makeIndexNestedLoopJoinedRowIterator(from, joinCondition,
1225: joinContext);
1226: // Else use NestedLoopJoinedIterator.
1227: if (joinContext.getRowIterator() == null) {
1228: makeNestedLoopJoinedIterator(from, joinCondition,
1229: joinContext);
1230: }
1231: return joinContext;
1232: }
1233:
1234: private boolean findFilterOnIndexColumnForRightTable(FromNode from,
1235: Database db, QueryPlannerJoinContext joinContext,
1236: JoinCondition joinCondition) throws AxionException {
1237: if (!_isAllInnerJoin) {
1238: return false;
1239: }
1240:
1241: Function fn = null;
1242: if (from.isInnerJoin()
1243: && from.getRight() instanceof TableIdentifier) {
1244: TableIdentifier rtid = (TableIdentifier) from.getRight();
1245: Table rightTable = db.getTable(rtid);
1246: fn = AxionQueryOptimizer.findColumnLiteralEqualFunction(
1247: rtid, rightTable, _unappliedTableFilters, true);
1248: if (fn != null) {
1249: fn = AxionQueryOptimizer
1250: .findFirstColumnColumnComparisonFunction(
1251: joinCondition.getNodes(), rtid,
1252: rightTable, false);
1253: if (fn != null) {
1254: // Assume that right argument of function is from right table
1255: joinContext.setLeftTableKey((ColumnIdentifier) fn
1256: .getArgument(0));
1257: joinContext.setRightTablekey((ColumnIdentifier) fn
1258: .getArgument(1));
1259:
1260: // Right argument of function is not from right table so flip it
1261: if (!rtid.equals(joinContext.getRightTablekey()
1262: .getTableIdentifier())) {
1263: joinContext.flipKey();
1264: }
1265: joinContext.setSwapRightToLeft(true);
1266: pushUnwantedConditions(from, joinCondition, rtid);
1267: }
1268: }
1269: }
1270: return (fn != null ? true : false);
1271: }
1272:
1273: private JoinCondition processJoinConditionTree(FromNode from)
1274: throws AxionException {
1275: // ANSI Join Syntax: if join type is inner join we can derive condition from where
1276: // node for other table based on the join condition
1277: Set joinConditions = AxionQueryOptimizer.flatConditionTree(from
1278: .getCondition());
1279: if (from.isInnerJoin()) {
1280: Set joinAndWhereConditions = new LinkedHashSet();
1281: joinAndWhereConditions.addAll(joinConditions);
1282: joinAndWhereConditions.addAll(_unappliedWhereNodes);
1283: Set conditions = AxionQueryOptimizer.deriveTableFilter(
1284: joinAndWhereConditions, _isAllInnerJoin);
1285: Set[] splitConditions = AxionQueryOptimizer
1286: .decomposeWhereConditionNodes(conditions,
1287: _isAllInnerJoin);
1288: _unappliedTableFilters.addAll(splitConditions[1]);
1289: _unappliedWhereNodes = splitConditions[2];
1290:
1291: return new JoinCondition(splitConditions[0]);
1292: } else {
1293: return new JoinCondition(joinConditions);
1294: }
1295: }
1296:
1297: private RowIterator processQuery(Database db, boolean readOnly,
1298: AxionQueryContext context) throws AxionException {
1299: _unappliedWhereNodes = AxionQueryOptimizer
1300: .flatConditionTree(context.getWhere());
1301: _isAllInnerJoin = AxionQueryOptimizer.isAllInnerJoin(context
1302: .getFrom());
1303:
1304: QueryPlannerJoinContext rootJoinContext = processFromTree(
1305: context.getFrom(), db, context, readOnly);
1306:
1307: // Get _rowIterator for literals (if any) in the select list
1308: RowIterator literaliter = makeLiteralRowIterator(rootJoinContext
1309: .getColumnIdentifiers());
1310: if (literaliter != null) {
1311: rootJoinContext.setIteratorCount(rootJoinContext
1312: .getIteratorCount() + 1);
1313: int literaliterRowCount = literaliter.first().size();
1314: RowIterator cpjRows = new NestedLoopJoinedRowIterator(
1315: rootJoinContext.getRowIterator(), literaliter,
1316: literaliterRowCount);
1317: rootJoinContext.setRowIterator(cpjRows);
1318: }
1319: RowIterator rows = rootJoinContext.getRowIterator();
1320:
1321: Map colIdToFieldMap = clearAndGetColumnIdToFieldMap();
1322: populateColumnIdToFieldMap(rootJoinContext
1323: .getColumnIdentifiers(), colIdToFieldMap);
1324:
1325: // And apply any remaining where nodes to the join.
1326: if (!_unappliedWhereNodes.isEmpty()
1327: || !_unappliedTableFilters.isEmpty()) {
1328: _unappliedWhereNodes.addAll(_unappliedTableFilters);
1329: Selectable unappliedWhere = AxionQueryOptimizer
1330: .createOneRootFunction(_unappliedWhereNodes);
1331: rows = new FilteringRowIterator(rows, new RowDecorator(
1332: colIdToFieldMap), unappliedWhere);
1333: addExplainRow(rows);
1334: }
1335: return rows;
1336: }
1337:
1338: private RowIterator processQueryForSingleTable(Database db,
1339: boolean readOnly, AxionQueryContext context)
1340: throws AxionException {
1341: Map colIdToFieldMap = clearAndGetColumnIdToFieldMap();
1342: Table table = db.getTable(context.getTables(0));
1343: List columnList = new ArrayList();
1344: populateColumnList(columnList, context.getTables(0), table,
1345: context);
1346: RowIterator literaliter = makeLiteralRowIterator(columnList);
1347: populateColumnIdToFieldMap(columnList, colIdToFieldMap);
1348:
1349: RowIterator rows = null;
1350: if (context.getOrderByCount() == 1
1351: && context.getGroupByCount() < 1) {
1352: rows = makeOrderedIndexBasedRowIterator(readOnly, context,
1353: table);
1354: } else if (context.getGroupByCount() == 1) {
1355: rows = makeGroupedIndexBasedRowIterator(readOnly, context,
1356: table);
1357: }
1358:
1359: if (rows == null) {
1360: _unappliedWhereNodes = AxionQueryOptimizer
1361: .flatConditionTree(context.getWhere());
1362: rows = getRowIteratorFromTable(db, context.getTables(0),
1363: table, rows, readOnly, _unappliedWhereNodes);
1364: }
1365:
1366: // Add RowIterator for literals (if any) in the select list
1367: if (literaliter != null) {
1368: int literaliterRowCount = literaliter.first().size();
1369: rows = new NestedLoopJoinedRowIterator(rows, literaliter,
1370: literaliterRowCount);
1371: addExplainRow(rows);
1372: }
1373:
1374: if (_unappliedWhereNodes != null
1375: && !_unappliedWhereNodes.isEmpty()) {
1376: Selectable unappliedWhere = AxionQueryOptimizer
1377: .createOneRootFunction(_unappliedWhereNodes);
1378: rows = new FilteringRowIterator(rows, new RowDecorator(
1379: colIdToFieldMap), unappliedWhere);
1380: addExplainRow(rows);
1381: }
1382: return rows;
1383: }
1384:
1385: private RowIterator processQueryWithNoTable(
1386: AxionQueryContext context) throws AxionException {
1387: RowIterator rows;
1388: Map colIdToFieldMap = clearAndGetColumnIdToFieldMap();
1389: List columnList = new ArrayList();
1390: rows = makeLiteralRowIterator(columnList);
1391: populateColumnIdToFieldMap(columnList, colIdToFieldMap);
1392: if (rows == null) {
1393: rows = new SingleRowIterator(new SimpleRow(0));
1394: }
1395: if (context.getWhere() != null) {
1396: rows = new FilteringRowIterator(rows, new RowDecorator(
1397: colIdToFieldMap), context.getWhere());
1398: }
1399: return rows;
1400: }
1401:
1402: private void resolveOrderByAfterApplyingGroupBy(
1403: AxionQueryContext context, Selectable oldSel,
1404: Selectable newSel) {
1405: Selectable temp = null;
1406: for (int i = 0, I = context.getOrderByCount(); i < I; i++) {
1407: temp = context.getOrderBy(i).getSelectable();
1408: if (oldSel.equals(temp)) {
1409: context.getOrderBy(i).setSelectable(newSel);
1410: }
1411: }
1412: }
1413:
1414: private void resolveSelectedAfterGrouping(
1415: AxionQueryContext context, Map colIdToFieldMap)
1416: throws AxionException {
1417: colIdToFieldMap.clear();
1418: Selectable[] newSelected = new Selectable[context
1419: .getSelectCount()];
1420:
1421: for (int i = 0, I = context.getSelectCount(); i < I; i++) {
1422: Selectable sel = context.getSelect(i);
1423: TableIdentifier tid = null;
1424:
1425: if (sel instanceof ColumnIdentifier) {
1426: tid = ((ColumnIdentifier) sel).getTableIdentifier();
1427: } else {
1428: tid = new TableIdentifier(context.getAliasName());
1429: }
1430: newSelected[i] = new ColumnIdentifier(tid, sel.getLabel(),
1431: null, sel.getDataType());
1432:
1433: if (context.getGroupByCount() > 0) {
1434: resolveOrderByAfterApplyingGroupBy(context, sel,
1435: newSelected[i]);
1436: }
1437: colIdToFieldMap.put(newSelected[i], ValuePool.getInt(i));
1438: }
1439:
1440: context.setSelected(newSelected);
1441: context.setResolvedSelect(Arrays.asList(newSelected));
1442: }
1443:
1444: private boolean setIndexUsedForGroupBy(boolean indexUsed) {
1445: return _wasIndexUsedForGroupBy = indexUsed;
1446: }
1447:
1448: private void setSkipSorting(boolean skipSorting) {
1449: _skipSorting = skipSorting;
1450: }
1451:
1452: private boolean skipSorting() {
1453: return _skipSorting;
1454: }
1455:
1456: // Swap the key , in case index is available for the other table we will make use of
1457: // index for order by and group by and avoid extra sorting. Note that we don't swap
1458: // key for index scan for non-equal function
1459: private void swapKeyForSortingIfUSedInOrderByOrGroupBy(
1460: ColumnIdentifier current, ColumnIdentifier swapWith) {
1461: AxionQueryContext context = getContext();
1462: if (context.getGroupByCount() == 1) {
1463: ColumnIdentifier grpCol = (ColumnIdentifier) context
1464: .getGroupBy(0);
1465: if (grpCol.equals(current)) {
1466: context.setGroupBy(0, swapWith);
1467: }
1468: }
1469:
1470: // Attempt to get Index based row iterator, if order column is from this table
1471: if (context.getOrderByCount() == 1) {
1472: // List OrdList = context.getOrderBy();
1473: OrderNode node = context.getOrderBy(0);
1474: Selectable ordCol = node.getSelectable();
1475: if (ordCol instanceof ColumnIdentifier
1476: && ordCol.equals(current)) {
1477: node.setSelectable(swapWith);
1478: }
1479: }
1480: }
1481:
1482: private boolean wasIndexUsedForGroupBy() {
1483: return _wasIndexUsedForGroupBy;
1484: }
1485:
1486: // Note: For now its only used in Explain command and Junit test cases.
1487: private class AxionQueryPlanNode {
1488: List _explainRows = new ArrayList(2);
1489:
1490: public void addExplainRow(String value) {
1491: Row row = new SimpleRow(1);
1492: row.set(0, value);
1493: _explainRows.add(row);
1494: }
1495:
1496: public RowIterator getRowIterator() {
1497: return new ListRowIterator(_explainRows);
1498: }
1499: }
1500:
1501: class JoinCondition {
1502: private Set _joinConditions;
1503:
1504: // Conditions which specifies join between two tables.
1505: public JoinCondition(Set jConditions) {
1506: _joinConditions = jConditions;
1507: }
1508:
1509: public Set getNodes() {
1510: return _joinConditions;
1511: }
1512:
1513: public void setNodes(Set conditions) {
1514: _joinConditions = conditions;
1515: }
1516:
1517: public boolean isEmpty() {
1518: return _joinConditions == null || _joinConditions.isEmpty();
1519: }
1520:
1521: public Selectable stitchAll() {
1522: return AxionQueryOptimizer
1523: .createOneRootFunction(_joinConditions);
1524: }
1525:
1526: public String toString() {
1527: return "JoinCondition[" + _joinConditions.toString() + "]";
1528: }
1529: }
1530:
1531: class QueryPlannerJoinContext {
1532: private List _columns = new ArrayList();
1533: private int _iteratorCount = 0;
1534: private int _leftColumnCount = -1;
1535: private int _leftColumnPosition = -1;
1536:
1537: private RowIterator _leftIterator;
1538: private ColumnIdentifier _leftTableKey;
1539: private int _rightColumnCount = -1;
1540: private int _rightColumnPosition = -1;
1541: private RowIterator _rightIterator;
1542: private ColumnIdentifier _rightTablekey;
1543: private RowIterator _rowIterator;
1544:
1545: private boolean _rowsAreSortedByJoinKey = false;
1546: private boolean _swapRightToLeft = false;
1547:
1548: /**
1549: * Default constructor
1550: */
1551: public QueryPlannerJoinContext() {
1552: }
1553:
1554: public void addColumnIdentifiers(List columns) {
1555: _columns.addAll(columns);
1556: }
1557:
1558: public void flipKey() {
1559: ColumnIdentifier temp = _rightTablekey;
1560: _rightTablekey = _leftTableKey;
1561: _leftTableKey = temp;
1562: }
1563:
1564: public List getColumnIdentifiers() {
1565: return _columns;
1566: }
1567:
1568: public Map getColumnIdToFieldMap() {
1569: int size = _columns.size();
1570: Map colIdToFieldMap = new HashMap(size);
1571: for (int i = 0; i < size; i++) {
1572: colIdToFieldMap.put(_columns.get(i), ValuePool
1573: .getInt(i));
1574: }
1575: return colIdToFieldMap;
1576: }
1577:
1578: /**
1579: * @return Returns the _iteratorCount.
1580: */
1581: public int getIteratorCount() {
1582: return _iteratorCount;
1583: }
1584:
1585: /**
1586: * @return Returns the _leftColumnCount.
1587: */
1588: public int getLeftColumnCount() {
1589: return _leftColumnCount;
1590: }
1591:
1592: /**
1593: * @return Returns the _leftColumnPosition.
1594: */
1595: public int getLeftColumnPosition() {
1596: return _leftColumnPosition;
1597: }
1598:
1599: /**
1600: * @return Returns the _leftIterator.
1601: */
1602: public RowIterator getLeftIterator() {
1603: return _leftIterator;
1604: }
1605:
1606: /**
1607: * @return Returns the _leftTableKey.
1608: */
1609: public ColumnIdentifier getLeftTableKey() {
1610: return _leftTableKey;
1611: }
1612:
1613: /**
1614: * @return Returns the _rightColumnCount.
1615: */
1616: public int getRightColumnCount() {
1617: return _rightColumnCount;
1618: }
1619:
1620: /**
1621: * @return Returns the _rightColumnPosition.
1622: */
1623: public int getRightColumnPosition() {
1624: return _rightColumnPosition;
1625: }
1626:
1627: /**
1628: * @return Returns the _rightIterator.
1629: */
1630: public RowIterator getRightIterator() {
1631: return _rightIterator;
1632: }
1633:
1634: /**
1635: * @return Returns the _rightTablekey.
1636: */
1637: public ColumnIdentifier getRightTablekey() {
1638: return _rightTablekey;
1639: }
1640:
1641: /**
1642: * @return Returns the _rowIterator.
1643: */
1644: public RowIterator getRowIterator() {
1645: return _rowIterator;
1646: }
1647:
1648: public int getTotalColumnCount() {
1649: return _leftColumnCount + _rightColumnCount;
1650: }
1651:
1652: /**
1653: * @param _iteratorCount The _iteratorCount to set.
1654: */
1655: public void setIteratorCount(int iteratorCount) {
1656: _iteratorCount = iteratorCount;
1657: }
1658:
1659: /**
1660: * @param _leftColumnCount The _leftColumnCount to set.
1661: */
1662: public void setLeftColumnCount(int leftColumnCount) {
1663: _leftColumnCount = leftColumnCount;
1664: }
1665:
1666: /**
1667: * @param _leftColumnPosition The _leftColumnPosition to set.
1668: */
1669: public void setLeftColumnPosition(int leftColumnPosition) {
1670: _leftColumnPosition = leftColumnPosition;
1671: }
1672:
1673: /**
1674: * @param _leftIterator The _leftIterator to set.
1675: */
1676: public void setLeftIterator(RowIterator leftIterator) {
1677: _leftIterator = leftIterator;
1678: }
1679:
1680: /**
1681: * @param _leftTableKey The _leftTableKey to set.
1682: */
1683: public void setLeftTableKey(ColumnIdentifier leftTableKey) {
1684: _leftTableKey = leftTableKey;
1685: }
1686:
1687: /**
1688: * @param _rightColumnCount The _rightColumnCount to set.
1689: */
1690: public void setRightColumnCount(int rightColumnCount) {
1691: _rightColumnCount = rightColumnCount;
1692: }
1693:
1694: /**
1695: * @param _rightColumnPosition The _rightColumnPosition to set.
1696: */
1697: public void setRightColumnPosition(int rightColumnPosition) {
1698: _rightColumnPosition = rightColumnPosition;
1699: }
1700:
1701: /**
1702: * @param _rightIterator The _rightIterator to set.
1703: */
1704: public void setRightIterator(RowIterator rightIterator) {
1705: _rightIterator = rightIterator;
1706: }
1707:
1708: /**
1709: * @param _rightTablekey The _rightTablekey to set.
1710: */
1711: public void setRightTablekey(ColumnIdentifier rightTablekey) {
1712: _rightTablekey = rightTablekey;
1713: }
1714:
1715: /**
1716: * @param _rowIterator The _rowIterator to set.
1717: */
1718: public void setRowIterator(RowIterator rowIterator) {
1719: _rowIterator = rowIterator;
1720: }
1721:
1722: /**
1723: * @return true if Rows are sorted by left key
1724: */
1725: public boolean isRowsAreSortedByJoinKey() {
1726: return _rowsAreSortedByJoinKey;
1727: }
1728:
1729: /**
1730: * @param areSortedByLeftKey
1731: */
1732: public void setRowsAreSortedByJoinKey(boolean areSortedByJoinKey) {
1733: _rowsAreSortedByJoinKey = areSortedByJoinKey;
1734: }
1735:
1736: public boolean swapRightToLeft() {
1737: return _swapRightToLeft;
1738: }
1739:
1740: public void setSwapRightToLeft(boolean swapRightToLeft) {
1741: _swapRightToLeft = swapRightToLeft;
1742: }
1743:
1744: public String toString() {
1745: StringBuffer buf = new StringBuffer(20);
1746: buf.append("JoinContext{");
1747: buf.append("\niteratorCount=").append(_iteratorCount);
1748: buf.append("\nrowIterator=").append(_rowIterator);
1749:
1750: buf.append("\n\nleftColumnCount=").append(_leftColumnCount);
1751: buf.append("\nleftColumnPosition=").append(
1752: _leftColumnPosition);
1753: buf.append("\nleftIterator=").append(_leftIterator);
1754: buf.append("\nleftTableKey=").append(_leftTableKey);
1755:
1756: buf.append("\n\nrightColumnCount=").append(
1757: _rightColumnCount);
1758: buf.append("\nrightColumnPosition=").append(
1759: _rightColumnPosition);
1760: buf.append("\nrightIterator=").append(_rightIterator);
1761: buf.append("\nrightTablekey=").append(_rightTablekey);
1762:
1763: buf.append("\n\nrowsAreSortedByJoinKey=").append(
1764: _rowsAreSortedByJoinKey);
1765: buf.append("}");
1766: return buf.toString();
1767: }
1768: }
1769:
1770: private Map _colIdToFieldMap = new HashMap();
1771: private AxionQueryContext _context;
1772: private List _literals;
1773: private RowDecorator _parentRow;
1774: private Set _unappliedWhereNodes = new LinkedHashSet();
1775: private Set _unappliedTableFilters = new LinkedHashSet();
1776: private boolean _isAllInnerJoin = false;
1777:
1778: private AxionQueryPlanNode _planNode = new AxionQueryPlanNode();
1779: private boolean _skipSorting = false;
1780: private boolean _doReverseSorting = false;
1781: private boolean _wasIndexUsedForGroupBy = false;
1782:
1783: }
|