0001: /**
0002: * com.mckoi.database.interpret.Planner 12 Nov 2001
0003: *
0004: * Mckoi SQL Database ( http://www.mckoi.com/database )
0005: * Copyright (C) 2000, 2001, 2002 Diehl and Associates, Inc.
0006: *
0007: * This program is free software; you can redistribute it and/or
0008: * modify it under the terms of the GNU General Public License
0009: * Version 2 as published by the Free Software Foundation.
0010: *
0011: * This program is distributed in the hope that it will be useful,
0012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
0014: * GNU General Public License Version 2 for more details.
0015: *
0016: * You should have received a copy of the GNU General Public License
0017: * Version 2 along with this program; if not, write to the Free Software
0018: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
0019: *
0020: * Change Log:
0021: *
0022: *
0023: */package com.mckoi.database.interpret;
0024:
0025: import java.util.Collections;
0026: import java.util.ArrayList;
0027: import java.util.Iterator;
0028: import java.util.List;
0029: import com.mckoi.database.*;
0030: import com.mckoi.util.BigNumber;
0031:
0032: /**
0033: * Various methods for forming query plans on SQL queries.
0034: *
0035: * @author Tobias Downer
0036: */
0037:
0038: public class Planner {
0039:
0040: /**
0041: * The name of the GROUP BY function table.
0042: */
0043: private static TableName GROUP_BY_FUNCTION_TABLE = new TableName(
0044: "FUNCTIONTABLE");
0045:
0046: /**
0047: * Prepares the given SearchExpression object. This goes through each
0048: * element of the Expression. If the element is a variable it is qualified.
0049: * If the element is a TableSelectExpression it's converted to a
0050: * SelectQueriable object and prepared.
0051: */
0052: private static void prepareSearchExpression(
0053: final DatabaseConnection db,
0054: final TableExpressionFromSet from_set,
0055: SearchExpression expression) throws DatabaseException {
0056: // This is used to prepare sub-queries and qualify variables in a
0057: // search expression such as WHERE or HAVING.
0058:
0059: // Prepare the sub-queries first
0060: expression.prepare(new ExpressionPreparer() {
0061: public boolean canPrepare(Object element) {
0062: return element instanceof TableSelectExpression;
0063: }
0064:
0065: public Object prepare(Object element)
0066: throws DatabaseException {
0067: TableSelectExpression sq_expr = (TableSelectExpression) element;
0068: TableExpressionFromSet sq_from_set = generateFromSet(
0069: sq_expr, db);
0070: sq_from_set.setParent(from_set);
0071: QueryPlanNode sq_plan = formQueryPlan(db, sq_expr,
0072: sq_from_set, null);
0073: // Form this into a query plan type
0074: return new TObject(TType.QUERY_PLAN_TYPE,
0075: new QueryPlan.CachePointNode(sq_plan));
0076: }
0077: });
0078:
0079: // Then qualify all the variables. Note that this will not qualify
0080: // variables in the sub-queries.
0081: expression.prepare(from_set.expressionQualifier());
0082:
0083: }
0084:
0085: /**
0086: * Given a HAVING clause expression, this will generate a new HAVING clause
0087: * expression with all aggregate expressions put into the given extra
0088: * function list.
0089: */
0090: private static Expression filterHavingClause(
0091: Expression having_expr, ArrayList aggregate_list,
0092: QueryContext context) {
0093: if (having_expr.size() > 1) {
0094: Operator op = (Operator) having_expr.last();
0095: // If logical, split and filter the left and right expressions
0096: Expression[] exps = having_expr.split();
0097: Expression new_left = filterHavingClause(exps[0],
0098: aggregate_list, context);
0099: Expression new_right = filterHavingClause(exps[1],
0100: aggregate_list, context);
0101: Expression expr = new Expression(new_left, op, new_right);
0102: return expr;
0103: } else {
0104: // Not logical so determine if the expression is an aggregate or not
0105: if (having_expr.hasAggregateFunction(context)) {
0106: // Has aggregate functions so we must put this expression on the
0107: // aggregate list.
0108: aggregate_list.add(having_expr);
0109: // And substitute it with a variable reference.
0110: Variable v = Variable.resolve("FUNCTIONTABLE.HAVINGAG_"
0111: + aggregate_list.size());
0112: return new Expression(v);
0113: } else {
0114: // No aggregate functions so leave it as is.
0115: return having_expr;
0116: }
0117: }
0118:
0119: }
0120:
0121: /**
0122: * Given a TableExpression, generates a TableExpressionFromSet object. This
0123: * object is used to help qualify variable references. This
0124: */
0125: static TableExpressionFromSet generateFromSet(
0126: TableSelectExpression select_expression,
0127: DatabaseConnection db) {
0128:
0129: // Get the 'from_clause' from the table expression
0130: FromClause from_clause = select_expression.from_clause;
0131:
0132: // Prepares the from_clause joining set.
0133: from_clause.getJoinSet().prepare(db);
0134:
0135: // Create a TableExpressionFromSet for this table expression
0136: TableExpressionFromSet from_set = new TableExpressionFromSet(db);
0137:
0138: // Add all tables from the 'from_clause'
0139: Iterator tables = from_clause.allTables().iterator();
0140: while (tables.hasNext()) {
0141: FromTableDef ftdef = (FromTableDef) tables.next();
0142: String unique_key = ftdef.getUniqueKey();
0143: String alias = ftdef.getAlias();
0144:
0145: // If this is a sub-query table,
0146: if (ftdef.isSubQueryTable()) {
0147: // eg. FROM ( SELECT id FROM Part )
0148: TableSelectExpression sub_query = ftdef
0149: .getTableSelectExpression();
0150: TableExpressionFromSet sub_query_from_set = generateFromSet(
0151: sub_query, db);
0152: // The aliased name of the table
0153: TableName alias_table_name = null;
0154: if (alias != null) {
0155: alias_table_name = new TableName(alias);
0156: }
0157: FromTableSubQuerySource source = new FromTableSubQuerySource(
0158: db, unique_key, sub_query, sub_query_from_set,
0159: alias_table_name);
0160: // Add to list of subquery tables to add to query,
0161: from_set.addTable(source);
0162: }
0163: // Else must be a standard query table,
0164: else {
0165: String name = ftdef.getName();
0166:
0167: // Resolve to full table name
0168: TableName table_name = db.resolveTableName(name);
0169:
0170: if (!db.tableExists(table_name)) {
0171: throw new StatementException("Table '" + table_name
0172: + "' was not found.");
0173: }
0174:
0175: TableName given_name = null;
0176: if (alias != null) {
0177: given_name = new TableName(alias);
0178: }
0179:
0180: // Get the TableQueryDef object for this table name (aliased).
0181: TableQueryDef table_query_def = db.getTableQueryDef(
0182: table_name, given_name);
0183: FromTableDirectSource source = new FromTableDirectSource(
0184: db, table_query_def, unique_key, given_name,
0185: table_name);
0186:
0187: from_set.addTable(source);
0188: }
0189: } // while (tables.hasNext())
0190:
0191: // Set up functions, aliases and exposed variables for this from set,
0192:
0193: // The list of columns being selected (SelectColumn).
0194: ArrayList columns = select_expression.columns;
0195:
0196: // For each column being selected
0197: for (int i = 0; i < columns.size(); ++i) {
0198: SelectColumn col = (SelectColumn) columns.get(i);
0199: // Is this a glob? (eg. Part.* )
0200: if (col.glob_name != null) {
0201: // Find the columns globbed and add to the 's_col_list' result.
0202: if (col.glob_name.equals("*")) {
0203: from_set.exposeAllColumns();
0204: } else {
0205: // Otherwise the glob must be of the form '[table name].*'
0206: String tname = col.glob_name.substring(0,
0207: col.glob_name.indexOf(".*"));
0208: TableName tn = TableName.resolve(tname);
0209: from_set.exposeAllColumnsFromSource(tn);
0210: }
0211: } else {
0212: // Otherwise must be a standard column reference. Note that at this
0213: // time we aren't sure if a column expression is correlated and is
0214: // referencing an outer source. This means we can't verify if the
0215: // column expression is valid or not at this point.
0216:
0217: // If this column is aliased, add it as a function reference to the
0218: // TableExpressionFromSet.
0219: String alias = col.alias;
0220: Variable v = col.expression.getVariable();
0221: boolean alias_match_v = (v != null && alias != null && from_set
0222: .stringCompare(v.getName(), alias));
0223: if (alias != null && !alias_match_v) {
0224: from_set.addFunctionRef(alias, col.expression);
0225: from_set.exposeVariable(new Variable(alias));
0226: } else if (v != null) {
0227: Variable resolved = from_set.resolveReference(v);
0228: if (resolved == null) {
0229: from_set.exposeVariable(v);
0230: } else {
0231: from_set.exposeVariable(resolved);
0232: }
0233: } else {
0234: String fun_name = col.expression.text().toString();
0235: from_set.addFunctionRef(fun_name, col.expression);
0236: from_set.exposeVariable(new Variable(fun_name));
0237: }
0238: }
0239:
0240: } // for each column selected
0241:
0242: return from_set;
0243: }
0244:
0245: /**
0246: * Forms a query plan (QueryPlanNode) from the given TableSelectExpression
0247: * and TableExpressionFromSet. The TableSelectExpression describes the
0248: * SELECT query (or sub-query), and the TableExpressionFromSet is used to
0249: * resolve expression references.
0250: * <p>
0251: * The 'order_by' argument is a list of ByColumn objects that represent
0252: * an optional ORDER BY clause. If this is null or the list is empty, no
0253: * ordering is done.
0254: */
0255: public static QueryPlanNode formQueryPlan(DatabaseConnection db,
0256: TableSelectExpression expression,
0257: TableExpressionFromSet from_set, ArrayList order_by)
0258: throws DatabaseException {
0259:
0260: QueryContext context = new DatabaseQueryContext(db);
0261:
0262: // ----- Resolve the SELECT list
0263:
0264: // What we are selecting
0265: QuerySelectColumnSet column_set = new QuerySelectColumnSet(
0266: from_set);
0267:
0268: // The list of columns being selected (SelectColumn).
0269: ArrayList columns = expression.columns;
0270:
0271: // If there are 0 columns selected, then we assume the result should
0272: // show all of the columns in the result.
0273: boolean do_subset_column = (columns.size() != 0);
0274:
0275: // For each column being selected
0276: for (int i = 0; i < columns.size(); ++i) {
0277: SelectColumn col = (SelectColumn) columns.get(i);
0278: // Is this a glob? (eg. Part.* )
0279: if (col.glob_name != null) {
0280: // Find the columns globbed and add to the 's_col_list' result.
0281: if (col.glob_name.equals("*")) {
0282: column_set.selectAllColumnsFromAllSources();
0283: } else {
0284: // Otherwise the glob must be of the form '[table name].*'
0285: String tname = col.glob_name.substring(0,
0286: col.glob_name.indexOf(".*"));
0287: TableName tn = TableName.resolve(tname);
0288: column_set.selectAllColumnsFromSource(tn);
0289: }
0290: } else {
0291: // Otherwise must be a standard column reference.
0292: column_set.selectSingleColumn(col);
0293: }
0294:
0295: } // for each column selected
0296:
0297: // Prepare the column_set,
0298: column_set.prepare(context);
0299:
0300: // -----
0301:
0302: // Resolve any numerical references in the ORDER BY list (eg.
0303: // '1' will be a reference to column 1.
0304:
0305: if (order_by != null) {
0306: ArrayList prepared_col_set = column_set.s_col_list;
0307: for (int i = 0; i < order_by.size(); ++i) {
0308: ByColumn col = (ByColumn) order_by.get(i);
0309: Expression exp = col.exp;
0310: if (exp.size() == 1) {
0311: Object last_elem = exp.last();
0312: if (last_elem instanceof TObject) {
0313: BigNumber bnum = ((TObject) last_elem)
0314: .toBigNumber();
0315: if (bnum.getScale() == 0) {
0316: int col_ref = bnum.intValue() - 1;
0317: if (col_ref >= 0
0318: && col_ref < prepared_col_set
0319: .size()) {
0320: SelectColumn scol = (SelectColumn) prepared_col_set
0321: .get(col_ref);
0322: col.exp = new Expression(
0323: scol.expression);
0324: }
0325: }
0326: }
0327: }
0328: }
0329: }
0330:
0331: // -----
0332:
0333: // Set up plans for each table in the from clause of the query. For
0334: // sub-queries, we recurse.
0335:
0336: QueryTableSetPlanner table_planner = new QueryTableSetPlanner();
0337:
0338: for (int i = 0; i < from_set.setCount(); ++i) {
0339: FromTableInterface table = from_set.getTable(i);
0340: if (table instanceof FromTableSubQuerySource) {
0341: // This represents a sub-query in the FROM clause
0342:
0343: FromTableSubQuerySource sq_table = (FromTableSubQuerySource) table;
0344: TableSelectExpression sq_expr = sq_table
0345: .getTableExpression();
0346: TableExpressionFromSet sq_from_set = sq_table
0347: .getFromSet();
0348:
0349: // Form a plan for evaluating the sub-query FROM
0350: QueryPlanNode sq_plan = formQueryPlan(db, sq_expr,
0351: sq_from_set, null);
0352:
0353: // The top should always be a SubsetNode,
0354: if (sq_plan instanceof QueryPlan.SubsetNode) {
0355: QueryPlan.SubsetNode subset_node = (QueryPlan.SubsetNode) sq_plan;
0356: subset_node.setGivenName(sq_table.getAliasedName());
0357: } else {
0358: throw new RuntimeException(
0359: "Top plan is not a SubsetNode!");
0360: }
0361:
0362: table_planner.addTableSource(sq_plan, sq_table);
0363: } else if (table instanceof FromTableDirectSource) {
0364: // This represents a direct referencable table in the FROM clause
0365:
0366: FromTableDirectSource ds_table = (FromTableDirectSource) table;
0367: TableName given_name = ds_table.getGivenTableName();
0368: TableName root_name = ds_table.getRootTableName();
0369: String aliased_name = null;
0370: if (!root_name.equals(given_name)) {
0371: aliased_name = given_name.getName();
0372: }
0373:
0374: QueryPlanNode ds_plan = ds_table
0375: .createFetchQueryPlanNode();
0376: table_planner.addTableSource(ds_plan, ds_table);
0377: } else {
0378: throw new RuntimeException(
0379: "Unknown table source instance: "
0380: + table.getClass());
0381: }
0382:
0383: }
0384:
0385: // -----
0386:
0387: // The WHERE and HAVING clauses
0388: SearchExpression where_clause = expression.where_clause;
0389: SearchExpression having_clause = expression.having_clause;
0390:
0391: // Look at the join set and resolve the ON Expression to this statement
0392: JoiningSet join_set = expression.from_clause.getJoinSet();
0393:
0394: // Perform a quick scan and see if there are any outer joins in the
0395: // expression.
0396: boolean all_inner_joins = true;
0397: for (int i = 0; i < join_set.getTableCount() - 1; ++i) {
0398: int type = join_set.getJoinType(i);
0399: if (type != JoiningSet.INNER_JOIN) {
0400: all_inner_joins = false;
0401: }
0402: }
0403:
0404: // Prepare the joins
0405: for (int i = 0; i < join_set.getTableCount() - 1; ++i) {
0406: int type = join_set.getJoinType(i);
0407: Expression on_expression = join_set.getOnExpression(i);
0408:
0409: if (all_inner_joins) {
0410: // If the whole join set is inner joins then simply move the on
0411: // expression (if there is one) to the WHERE clause.
0412: if (on_expression != null) {
0413: where_clause.appendExpression(on_expression);
0414: }
0415: } else {
0416: // Not all inner joins,
0417: if (type == JoiningSet.INNER_JOIN
0418: && on_expression == null) {
0419: // Regular join with no ON expression, so no preparation necessary
0420: } else {
0421: // Either an inner join with an ON expression, or an outer join with
0422: // ON expression
0423: if (on_expression == null) {
0424: throw new RuntimeException(
0425: "No ON expression in join.");
0426: }
0427: // Resolve the on_expression
0428: on_expression.prepare(from_set
0429: .expressionQualifier());
0430: // And set it in the planner
0431: table_planner.setJoinInfoBetweenSources(i, type,
0432: on_expression);
0433: }
0434: }
0435:
0436: }
0437:
0438: // Prepare the WHERE and HAVING clause, qualifies all variables and
0439: // prepares sub-queries.
0440: prepareSearchExpression(db, from_set, where_clause);
0441: prepareSearchExpression(db, from_set, having_clause);
0442:
0443: // Any extra AGGREGATE functions that are part of the HAVING clause that
0444: // we need to add. This is a list of a name followed by the expression
0445: // that contains the aggregate function.
0446: ArrayList extra_aggregate_functions = new ArrayList();
0447: Expression new_having_clause = null;
0448: if (having_clause.getFromExpression() != null) {
0449: new_having_clause = filterHavingClause(having_clause
0450: .getFromExpression(), extra_aggregate_functions,
0451: context);
0452: having_clause.setFromExpression(new_having_clause);
0453: }
0454:
0455: // Any GROUP BY functions,
0456: ArrayList group_by_functions = new ArrayList();
0457:
0458: // Resolve the GROUP BY variable list references in this from set
0459: ArrayList group_list_in = expression.group_by;
0460: int gsz = group_list_in.size();
0461: Variable[] group_by_list = new Variable[gsz];
0462: for (int i = 0; i < gsz; ++i) {
0463: ByColumn by_column = (ByColumn) group_list_in.get(i);
0464: Expression exp = by_column.exp;
0465: // Prepare the group by expression
0466: exp.prepare(from_set.expressionQualifier());
0467: // Is the group by variable a complex expression?
0468: Variable v = exp.getVariable();
0469:
0470: Expression group_by_expression;
0471: if (v == null) {
0472: group_by_expression = exp;
0473: } else {
0474: // Can we dereference the variable to an expression in the SELECT?
0475: group_by_expression = from_set.dereferenceAssignment(v);
0476: }
0477:
0478: if (group_by_expression != null) {
0479: if (group_by_expression.hasAggregateFunction(context)) {
0480: throw new StatementException(
0481: "Aggregate expression '"
0482: + group_by_expression.text()
0483: .toString()
0484: + "' is not allowed in GROUP BY clause.");
0485: }
0486: // Complex expression so add this to the function list.
0487: int group_by_fun_num = group_by_functions.size();
0488: group_by_functions.add(group_by_expression);
0489: v = new Variable(GROUP_BY_FUNCTION_TABLE, "#GROUPBY-"
0490: + group_by_fun_num);
0491: }
0492: group_by_list[i] = v;
0493: }
0494:
0495: // Resolve GROUP MAX variable to a reference in this from set
0496: Variable groupmax_column = expression.group_max;
0497: if (groupmax_column != null) {
0498: Variable v = from_set.resolveReference(groupmax_column);
0499: if (v == null) {
0500: throw new StatementException(
0501: "Could find GROUP MAX reference '"
0502: + groupmax_column + "'");
0503: }
0504: groupmax_column = v;
0505: }
0506:
0507: // -----
0508:
0509: // Now all the variables should be resolved and correlated variables set
0510: // up as appropriate.
0511:
0512: // If nothing in the FROM clause then simply evaluate the result of the
0513: // select
0514: if (from_set.setCount() == 0) {
0515: if (column_set.aggregate_count > 0) {
0516: throw new StatementException(
0517: "Invalid use of aggregate function in select with no FROM clause");
0518: }
0519: // Make up the lists
0520: ArrayList s_col_list = column_set.s_col_list;
0521: int sz = s_col_list.size();
0522: String[] col_names = new String[sz];
0523: Expression[] exp_list = new Expression[sz];
0524: Variable[] subset_vars = new Variable[sz];
0525: Variable[] aliases = new Variable[sz];
0526: for (int i = 0; i < sz; ++i) {
0527: SelectColumn scol = (SelectColumn) s_col_list.get(i);
0528: exp_list[i] = scol.expression;
0529: col_names[i] = scol.internal_name.getName();
0530: subset_vars[i] = new Variable(scol.internal_name);
0531: aliases[i] = new Variable(scol.resolved_name);
0532: }
0533:
0534: return new QueryPlan.SubsetNode(
0535: new QueryPlan.CreateFunctionsNode(
0536: new QueryPlan.SingleRowTableNode(),
0537: exp_list, col_names), subset_vars, aliases);
0538: }
0539:
0540: // Plan the where clause. The returned node is the plan to evaluate the
0541: // WHERE clause.
0542: QueryPlanNode node = table_planner
0543: .planSearchExpression(expression.where_clause);
0544:
0545: // Make up the functions list,
0546: ArrayList functions_list = column_set.function_col_list;
0547: int fsz = functions_list.size();
0548: ArrayList complete_fun_list = new ArrayList();
0549: for (int i = 0; i < fsz; ++i) {
0550: SelectColumn scol = (SelectColumn) functions_list.get(i);
0551: complete_fun_list.add(scol.expression);
0552: complete_fun_list.add(scol.internal_name.getName());
0553: }
0554: for (int i = 0; i < extra_aggregate_functions.size(); ++i) {
0555: complete_fun_list.add(extra_aggregate_functions.get(i));
0556: complete_fun_list.add("HAVINGAG_" + (i + 1));
0557: }
0558:
0559: int fsz2 = complete_fun_list.size() / 2;
0560: Expression[] def_fun_list = new Expression[fsz2];
0561: String[] def_fun_names = new String[fsz2];
0562: for (int i = 0; i < fsz2; ++i) {
0563: def_fun_list[i] = (Expression) complete_fun_list.get(i * 2);
0564: def_fun_names[i] = (String) complete_fun_list
0565: .get((i * 2) + 1);
0566: }
0567:
0568: // If there is more than 1 aggregate function or there is a group by
0569: // clause, then we must add a grouping plan.
0570: if (column_set.aggregate_count > 0 || gsz > 0) {
0571:
0572: // If there is no GROUP BY clause then assume the entire result is the
0573: // group.
0574: if (gsz == 0) {
0575: node = new QueryPlan.GroupNode(node, groupmax_column,
0576: def_fun_list, def_fun_names);
0577: } else {
0578: // Do we have any group by functions that need to be planned first?
0579: int gfsz = group_by_functions.size();
0580: if (gfsz > 0) {
0581: Expression[] group_fun_list = new Expression[gfsz];
0582: String[] group_fun_name = new String[gfsz];
0583: for (int i = 0; i < gfsz; ++i) {
0584: group_fun_list[i] = (Expression) group_by_functions
0585: .get(i);
0586: group_fun_name[i] = "#GROUPBY-" + i;
0587: }
0588: node = new QueryPlan.CreateFunctionsNode(node,
0589: group_fun_list, group_fun_name);
0590: }
0591:
0592: // Otherwise we provide the 'group_by_list' argument
0593: node = new QueryPlan.GroupNode(node, group_by_list,
0594: groupmax_column, def_fun_list, def_fun_names);
0595:
0596: }
0597:
0598: } else {
0599: // Otherwise no grouping is occuring. We simply need create a function
0600: // node with any functions defined in the SELECT.
0601: // Plan a FunctionsNode with the functions defined in the SELECT.
0602: if (fsz > 0) {
0603: node = new QueryPlan.CreateFunctionsNode(node,
0604: def_fun_list, def_fun_names);
0605: }
0606: }
0607:
0608: // The result column list
0609: ArrayList s_col_list = column_set.s_col_list;
0610: int sz = s_col_list.size();
0611:
0612: // Evaluate the having clause if necessary
0613: if (expression.having_clause.getFromExpression() != null) {
0614: // Before we evaluate the having expression we must substitute all the
0615: // aliased variables.
0616: Expression having_expr = having_clause.getFromExpression();
0617: substituteAliasedVariables(having_expr, s_col_list);
0618:
0619: PlanTableSource source = table_planner
0620: .getSingleTableSource();
0621: source.updatePlan(node);
0622: node = table_planner.planSearchExpression(having_clause);
0623: }
0624:
0625: // Do we have a composite select expression to process?
0626: QueryPlanNode right_composite = null;
0627: if (expression.next_composite != null) {
0628: TableSelectExpression composite_expr = expression.next_composite;
0629: // Generate the TableExpressionFromSet hierarchy for the expression,
0630: TableExpressionFromSet composite_from_set = generateFromSet(
0631: composite_expr, db);
0632:
0633: // Form the right plan
0634: right_composite = formQueryPlan(db, composite_expr,
0635: composite_from_set, null);
0636:
0637: }
0638:
0639: // Do we do a final subset column?
0640: Variable[] aliases = null;
0641: if (do_subset_column) {
0642: // Make up the lists
0643: Variable[] subset_vars = new Variable[sz];
0644: aliases = new Variable[sz];
0645: for (int i = 0; i < sz; ++i) {
0646: SelectColumn scol = (SelectColumn) s_col_list.get(i);
0647: subset_vars[i] = new Variable(scol.internal_name);
0648: aliases[i] = new Variable(scol.resolved_name);
0649: }
0650:
0651: // If we are distinct then add the DistinctNode here
0652: if (expression.distinct) {
0653: node = new QueryPlan.DistinctNode(node, subset_vars);
0654: }
0655:
0656: // Process the ORDER BY?
0657: // Note that the ORDER BY has to occur before the subset call, but
0658: // after the distinct because distinct can affect the ordering of the
0659: // result.
0660: if (right_composite == null && order_by != null) {
0661: node = planForOrderBy(node, order_by, from_set,
0662: s_col_list);
0663: }
0664:
0665: // Rename the columns as specified in the SELECT
0666: node = new QueryPlan.SubsetNode(node, subset_vars, aliases);
0667:
0668: } else {
0669: // Process the ORDER BY?
0670: if (right_composite == null && order_by != null) {
0671: node = planForOrderBy(node, order_by, from_set,
0672: s_col_list);
0673: }
0674: }
0675:
0676: // Do we have a composite to merge in?
0677: if (right_composite != null) {
0678: // For the composite
0679: node = new QueryPlan.CompositeNode(node, right_composite,
0680: expression.composite_function,
0681: expression.is_composite_all);
0682: // Final order by?
0683: if (order_by != null) {
0684: node = planForOrderBy(node, order_by, from_set,
0685: s_col_list);
0686: }
0687: // Ensure a final subset node
0688: if (!(node instanceof QueryPlan.SubsetNode)
0689: && aliases != null) {
0690: node = new QueryPlan.SubsetNode(node, aliases, aliases);
0691: }
0692:
0693: }
0694:
0695: return node;
0696: }
0697:
0698: /**
0699: * Plans an ORDER BY set. This is given its own function because we may
0700: * want to plan this at the end of a number of composite functions.
0701: * <p>
0702: * NOTE: s_col_list is optional.
0703: */
0704: public static QueryPlanNode planForOrderBy(QueryPlanNode plan,
0705: ArrayList order_by, TableExpressionFromSet from_set,
0706: ArrayList s_col_list) throws DatabaseException {
0707:
0708: TableName FUNCTION_TABLE = new TableName("FUNCTIONTABLE");
0709:
0710: // Sort on the ORDER BY clause
0711: if (order_by.size() > 0) {
0712: int sz = order_by.size();
0713: Variable[] order_list = new Variable[sz];
0714: boolean[] ascending_list = new boolean[sz];
0715:
0716: ArrayList function_orders = new ArrayList();
0717:
0718: for (int i = 0; i < sz; ++i) {
0719: ByColumn column = (ByColumn) order_by.get(i);
0720: Expression exp = column.exp;
0721: ascending_list[i] = column.ascending;
0722: Variable v = exp.getVariable();
0723: if (v != null) {
0724: Variable new_v = from_set.resolveReference(v);
0725: if (new_v == null) {
0726: throw new StatementException(
0727: "Can not resolve ORDER BY variable: "
0728: + v);
0729: }
0730: substituteAliasedVariable(new_v, s_col_list);
0731:
0732: order_list[i] = new_v;
0733: } else {
0734: // Otherwise we must be ordering by an expression such as
0735: // '0 - a'.
0736:
0737: // Resolve the expression,
0738: exp.prepare(from_set.expressionQualifier());
0739:
0740: // Make sure we substitute any aliased columns in the order by
0741: // columns.
0742: substituteAliasedVariables(exp, s_col_list);
0743:
0744: // The new ordering functions are called 'FUNCTIONTABLE.#ORDER-n'
0745: // where n is the number of the ordering expression.
0746: order_list[i] = new Variable(FUNCTION_TABLE,
0747: "#ORDER-" + function_orders.size());
0748: function_orders.add(exp);
0749: }
0750:
0751: // System.out.println(exp);
0752:
0753: }
0754:
0755: // If there are functional orderings,
0756: // For this we must define a new FunctionTable with the expressions,
0757: // then order by those columns, and then use another SubsetNode
0758: // query node.
0759: int fsz = function_orders.size();
0760: if (fsz > 0) {
0761: Expression[] funs = new Expression[fsz];
0762: String[] fnames = new String[fsz];
0763: for (int n = 0; n < fsz; ++n) {
0764: funs[n] = (Expression) function_orders.get(n);
0765: fnames[n] = "#ORDER-" + n;
0766: }
0767:
0768: if (plan instanceof QueryPlan.SubsetNode) {
0769: // If the top plan is a QueryPlan.SubsetNode then we use the
0770: // information from it to create a new SubsetNode that
0771: // doesn't include the functional orders we have attached here.
0772: QueryPlan.SubsetNode top_subset_node = (QueryPlan.SubsetNode) plan;
0773: Variable[] mapped_names = top_subset_node
0774: .getNewColumnNames();
0775:
0776: // Defines the sort functions
0777: plan = new QueryPlan.CreateFunctionsNode(plan,
0778: funs, fnames);
0779: // Then plan the sort
0780: plan = new QueryPlan.SortNode(plan, order_list,
0781: ascending_list);
0782: // Then plan the subset
0783: plan = new QueryPlan.SubsetNode(plan, mapped_names,
0784: mapped_names);
0785: } else {
0786: // Defines the sort functions
0787: plan = new QueryPlan.CreateFunctionsNode(plan,
0788: funs, fnames);
0789: // Plan the sort
0790: plan = new QueryPlan.SortNode(plan, order_list,
0791: ascending_list);
0792: }
0793:
0794: } else {
0795: // No functional orders so we only need to sort by the columns
0796: // defined.
0797: plan = new QueryPlan.SortNode(plan, order_list,
0798: ascending_list);
0799: }
0800:
0801: }
0802:
0803: return plan;
0804: }
0805:
0806: /**
0807: * Substitutes any aliased variables in the given expression with the
0808: * function name equivalent. For example, if we have a 'SELECT 3 + 4 Bah'
0809: * then resolving on variable Bah will be subsituted to the function column
0810: * that represents the result of 3 + 4.
0811: */
0812: private static void substituteAliasedVariables(
0813: Expression expression, ArrayList s_col_list) {
0814: List all_vars = expression.allVariables();
0815: for (int i = 0; i < all_vars.size(); ++i) {
0816: Variable v = (Variable) all_vars.get(i);
0817: substituteAliasedVariable(v, s_col_list);
0818: }
0819: }
0820:
0821: private static void substituteAliasedVariable(Variable v,
0822: ArrayList s_col_list) {
0823: if (s_col_list != null) {
0824: int sz = s_col_list.size();
0825: for (int n = 0; n < sz; ++n) {
0826: SelectColumn scol = (SelectColumn) s_col_list.get(n);
0827: if (v.equals(scol.resolved_name)) {
0828: v.set(scol.internal_name);
0829: }
0830: }
0831: }
0832: }
0833:
0834: // ---------- Inner classes ----------
0835:
0836: /**
0837: * A container object for the set of SelectColumn objects selected in a
0838: * query.
0839: */
0840: private static class QuerySelectColumnSet {
0841:
0842: /**
0843: * The name of the table where functions are defined.
0844: */
0845: private static TableName FUNCTION_TABLE_NAME = new TableName(
0846: "FUNCTIONTABLE");
0847:
0848: /**
0849: * The tables we are selecting from.
0850: */
0851: private TableExpressionFromSet from_set;
0852:
0853: /**
0854: * The list of SelectColumn.
0855: */
0856: ArrayList s_col_list;
0857:
0858: /**
0859: * The list of functions in this column set.
0860: */
0861: ArrayList function_col_list;
0862:
0863: /**
0864: * The current number of 'FUNCTIONTABLE.' columns in the table. This is
0865: * incremented for each custom column.
0866: */
0867: private int running_fun_number = 0;
0868:
0869: /**
0870: * The count of aggregate and constant columns included in the result set.
0871: * Aggregate columns are, (count(*), avg(cost_of) * 0.75, etc). Constant
0872: * columns are, (9 * 4, 2, (9 * 7 / 4) + 4, etc).
0873: */
0874: int aggregate_count = 0, constant_count = 0;
0875:
0876: /**
0877: * Constructor.
0878: */
0879: public QuerySelectColumnSet(TableExpressionFromSet from_set) {
0880: this .from_set = from_set;
0881: s_col_list = new ArrayList();
0882: function_col_list = new ArrayList();
0883: }
0884:
0885: /**
0886: * Adds a single SelectColumn to the list of output columns from the
0887: * query.
0888: * <p>
0889: * Note that at this point the the information in the given SelectColumn
0890: * may not be completely qualified.
0891: */
0892: void selectSingleColumn(SelectColumn col) {
0893: s_col_list.add(col);
0894: }
0895:
0896: /**
0897: * Adds all columns from the given FromTableInterface object.
0898: */
0899: void addAllFromTable(FromTableInterface table) {
0900: // Select all the tables
0901: Variable[] vars = table.allColumns();
0902: int s_col_list_max = s_col_list.size();
0903: for (int i = 0; i < vars.length; ++i) {
0904: // The Variable
0905: Variable v = vars[i];
0906:
0907: // Make up the SelectColumn
0908: SelectColumn ncol = new SelectColumn();
0909: Expression e = new Expression(v);
0910: e.text().append(v.toString());
0911: ncol.alias = null;
0912: ncol.expression = e;
0913: ncol.resolved_name = v;
0914: ncol.internal_name = v;
0915:
0916: // Add to the list of columns selected
0917: selectSingleColumn(ncol);
0918: }
0919: }
0920:
0921: /**
0922: * Adds all column from the given table object. This is used to set up the
0923: * columns that are to be viewed as the result of the select statement.
0924: */
0925: void selectAllColumnsFromSource(TableName table_name) {
0926: // Attempt to find the table in the from set.
0927: FromTableInterface table = from_set.findTable(table_name
0928: .getSchema(), table_name.getName());
0929: if (table == null) {
0930: throw new StatementException(table_name.toString()
0931: + ".* is not a valid reference.");
0932: }
0933:
0934: addAllFromTable(table);
0935: }
0936:
0937: /**
0938: * Sets up this queriable with all columns from all table sources.
0939: */
0940: void selectAllColumnsFromAllSources() {
0941: for (int p = 0; p < from_set.setCount(); ++p) {
0942: FromTableInterface table = from_set.getTable(p);
0943: addAllFromTable(table);
0944: }
0945: }
0946:
0947: /**
0948: * Adds a new hidden function into the column set. This is intended
0949: * to be used for implied functions. For example, a query may have a
0950: * function in a GROUP BY clause. It's desirable to include the function
0951: * in the column set but not in the final result.
0952: * <p>
0953: * Returns an absolute Variable object that can be used to reference
0954: * this hidden column.
0955: */
0956: Variable addHiddenFunction(String fun_alias,
0957: Expression function, QueryContext context) {
0958: SelectColumn scol = new SelectColumn();
0959: scol.resolved_name = new Variable(fun_alias);
0960: scol.alias = fun_alias;
0961: scol.expression = function;
0962: scol.internal_name = new Variable(FUNCTION_TABLE_NAME,
0963: fun_alias);
0964:
0965: // If this is an aggregate column then add to aggregate count.
0966: if (function.hasAggregateFunction(context)) {
0967: ++aggregate_count;
0968: }
0969: // If this is a constant column then add to constant cound.
0970: else if (function.isConstant()) {
0971: ++constant_count;
0972: }
0973:
0974: function_col_list.add(scol);
0975:
0976: return scol.internal_name;
0977: }
0978:
0979: /**
0980: * Prepares the given SelectColumn by fully qualifying the expression and
0981: * allocating it correctly within this context.
0982: */
0983: private void prepareSelectColumn(SelectColumn col,
0984: QueryContext context) throws DatabaseException {
0985: // Check to see if we have any Select statements in the
0986: // Expression. This is necessary, because we can't have a
0987: // sub-select evaluated during list table downloading.
0988: List exp_elements = col.expression.allElements();
0989: for (int n = 0; n < exp_elements.size(); ++n) {
0990: if (exp_elements.get(n) instanceof TableSelectExpression) {
0991: throw new StatementException(
0992: "Sub-query not allowed in column list.");
0993: }
0994: }
0995:
0996: // First fully qualify the select expression
0997: col.expression.prepare(from_set.expressionQualifier());
0998:
0999: // If the expression isn't a simple variable, then add to
1000: // function list.
1001: Variable v = col.expression.getVariable();
1002: if (v == null) {
1003: // This means we have a complex expression.
1004:
1005: ++running_fun_number;
1006: String agg_str = Integer.toString(running_fun_number);
1007:
1008: // If this is an aggregate column then add to aggregate count.
1009: if (col.expression.hasAggregateFunction(context)) {
1010: ++aggregate_count;
1011: // Add '_A' code to end of internal name of column to signify this is
1012: // an aggregate column
1013: agg_str += "_A";
1014: }
1015: // If this is a constant column then add to constant cound.
1016: else if (col.expression.isConstant()) {
1017: ++constant_count;
1018: } else {
1019: // Must be an expression with variable's embedded ( eg.
1020: // (part_id + 3) * 4, (id * value_of_part), etc )
1021: }
1022: function_col_list.add(col);
1023:
1024: col.internal_name = new Variable(FUNCTION_TABLE_NAME,
1025: agg_str);
1026: if (col.alias == null) {
1027: col.alias = new String(col.expression.text());
1028: }
1029: col.resolved_name = new Variable(col.alias);
1030:
1031: } else {
1032: // Not a complex expression
1033: col.internal_name = v;
1034: if (col.alias == null) {
1035: col.resolved_name = v;
1036: } else {
1037: col.resolved_name = new Variable(col.alias);
1038: }
1039: }
1040:
1041: }
1042:
1043: /**
1044: * Resolves all variable objects in each column.
1045: */
1046: void prepare(QueryContext context) throws DatabaseException {
1047: // Prepare each of the columns selected.
1048: // NOTE: A side-effect of this is that it qualifies all the Expressions
1049: // that are functions in TableExpressionFromSet. After this section,
1050: // we can dereference variables for their function Expression.
1051: for (int i = 0; i < s_col_list.size(); ++i) {
1052: SelectColumn column = (SelectColumn) s_col_list.get(i);
1053: prepareSelectColumn(column, context);
1054: }
1055: }
1056:
1057: }
1058:
1059: /**
1060: * A table set planner that maintains a list of table dependence lists and
1061: * progressively constructs a plan tree from the bottom up.
1062: */
1063: private static class QueryTableSetPlanner {
1064:
1065: /**
1066: * The list of PlanTableSource objects for each source being planned.
1067: */
1068: private ArrayList table_list;
1069:
1070: /**
1071: * If a join has occurred since the planner was constructed or copied then
1072: * this is set to true.
1073: */
1074: private boolean has_join_occurred;
1075:
1076: /**
1077: * Constructor.
1078: */
1079: public QueryTableSetPlanner() {
1080: this .table_list = new ArrayList();
1081: has_join_occurred = false;
1082: }
1083:
1084: /**
1085: * Add a PlanTableSource to this planner.
1086: */
1087: private void addPlanTableSource(PlanTableSource source) {
1088: table_list.add(source);
1089: has_join_occurred = true;
1090: }
1091:
1092: /**
1093: * Returns true if a join has occurred ('table_list' has been modified).
1094: */
1095: public boolean hasJoinOccured() {
1096: return has_join_occurred;
1097: }
1098:
1099: /**
1100: * Adds a new table source to the planner given a Plan that 'creates'
1101: * the source, and a FromTableInterface that describes the source created
1102: * by the plan.
1103: */
1104: public void addTableSource(QueryPlanNode plan,
1105: FromTableInterface from_def) {
1106: Variable[] all_cols = from_def.allColumns();
1107: String[] unique_names = new String[] { from_def
1108: .getUniqueName() };
1109: addPlanTableSource(new PlanTableSource(plan, all_cols,
1110: unique_names));
1111: }
1112:
1113: /**
1114: * Returns the index of the given PlanTableSource in the table list.
1115: */
1116: private int indexOfPlanTableSource(PlanTableSource source) {
1117: int sz = table_list.size();
1118: for (int i = 0; i < sz; ++i) {
1119: if (table_list.get(i) == source) {
1120: return i;
1121: }
1122: }
1123: return -1;
1124: }
1125:
1126: /**
1127: * Links the last added table source to the previous added table source
1128: * through this joining information.
1129: * <p>
1130: * 'between_index' represents the point in between the table sources that
1131: * the join should be setup for. For example, to set the join between
1132: * TableSource 0 and 1, use 0 as the between index. A between index of 3
1133: * represents the join between TableSource index 2 and 2.
1134: */
1135: public void setJoinInfoBetweenSources(int between_index,
1136: int join_type, Expression on_expr) {
1137: PlanTableSource plan_left = (PlanTableSource) table_list
1138: .get(between_index);
1139: PlanTableSource plan_right = (PlanTableSource) table_list
1140: .get(between_index + 1);
1141: plan_left.setRightJoinInfo(plan_right, join_type, on_expr);
1142: plan_right.setLeftJoinInfo(plan_left, join_type, on_expr);
1143: }
1144:
1145: /**
1146: * Forms a new PlanTableSource that's the concatination of the given
1147: * two PlanTableSource objects.
1148: */
1149: public static PlanTableSource concatTableSources(
1150: PlanTableSource left, PlanTableSource right,
1151: QueryPlanNode plan) {
1152:
1153: // Merge the variable list
1154: Variable[] new_var_list = new Variable[left.var_list.length
1155: + right.var_list.length];
1156: int i = 0;
1157: for (int n = 0; n < left.var_list.length; ++n) {
1158: new_var_list[i] = left.var_list[n];
1159: ++i;
1160: }
1161: for (int n = 0; n < right.var_list.length; ++n) {
1162: new_var_list[i] = right.var_list[n];
1163: ++i;
1164: }
1165:
1166: // Merge the unique table names list
1167: String[] new_unique_list = new String[left.unique_names.length
1168: + right.unique_names.length];
1169: i = 0;
1170: for (int n = 0; n < left.unique_names.length; ++n) {
1171: new_unique_list[i] = left.unique_names[n];
1172: ++i;
1173: }
1174: for (int n = 0; n < right.unique_names.length; ++n) {
1175: new_unique_list[i] = right.unique_names[n];
1176: ++i;
1177: }
1178:
1179: // Return the new table source plan.
1180: return new PlanTableSource(plan, new_var_list,
1181: new_unique_list);
1182: }
1183:
1184: /**
1185: * Joins two tables when a plan is generated for joining the two tables.
1186: */
1187: public PlanTableSource mergeTables(PlanTableSource left,
1188: PlanTableSource right, QueryPlanNode merge_plan) {
1189:
1190: // Remove the sources from the table list.
1191: table_list.remove(left);
1192: table_list.remove(right);
1193: // Add the concatination of the left and right tables.
1194: PlanTableSource c_plan = concatTableSources(left, right,
1195: merge_plan);
1196: c_plan.setJoinInfoMergedBetween(left, right);
1197: c_plan.setUpdated();
1198: addPlanTableSource(c_plan);
1199: // Return the name plan
1200: return c_plan;
1201: }
1202:
1203: /**
1204: * Finds and returns the PlanTableSource in the list of tables that
1205: * contains the given Variable reference.
1206: */
1207: public PlanTableSource findTableSource(Variable ref) {
1208: int sz = table_list.size();
1209:
1210: // If there is only 1 plan then assume the variable is in there.
1211: if (sz == 1) {
1212: return (PlanTableSource) table_list.get(0);
1213: }
1214:
1215: for (int i = 0; i < sz; ++i) {
1216: PlanTableSource source = (PlanTableSource) table_list
1217: .get(i);
1218: if (source.containsVariable(ref)) {
1219: return source;
1220: }
1221: }
1222: throw new RuntimeException(
1223: "Unable to find table with variable reference: "
1224: + ref);
1225: }
1226:
1227: /**
1228: * Finds a common PlanTableSource that contains the list of variables
1229: * given. If the list is 0 or there is no common source then null is
1230: * returned.
1231: */
1232: public PlanTableSource findCommonTableSource(List var_list) {
1233: if (var_list.size() == 0) {
1234: return null;
1235: }
1236:
1237: PlanTableSource plan = findTableSource((Variable) var_list
1238: .get(0));
1239: int i = 1;
1240: int sz = var_list.size();
1241: while (i < sz) {
1242: PlanTableSource p2 = findTableSource((Variable) var_list
1243: .get(i));
1244: if (plan != p2) {
1245: return null;
1246: }
1247: ++i;
1248: }
1249:
1250: return plan;
1251: }
1252:
1253: /**
1254: * Finds and returns the PlanTableSource in the list of table that
1255: * contains the given unique key name.
1256: */
1257: public PlanTableSource findTableSourceWithUniqueKey(String key) {
1258: int sz = table_list.size();
1259: for (int i = 0; i < sz; ++i) {
1260: PlanTableSource source = (PlanTableSource) table_list
1261: .get(i);
1262: if (source.containsUniqueKey(key)) {
1263: return source;
1264: }
1265: }
1266: throw new RuntimeException(
1267: "Unable to find table with unique key: " + key);
1268: }
1269:
1270: /**
1271: * Returns the single PlanTableSource for this planner.
1272: */
1273: private PlanTableSource getSingleTableSource() {
1274: if (table_list.size() != 1) {
1275: throw new RuntimeException("Not a single table source.");
1276: }
1277: return (PlanTableSource) table_list.get(0);
1278: }
1279:
1280: /**
1281: * Sets a CachePointNode with the given key on all of the plan table
1282: * sources in 'table_list'. Note that this does not change the 'update'
1283: * status of the table sources. If there is currently a CachePointNode
1284: * on any of the sources then no update is made.
1285: */
1286: private void setCachePoints() {
1287: int sz = table_list.size();
1288: for (int i = 0; i < sz; ++i) {
1289: PlanTableSource plan = (PlanTableSource) table_list
1290: .get(i);
1291: if (!(plan.getPlan() instanceof QueryPlan.CachePointNode)) {
1292: plan.plan = new QueryPlan.CachePointNode(plan
1293: .getPlan());
1294: }
1295: }
1296: }
1297:
1298: /**
1299: * Creates a single PlanTableSource that encapsulates all the given
1300: * variables in a single table. If this means a table must be joined with
1301: * another using the natural join conditions then this happens here.
1302: * <p>
1303: * The intention of this function is to produce a plan that encapsulates
1304: * all the variables needed to perform a specific evaluation.
1305: * <p>
1306: * Note, this has the potential to cause 'natural join' situations which
1307: * are bad performance. It is a good idea to perform joins using other
1308: * methods before this is used.
1309: * <p>
1310: * Note, this will change the 'table_list' variable in this class if tables
1311: * are joined.
1312: */
1313: private PlanTableSource joinAllPlansWithVariables(List all_vars) {
1314: // Collect all the plans that encapsulate these variables.
1315: ArrayList touched_plans = new ArrayList();
1316: int sz = all_vars.size();
1317: for (int i = 0; i < sz; ++i) {
1318: Variable v = (Variable) all_vars.get(i);
1319: PlanTableSource plan = findTableSource(v);
1320: if (!touched_plans.contains(plan)) {
1321: touched_plans.add(plan);
1322: }
1323: }
1324: // Now 'touched_plans' contains a list of PlanTableSource for each
1325: // plan to be joined.
1326:
1327: return joinAllPlansToSingleSource(touched_plans);
1328: }
1329:
1330: /**
1331: * Returns true if it is possible to naturally join the two plans. Two
1332: * plans can be joined under the following sitations;
1333: * 1) The left or right plan of the first source points to the second
1334: * source.
1335: * 2) Either one has no left plan and the other has no right plan, or
1336: * one has no right plan and the other has no left plan.
1337: */
1338: private int canPlansBeNaturallyJoined(PlanTableSource plan1,
1339: PlanTableSource plan2) {
1340: if (plan1.left_plan == plan2 || plan1.right_plan == plan2) {
1341: return 0;
1342: } else if (plan1.left_plan != null
1343: && plan2.left_plan != null) {
1344: // This is a left clash
1345: return 2;
1346: } else if (plan1.right_plan != null
1347: && plan2.right_plan != null) {
1348: // This is a right clash
1349: return 1;
1350: } else if ((plan1.left_plan == null && plan2.right_plan == null)
1351: || (plan1.right_plan == null && plan2.left_plan == null)) {
1352: // This means a merge between the plans is fine
1353: return 0;
1354: } else {
1355: // Must be a left and right clash
1356: return 2;
1357: }
1358: }
1359:
1360: /**
1361: * Given a list of PlanTableSource objects, this will produce a plan that
1362: * naturally joins all the tables together into a single plan. The
1363: * join algorithm used is determined by the information in the FROM clause.
1364: * An OUTER JOIN, for example, will join depending on the conditions
1365: * provided in the ON clause. If no explicit join method is provided then
1366: * a natural join will be planned.
1367: * <p>
1368: * Care should be taken with this because this method can produce natural
1369: * joins which are often optimized out by more appropriate join expressions
1370: * that can be processed before this is called.
1371: * <p>
1372: * Note, this will change the 'table_list' variable in this class if tables
1373: * are joined.
1374: * <p>
1375: * Returns null if no plans are provided.
1376: */
1377: private PlanTableSource joinAllPlansToSingleSource(
1378: List all_plans) {
1379: // If there are no plans then return null
1380: if (all_plans.size() == 0) {
1381: return null;
1382: }
1383: // Return early if there is only 1 table.
1384: else if (all_plans.size() == 1) {
1385: return (PlanTableSource) all_plans.get(0);
1386: }
1387:
1388: // Make a working copy of the plan list.
1389: ArrayList working_plan_list = new ArrayList(all_plans
1390: .size());
1391: for (int i = 0; i < all_plans.size(); ++i) {
1392: working_plan_list.add(all_plans.get(i));
1393: }
1394:
1395: // We go through each plan in turn.
1396: while (working_plan_list.size() > 1) {
1397: PlanTableSource left_plan = (PlanTableSource) working_plan_list
1398: .get(0);
1399: PlanTableSource right_plan = (PlanTableSource) working_plan_list
1400: .get(1);
1401: // First we need to determine if the left and right plan can be
1402: // naturally joined.
1403: int status = canPlansBeNaturallyJoined(left_plan,
1404: right_plan);
1405: if (status == 0) {
1406: // Yes they can so join them
1407: PlanTableSource new_plan = naturallyJoinPlans(
1408: left_plan, right_plan);
1409: // Remove the left and right plan from the list and add the new plan
1410: working_plan_list.remove(left_plan);
1411: working_plan_list.remove(right_plan);
1412: working_plan_list.add(0, new_plan);
1413: } else if (status == 1) {
1414: // No we can't because of a right join clash, so we join the left
1415: // plan right in hopes of resolving the clash.
1416: PlanTableSource new_plan = naturallyJoinPlans(
1417: left_plan, left_plan.right_plan);
1418: working_plan_list.remove(left_plan);
1419: working_plan_list.remove(left_plan.right_plan);
1420: working_plan_list.add(0, new_plan);
1421: } else if (status == 2) {
1422: // No we can't because of a left join clash, so we join the left
1423: // plan left in hopes of resolving the clash.
1424: PlanTableSource new_plan = naturallyJoinPlans(
1425: left_plan, left_plan.left_plan);
1426: working_plan_list.remove(left_plan);
1427: working_plan_list.remove(left_plan.left_plan);
1428: working_plan_list.add(0, new_plan);
1429: } else {
1430: throw new RuntimeException("Unknown status: "
1431: + status);
1432: }
1433: }
1434:
1435: // Return the working plan of the merged tables.
1436: return (PlanTableSource) working_plan_list.get(0);
1437:
1438: }
1439:
1440: /**
1441: * Naturally joins two PlanTableSource objects in this planner. When this
1442: * method returns the actual plans will be joined together. This method
1443: * modifies 'table_list'.
1444: */
1445: private PlanTableSource naturallyJoinPlans(
1446: PlanTableSource plan1, PlanTableSource plan2) {
1447: int join_type;
1448: Expression on_expr;
1449: PlanTableSource left_plan, right_plan;
1450: // Are the plans linked by common join information?
1451: if (plan1.right_plan == plan2) {
1452: join_type = plan1.right_join_type;
1453: on_expr = plan1.right_on_expr;
1454: left_plan = plan1;
1455: right_plan = plan2;
1456: } else if (plan1.left_plan == plan2) {
1457: join_type = plan1.left_join_type;
1458: on_expr = plan1.left_on_expr;
1459: left_plan = plan2;
1460: right_plan = plan1;
1461: } else {
1462: // Assertion - make sure no join clashes!
1463: if ((plan1.left_plan != null && plan2.left_plan != null)
1464: || (plan1.right_plan != null && plan2.right_plan != null)) {
1465: throw new RuntimeException(
1466: "Assertion failed - plans can not be naturally join because "
1467: + "the left/right join plans clash.");
1468: }
1469:
1470: // Else we must assume a non-dependant join (not an outer join).
1471: // Perform a natural join
1472: QueryPlanNode node = new QueryPlan.NaturalJoinNode(
1473: plan1.getPlan(), plan2.getPlan());
1474: return mergeTables(plan1, plan2, node);
1475: }
1476:
1477: // This means plan1 and plan2 are linked by a common join and ON
1478: // expression which we evaluate now.
1479: boolean outer_join;
1480: if (join_type == JoiningSet.LEFT_OUTER_JOIN) {
1481: // Mark the left plan
1482: left_plan.updatePlan(new QueryPlan.MarkerNode(left_plan
1483: .getPlan(), "OUTER_JOIN"));
1484: outer_join = true;
1485: } else if (join_type == JoiningSet.RIGHT_OUTER_JOIN) {
1486: // Mark the right plan
1487: right_plan.updatePlan(new QueryPlan.MarkerNode(
1488: right_plan.getPlan(), "OUTER_JOIN"));
1489: outer_join = true;
1490: } else if (join_type == JoiningSet.INNER_JOIN) {
1491: // Inner join with ON expression
1492: outer_join = false;
1493: } else {
1494: throw new RuntimeException("Join type (" + join_type
1495: + ") is not supported.");
1496: }
1497:
1498: // Make a Planner object for joining these plans.
1499: QueryTableSetPlanner planner = new QueryTableSetPlanner();
1500: planner.addPlanTableSource(left_plan.copy());
1501: planner.addPlanTableSource(right_plan.copy());
1502:
1503: // planner.printDebugInfo();
1504:
1505: // Evaluate the on expression
1506: QueryPlanNode node = planner.logicalEvaluate(on_expr);
1507: // If outer join add the left outer join node
1508: if (outer_join) {
1509: node = new QueryPlan.LeftOuterJoinNode(node,
1510: "OUTER_JOIN");
1511: }
1512: // And merge the plans in this set with the new node.
1513: return mergeTables(plan1, plan2, node);
1514:
1515: // System.out.println("OUTER JOIN: " + on_expr);
1516: // throw new RuntimeException("PENDING");
1517:
1518: }
1519:
1520: /**
1521: * Plans all outer joins.
1522: * <p>
1523: * Note, this will change the 'table_list' variable in this class if tables
1524: * are joined.
1525: */
1526: private void planAllOuterJoins() {
1527: // new Error().printStackTrace();
1528:
1529: int sz = table_list.size();
1530: if (sz <= 1) {
1531: return;
1532: }
1533:
1534: // Make a working copy of the plan list.
1535: ArrayList working_plan_list = new ArrayList(sz);
1536: for (int i = 0; i < sz; ++i) {
1537: working_plan_list.add(table_list.get(i));
1538: }
1539:
1540: // System.out.println("----");
1541:
1542: PlanTableSource plan1 = (PlanTableSource) working_plan_list
1543: .get(0);
1544: for (int i = 1; i < sz; ++i) {
1545: PlanTableSource plan2 = (PlanTableSource) working_plan_list
1546: .get(i);
1547:
1548: // System.out.println("Joining: " + plan1);
1549: // System.out.println(" with: " + plan2);
1550:
1551: if (plan1.right_plan == plan2) {
1552: plan1 = naturallyJoinPlans(plan1, plan2);
1553: } else {
1554: plan1 = plan2;
1555: }
1556: }
1557:
1558: }
1559:
1560: /**
1561: * Naturally joins all remaining tables sources to make a final single
1562: * plan which is returned.
1563: * <p>
1564: * Note, this will change the 'table_list' variable in this class if tables
1565: * are joined.
1566: */
1567: private PlanTableSource naturalJoinAll() {
1568: int sz = table_list.size();
1569: if (sz == 1) {
1570: return (PlanTableSource) table_list.get(0);
1571: }
1572:
1573: // Produce a plan that naturally joins all tables.
1574: return joinAllPlansToSingleSource(table_list);
1575: }
1576:
1577: /**
1578: * Convenience class that stores an expression to evaluate for a table.
1579: */
1580: private static class SingleVarPlan {
1581: PlanTableSource table_source;
1582: Variable single_var;
1583: Variable variable;
1584: Expression expression;
1585: }
1586:
1587: /**
1588: * Adds a single var plan to the given list.
1589: */
1590: private void addSingleVarPlanTo(ArrayList list,
1591: PlanTableSource table, Variable variable,
1592: Variable single_var, Expression[] exp_parts, Operator op) {
1593: Expression exp = new Expression(exp_parts[0], op,
1594: exp_parts[1]);
1595: // Is this source in the list already?
1596: int sz = list.size();
1597: for (int i = 0; i < sz; ++i) {
1598: SingleVarPlan plan = (SingleVarPlan) list.get(i);
1599: if (plan.table_source == table
1600: && (variable == null || plan.variable
1601: .equals(variable))) {
1602: // Append to end of current expression
1603: plan.variable = variable;
1604: plan.expression = new Expression(plan.expression,
1605: Operator.get("and"), exp);
1606: return;
1607: }
1608: }
1609: // Didn't find so make a new entry in the list.
1610: SingleVarPlan plan = new SingleVarPlan();
1611: plan.table_source = table;
1612: plan.variable = variable;
1613: plan.single_var = single_var;
1614: plan.expression = exp;
1615: list.add(plan);
1616: return;
1617: }
1618:
1619: // ----
1620:
1621: // An expression plan for a constant expression. These are very
1622: // optimizable indeed.
1623: private class ConstantExpressionPlan extends ExpressionPlan {
1624: private Expression expression;
1625:
1626: public ConstantExpressionPlan(Expression e) {
1627: expression = e;
1628: }
1629:
1630: public void addToPlanTree() {
1631: // Each currently open branch must have this constant expression added
1632: // to it.
1633: for (int n = 0; n < table_list.size(); ++n) {
1634: PlanTableSource plan = (PlanTableSource) table_list
1635: .get(n);
1636: plan.updatePlan(new QueryPlan.ConstantSelectNode(
1637: plan.getPlan(), expression));
1638: }
1639: }
1640: }
1641:
1642: private class SimpleSelectExpressionPlan extends ExpressionPlan {
1643: private Variable single_var;
1644: private Operator op;
1645: private Expression expression;
1646:
1647: public SimpleSelectExpressionPlan(Variable v, Operator op,
1648: Expression e) {
1649: single_var = v;
1650: this .op = op;
1651: expression = e;
1652: }
1653:
1654: public void addToPlanTree() {
1655: // Find the table source for this variable
1656: PlanTableSource table_source = findTableSource(single_var);
1657: table_source.updatePlan(new QueryPlan.SimpleSelectNode(
1658: table_source.getPlan(), single_var, op,
1659: expression));
1660: }
1661: }
1662:
1663: private class SimpleSingleExpressionPlan extends ExpressionPlan {
1664: private Variable single_var;
1665: private Expression expression;
1666:
1667: public SimpleSingleExpressionPlan(Variable v, Expression e) {
1668: single_var = v;
1669: expression = e;
1670: }
1671:
1672: public void addToPlanTree() {
1673: // Find the table source for this variable
1674: PlanTableSource table_source = findTableSource(single_var);
1675: table_source.updatePlan(new QueryPlan.RangeSelectNode(
1676: table_source.getPlan(), expression));
1677: }
1678: }
1679:
1680: private class ComplexSingleExpressionPlan extends
1681: ExpressionPlan {
1682: private Variable single_var;
1683: private Expression expression;
1684:
1685: public ComplexSingleExpressionPlan(Variable v, Expression e) {
1686: single_var = v;
1687: expression = e;
1688: }
1689:
1690: public void addToPlanTree() {
1691: // Find the table source for this variable
1692: PlanTableSource table_source = findTableSource(single_var);
1693: table_source
1694: .updatePlan(new QueryPlan.ExhaustiveSelectNode(
1695: table_source.getPlan(), expression));
1696: }
1697: }
1698:
1699: private class SimplePatternExpressionPlan extends
1700: ExpressionPlan {
1701: private Variable single_var;
1702: private Expression expression;
1703:
1704: public SimplePatternExpressionPlan(Variable v, Expression e) {
1705: single_var = v;
1706: expression = e;
1707: }
1708:
1709: public void addToPlanTree() {
1710: // Find the table source for this variable
1711: PlanTableSource table_source = findTableSource(single_var);
1712: table_source
1713: .updatePlan(new QueryPlan.SimplePatternSelectNode(
1714: table_source.getPlan(), expression));
1715: }
1716: }
1717:
1718: private class ExhaustiveSelectExpressionPlan extends
1719: ExpressionPlan {
1720: private Expression expression;
1721:
1722: public ExhaustiveSelectExpressionPlan(Expression e) {
1723: expression = e;
1724: }
1725:
1726: public void addToPlanTree() {
1727: // Get all the variables of this expression.
1728: List all_vars = expression.allVariables();
1729: // Find the table source for this set of variables.
1730: PlanTableSource table_source = joinAllPlansWithVariables(all_vars);
1731: // Perform the exhaustive select
1732: table_source
1733: .updatePlan(new QueryPlan.ExhaustiveSelectNode(
1734: table_source.getPlan(), expression));
1735: }
1736: }
1737:
1738: private class ExhaustiveSubQueryExpressionPlan extends
1739: ExpressionPlan {
1740: private List all_vars;
1741: private Expression expression;
1742:
1743: public ExhaustiveSubQueryExpressionPlan(List vars,
1744: Expression e) {
1745: this .all_vars = vars;
1746: this .expression = e;
1747: }
1748:
1749: public void addToPlanTree() {
1750: PlanTableSource table_source = joinAllPlansWithVariables(all_vars);
1751: // Update the plan
1752: table_source
1753: .updatePlan(new QueryPlan.ExhaustiveSelectNode(
1754: table_source.getPlan(), expression));
1755:
1756: }
1757: }
1758:
1759: private class SimpleSubQueryExpressionPlan extends
1760: ExpressionPlan {
1761: private Expression expression;
1762:
1763: public SimpleSubQueryExpressionPlan(Expression e) {
1764: this .expression = e;
1765: }
1766:
1767: public void addToPlanTree() {
1768: Operator op = (Operator) expression.last();
1769: Expression[] exps = expression.split();
1770: Variable left_var = exps[0].getVariable();
1771: QueryPlanNode right_plan = exps[1].getQueryPlanNode();
1772:
1773: // Find the table source for this variable
1774: PlanTableSource table_source = findTableSource(left_var);
1775: // The left branch
1776: QueryPlanNode left_plan = table_source.getPlan();
1777: // Update the plan
1778: table_source
1779: .updatePlan(new QueryPlan.NonCorrelatedAnyAllNode(
1780: left_plan, right_plan,
1781: new Variable[] { left_var }, op));
1782: }
1783: }
1784:
1785: private class ExhaustiveJoinExpressionPlan extends
1786: ExpressionPlan {
1787: private Expression expression;
1788:
1789: public ExhaustiveJoinExpressionPlan(Expression e) {
1790: this .expression = e;
1791: }
1792:
1793: public void addToPlanTree() {
1794: // Get all the variables in the expression
1795: List all_vars = expression.allVariables();
1796: // Merge it into one plan (possibly performing natural joins).
1797: PlanTableSource all_plan = joinAllPlansWithVariables(all_vars);
1798: // And perform the exhaustive select,
1799: all_plan.updatePlan(new QueryPlan.ExhaustiveSelectNode(
1800: all_plan.getPlan(), expression));
1801: }
1802: }
1803:
1804: private class StandardJoinExpressionPlan extends ExpressionPlan {
1805: private Expression expression;
1806:
1807: public StandardJoinExpressionPlan(Expression e) {
1808: this .expression = e;
1809: }
1810:
1811: public void addToPlanTree() {
1812:
1813: // Get the expression with the multiple variables
1814: Expression[] exps = expression.split();
1815:
1816: // Get the list of variables in the left hand and right hand side
1817: Variable lhs_v = exps[0].getVariable();
1818: Variable rhs_v = exps[1].getVariable();
1819: List lhs_vars = exps[0].allVariables();
1820: List rhs_vars = exps[1].allVariables();
1821:
1822: // Get the operator
1823: Operator op = (Operator) expression.last();
1824:
1825: // Get the left and right plan for the variables in the expression.
1826: // Note that these methods may perform natural joins on the table.
1827: PlanTableSource lhs_plan = joinAllPlansWithVariables(lhs_vars);
1828: PlanTableSource rhs_plan = joinAllPlansWithVariables(rhs_vars);
1829:
1830: // If the lhs and rhs plans are different (there is a joining
1831: // situation).
1832: if (lhs_plan != rhs_plan) {
1833:
1834: // If either the LHS or the RHS is a single variable then we can
1835: // optimize the join.
1836:
1837: if (lhs_v != null || rhs_v != null) {
1838: // If rhs_v is a single variable and lhs_v is not then we must
1839: // reverse the expression.
1840: QueryPlan.JoinNode join_node;
1841: if (lhs_v == null && rhs_v != null) {
1842: // Reverse the expressions and the operator
1843: join_node = new QueryPlan.JoinNode(rhs_plan
1844: .getPlan(), lhs_plan.getPlan(),
1845: rhs_v, op.reverse(), exps[0]);
1846: mergeTables(rhs_plan, lhs_plan, join_node);
1847: } else {
1848: // Otherwise, use it as it is.
1849: join_node = new QueryPlan.JoinNode(lhs_plan
1850: .getPlan(), rhs_plan.getPlan(),
1851: lhs_v, op, exps[1]);
1852: mergeTables(lhs_plan, rhs_plan, join_node);
1853: }
1854: // Return because we are done
1855: return;
1856: }
1857:
1858: } // if lhs and rhs plans are different
1859:
1860: // If we get here either both the lhs and rhs are complex expressions
1861: // or the lhs and rhs of the variable are not different plans, or
1862: // the operator is not a conditional. Either way, we must evaluate
1863: // this via a natural join of the variables involved coupled with an
1864: // exhaustive select. These types of queries are poor performing.
1865:
1866: // Get all the variables in the expression
1867: List all_vars = expression.allVariables();
1868: // Merge it into one plan (possibly performing natural joins).
1869: PlanTableSource all_plan = joinAllPlansWithVariables(all_vars);
1870: // And perform the exhaustive select,
1871: all_plan.updatePlan(new QueryPlan.ExhaustiveSelectNode(
1872: all_plan.getPlan(), expression));
1873: }
1874: }
1875:
1876: private class SubLogicExpressionPlan extends ExpressionPlan {
1877: private Expression expression;
1878:
1879: public SubLogicExpressionPlan(Expression e) {
1880: this .expression = e;
1881: }
1882:
1883: public void addToPlanTree() {
1884: planForExpression(expression);
1885: }
1886: }
1887:
1888: /**
1889: * Evaluates a list of constant conditional exressions of the form
1890: * '3 + 2 = 0', 'true = true', etc.
1891: */
1892: void evaluateConstants(ArrayList constant_vars,
1893: ArrayList evaluate_order) {
1894: // For each constant variable
1895: for (int i = 0; i < constant_vars.size(); ++i) {
1896: Expression expr = (Expression) constant_vars.get(i);
1897: // Add the exression plan
1898: ExpressionPlan exp_plan = new ConstantExpressionPlan(
1899: expr);
1900: exp_plan.setOptimizableValue(0f);
1901: evaluate_order.add(exp_plan);
1902: }
1903: }
1904:
1905: /**
1906: * Evaluates a list of single variable conditional expressions of the
1907: * form a = 3, a > 1 + 2, a - 2 = 1, 3 = a, concat(a, 'a') = '3a', etc.
1908: * The rule is there must be only one variable, a conditional operator,
1909: * and a constant on one side.
1910: * <p>
1911: * This method takes the list and modifies the plan as necessary.
1912: */
1913: void evaluateSingles(ArrayList single_vars,
1914: ArrayList evaluate_order) {
1915:
1916: // The list of simple expression plans (lhs = single)
1917: ArrayList simple_plan_list = new ArrayList();
1918: // The list of complex function expression plans (lhs = expression)
1919: ArrayList complex_plan_list = new ArrayList();
1920:
1921: // For each single variable expression
1922: for (int i = 0; i < single_vars.size(); ++i) {
1923: Expression andexp = (Expression) single_vars.get(i);
1924: // The operator
1925: Operator op = (Operator) andexp.last();
1926:
1927: // Split the expression
1928: Expression[] exps = andexp.split();
1929: // The single var
1930: Variable single_var;
1931:
1932: // If the operator is a sub-query we must be of the form,
1933: // 'a in ( 1, 2, 3 )'
1934: if (op.isSubQuery()) {
1935: single_var = exps[0].getVariable();
1936: if (single_var != null) {
1937: ExpressionPlan exp_plan = new SimpleSelectExpressionPlan(
1938: single_var, op, exps[1]);
1939: exp_plan.setOptimizableValue(0.2f);
1940: evaluate_order.add(exp_plan);
1941: } else {
1942: single_var = (Variable) exps[0].allVariables()
1943: .get(0);
1944: ExpressionPlan exp_plan = new ComplexSingleExpressionPlan(
1945: single_var, andexp);
1946: exp_plan.setOptimizableValue(0.8f);
1947: evaluate_order.add(exp_plan);
1948: }
1949: } else {
1950: // Put the variable on the LHS, constant on the RHS
1951: List all_vars = exps[0].allVariables();
1952: if (all_vars.size() == 0) {
1953: // Reverse the expressions and the operator
1954: Expression temp_exp = exps[0];
1955: exps[0] = exps[1];
1956: exps[1] = temp_exp;
1957: op = op.reverse();
1958: single_var = (Variable) exps[0].allVariables()
1959: .get(0);
1960: } else {
1961: single_var = (Variable) all_vars.get(0);
1962: }
1963: // The table source
1964: PlanTableSource table_source = findTableSource(single_var);
1965: // Simple LHS?
1966: Variable v = exps[0].getVariable();
1967: if (v != null) {
1968: addSingleVarPlanTo(simple_plan_list,
1969: table_source, v, single_var, exps, op);
1970: } else {
1971: // No, complex lhs
1972: addSingleVarPlanTo(complex_plan_list,
1973: table_source, null, single_var, exps,
1974: op);
1975: }
1976: }
1977: }
1978:
1979: // We now have a list of simple and complex plans for each table,
1980: int sz = simple_plan_list.size();
1981: for (int i = 0; i < sz; ++i) {
1982: SingleVarPlan var_plan = (SingleVarPlan) simple_plan_list
1983: .get(i);
1984: ExpressionPlan exp_plan = new SimpleSingleExpressionPlan(
1985: var_plan.single_var, var_plan.expression);
1986: exp_plan.setOptimizableValue(0.2f);
1987: evaluate_order.add(exp_plan);
1988: }
1989:
1990: sz = complex_plan_list.size();
1991: for (int i = 0; i < sz; ++i) {
1992: SingleVarPlan var_plan = (SingleVarPlan) complex_plan_list
1993: .get(i);
1994: ExpressionPlan exp_plan = new ComplexSingleExpressionPlan(
1995: var_plan.single_var, var_plan.expression);
1996: exp_plan.setOptimizableValue(0.8f);
1997: evaluate_order.add(exp_plan);
1998: }
1999:
2000: }
2001:
2002: /**
2003: * Evaluates a list of expressions that are pattern searches (eg. LIKE,
2004: * NOT LIKE and REGEXP). Note that the LHS or RHS may be complex
2005: * expressions with variables, but we are guarenteed that there are
2006: * no sub-expressions in the expression.
2007: */
2008: void evaluatePatterns(ArrayList pattern_exprs,
2009: ArrayList evaluate_order) {
2010:
2011: // Split the patterns into simple and complex plans. A complex plan
2012: // may require that a join occurs.
2013:
2014: for (int i = 0; i < pattern_exprs.size(); ++i) {
2015: Expression expr = (Expression) pattern_exprs.get(i);
2016:
2017: Expression[] exps = expr.split();
2018: // If the LHS is a single variable and the RHS is a constant then
2019: // the conditions are right for a simple pattern search.
2020: Variable lhs_v = exps[0].getVariable();
2021: if (expr.isConstant()) {
2022: ExpressionPlan expr_plan = new ConstantExpressionPlan(
2023: expr);
2024: expr_plan.setOptimizableValue(0f);
2025: evaluate_order.add(expr_plan);
2026: } else if (lhs_v != null && exps[1].isConstant()) {
2027: ExpressionPlan expr_plan = new SimplePatternExpressionPlan(
2028: lhs_v, expr);
2029: expr_plan.setOptimizableValue(0.25f);
2030: evaluate_order.add(expr_plan);
2031: } else {
2032: // Otherwise we must assume a complex pattern search which may
2033: // require a join. For example, 'a + b LIKE 'a%'' or
2034: // 'a LIKE b'. At the very least, this will be an exhaustive
2035: // search and at the worst it will be a join + exhaustive search.
2036: // So we should evaluate these at the end of the evaluation order.
2037: ExpressionPlan expr_plan = new ExhaustiveSelectExpressionPlan(
2038: expr);
2039: expr_plan.setOptimizableValue(0.82f);
2040: evaluate_order.add(expr_plan);
2041: }
2042:
2043: }
2044:
2045: }
2046:
2047: /**
2048: * Evaluates a list of expressions containing sub-queries. Non-correlated
2049: * sub-queries can often be optimized in to fast searches. Correlated
2050: * queries, or expressions containing multiple sub-queries are put
2051: * through the ExhaustiveSelect plan.
2052: */
2053: void evaluateSubQueries(ArrayList expressions,
2054: ArrayList evaluate_order) {
2055:
2056: // For each sub-query expression
2057: for (int i = 0; i < expressions.size(); ++i) {
2058: Expression andexp = (Expression) expressions.get(i);
2059:
2060: boolean is_exhaustive;
2061: Variable left_var = null;
2062: QueryPlanNode right_plan = null;
2063:
2064: // Is this an easy sub-query?
2065: Operator op = (Operator) andexp.last();
2066: if (op.isSubQuery()) {
2067: // Split the expression.
2068: Expression[] exps = andexp.split();
2069: // Check that the left is a simple enough variable reference
2070: left_var = exps[0].getVariable();
2071: if (left_var != null) {
2072: // Check that the right is a sub-query plan.
2073: right_plan = exps[1].getQueryPlanNode();
2074: if (right_plan != null) {
2075: // Finally, check if the plan is correlated or not
2076: ArrayList cv = right_plan
2077: .discoverCorrelatedVariables(1,
2078: new ArrayList());
2079: // System.out.println("Right Plan: " + right_plan);
2080: // System.out.println("Correlated variables: " + cv);
2081: if (cv.size() == 0) {
2082: // No correlated variables so we are a standard, non-correlated
2083: // query!
2084: is_exhaustive = false;
2085: } else {
2086: is_exhaustive = true;
2087: }
2088: } else {
2089: is_exhaustive = true;
2090: }
2091: } else {
2092: is_exhaustive = true;
2093: }
2094: } else {
2095: // Must be an exhaustive sub-query
2096: is_exhaustive = true;
2097: }
2098:
2099: // If this is an exhaustive operation,
2100: if (is_exhaustive) {
2101: // This expression could involve multiple variables, so we may need
2102: // to join.
2103: List all_vars = andexp.allVariables();
2104:
2105: // Also find all correlated variables.
2106: List all_correlated = andexp
2107: .discoverCorrelatedVariables(0,
2108: new ArrayList());
2109: int sz = all_correlated.size();
2110:
2111: // If there are no variables (and no correlated variables) then this
2112: // must be a constant select, For example, 3 in ( select ... )
2113: if (all_vars.size() == 0 && sz == 0) {
2114: ExpressionPlan expr_plan = new ConstantExpressionPlan(
2115: andexp);
2116: expr_plan.setOptimizableValue(0f);
2117: evaluate_order.add(expr_plan);
2118: } else {
2119:
2120: for (int n = 0; n < sz; ++n) {
2121: CorrelatedVariable cv = (CorrelatedVariable) all_correlated
2122: .get(n);
2123: all_vars.add(cv.getVariable());
2124: }
2125:
2126: // An exhaustive expression plan which might require a join or a
2127: // slow correlated search. This should be evaluated after the
2128: // multiple variables are processed.
2129: ExpressionPlan exp_plan = new ExhaustiveSubQueryExpressionPlan(
2130: all_vars, andexp);
2131: exp_plan.setOptimizableValue(0.85f);
2132: evaluate_order.add(exp_plan);
2133: }
2134:
2135: } else {
2136:
2137: // This is a simple sub-query expression plan with a single LHS
2138: // variable and a single RHS sub-query.
2139: ExpressionPlan exp_plan = new SimpleSubQueryExpressionPlan(
2140: andexp);
2141: exp_plan.setOptimizableValue(0.3f);
2142: evaluate_order.add(exp_plan);
2143:
2144: }
2145:
2146: } // For each 'and' expression
2147:
2148: }
2149:
2150: /**
2151: * Evaluates a list of expressions containing multiple variable expression.
2152: * For example, 'a = b', 'a > b + c', 'a + 5 * b = 2', etc. If an
2153: * expression represents a simple join condition then a join plan is
2154: * made to the query plan tree. If an expression represents a more
2155: * complex joining condition then an exhaustive search must be used.
2156: */
2157: void evaluateMultiples(ArrayList multi_vars,
2158: ArrayList evaluate_order) {
2159:
2160: // FUTURE OPTIMIZATION:
2161: // This join order planner is a little primitive in design. It orders
2162: // optimizable joins first and least optimizable last, but does not
2163: // take into account other factors that we could use to optimize
2164: // joins in the future.
2165:
2166: // For each single variable expression
2167: for (int i = 0; i < multi_vars.size(); ++i) {
2168:
2169: // Get the expression with the multiple variables
2170: Expression expr = (Expression) multi_vars.get(i);
2171: Expression[] exps = expr.split();
2172:
2173: // Get the list of variables in the left hand and right hand side
2174: Variable lhs_v = exps[0].getVariable();
2175: Variable rhs_v = exps[1].getVariable();
2176:
2177: // Work out how optimizable the join is.
2178: // The calculation is as follows;
2179: // a) If both the lhs and rhs are a single variable then the
2180: // optimizable value is set to 0.6f.
2181: // b) If only one of lhs or rhs is a single variable then the
2182: // optimizable value is set to 0.64f.
2183: // c) Otherwise it is set to 0.68f (exhaustive select guarenteed).
2184:
2185: if (lhs_v == null && rhs_v == null) {
2186: // Neither lhs or rhs are single vars
2187: ExpressionPlan exp_plan = new ExhaustiveJoinExpressionPlan(
2188: expr);
2189: exp_plan.setOptimizableValue(0.68f);
2190: evaluate_order.add(exp_plan);
2191: } else if (lhs_v != null && rhs_v != null) {
2192: // Both lhs and rhs are a single var (most optimizable type of
2193: // join).
2194: ExpressionPlan exp_plan = new StandardJoinExpressionPlan(
2195: expr);
2196: exp_plan.setOptimizableValue(0.60f);
2197: evaluate_order.add(exp_plan);
2198: } else {
2199: // Either lhs or rhs is a single var
2200: ExpressionPlan exp_plan = new StandardJoinExpressionPlan(
2201: expr);
2202: exp_plan.setOptimizableValue(0.64f);
2203: evaluate_order.add(exp_plan);
2204: }
2205:
2206: } // for each expression we are 'and'ing against
2207:
2208: }
2209:
2210: /**
2211: * Evaluates a list of expressions that are sub-expressions themselves.
2212: * This is typically called when we have OR queries in the expression.
2213: */
2214: void evaluateSubLogic(ArrayList sublogic_exprs,
2215: ArrayList evaluate_order) {
2216:
2217: each_logic_expr: for (int i = 0; i < sublogic_exprs.size(); ++i) {
2218: Expression expr = (Expression) sublogic_exprs.get(i);
2219:
2220: // Break the expression down to a list of OR expressions,
2221: ArrayList or_exprs = expr.breakByOperator(
2222: new ArrayList(), "or");
2223:
2224: // An optimizations here;
2225:
2226: // If all the expressions we are ORing together are in the same table
2227: // then we should execute them before the joins, otherwise they
2228: // should go after the joins.
2229:
2230: // The reason for this is because if we can lesson the amount of work a
2231: // join has to do then we should. The actual time it takes to perform
2232: // an OR search shouldn't change if it is before or after the joins.
2233:
2234: PlanTableSource common = null;
2235:
2236: for (int n = 0; n < or_exprs.size(); ++n) {
2237: Expression or_expr = (Expression) or_exprs.get(n);
2238: List vars = or_expr.allVariables();
2239: // If there are no variables then don't bother with this expression
2240: if (vars.size() > 0) {
2241: // Find the common table source (if any)
2242: PlanTableSource ts = findCommonTableSource(vars);
2243: boolean or_after_joins = false;
2244: if (ts == null) {
2245: // No common table, so OR after the joins
2246: or_after_joins = true;
2247: } else if (common == null) {
2248: common = ts;
2249: } else if (common != ts) {
2250: // No common table with the vars in this OR list so do this OR
2251: // after the joins.
2252: or_after_joins = true;
2253: }
2254:
2255: if (or_after_joins) {
2256: ExpressionPlan exp_plan = new SubLogicExpressionPlan(
2257: expr);
2258: exp_plan.setOptimizableValue(0.70f);
2259: evaluate_order.add(exp_plan);
2260: // Continue to the next logic expression
2261: continue each_logic_expr;
2262: }
2263: }
2264: }
2265:
2266: // Either we found a common table or there are no variables in the OR.
2267: // Either way we should evaluate this after the join.
2268: ExpressionPlan exp_plan = new SubLogicExpressionPlan(
2269: expr);
2270: exp_plan.setOptimizableValue(0.58f);
2271: evaluate_order.add(exp_plan);
2272:
2273: }
2274:
2275: }
2276:
2277: // -----
2278:
2279: /**
2280: * Generates a plan to evaluate the given list of expressions
2281: * (logically separated with AND).
2282: */
2283: void planForExpressionList(List and_list) {
2284:
2285: ArrayList sub_logic_expressions = new ArrayList();
2286: // The list of expressions that have a sub-select in them.
2287: ArrayList sub_query_expressions = new ArrayList();
2288: // The list of all constant expressions ( true = true )
2289: ArrayList constants = new ArrayList();
2290: // The list of pattern matching expressions (eg. 't LIKE 'a%')
2291: ArrayList pattern_expressions = new ArrayList();
2292: // The list of all expressions that are a single variable on one
2293: // side, a conditional operator, and a constant on the other side.
2294: ArrayList single_vars = new ArrayList();
2295: // The list of multi variable expressions (possible joins)
2296: ArrayList multi_vars = new ArrayList();
2297:
2298: // Separate out each condition type.
2299: for (int i = 0; i < and_list.size(); ++i) {
2300: Object el = and_list.get(i);
2301: Expression andexp = (Expression) el;
2302: // If we end with a logical operator then we must recurse them
2303: // through this method.
2304: Object lob = andexp.last();
2305: Operator op;
2306: // If the last is not an operator, then we imply
2307: // '[expression] = true'
2308: if (!(lob instanceof Operator)
2309: || ((Operator) lob).isMathematical()) {
2310: Operator EQUAL_OP = Operator.get("=");
2311: andexp.addElement(TObject.booleanVal(true));
2312: andexp.addOperator(EQUAL_OP);
2313: op = EQUAL_OP;
2314: } else {
2315: op = (Operator) lob;
2316: }
2317: // If the last is logical (eg. AND, OR) then we must process the
2318: // sub logic expression
2319: if (op.isLogical()) {
2320: sub_logic_expressions.add(andexp);
2321: }
2322: // Does the expression have a sub-query? (eg. Another select
2323: // statement somewhere in it)
2324: else if (andexp.hasSubQuery()) {
2325: sub_query_expressions.add(andexp);
2326: } else if (op.isPattern()) {
2327: pattern_expressions.add(andexp);
2328: } else { //if (op.isCondition()) {
2329: // The list of variables in the expression.
2330: List vars = andexp.allVariables();
2331: if (vars.size() == 0) {
2332: // These are ( 54 + 9 = 9 ), ( "z" > "a" ), ( 9.01 - 2 ), etc
2333: constants.add(andexp);
2334: } else if (vars.size() == 1) {
2335: // These are ( id = 90 ), ( 'a' < number ), etc
2336: single_vars.add(andexp);
2337: } else if (vars.size() > 1) {
2338: // These are ( id = part_id ),
2339: // ( cost_of + value_of < sold_at ), ( id = part_id - 10 )
2340: multi_vars.add(andexp);
2341: } else {
2342: throw new Error(
2343: "Hmm, vars list size is negative!");
2344: }
2345: }
2346: }
2347:
2348: // The order in which expression are evaluated,
2349: // (ExpressionPlan)
2350: ArrayList evaluate_order = new ArrayList();
2351:
2352: // Evaluate the constants. These should always be evaluated first
2353: // because they always evaluate to either true or false or null.
2354: evaluateConstants(constants, evaluate_order);
2355:
2356: // Evaluate the singles. If formed well these can be evaluated
2357: // using fast indices. eg. (a > 9 - 3) is more optimal than
2358: // (a + 3 > 9).
2359: evaluateSingles(single_vars, evaluate_order);
2360:
2361: // Evaluate the pattern operators. Note that some patterns can be
2362: // optimized better than others, but currently we keep this near the
2363: // middle of our evaluation sequence.
2364: evaluatePatterns(pattern_expressions, evaluate_order);
2365:
2366: // Evaluate the sub-queries. These are queries of the form,
2367: // (a IN ( SELECT ... )), (a = ( SELECT ... ) = ( SELECT ... )), etc.
2368: evaluateSubQueries(sub_query_expressions, evaluate_order);
2369:
2370: // Evaluate multiple variable expressions. It's possible these are
2371: // joins.
2372: evaluateMultiples(multi_vars, evaluate_order);
2373:
2374: // Lastly evaluate the sub-logic expressions. These expressions are
2375: // OR type expressions.
2376: evaluateSubLogic(sub_logic_expressions, evaluate_order);
2377:
2378: // Sort the evaluation list by how optimizable the expressions are,
2379: Collections.sort(evaluate_order);
2380: // And add each expression to the plan
2381: for (int i = 0; i < evaluate_order.size(); ++i) {
2382: ExpressionPlan plan = (ExpressionPlan) evaluate_order
2383: .get(i);
2384: plan.addToPlanTree();
2385: }
2386:
2387: }
2388:
2389: /**
2390: * Evaluates the search Expression clause and alters the banches of
2391: * the plans in this object as necessary. Unlike the 'logicalEvaluate'
2392: * method, this does not result in a single QueryPlanNode. It is the
2393: * responsibility of the callee to join branches as required.
2394: */
2395: void planForExpression(Expression exp) {
2396: if (exp == null) {
2397: return;
2398: }
2399:
2400: Object ob = exp.last();
2401: if (ob instanceof Operator && ((Operator) ob).isLogical()) {
2402: Operator last_op = (Operator) ob;
2403:
2404: if (last_op.is("or")) {
2405: // parsing an OR block
2406: // Split left and right of logical operator.
2407: Expression[] exps = exp.split();
2408: // If we are an 'or' then evaluate left and right and union the
2409: // result.
2410:
2411: // Before we branch set cache points.
2412: setCachePoints();
2413:
2414: // Make copies of the left and right planner
2415: QueryTableSetPlanner left_planner = copy();
2416: QueryTableSetPlanner right_planner = copy();
2417:
2418: // Plan the left and right side of the OR
2419: left_planner.planForExpression(exps[0]);
2420: right_planner.planForExpression(exps[1]);
2421:
2422: // Fix the left and right planner so that they represent the same
2423: // 'group'.
2424: // The current implementation naturally joins all sources if the
2425: // number of sources is different than the original size.
2426: int left_sz = left_planner.table_list.size();
2427: int right_sz = right_planner.table_list.size();
2428: if (left_sz != right_sz
2429: || left_planner.hasJoinOccured()
2430: || right_planner.hasJoinOccured()) {
2431: // Naturally join all in the left and right plan
2432: left_planner.naturalJoinAll();
2433: right_planner.naturalJoinAll();
2434: }
2435:
2436: // Union all table sources, but only if they have changed.
2437: ArrayList left_table_list = left_planner.table_list;
2438: ArrayList right_table_list = right_planner.table_list;
2439: int sz = left_table_list.size();
2440:
2441: // First we must determine the plans that need to be joined in the
2442: // left and right plan.
2443: ArrayList left_join_list = new ArrayList();
2444: ArrayList right_join_list = new ArrayList();
2445: for (int i = 0; i < sz; ++i) {
2446: PlanTableSource left_plan = (PlanTableSource) left_table_list
2447: .get(i);
2448: PlanTableSource right_plan = (PlanTableSource) right_table_list
2449: .get(i);
2450: if (left_plan.isUpdated()
2451: || right_plan.isUpdated()) {
2452: left_join_list.add(left_plan);
2453: right_join_list.add(right_plan);
2454: }
2455: }
2456:
2457: // Make sure the plans are joined in the left and right planners
2458: left_planner
2459: .joinAllPlansToSingleSource(left_join_list);
2460: right_planner
2461: .joinAllPlansToSingleSource(right_join_list);
2462:
2463: // Since the planner lists may have changed we update them here.
2464: left_table_list = left_planner.table_list;
2465: right_table_list = right_planner.table_list;
2466: sz = left_table_list.size();
2467:
2468: ArrayList new_table_list = new ArrayList(sz);
2469:
2470: for (int i = 0; i < sz; ++i) {
2471: PlanTableSource left_plan = (PlanTableSource) left_table_list
2472: .get(i);
2473: PlanTableSource right_plan = (PlanTableSource) right_table_list
2474: .get(i);
2475:
2476: PlanTableSource new_plan;
2477:
2478: // If left and right plan updated so we need to union them
2479: if (left_plan.isUpdated()
2480: || right_plan.isUpdated()) {
2481:
2482: // In many causes, the left and right branches will contain
2483: // identical branches that would best be optimized out.
2484:
2485: // Take the left plan, add the logical union to it, and make it
2486: // the plan for this.
2487: QueryPlanNode node = new QueryPlan.LogicalUnionNode(
2488: left_plan.getPlan(), right_plan
2489: .getPlan());
2490:
2491: // Update the plan in this table list
2492: left_plan.updatePlan(node);
2493:
2494: new_plan = left_plan;
2495: } else {
2496: // If the left and right plan didn't update, then use the
2497: // left plan (it doesn't matter if we use left or right because
2498: // they are the same).
2499: new_plan = left_plan;
2500: }
2501:
2502: // Add the left plan to the new table list we are creating
2503: new_table_list.add(new_plan);
2504:
2505: }
2506:
2507: // Set the new table list
2508: table_list = new_table_list;
2509:
2510: }
2511:
2512: else if (last_op.is("and")) {
2513: // parsing an AND block
2514: // The list of AND expressions that are here
2515: ArrayList and_list = new ArrayList();
2516: and_list = createAndList(and_list, exp);
2517:
2518: planForExpressionList(and_list);
2519:
2520: }
2521:
2522: else {
2523: throw new RuntimeException(
2524: "Unknown logical operator: " + ob);
2525: }
2526:
2527: } else {
2528: // Not a logical expression so just plan for this single expression.
2529: ArrayList exp_list = new ArrayList(1);
2530: exp_list.add(exp);
2531: planForExpressionList(exp_list);
2532: }
2533:
2534: }
2535:
2536: /**
2537: * Evaluates a search Expression clause. Note that is some cases this
2538: * will generate a plan tree that has many identical branches that can be
2539: * optimized out.
2540: */
2541: QueryPlanNode logicalEvaluate(Expression exp) {
2542:
2543: // System.out.println("Logical Evaluate: " + exp);
2544:
2545: if (exp == null) {
2546: // Naturally join everything and return the plan.
2547: naturalJoinAll();
2548: // Return the plan
2549: return getSingleTableSource().getPlan();
2550: }
2551:
2552: // Plan the expression
2553: planForExpression(exp);
2554:
2555: // Naturally join any straggling tables
2556: naturalJoinAll();
2557:
2558: // Return the plan
2559: return getSingleTableSource().getPlan();
2560: }
2561:
2562: /**
2563: * Given an Expression, this will return a list of expressions that can be
2564: * safely executed as a set of 'and' operations. For example, an
2565: * expression of 'a=9 and b=c and d=2' would return the list; 'a=9','b=c',
2566: * 'd=2'.
2567: * <p>
2568: * If non 'and' operators are found then the reduction stops.
2569: */
2570: private ArrayList createAndList(ArrayList list, Expression exp) {
2571: return exp.breakByOperator(list, "and");
2572: }
2573:
2574: /**
2575: * Evalutes the WHERE clause of the table expression.
2576: */
2577: QueryPlanNode planSearchExpression(
2578: SearchExpression search_expression) {
2579: // First perform all outer tables.
2580: planAllOuterJoins();
2581:
2582: QueryPlanNode node = logicalEvaluate(search_expression
2583: .getFromExpression());
2584: return node;
2585: }
2586:
2587: /**
2588: * Makes an exact duplicate copy (deep clone) of this planner object.
2589: */
2590: private QueryTableSetPlanner copy() {
2591: QueryTableSetPlanner copy = new QueryTableSetPlanner();
2592: int sz = table_list.size();
2593: for (int i = 0; i < sz; ++i) {
2594: copy.table_list.add(((PlanTableSource) table_list
2595: .get(i)).copy());
2596: }
2597: // Copy the left and right links in the PlanTableSource
2598: for (int i = 0; i < sz; ++i) {
2599: PlanTableSource src = (PlanTableSource) table_list
2600: .get(i);
2601: PlanTableSource mod = (PlanTableSource) copy.table_list
2602: .get(i);
2603: // See how the left plan links to which index,
2604: if (src.left_plan != null) {
2605: int n = indexOfPlanTableSource(src.left_plan);
2606: mod.setLeftJoinInfo(
2607: (PlanTableSource) copy.table_list.get(n),
2608: src.left_join_type, src.left_on_expr);
2609: }
2610: // See how the right plan links to which index,
2611: if (src.right_plan != null) {
2612: int n = indexOfPlanTableSource(src.right_plan);
2613: mod.setRightJoinInfo(
2614: (PlanTableSource) copy.table_list.get(n),
2615: src.right_join_type, src.right_on_expr);
2616: }
2617: }
2618:
2619: return copy;
2620: }
2621:
2622: void printDebugInfo() {
2623: StringBuffer buf = new StringBuffer();
2624: buf.append("PLANNER:\n");
2625: for (int i = 0; i < table_list.size(); ++i) {
2626: buf.append("TABLE " + i + "\n");
2627: ((PlanTableSource) table_list.get(i)).getPlan()
2628: .debugString(2, buf);
2629: buf.append("\n");
2630: }
2631: System.out.println(buf);
2632: }
2633:
2634: }
2635:
2636: /**
2637: * Represents a single table source being planned.
2638: */
2639: private static class PlanTableSource {
2640:
2641: /**
2642: * The Plan for this table source.
2643: */
2644: private QueryPlanNode plan;
2645:
2646: /**
2647: * The list of fully qualified Variable objects that are accessable within
2648: * this plan.
2649: */
2650: private final Variable[] var_list;
2651:
2652: /**
2653: * The list of unique key names of the tables in this plan.
2654: */
2655: private final String[] unique_names;
2656:
2657: /**
2658: * Set to true when this source has been updated from when it was
2659: * constructed or copied.
2660: */
2661: private boolean is_updated;
2662:
2663: /**
2664: * How this plan is naturally joined to other plans in the source. A
2665: * plan either has no dependance, a left or a right dependance, or a left
2666: * and right dependance.
2667: */
2668: PlanTableSource left_plan, right_plan;
2669: int left_join_type, right_join_type;
2670: Expression left_on_expr, right_on_expr;
2671:
2672: /**
2673: * Constructor.
2674: */
2675: public PlanTableSource(QueryPlanNode plan, Variable[] var_list,
2676: String[] table_unique_names) {
2677: this .plan = plan;
2678: this .var_list = var_list;
2679: this .unique_names = table_unique_names;
2680: left_join_type = -1;
2681: right_join_type = -1;
2682: is_updated = false;
2683: }
2684:
2685: /**
2686: * Sets the left join information for this plan.
2687: */
2688: void setLeftJoinInfo(PlanTableSource left_plan, int join_type,
2689: Expression on_expr) {
2690: this .left_plan = left_plan;
2691: this .left_join_type = join_type;
2692: this .left_on_expr = on_expr;
2693: }
2694:
2695: /**
2696: * Sets the right join information for this plan.
2697: */
2698: void setRightJoinInfo(PlanTableSource right_plan,
2699: int join_type, Expression on_expr) {
2700: this .right_plan = right_plan;
2701: this .right_join_type = join_type;
2702: this .right_on_expr = on_expr;
2703: }
2704:
2705: /**
2706: * This is called when two plans are merged together to set up the
2707: * left and right join information for the new plan. This sets the left
2708: * join info from the left plan and the right join info from the right
2709: * plan.
2710: */
2711: void setJoinInfoMergedBetween(PlanTableSource left,
2712: PlanTableSource right) {
2713:
2714: if (left.right_plan != right) {
2715: if (left.right_plan != null) {
2716: setRightJoinInfo(left.right_plan,
2717: left.right_join_type, left.right_on_expr);
2718: right_plan.left_plan = this ;
2719: }
2720: if (right.left_plan != null) {
2721: setLeftJoinInfo(right.left_plan,
2722: right.left_join_type, right.left_on_expr);
2723: left_plan.right_plan = this ;
2724: }
2725: }
2726: if (left.left_plan != right) {
2727: if (left_plan == null && left.left_plan != null) {
2728: setLeftJoinInfo(left.left_plan,
2729: left.left_join_type, left.left_on_expr);
2730: left_plan.right_plan = this ;
2731: }
2732: if (right_plan == null && right.right_plan != null) {
2733: setRightJoinInfo(right.right_plan,
2734: right.right_join_type, right.right_on_expr);
2735: right_plan.left_plan = this ;
2736: }
2737: }
2738:
2739: }
2740:
2741: /**
2742: * Returns true if this table source contains the variable reference.
2743: */
2744: public boolean containsVariable(Variable v) {
2745: // System.out.println("Looking for: " + v);
2746: for (int i = 0; i < var_list.length; ++i) {
2747: // System.out.println(var_list[i]);
2748: if (var_list[i].equals(v)) {
2749: return true;
2750: }
2751: }
2752: return false;
2753: }
2754:
2755: /**
2756: * Returns true if this table source contains the unique table name
2757: * reference.
2758: */
2759: public boolean containsUniqueKey(String name) {
2760: for (int i = 0; i < unique_names.length; ++i) {
2761: if (unique_names[i].equals(name)) {
2762: return true;
2763: }
2764: }
2765: return false;
2766: }
2767:
2768: /**
2769: * Sets the updated flag.
2770: */
2771: public void setUpdated() {
2772: is_updated = true;
2773: }
2774:
2775: /**
2776: * Updates the plan.
2777: */
2778: public void updatePlan(QueryPlanNode node) {
2779: plan = node;
2780: setUpdated();
2781: }
2782:
2783: /**
2784: * Returns the plan for this table source.
2785: */
2786: public QueryPlanNode getPlan() {
2787: return plan;
2788: }
2789:
2790: /**
2791: * Returns true if the planner was updated.
2792: */
2793: public boolean isUpdated() {
2794: return is_updated;
2795: }
2796:
2797: /**
2798: * Makes a copy of this table source.
2799: */
2800: public PlanTableSource copy() {
2801: return new PlanTableSource(plan, var_list, unique_names);
2802: }
2803:
2804: }
2805:
2806: /**
2807: * An abstract class that represents an expression to be added into a plan.
2808: * Many sets of expressions can be added into the plan tree in any order,
2809: * however it is often desirable to add some more intensive expressions
2810: * higher up the branches. This object allows us to order expressions by
2811: * optimization value. More optimizable expressions are put near the leafs
2812: * of the plan tree and least optimizable and put near the top.
2813: */
2814: static abstract class ExpressionPlan implements Comparable {
2815:
2816: /**
2817: * How optimizable an expression is. A value of 0 indicates most
2818: * optimizable and 1 indicates least optimizable.
2819: */
2820: private float optimizable_value;
2821:
2822: /**
2823: * Sets the optimizable value of this plan.
2824: */
2825: public void setOptimizableValue(float v) {
2826: optimizable_value = v;
2827: }
2828:
2829: /**
2830: * Returns the optimizable value for this plan.
2831: */
2832: public float getOptimizableValue() {
2833: return optimizable_value;
2834: }
2835:
2836: /**
2837: * Adds this expression into the plan tree.
2838: */
2839: public abstract void addToPlanTree();
2840:
2841: public int compareTo(Object ob) {
2842: ExpressionPlan dest_plan = (ExpressionPlan) ob;
2843: float dest_val = dest_plan.optimizable_value;
2844: if (optimizable_value > dest_val) {
2845: return 1;
2846: } else if (optimizable_value < dest_val) {
2847: return -1;
2848: } else {
2849: return 0;
2850: }
2851: }
2852:
2853: }
2854:
2855: }
|