0001: /**
0002: * com.mckoi.database.QueryPlan 06 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;
0024:
0025: import java.util.List;
0026: import java.util.ArrayList;
0027:
0028: /**
0029: * Various helper methods for constructing a plan tree, and the plan node
0030: * implementations themselves.
0031: *
0032: * @author Tobias Downer
0033: */
0034:
0035: public class QueryPlan {
0036:
0037: /**
0038: * Convenience, replaces all elements of the array with clone versions of
0039: * themselves.
0040: */
0041: private static void cloneArray(Variable[] array)
0042: throws CloneNotSupportedException {
0043: if (array != null) {
0044: for (int i = 0; i < array.length; ++i) {
0045: array[i] = (Variable) array[i].clone();
0046: }
0047: }
0048: }
0049:
0050: /**
0051: * Convenience, replaces all elements of the array with clone versions of
0052: * themselves.
0053: */
0054: private static void cloneArray(Expression[] array)
0055: throws CloneNotSupportedException {
0056: if (array != null) {
0057: for (int i = 0; i < array.length; ++i) {
0058: array[i] = (Expression) array[i].clone();
0059: }
0060: }
0061: }
0062:
0063: private static void indentBuffer(int level, StringBuffer buf) {
0064: for (int i = 0; i < level; ++i) {
0065: buf.append(' ');
0066: }
0067: }
0068:
0069: // ---------- Plan node implementations ----------
0070:
0071: /**
0072: * A QueryPlanNode with a single child.
0073: */
0074: public static abstract class SingleQueryPlanNode implements
0075: QueryPlanNode {
0076:
0077: static final long serialVersionUID = -6753991881140638658L;
0078:
0079: /**
0080: * The single child node.
0081: */
0082: protected QueryPlanNode child;
0083:
0084: /**
0085: * Constructor.
0086: */
0087: protected SingleQueryPlanNode(QueryPlanNode child) {
0088: this .child = child;
0089: }
0090:
0091: /**
0092: * Returns the child plan.
0093: */
0094: public QueryPlanNode child() {
0095: return child;
0096: }
0097:
0098: /**
0099: * Default implementation delegates responsibility to child.
0100: */
0101: public ArrayList discoverTableNames(ArrayList list) {
0102: return child.discoverTableNames(list);
0103: }
0104:
0105: /**
0106: * Default implementation that discovers correlated variables for the
0107: * given offset level.
0108: */
0109: public ArrayList discoverCorrelatedVariables(int level,
0110: ArrayList list) {
0111: return child.discoverCorrelatedVariables(level, list);
0112: }
0113:
0114: /**
0115: * Deep clone.
0116: */
0117: public Object clone() throws CloneNotSupportedException {
0118: SingleQueryPlanNode node = (SingleQueryPlanNode) super
0119: .clone();
0120: node.child = (QueryPlanNode) child.clone();
0121: return node;
0122: }
0123:
0124: public String titleString() {
0125: return getClass().getName();
0126: }
0127:
0128: public void debugString(int level, StringBuffer buf) {
0129: indentBuffer(level, buf);
0130: buf.append(titleString());
0131: buf.append('\n');
0132: child.debugString(level + 2, buf);
0133: }
0134:
0135: }
0136:
0137: /**
0138: * A QueryPlanNode that is a branch with two child nodes.
0139: */
0140: public static abstract class BranchQueryPlanNode implements
0141: QueryPlanNode {
0142:
0143: static final long serialVersionUID = 2938130775577221138L;
0144:
0145: /**
0146: * The left and right node.
0147: */
0148: protected QueryPlanNode left, right;
0149:
0150: /**
0151: * The Constructor.
0152: */
0153: protected BranchQueryPlanNode(QueryPlanNode left,
0154: QueryPlanNode right) {
0155: this .left = left;
0156: this .right = right;
0157: }
0158:
0159: /**
0160: * Returns the left node.
0161: */
0162: public QueryPlanNode left() {
0163: return left;
0164: }
0165:
0166: /**
0167: * Returns the right node.
0168: */
0169: public QueryPlanNode right() {
0170: return right;
0171: }
0172:
0173: /**
0174: * Default implementation delegates responsibility to children.
0175: */
0176: public ArrayList discoverTableNames(ArrayList list) {
0177: return right.discoverTableNames(left
0178: .discoverTableNames(list));
0179: }
0180:
0181: /**
0182: * Default implementation that discovers correlated variables for the
0183: * given offset level.
0184: */
0185: public ArrayList discoverCorrelatedVariables(int level,
0186: ArrayList list) {
0187: return right.discoverCorrelatedVariables(level, left
0188: .discoverCorrelatedVariables(level, list));
0189: }
0190:
0191: /**
0192: * Deep clone.
0193: */
0194: public Object clone() throws CloneNotSupportedException {
0195: BranchQueryPlanNode node = (BranchQueryPlanNode) super
0196: .clone();
0197: node.left = (QueryPlanNode) left.clone();
0198: node.right = (QueryPlanNode) right.clone();
0199: return node;
0200: }
0201:
0202: public String titleString() {
0203: return getClass().getName();
0204: }
0205:
0206: public void debugString(int level, StringBuffer buf) {
0207: indentBuffer(level, buf);
0208: buf.append(titleString());
0209: buf.append('\n');
0210: left.debugString(level + 2, buf);
0211: right.debugString(level + 2, buf);
0212: }
0213:
0214: }
0215:
0216: /**
0217: * The node for fetching a table from the current transaction. This is
0218: * a tree node and has no children.
0219: */
0220: public static class FetchTableNode implements QueryPlanNode {
0221:
0222: static final long serialVersionUID = 7545493568015241717L;
0223:
0224: /**
0225: * The name of the table to fetch.
0226: */
0227: private TableName table_name;
0228:
0229: /**
0230: * The name to alias the table as.
0231: */
0232: private TableName alias_name;
0233:
0234: public FetchTableNode(TableName table_name, TableName aliased_as) {
0235: this .table_name = table_name;
0236: this .alias_name = aliased_as;
0237: }
0238:
0239: /**
0240: * Adds the table name to the list if it's not already in there.
0241: */
0242: public ArrayList discoverTableNames(ArrayList list) {
0243: if (!list.contains(table_name)) {
0244: list.add(table_name);
0245: }
0246: return list;
0247: }
0248:
0249: public Table evaluate(QueryContext context) {
0250: // MILD HACK: Cast the context to a DatabaseQueryContext
0251: DatabaseQueryContext db_context = (DatabaseQueryContext) context;
0252: DataTable t = db_context.getTable(table_name);
0253: if (alias_name != null) {
0254: return new ReferenceTable(t, alias_name);
0255: }
0256: return t;
0257: }
0258:
0259: public ArrayList discoverCorrelatedVariables(int level,
0260: ArrayList list) {
0261: return list;
0262: }
0263:
0264: public Object clone() throws CloneNotSupportedException {
0265: return super .clone();
0266: }
0267:
0268: public String titleString() {
0269: return "FETCH: " + table_name + " AS " + alias_name;
0270: }
0271:
0272: public void debugString(int level, StringBuffer buf) {
0273: indentBuffer(level, buf);
0274: buf.append(titleString());
0275: buf.append('\n');
0276: }
0277:
0278: }
0279:
0280: /**
0281: * A node for creating a table with a single row. This table is useful for
0282: * queries that have no underlying row. For example, a pure functional
0283: * table expression.
0284: */
0285: public static class SingleRowTableNode implements QueryPlanNode {
0286:
0287: static final long serialVersionUID = -7180494964138911604L;
0288:
0289: public SingleRowTableNode() {
0290: }
0291:
0292: public ArrayList discoverTableNames(ArrayList list) {
0293: return list;
0294: }
0295:
0296: public Table evaluate(QueryContext context) {
0297: // MILD HACK: Cast the context to a DatabaseQueryContext
0298: DatabaseQueryContext db_context = (DatabaseQueryContext) context;
0299: return db_context.getDatabase().getSingleRowTable();
0300: }
0301:
0302: public ArrayList discoverCorrelatedVariables(int level,
0303: ArrayList list) {
0304: return list;
0305: }
0306:
0307: public Object clone() throws CloneNotSupportedException {
0308: return super .clone();
0309: }
0310:
0311: public String titleString() {
0312: return "SINGLE ROW";
0313: }
0314:
0315: public void debugString(int level, StringBuffer buf) {
0316: indentBuffer(level, buf);
0317: buf.append(titleString());
0318: buf.append('\n');
0319: }
0320:
0321: }
0322:
0323: /**
0324: * The node that fetches a view from the current connection. This is a
0325: * tree node that has no children, however the child can be created by
0326: * calling the 'createViewChildNode' method. This node can be removed from a
0327: * plan tree by calling the 'createViewChildNode' method and substituting this
0328: * node with the returned child. For a planner that normalizes and optimizes
0329: * plan trees, this is a useful feature.
0330: */
0331: public static class FetchViewNode implements QueryPlanNode {
0332:
0333: static final long serialVersionUID = -6557333346211179284L;
0334:
0335: /**
0336: * The name of the view to fetch.
0337: */
0338: private TableName table_name;
0339:
0340: /**
0341: * The name to alias the table as.
0342: */
0343: private TableName alias_name;
0344:
0345: public FetchViewNode(TableName table_name, TableName aliased_as) {
0346: this .table_name = table_name;
0347: this .alias_name = aliased_as;
0348: }
0349:
0350: /**
0351: * Returns the QueryPlanNode that resolves to the view. This looks up the
0352: * query plan in the context given.
0353: */
0354: public QueryPlanNode createViewChildNode(QueryContext context) {
0355: DatabaseQueryContext db = (DatabaseQueryContext) context;
0356: return db.createViewQueryPlanNode(table_name);
0357: }
0358:
0359: /**
0360: * Adds the table name to the list if it's not already in there.
0361: */
0362: public ArrayList discoverTableNames(ArrayList list) {
0363: if (!list.contains(table_name)) {
0364: list.add(table_name);
0365: }
0366: return list;
0367: }
0368:
0369: public Table evaluate(QueryContext context) {
0370:
0371: // Create the view child node
0372: QueryPlanNode node = createViewChildNode(context);
0373: // Evaluate the plan
0374: Table t = node.evaluate(context);
0375:
0376: if (alias_name != null) {
0377: return new ReferenceTable(t, alias_name);
0378: } else {
0379: return t;
0380: }
0381:
0382: }
0383:
0384: public ArrayList discoverCorrelatedVariables(int level,
0385: ArrayList list) {
0386: return list;
0387: }
0388:
0389: public Object clone() throws CloneNotSupportedException {
0390: return super .clone();
0391: }
0392:
0393: public String titleString() {
0394: return "VIEW: " + table_name + " AS " + alias_name;
0395: }
0396:
0397: public void debugString(int level, StringBuffer buf) {
0398: indentBuffer(level, buf);
0399: buf.append(titleString());
0400: buf.append('\n');
0401: }
0402:
0403: }
0404:
0405: /**
0406: * The node for performing a simple indexed query on a single column of the
0407: * child node. Finds the set from the child node that matches the range.
0408: * <p>
0409: * The given Expression object must conform to a number of rules. It may
0410: * reference only one column in the child node. It must consist of only
0411: * simple mathemetical and logical operators (<, >, =, <>, >=, <=, AND, OR).
0412: * The left side of each mathematical operator must be a variable, and the
0413: * right side must be a constant (parameter subsitution or correlated value).
0414: * For example;
0415: * (col > 10 AND col < 100) OR col > 1000 OR col == 10
0416: * <p>
0417: * Breaking any of these rules will mean the range select can not happen.
0418: */
0419: public static class RangeSelectNode extends SingleQueryPlanNode {
0420:
0421: static final long serialVersionUID = -108747827391465748L;
0422:
0423: /**
0424: * A simple expression that represents the range to select. See the
0425: * class comments for a description for how this expression must be
0426: * formed.
0427: */
0428: private Expression expression;
0429:
0430: public RangeSelectNode(QueryPlanNode child, Expression exp) {
0431: super (child);
0432: this .expression = exp;
0433: }
0434:
0435: /**
0436: * Given an Expression, this will return a list of expressions that can be
0437: * safely executed as a set of 'and' operations. For example, an
0438: * expression of 'a=9 and b=c and d=2' would return the list; 'a=9','b=c',
0439: * 'd=2'.
0440: * <p>
0441: * If non 'and' operators are found then the reduction stops.
0442: */
0443: private ArrayList createAndList(ArrayList list, Expression exp) {
0444: return exp.breakByOperator(list, "and");
0445: }
0446:
0447: /**
0448: * Updates a range with the given expression.
0449: */
0450: private void updateRange(QueryContext context,
0451: SelectableRangeSet range, DataTableColumnDef field,
0452: Expression e) {
0453: Operator op = (Operator) e.last();
0454: Expression[] exps = e.split();
0455: // Evaluate to an object
0456: TObject cell = exps[1].evaluate(null, null, context);
0457:
0458: // If the evaluated object is not of a comparable type, then it becomes
0459: // null.
0460: TType field_type = field.getTType();
0461: if (!cell.getTType().comparableTypes(field_type)) {
0462: cell = new TObject(field_type, null);
0463: }
0464:
0465: // Intersect this in the range set
0466: range.intersect(op, cell);
0467: }
0468:
0469: /**
0470: * Calculates a list of SelectableRange objects that represent the range
0471: * of the expression.
0472: */
0473: private void calcRange(final QueryContext context,
0474: final DataTableColumnDef field,
0475: final SelectableRangeSet range, final Expression exp) {
0476: Operator op = (Operator) exp.last();
0477: if (op.isLogical()) {
0478: if (op.is("and")) {
0479: ArrayList and_list = createAndList(new ArrayList(),
0480: exp);
0481: int sz = and_list.size();
0482: for (int i = 0; i < sz; ++i) {
0483: updateRange(context, range, field,
0484: (Expression) and_list.get(i));
0485: }
0486: } else if (op.is("or")) {
0487: // Split left and right of logical operator.
0488: Expression[] exps = exp.split();
0489: // Calculate the range of the left and right
0490: SelectableRangeSet left = new SelectableRangeSet();
0491: calcRange(context, field, left, exps[0]);
0492: SelectableRangeSet right = new SelectableRangeSet();
0493: calcRange(context, field, right, exps[1]);
0494:
0495: // Union the left and right range with the current range
0496: range.union(left);
0497: range.union(right);
0498: } else {
0499: throw new Error("Unrecognised logical operator.");
0500: }
0501: } else {
0502: // Not an operator so this is the value.
0503: updateRange(context, range, field, exp);
0504: }
0505:
0506: }
0507:
0508: public Table evaluate(QueryContext context) {
0509: Table t = child.evaluate(context);
0510:
0511: Expression exp = expression;
0512:
0513: // Assert that all variables in the expression are identical.
0514: List all_vars = exp.allVariables();
0515: Variable v = null;
0516: int sz = all_vars.size();
0517: for (int i = 0; i < sz; ++i) {
0518: Variable cv = (Variable) all_vars.get(i);
0519: if (v != null) {
0520: if (!cv.equals(v)) {
0521: throw new Error(
0522: "Assertion failed: "
0523: + "Range plan does not contain common variable.");
0524: }
0525: }
0526: v = cv;
0527: }
0528:
0529: // Find the variable field in the table.
0530: int col = t.findFieldName(v);
0531: if (col == -1) {
0532: throw new Error(
0533: "Couldn't find column reference in table: " + v);
0534: }
0535: DataTableColumnDef field = t.getColumnDefAt(col);
0536: // Calculate the range
0537: SelectableRangeSet range = new SelectableRangeSet();
0538: calcRange(context, field, range, exp);
0539:
0540: // System.out.println("RANGE: ");
0541: // System.out.println(range);
0542:
0543: // Select the range from the table
0544: SelectableRange[] ranges = range.toSelectableRangeArray();
0545: return t.rangeSelect(v, ranges);
0546:
0547: }
0548:
0549: public ArrayList discoverTableNames(ArrayList list) {
0550: return expression.discoverTableNames(super
0551: .discoverTableNames(list));
0552: }
0553:
0554: public ArrayList discoverCorrelatedVariables(int level,
0555: ArrayList list) {
0556: // System.out.println(expression);
0557: return expression.discoverCorrelatedVariables(level, super
0558: .discoverCorrelatedVariables(level, list));
0559: }
0560:
0561: public Object clone() throws CloneNotSupportedException {
0562: RangeSelectNode node = (RangeSelectNode) super .clone();
0563: node.expression = (Expression) expression.clone();
0564: return node;
0565: }
0566:
0567: public String titleString() {
0568: return "RANGE: " + expression;
0569: }
0570:
0571: }
0572:
0573: /**
0574: * The node for performing a simple select operation on a table. The simple
0575: * select requires a LHS variable, an operator, and an expression
0576: * representing the RHS.
0577: */
0578: public static class SimpleSelectNode extends SingleQueryPlanNode {
0579:
0580: static final long serialVersionUID = 5502157970886270867L;
0581:
0582: /**
0583: * The LHS variable.
0584: */
0585: private Variable left_var;
0586:
0587: /**
0588: * The operator to select under (=, <>, >, <, >=, <=).
0589: */
0590: private Operator op;
0591:
0592: /**
0593: * The RHS expression.
0594: */
0595: private Expression right_expression;
0596:
0597: public SimpleSelectNode(QueryPlanNode child, Variable left_var,
0598: Operator op, Expression right_expression) {
0599: super (child);
0600: this .left_var = left_var;
0601: this .op = op;
0602: this .right_expression = right_expression;
0603: }
0604:
0605: public Table evaluate(QueryContext context) {
0606: // Solve the child branch result
0607: Table table = child.evaluate(context);
0608:
0609: // The select operation.
0610: return table.simpleSelect(context, left_var, op,
0611: right_expression);
0612: }
0613:
0614: public ArrayList discoverTableNames(ArrayList list) {
0615: return right_expression.discoverTableNames(super
0616: .discoverTableNames(list));
0617: }
0618:
0619: public ArrayList discoverCorrelatedVariables(int level,
0620: ArrayList list) {
0621: return right_expression.discoverCorrelatedVariables(level,
0622: super .discoverCorrelatedVariables(level, list));
0623: }
0624:
0625: public Object clone() throws CloneNotSupportedException {
0626: SimpleSelectNode node = (SimpleSelectNode) super .clone();
0627: node.left_var = (Variable) left_var.clone();
0628: node.right_expression = (Expression) right_expression
0629: .clone();
0630: return node;
0631: }
0632:
0633: public String titleString() {
0634: return "SIMPLE: " + left_var + op + right_expression;
0635: }
0636:
0637: }
0638:
0639: /**
0640: * The node for performing an equi-select on a group of columns of the
0641: * child node. This is a separate node instead of chained
0642: * IndexedSelectNode's so that we might exploit multi-column indexes.
0643: */
0644: public static class MultiColumnEquiSelectNode extends
0645: SingleQueryPlanNode {
0646:
0647: static final long serialVersionUID = -1407710412096857588L;
0648:
0649: /**
0650: * The list of columns to select the range of.
0651: */
0652: private Variable[] columns;
0653:
0654: /**
0655: * The values of the cells to equi-select (must be constant expressions).
0656: */
0657: private Expression[] values;
0658:
0659: public MultiColumnEquiSelectNode(QueryPlanNode child,
0660: Variable[] columns, Expression[] values) {
0661: super (child);
0662: this .columns = columns;
0663: this .values = values;
0664: }
0665:
0666: public Table evaluate(QueryContext context) {
0667: Table t = child.evaluate(context);
0668:
0669: // PENDING: Exploit multi-column indexes when they are implemented...
0670:
0671: // We select each column in turn
0672: Operator EQUALS_OP = Operator.get("=");
0673: for (int i = 0; i < columns.length; ++i) {
0674: t = t.simpleSelect(context, columns[i], EQUALS_OP,
0675: values[i]);
0676: }
0677:
0678: return t;
0679: }
0680:
0681: public ArrayList discoverTableNames(ArrayList list) {
0682: throw new Error("PENDING");
0683: }
0684:
0685: public ArrayList discoverCorrelatedVariables(int level,
0686: ArrayList list) {
0687: throw new Error("PENDING");
0688: }
0689:
0690: public Object clone() throws CloneNotSupportedException {
0691: MultiColumnEquiSelectNode node = (MultiColumnEquiSelectNode) super
0692: .clone();
0693: cloneArray(node.columns);
0694: cloneArray(node.values);
0695: return node;
0696: }
0697:
0698: }
0699:
0700: /**
0701: * The node for performing a functional select operation on the child node.
0702: * Some examples of this type of query are;
0703: * CONCAT(a, ' ', b) > 'abba boh'
0704: * TONUMBER(DATEFORMAT(a, 'yyyy')) > 2001
0705: * LOWER(a) < 'ook'
0706: * The reason this is a separate node is because it is possible to exploit
0707: * a functional indexes on a table with this node.
0708: * <p>
0709: * The given expression MUST be of the form;
0710: * 'function_expression' 'operator' 'constant'
0711: */
0712: public static class FunctionalSelectNode extends
0713: SingleQueryPlanNode {
0714:
0715: static final long serialVersionUID = -1428022600352236457L;
0716:
0717: /**
0718: * The function expression (eg. CONCAT(a, ' ', b) == 'abba bo').
0719: */
0720: private Expression expression;
0721:
0722: public FunctionalSelectNode(QueryPlanNode child, Expression exp) {
0723: super (child);
0724: this .expression = exp;
0725: }
0726:
0727: public Table evaluate(QueryContext context) {
0728: Table t = child.evaluate(context);
0729: // NOTE: currently this uses exhaustive select but should exploit
0730: // function indexes when they are available.
0731: return t.exhaustiveSelect(context, expression);
0732: }
0733:
0734: public ArrayList discoverTableNames(ArrayList list) {
0735: return expression.discoverTableNames(super
0736: .discoverTableNames(list));
0737: }
0738:
0739: public ArrayList discoverCorrelatedVariables(int level,
0740: ArrayList list) {
0741: return expression.discoverCorrelatedVariables(level, super
0742: .discoverCorrelatedVariables(level, list));
0743: }
0744:
0745: public Object clone() throws CloneNotSupportedException {
0746: FunctionalSelectNode node = (FunctionalSelectNode) super
0747: .clone();
0748: node.expression = (Expression) expression.clone();
0749: return node;
0750: }
0751:
0752: }
0753:
0754: /**
0755: * The node for performing a exhaustive select operation on the child node.
0756: * This node will iterate through the entire child result and all
0757: * results that evaulate to true are included in the result.
0758: * <p>
0759: * NOTE: The Expression may have correlated sub-queries.
0760: */
0761: public static class ExhaustiveSelectNode extends
0762: SingleQueryPlanNode {
0763:
0764: static final long serialVersionUID = -2005551680157574172L;
0765:
0766: /**
0767: * The search expression.
0768: */
0769: private Expression expression;
0770:
0771: public ExhaustiveSelectNode(QueryPlanNode child, Expression exp) {
0772: super (child);
0773: this .expression = exp;
0774: }
0775:
0776: public Table evaluate(QueryContext context) {
0777: Table t = child.evaluate(context);
0778: return t.exhaustiveSelect(context, expression);
0779: }
0780:
0781: public ArrayList discoverTableNames(ArrayList list) {
0782: return expression.discoverTableNames(super
0783: .discoverTableNames(list));
0784: }
0785:
0786: public ArrayList discoverCorrelatedVariables(int level,
0787: ArrayList list) {
0788: return expression.discoverCorrelatedVariables(level, super
0789: .discoverCorrelatedVariables(level, list));
0790: }
0791:
0792: public Object clone() throws CloneNotSupportedException {
0793: ExhaustiveSelectNode node = (ExhaustiveSelectNode) super
0794: .clone();
0795: node.expression = (Expression) expression.clone();
0796: return node;
0797: }
0798:
0799: public String titleString() {
0800: return "EXHAUSTIVE: " + expression;
0801: }
0802:
0803: }
0804:
0805: /**
0806: * The node for evaluating an expression that contains entirely constant
0807: * values (no variables).
0808: */
0809: public static class ConstantSelectNode extends SingleQueryPlanNode {
0810:
0811: static final long serialVersionUID = -4435336817396073146L;
0812:
0813: /**
0814: * The search expression.
0815: */
0816: private Expression expression;
0817:
0818: public ConstantSelectNode(QueryPlanNode child, Expression exp) {
0819: super (child);
0820: this .expression = exp;
0821: }
0822:
0823: public Table evaluate(QueryContext context) {
0824: // Evaluate the expression
0825: TObject v = expression.evaluate(null, null, context);
0826: // If it evaluates to NULL or FALSE then return an empty set
0827: if (v.isNull() || v.getObject().equals(Boolean.FALSE)) {
0828: return child.evaluate(context).emptySelect();
0829: } else {
0830: return child.evaluate(context);
0831: }
0832: }
0833:
0834: public ArrayList discoverTableNames(ArrayList list) {
0835: return expression.discoverTableNames(super
0836: .discoverTableNames(list));
0837: }
0838:
0839: public ArrayList discoverCorrelatedVariables(int level,
0840: ArrayList list) {
0841: return expression.discoverCorrelatedVariables(level, super
0842: .discoverCorrelatedVariables(level, list));
0843: }
0844:
0845: public Object clone() throws CloneNotSupportedException {
0846: ConstantSelectNode node = (ConstantSelectNode) super
0847: .clone();
0848: node.expression = (Expression) expression.clone();
0849: return node;
0850: }
0851:
0852: public String titleString() {
0853: return "CONSTANT: " + expression;
0854: }
0855:
0856: }
0857:
0858: /**
0859: * The node for evaluating a simple pattern search on a table which
0860: * includes a single left hand variable or constant, a pattern type (LIKE,
0861: * NOT LIKE or REGEXP), and a right hand constant (eg. 'T__y'). If the
0862: * expression is not in this form then this node will not operate
0863: * correctly.
0864: */
0865: public static class SimplePatternSelectNode extends
0866: SingleQueryPlanNode {
0867:
0868: static final long serialVersionUID = -8247282157310682761L;
0869:
0870: /**
0871: * The search expression.
0872: */
0873: private Expression expression;
0874:
0875: public SimplePatternSelectNode(QueryPlanNode child,
0876: Expression exp) {
0877: super (child);
0878: this .expression = exp;
0879: }
0880:
0881: public Table evaluate(QueryContext context) {
0882: // Evaluate the child
0883: Table t = child.evaluate(context);
0884: // Perform the pattern search expression on the table.
0885: // Split the expression,
0886: Expression[] exps = expression.split();
0887: Variable lhs_var = exps[0].getVariable();
0888: if (lhs_var != null) {
0889: // LHS is a simple variable so do a simple select
0890: Operator op = (Operator) expression.last();
0891: return t.simpleSelect(context, lhs_var, op, exps[1]);
0892: } else {
0893: // LHS must be a constant so we can just evaluate the expression
0894: // and see if we get true, false, null, etc.
0895: TObject v = expression.evaluate(null, context);
0896: // If it evaluates to NULL or FALSE then return an empty set
0897: if (v.isNull() || v.getObject().equals(Boolean.FALSE)) {
0898: return t.emptySelect();
0899: } else {
0900: return t;
0901: }
0902: }
0903: }
0904:
0905: public ArrayList discoverTableNames(ArrayList list) {
0906: return expression.discoverTableNames(super
0907: .discoverTableNames(list));
0908: }
0909:
0910: public ArrayList discoverCorrelatedVariables(int level,
0911: ArrayList list) {
0912: return expression.discoverCorrelatedVariables(level, super
0913: .discoverCorrelatedVariables(level, list));
0914: }
0915:
0916: public Object clone() throws CloneNotSupportedException {
0917: SimplePatternSelectNode node = (SimplePatternSelectNode) super
0918: .clone();
0919: node.expression = (Expression) expression.clone();
0920: return node;
0921: }
0922:
0923: public String titleString() {
0924: return "PATTERN: " + expression;
0925: }
0926:
0927: }
0928:
0929: /**
0930: * The node for finding a subset and renaming the columns of the results in
0931: * the child node.
0932: */
0933: public static class SubsetNode extends SingleQueryPlanNode {
0934:
0935: static final long serialVersionUID = 3784462788248510832L;
0936:
0937: /**
0938: * The original columns in the child that we are to make the subset of.
0939: */
0940: private Variable[] original_columns;
0941:
0942: /**
0943: * New names to assign the columns.
0944: */
0945: private Variable[] new_column_names;
0946:
0947: public SubsetNode(QueryPlanNode child,
0948: Variable[] original_columns, Variable[] new_column_names) {
0949: super (child);
0950: this .original_columns = original_columns;
0951: this .new_column_names = new_column_names;
0952:
0953: }
0954:
0955: public Table evaluate(QueryContext context) {
0956: Table t = child.evaluate(context);
0957:
0958: int sz = original_columns.length;
0959: int[] col_map = new int[sz];
0960:
0961: // // DEBUG
0962: // for (int n = 0; n < t.getColumnCount(); ++n) {
0963: // System.out.print(t.getResolvedVariable(n).toTechString());
0964: // System.out.print(", ");
0965: // }
0966: // System.out.println();
0967: // // - DEBUG
0968:
0969: for (int i = 0; i < sz; ++i) {
0970:
0971: // // DEBUG
0972: // System.out.print(t.getClass() + ".findFieldName(" +
0973: // original_columns[i].toTechString() + ") = ");
0974: // // - DEBUG
0975:
0976: col_map[i] = t.findFieldName(original_columns[i]);
0977:
0978: // // DEBUG
0979: // System.out.println(col_map[i]);
0980: // // - DEBUG
0981:
0982: }
0983:
0984: SubsetColumnTable col_table = new SubsetColumnTable(t);
0985: col_table.setColumnMap(col_map, new_column_names);
0986:
0987: return col_table;
0988: }
0989:
0990: // ---------- Set methods ----------
0991:
0992: /**
0993: * Sets the given table name of the resultant table. This is intended
0994: * if we want to create a sub-query that has an aliased table name.
0995: */
0996: public void setGivenName(TableName name) {
0997: // given_name = name;
0998: if (name != null) {
0999: int sz = new_column_names.length;
1000: for (int i = 0; i < sz; ++i) {
1001: new_column_names[i].setTableName(name);
1002: }
1003: }
1004: }
1005:
1006: // ---------- Get methods ----------
1007:
1008: /**
1009: * Returns the list of original columns that represent the mappings from
1010: * the columns in this subset.
1011: */
1012: public Variable[] getOriginalColumns() {
1013: return original_columns;
1014: }
1015:
1016: /**
1017: * Returns the list of new column names that represent the new columns
1018: * in this subset.
1019: */
1020: public Variable[] getNewColumnNames() {
1021: return new_column_names;
1022: }
1023:
1024: public Object clone() throws CloneNotSupportedException {
1025: SubsetNode node = (SubsetNode) super .clone();
1026: cloneArray(node.original_columns);
1027: cloneArray(node.new_column_names);
1028: return node;
1029: }
1030:
1031: public String titleString() {
1032: StringBuffer buf = new StringBuffer();
1033: buf.append("SUBSET: ");
1034: for (int i = 0; i < new_column_names.length; ++i) {
1035: buf.append(new_column_names[i]);
1036: buf.append("->");
1037: buf.append(original_columns[i]);
1038: buf.append(", ");
1039: }
1040: return new String(buf);
1041: }
1042:
1043: }
1044:
1045: /**
1046: * The node for performing a distinct operation on the given columns of the
1047: * child node.
1048: */
1049: public static class DistinctNode extends SingleQueryPlanNode {
1050:
1051: static final long serialVersionUID = -1538264313804102373L;
1052:
1053: /**
1054: * The list of columns to be distinct.
1055: */
1056: private Variable[] columns;
1057:
1058: public DistinctNode(QueryPlanNode child, Variable[] columns) {
1059: super (child);
1060: this .columns = columns;
1061: }
1062:
1063: public Table evaluate(QueryContext context) {
1064: Table t = child.evaluate(context);
1065: int sz = columns.length;
1066: int[] col_map = new int[sz];
1067: for (int i = 0; i < sz; ++i) {
1068: col_map[i] = t.findFieldName(columns[i]);
1069: }
1070: return t.distinct(col_map);
1071: }
1072:
1073: public Object clone() throws CloneNotSupportedException {
1074: DistinctNode node = (DistinctNode) super .clone();
1075: cloneArray(node.columns);
1076: return node;
1077: }
1078:
1079: public String titleString() {
1080: StringBuffer buf = new StringBuffer();
1081: buf.append("DISTINCT: (");
1082: for (int i = 0; i < columns.length; ++i) {
1083: buf.append(columns[i]);
1084: buf.append(", ");
1085: }
1086: buf.append(")");
1087: return new String(buf);
1088: }
1089:
1090: }
1091:
1092: /**
1093: * The node for performing a sort operation on the given columns of the
1094: * child node.
1095: */
1096: public static class SortNode extends SingleQueryPlanNode {
1097:
1098: static final long serialVersionUID = 3644480534542996928L;
1099:
1100: /**
1101: * The list of columns to sort.
1102: */
1103: private Variable[] columns;
1104:
1105: /**
1106: * Whether to sort the column in ascending or descending order
1107: */
1108: private boolean[] correct_ascending;
1109:
1110: public SortNode(QueryPlanNode child, Variable[] columns,
1111: boolean[] ascending) {
1112: super (child);
1113: this .columns = columns;
1114: this .correct_ascending = ascending;
1115:
1116: // How we handle ascending/descending order
1117: // ----------------------------------------
1118: // Internally to the database, all columns are naturally ordered in
1119: // ascending order (start at lowest and end on highest). When a column
1120: // is ordered in descending order, a fast way to achieve this is to take
1121: // the ascending set and reverse it. This works for single columns,
1122: // however some thought is required for handling multiple column. We
1123: // order columns from RHS to LHS. If LHS is descending then this will
1124: // order the RHS incorrectly if we leave as is. Therefore, we must do
1125: // some pre-processing that looks ahead on any descending orders and
1126: // reverses the order of the columns to the right. This pre-processing
1127: // is done in the first pass.
1128:
1129: int sz = ascending.length;
1130: for (int n = 0; n < sz - 1; ++n) {
1131: if (!ascending[n]) { // if descending...
1132: // Reverse order of all columns to the right...
1133: for (int p = n + 1; p < sz; ++p) {
1134: ascending[p] = !ascending[p];
1135: }
1136: }
1137: }
1138:
1139: }
1140:
1141: public Table evaluate(QueryContext context) {
1142: Table t = child.evaluate(context);
1143: // Sort the results by the columns in reverse-safe order.
1144: int sz = correct_ascending.length;
1145: for (int n = sz - 1; n >= 0; --n) {
1146: t = t.orderByColumn(columns[n], correct_ascending[n]);
1147: }
1148: return t;
1149: }
1150:
1151: public Object clone() throws CloneNotSupportedException {
1152: SortNode node = (SortNode) super .clone();
1153: cloneArray(node.columns);
1154: return node;
1155: }
1156:
1157: public String titleString() {
1158: StringBuffer buf = new StringBuffer();
1159: buf.append("SORT: (");
1160: for (int i = 0; i < columns.length; ++i) {
1161: buf.append(columns[i]);
1162: if (correct_ascending[i]) {
1163: buf.append(" ASC");
1164: } else {
1165: buf.append(" DESC");
1166: }
1167: buf.append(", ");
1168: }
1169: buf.append(")");
1170: return new String(buf);
1171: }
1172:
1173: }
1174:
1175: /**
1176: * The node for performing a grouping operation on the columns of the child
1177: * node. As well as grouping, any aggregate functions must also be defined
1178: * with this plan.
1179: * <p>
1180: * NOTE: The whole child is a group if columns is null.
1181: */
1182: public static class GroupNode extends SingleQueryPlanNode {
1183:
1184: static final long serialVersionUID = 7140928678192396348L;
1185:
1186: /**
1187: * The columns to group by.
1188: */
1189: private Variable[] columns;
1190:
1191: /**
1192: * The group max column.
1193: */
1194: private Variable group_max_column;
1195:
1196: /**
1197: * Any aggregate functions (or regular function columns) that are to be
1198: * planned.
1199: */
1200: private Expression[] function_list;
1201:
1202: /**
1203: * The list of names to give each function table.
1204: */
1205: private String[] name_list;
1206:
1207: /**
1208: * Groups over the given columns from the child.
1209: */
1210: public GroupNode(QueryPlanNode child, Variable[] columns,
1211: Variable group_max_column, Expression[] function_list,
1212: String[] name_list) {
1213: super (child);
1214: this .columns = columns;
1215: this .group_max_column = group_max_column;
1216: this .function_list = function_list;
1217: this .name_list = name_list;
1218: }
1219:
1220: /**
1221: * Groups over the entire child (always ends in 1 result in set).
1222: */
1223: public GroupNode(QueryPlanNode child,
1224: Variable group_max_column, Expression[] function_list,
1225: String[] name_list) {
1226: this (child, null, group_max_column, function_list,
1227: name_list);
1228: }
1229:
1230: public Table evaluate(QueryContext context) {
1231: Table child_table = child.evaluate(context);
1232: DatabaseQueryContext db_context = (DatabaseQueryContext) context;
1233: FunctionTable fun_table = new FunctionTable(child_table,
1234: function_list, name_list, db_context);
1235: // If no columns then it is implied the whole table is the group.
1236: if (columns == null) {
1237: fun_table.setWholeTableAsGroup();
1238: } else {
1239: fun_table.createGroupMatrix(columns);
1240: }
1241: return fun_table.mergeWithReference(group_max_column);
1242: }
1243:
1244: public ArrayList discoverTableNames(ArrayList list) {
1245: list = super .discoverTableNames(list);
1246: for (int i = 0; i < function_list.length; ++i) {
1247: list = function_list[i].discoverTableNames(list);
1248: }
1249: return list;
1250: }
1251:
1252: public ArrayList discoverCorrelatedVariables(int level,
1253: ArrayList list) {
1254: list = super .discoverCorrelatedVariables(level, list);
1255: for (int i = 0; i < function_list.length; ++i) {
1256: list = function_list[i].discoverCorrelatedVariables(
1257: level, list);
1258: }
1259: return list;
1260: }
1261:
1262: public Object clone() throws CloneNotSupportedException {
1263: GroupNode node = (GroupNode) super .clone();
1264: cloneArray(node.columns);
1265: cloneArray(node.function_list);
1266: if (group_max_column != null) {
1267: node.group_max_column = (Variable) group_max_column
1268: .clone();
1269: } else {
1270: node.group_max_column = null;
1271: }
1272: return node;
1273: }
1274:
1275: public String titleString() {
1276: StringBuffer buf = new StringBuffer();
1277: buf.append("GROUP: (");
1278: if (columns == null) {
1279: buf.append("WHOLE TABLE");
1280: } else {
1281: for (int i = 0; i < columns.length; ++i) {
1282: buf.append(columns[i]);
1283: buf.append(", ");
1284: }
1285: }
1286: buf.append(")");
1287: if (function_list != null) {
1288: buf.append(" FUNS: [");
1289: for (int i = 0; i < function_list.length; ++i) {
1290: buf.append(function_list[i]);
1291: buf.append(", ");
1292: }
1293: buf.append("]");
1294: }
1295: return new String(buf);
1296: }
1297:
1298: }
1299:
1300: /**
1301: * The node for merging the child node with a set of new function columns
1302: * over the entire result. For example, we may want to add an expression
1303: * 'a + 10' or 'coalesce(a, b, 1)'.
1304: */
1305: public static class CreateFunctionsNode extends SingleQueryPlanNode {
1306:
1307: static final long serialVersionUID = -181012844247626327L;
1308:
1309: /**
1310: * The list of functions to create.
1311: */
1312: private Expression[] function_list;
1313:
1314: /**
1315: * The list of names to give each function table.
1316: */
1317: private String[] name_list;
1318:
1319: /**
1320: * Constructor.
1321: */
1322: public CreateFunctionsNode(QueryPlanNode child,
1323: Expression[] function_list, String[] name_list) {
1324: super (child);
1325: this .function_list = function_list;
1326: this .name_list = name_list;
1327: }
1328:
1329: public Table evaluate(QueryContext context) {
1330: Table child_table = child.evaluate(context);
1331: DatabaseQueryContext db_context = (DatabaseQueryContext) context;
1332: FunctionTable fun_table = new FunctionTable(child_table,
1333: function_list, name_list, db_context);
1334: Table t = fun_table.mergeWithReference(null);
1335: return t;
1336: }
1337:
1338: public ArrayList discoverTableNames(ArrayList list) {
1339: list = super .discoverTableNames(list);
1340: for (int i = 0; i < function_list.length; ++i) {
1341: list = function_list[i].discoverTableNames(list);
1342: }
1343: return list;
1344: }
1345:
1346: public ArrayList discoverCorrelatedVariables(int level,
1347: ArrayList list) {
1348: list = super .discoverCorrelatedVariables(level, list);
1349: for (int i = 0; i < function_list.length; ++i) {
1350: list = function_list[i].discoverCorrelatedVariables(
1351: level, list);
1352: }
1353: return list;
1354: }
1355:
1356: public Object clone() throws CloneNotSupportedException {
1357: CreateFunctionsNode node = (CreateFunctionsNode) super
1358: .clone();
1359: cloneArray(node.function_list);
1360: return node;
1361: }
1362:
1363: public String titleString() {
1364: StringBuffer buf = new StringBuffer();
1365: buf.append("FUNCTIONS: (");
1366: for (int i = 0; i < function_list.length; ++i) {
1367: buf.append(function_list[i]);
1368: buf.append(", ");
1369: }
1370: buf.append(")");
1371: return new String(buf);
1372: }
1373:
1374: }
1375:
1376: /**
1377: * A marker node that takes the result of a child and marks it as a name
1378: * that can later be retrieved. This is useful for implementing things
1379: * such as outer joins.
1380: */
1381: public static class MarkerNode extends SingleQueryPlanNode {
1382:
1383: static final long serialVersionUID = -8321710589608765270L;
1384:
1385: /**
1386: * The name of this mark.
1387: */
1388: private String mark_name;
1389:
1390: /**
1391: * Constructor.
1392: */
1393: public MarkerNode(QueryPlanNode child, String mark_name) {
1394: super (child);
1395: this .mark_name = mark_name;
1396: }
1397:
1398: public Table evaluate(QueryContext context) {
1399: Table child_table = child.evaluate(context);
1400: context.addMarkedTable(mark_name, child_table);
1401: return child_table;
1402: }
1403:
1404: public Object clone() throws CloneNotSupportedException {
1405: return super .clone();
1406: }
1407:
1408: }
1409:
1410: /**
1411: * A cache point node that only evaluates the child if the result can not
1412: * be found in the cache with the given unique id.
1413: */
1414: public static class CachePointNode extends SingleQueryPlanNode {
1415:
1416: static final long serialVersionUID = 7866310557831478639L;
1417:
1418: /**
1419: * The unique identifier of this cache point.
1420: */
1421: private long id;
1422:
1423: private final static Object GLOB_LOCK = new Object();
1424: private static int GLOB_ID = 0;
1425:
1426: /**
1427: * Constructor.
1428: */
1429: public CachePointNode(QueryPlanNode child) {
1430: super (child);
1431: synchronized (GLOB_LOCK) {
1432: id = (System.currentTimeMillis() << 16)
1433: | (GLOB_ID & 0x0FFFF);
1434: ++GLOB_ID;
1435: }
1436: }
1437:
1438: public Table evaluate(QueryContext context) {
1439: // Is the result available in the context?
1440: Table child_table = context.getCachedNode(id);
1441: if (child_table == null) {
1442: // No so evaluate the child and cache it
1443: child_table = child.evaluate(context);
1444: context.putCachedNode(id, child_table);
1445: }
1446: return child_table;
1447: }
1448:
1449: public Object clone() throws CloneNotSupportedException {
1450: return super .clone();
1451: }
1452:
1453: public String titleString() {
1454: return "CACHE: " + id;
1455: }
1456:
1457: }
1458:
1459: /**
1460: * A branch node for naturally joining two tables together. These branches
1461: * should be optimized out if possible because they result in huge results.
1462: */
1463: public static class NaturalJoinNode extends BranchQueryPlanNode {
1464:
1465: static final long serialVersionUID = 942526205653132810L;
1466:
1467: public NaturalJoinNode(QueryPlanNode left, QueryPlanNode right) {
1468: super (left, right);
1469: }
1470:
1471: public Table evaluate(QueryContext context) {
1472: // Solve the left branch result
1473: Table left_result = left.evaluate(context);
1474: // Solve the Join (natural)
1475: return left_result.join(right.evaluate(context));
1476: }
1477:
1478: public String titleString() {
1479: return "NATURAL JOIN";
1480: }
1481:
1482: }
1483:
1484: /**
1485: * A branch node for equi-joining two tables together given two sets of
1486: * columns. This is a seperate node from a general join operation to allow
1487: * for optimizations with multi-column indexes.
1488: * <p>
1489: * An equi-join is the most common type of join.
1490: * <p>
1491: * At query runtime, this decides the best best way to perform the join,
1492: * either by
1493: */
1494: public static class EquiJoinNode extends BranchQueryPlanNode {
1495:
1496: static final long serialVersionUID = 113332589582049607L;
1497:
1498: /**
1499: * The columns in the left table.
1500: */
1501: private Variable[] left_columns;
1502:
1503: /**
1504: * The columns in the right table.
1505: */
1506: private Variable[] right_columns;
1507:
1508: public EquiJoinNode(QueryPlanNode left, QueryPlanNode right,
1509: Variable[] left_cols, Variable[] right_cols) {
1510: super (left, right);
1511: this .left_columns = left_cols;
1512: this .right_columns = right_cols;
1513: }
1514:
1515: public Table evaluate(QueryContext context) {
1516: // Solve the left branch result
1517: Table left_result = left.evaluate(context);
1518: // Solve the right branch result
1519: Table right_result = right.evaluate(context);
1520:
1521: // PENDING: This needs to migrate to a better implementation that
1522: // exploits multi-column indexes if one is defined that can be used.
1523:
1524: Variable first_left = left_columns[0];
1525: Variable first_right = right_columns[0];
1526:
1527: Operator EQUALS_OP = Operator.get("=");
1528:
1529: Table result = left_result.simpleJoin(context,
1530: right_result, first_left, EQUALS_OP,
1531: new Expression(first_right));
1532:
1533: int sz = left_columns.length;
1534: // If there are columns left to equi-join, we resolve the rest with a
1535: // single exhaustive select of the form,
1536: // ( table1.col2 = table2.col2 AND table1.col3 = table2.col3 AND ... )
1537: if (sz > 1) {
1538: // Form the expression
1539: Expression rest_expression = new Expression();
1540: for (int i = 1; i < sz; ++i) {
1541: Variable left_var = left_columns[i];
1542: Variable right_var = right_columns[i];
1543: rest_expression.addElement(left_var);
1544: rest_expression.addElement(right_var);
1545: rest_expression.addOperator(EQUALS_OP);
1546: }
1547: Operator AND_OP = Operator.get("and");
1548: for (int i = 2; i < sz; ++i) {
1549: rest_expression.addOperator(AND_OP);
1550: }
1551: result = result.exhaustiveSelect(context,
1552: rest_expression);
1553: }
1554:
1555: return result;
1556: }
1557:
1558: public Object clone() throws CloneNotSupportedException {
1559: EquiJoinNode node = (EquiJoinNode) super .clone();
1560: cloneArray(node.left_columns);
1561: cloneArray(node.right_columns);
1562: return node;
1563: }
1564:
1565: }
1566:
1567: /**
1568: * A branch node for a non-equi join between two tables.
1569: * <p>
1570: * NOTE: The cost of a LeftJoin is higher if the right child result is
1571: * greater than the left child result. The plan should be arranged so
1572: * smaller results are on the left.
1573: */
1574: public static class JoinNode extends BranchQueryPlanNode {
1575:
1576: static final long serialVersionUID = 4133205808616807832L;
1577:
1578: /**
1579: * The variable in the left table to be joined.
1580: */
1581: private Variable left_var;
1582:
1583: /**
1584: * The operator to join under (=, <>, >, <, >=, <=).
1585: */
1586: private Operator join_op;
1587:
1588: /**
1589: * The expression evaluated on the right table.
1590: */
1591: private Expression right_expression;
1592:
1593: public JoinNode(QueryPlanNode left, QueryPlanNode right,
1594: Variable left_var, Operator join_op,
1595: Expression right_expression) {
1596: super (left, right);
1597: this .left_var = left_var;
1598: this .join_op = join_op;
1599: this .right_expression = right_expression;
1600: }
1601:
1602: public Table evaluate(QueryContext context) {
1603: // Solve the left branch result
1604: Table left_result = left.evaluate(context);
1605: // Solve the right branch result
1606: Table right_result = right.evaluate(context);
1607:
1608: // If the right_expression is a simple variable then we have the option
1609: // of optimizing this join by putting the smallest table on the LHS.
1610: Variable rhs_var = right_expression.getVariable();
1611: Variable lhs_var = left_var;
1612: Operator op = join_op;
1613: if (rhs_var != null) {
1614: // We should arrange the expression so the right table is the smallest
1615: // of the sides.
1616: // If the left result is less than the right result
1617: if (left_result.getRowCount() < right_result
1618: .getRowCount()) {
1619: // Reverse the join
1620: right_expression = new Expression(lhs_var);
1621: lhs_var = rhs_var;
1622: op = op.reverse();
1623: // Reverse the tables.
1624: Table t = right_result;
1625: right_result = left_result;
1626: left_result = t;
1627: }
1628: }
1629:
1630: // The join operation.
1631: return left_result.simpleJoin(context, right_result,
1632: lhs_var, op, right_expression);
1633: }
1634:
1635: public ArrayList discoverTableNames(ArrayList list) {
1636: return right_expression.discoverTableNames(super
1637: .discoverTableNames(list));
1638: }
1639:
1640: public ArrayList discoverCorrelatedVariables(int level,
1641: ArrayList list) {
1642: return right_expression.discoverCorrelatedVariables(level,
1643: super .discoverCorrelatedVariables(level, list));
1644: }
1645:
1646: public Object clone() throws CloneNotSupportedException {
1647: JoinNode node = (JoinNode) super .clone();
1648: node.left_var = (Variable) left_var.clone();
1649: node.right_expression = (Expression) right_expression
1650: .clone();
1651: return node;
1652: }
1653:
1654: public String titleString() {
1655: return "JOIN: " + left_var + join_op + right_expression;
1656: }
1657:
1658: }
1659:
1660: /**
1661: * A branch node for a left outer join. Using this node is a little non-
1662: * intuitive. This node will only work when used in conjuction with
1663: * MarkerNode.
1664: * <p>
1665: * To use - first the complete left table in the join must be marked with a
1666: * name. Then the ON expression is evaluated to a single plan node. Then
1667: * this plan node must be added to result in a left outer join. A tree for
1668: * a left outer join may look as follows;
1669: * <p><pre>
1670: * LeftOuterJoinNode
1671: * |
1672: * Join a = b
1673: * / \
1674: * Marker GetTable T2
1675: * |
1676: * GetTable T1
1677: * </pre>
1678: */
1679: public static class LeftOuterJoinNode extends SingleQueryPlanNode {
1680:
1681: static final long serialVersionUID = 8908801499550863492L;
1682:
1683: /**
1684: * The name of the mark that points to the left table that represents
1685: * the complete set.
1686: */
1687: private String complete_mark_name;
1688:
1689: public LeftOuterJoinNode(QueryPlanNode child,
1690: String complete_mark_name) {
1691: super (child);
1692: this .complete_mark_name = complete_mark_name;
1693: }
1694:
1695: public Table evaluate(QueryContext context) {
1696: // Evaluate the child branch,
1697: Table result = child.evaluate(context);
1698: // Get the table of the complete mark name,
1699: Table complete_left = context
1700: .getMarkedTable(complete_mark_name);
1701:
1702: // The rows in 'complete_left' that are outside (not in) the rows in the
1703: // left result.
1704: Table outside = complete_left.outside(result);
1705:
1706: // Create an OuterTable
1707: OuterTable outer_table = new OuterTable(result);
1708: outer_table.mergeIn(outside);
1709:
1710: // Return the outer table
1711: return outer_table;
1712: }
1713:
1714: public String titleString() {
1715: return "LEFT OUTER JOIN";
1716: }
1717:
1718: }
1719:
1720: /**
1721: * A branch node for a logical union of two tables of identical types. This
1722: * branch can only work if the left and right children have exactly the same
1723: * ancestor tables. If the ancestor tables are different it will fail. This
1724: * node is used for logical OR.
1725: * <p>
1726: * This union does not include duplicated rows.
1727: */
1728: public static class LogicalUnionNode extends BranchQueryPlanNode {
1729:
1730: static final long serialVersionUID = -7783166856668779902L;
1731:
1732: public LogicalUnionNode(QueryPlanNode left, QueryPlanNode right) {
1733: super (left, right);
1734: }
1735:
1736: public Table evaluate(QueryContext context) {
1737: // Solve the left branch result
1738: Table left_result = left.evaluate(context);
1739: // Solve the right branch result
1740: Table right_result = right.evaluate(context);
1741:
1742: return left_result.union(right_result);
1743: }
1744:
1745: public String titleString() {
1746: return "LOGICAL UNION";
1747: }
1748:
1749: }
1750:
1751: /**
1752: * A branch node for performing a composite function on two child nodes.
1753: * This branch is used for general UNION, EXCEPT, INTERSECT composites. The
1754: * left and right branch results must have the same number of columns and
1755: * column types.
1756: */
1757: public static class CompositeNode extends BranchQueryPlanNode {
1758:
1759: static final long serialVersionUID = -560587816928425857L;
1760:
1761: /**
1762: * The composite operation
1763: * (either CompositeTable.UNION, EXCEPT, INTERSECT).
1764: */
1765: private int composite_op;
1766:
1767: /**
1768: * If this is true, the composite includes all results from both children,
1769: * otherwise removes deplicates.
1770: */
1771: private boolean all_op;
1772:
1773: public CompositeNode(QueryPlanNode left, QueryPlanNode right,
1774: int composite_op, boolean all_op) {
1775: super (left, right);
1776: this .composite_op = composite_op;
1777: this .all_op = all_op;
1778: }
1779:
1780: public Table evaluate(QueryContext context) {
1781: // Solve the left branch result
1782: Table left_result = left.evaluate(context);
1783: // Solve the right branch result
1784: Table right_result = right.evaluate(context);
1785:
1786: // Form the composite table
1787: CompositeTable t = new CompositeTable(left_result,
1788: new Table[] { left_result, right_result });
1789: t.setupIndexesForCompositeFunction(composite_op, all_op);
1790:
1791: return t;
1792: }
1793:
1794: }
1795:
1796: /**
1797: * A branch node for a non-correlated ANY or ALL sub-query evaluation. This
1798: * node requires a set of columns from the left branch and an operator.
1799: * The right branch represents the non-correlated sub-query.
1800: * <p>
1801: * NOTE: The cost of a SubQuery is higher if the right child result is
1802: * greater than the left child result. The plan should be arranged so
1803: * smaller results are on the left.
1804: */
1805: public static class NonCorrelatedAnyAllNode extends
1806: BranchQueryPlanNode {
1807:
1808: static final long serialVersionUID = 7480579008259288291L;
1809:
1810: /**
1811: * The columns in the left table.
1812: */
1813: private Variable[] left_columns;
1814:
1815: /**
1816: * The SubQuery operator, eg. '= ANY', '<> ALL'
1817: */
1818: private Operator sub_query_operator;
1819:
1820: public NonCorrelatedAnyAllNode(QueryPlanNode left,
1821: QueryPlanNode right, Variable[] left_vars,
1822: Operator subquery_op) {
1823: super (left, right);
1824: this .left_columns = left_vars;
1825: this .sub_query_operator = subquery_op;
1826: }
1827:
1828: public Table evaluate(QueryContext context) {
1829: // Solve the left branch result
1830: Table left_result = left.evaluate(context);
1831: // Solve the right branch result
1832: Table right_result = right.evaluate(context);
1833:
1834: // Solve the sub query on the left columns with the right plan and the
1835: // given operator.
1836: return TableFunctions.anyAllNonCorrelated(left_result,
1837: left_columns, sub_query_operator, right_result);
1838: }
1839:
1840: public Object clone() throws CloneNotSupportedException {
1841: NonCorrelatedAnyAllNode node = (NonCorrelatedAnyAllNode) super
1842: .clone();
1843: cloneArray(node.left_columns);
1844: return node;
1845: }
1846:
1847: public String titleString() {
1848: StringBuffer buf = new StringBuffer();
1849: buf.append("NON_CORRELATED: (");
1850: for (int i = 0; i < left_columns.length; ++i) {
1851: buf.append(left_columns[i].toString());
1852: }
1853: buf.append(") ");
1854: buf.append(sub_query_operator.toString());
1855: return new String(buf);
1856: }
1857:
1858: }
1859:
1860: }
|