Planner


1   /**
2    * com.mckoi.database.interpret.Planner  12 Nov 2001
3    *
4    * Mckoi SQL Database ( http://www.mckoi.com/database )
5    * Copyright (C) 2000, 2001, 2002  Diehl and Associates, Inc.
6    *
7    * This program is free software; you can redistribute it and/or
8    * modify it under the terms of the GNU General Public License
9    * Version 2 as published by the Free Software Foundation.
10   *
11   * This program is distributed in the hope that it will be useful,
12   * but WITHOUT ANY WARRANTY; without even the implied warranty of
13   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   * GNU General Public License Version 2 for more details.
15   *
16   * You should have received a copy of the GNU General Public License
17   * Version 2 along with this program; if not, write to the Free Software
18   * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19   *
20   * Change Log:
21   * 
22   * 
23   */
24  
25  package com.mckoi.database.interpret;
26  
27  import java.util.Collections  ;
28  import java.util.ArrayList  ;
29  import java.util.Iterator  ;
30  import java.util.List  ;
31  import com.mckoi.database.*;
32  import com.mckoi.util.BigNumber;
33  
34  /**
35   * Various methods for forming query plans on SQL queries.
36   *
37   * @author Tobias Downer
38   */
39  
40  public class Planner {
41  
42    /**
43     * The name of the GROUP BY function table.
44     */
45    private static TableName GROUP_BY_FUNCTION_TABLE = new TableName(
46                                                               "FUNCTIONTABLE");
47  
48  
49  
50    /**
51     * Prepares the given SearchExpression object.  This goes through each
52     * element of the Expression.  If the element is a variable it is qualified.
53     * If the element is a TableSelectExpression it's converted to a
54     * SelectQueriable object and prepared.
55     */
56    private static void prepareSearchExpression(
57           final DatabaseConnection db, final TableExpressionFromSet from_set,
58           SearchExpression expression) throws DatabaseException {
59      // This is used to prepare sub-queries and qualify variables in a
60      // search expression such as WHERE or HAVING.
61  
62      // Prepare the sub-queries first
63      expression.prepare(new ExpressionPreparer() {
64        public boolean canPrepare(Object   element) {
65          return element instanceof TableSelectExpression;
66        }
67        public Object   prepare(Object   element) throws DatabaseException {
68          TableSelectExpression sq_expr = (TableSelectExpression) element;
69          TableExpressionFromSet sq_from_set = generateFromSet(sq_expr, db);
70          sq_from_set.setParent(from_set);
71          QueryPlanNode sq_plan = formQueryPlan(db, sq_expr, sq_from_set, null);
72          // Form this into a query plan type
73          return new TObject(TType.QUERY_PLAN_TYPE,
74                             new QueryPlan.CachePointNode(sq_plan));
75        }
76      });
77  
78      // Then qualify all the variables.  Note that this will not qualify
79      // variables in the sub-queries.
80      expression.prepare(from_set.expressionQualifier());
81  
82    }
83  
84    /**
85     * Given a HAVING clause expression, this will generate a new HAVING clause
86     * expression with all aggregate expressions put into the given extra
87     * function list.
88     */
89    private static Expression filterHavingClause(Expression having_expr,
90                                                 ArrayList   aggregate_list,
91                                                 QueryContext context) {
92      if (having_expr.size() > 1) {
93        Operator op = (Operator) having_expr.last();
94        // If logical, split and filter the left and right expressions
95        Expression[] exps = having_expr.split();
96        Expression new_left =
97                     filterHavingClause(exps[0], aggregate_list, context);
98        Expression new_right =
99                     filterHavingClause(exps[1], aggregate_list, context);
100       Expression expr = new Expression(new_left, op, new_right);
101       return expr;
102     }
103     else {
104       // Not logical so determine if the expression is an aggregate or not
105       if (having_expr.hasAggregateFunction(context)) {
106         // Has aggregate functions so we must put this expression on the
107         // aggregate list.
108         aggregate_list.add(having_expr);
109         // And substitute it with a variable reference.
110         Variable v = Variable.resolve("FUNCTIONTABLE.HAVINGAG_" +
111                                       aggregate_list.size());
112         return new Expression(v);
113       }
114       else {
115         // No aggregate functions so leave it as is.
116         return having_expr;
117       }
118     }
119 
120   }
121 
122   /**
123    * Given a TableExpression, generates a TableExpressionFromSet object.  This
124    * object is used to help qualify variable references.  This
125    */
126   static TableExpressionFromSet generateFromSet(
127             TableSelectExpression select_expression, DatabaseConnection db) {
128 
129     // Get the 'from_clause' from the table expression
130     FromClause from_clause = select_expression.from_clause;
131 
132     // Prepares the from_clause joining set.
133     from_clause.getJoinSet().prepare(db);
134 
135     // Create a TableExpressionFromSet for this table expression
136     TableExpressionFromSet from_set = new TableExpressionFromSet(db);
137 
138     // Add all tables from the 'from_clause'
139     Iterator   tables = from_clause.allTables().iterator();
140     while (tables.hasNext()) {
141       FromTableDef ftdef = (FromTableDef) tables.next();
142       String   unique_key = ftdef.getUniqueKey();
143       String   alias = ftdef.getAlias();
144 
145       // If this is a sub-query table,
146       if (ftdef.isSubQueryTable()) {
147         // eg. FROM ( SELECT id FROM Part )
148         TableSelectExpression sub_query = ftdef.getTableSelectExpression();
149         TableExpressionFromSet sub_query_from_set =
150                                             generateFromSet(sub_query, db);
151         // The aliased name of the table
152         TableName alias_table_name = null;
153         if (alias != null) {
154           alias_table_name = new TableName(alias);
155         }
156         FromTableSubQuerySource source =
157             new FromTableSubQuerySource(db, unique_key, sub_query,
158                                         sub_query_from_set, alias_table_name);
159         // Add to list of subquery tables to add to query,
160         from_set.addTable(source);
161       }
162       // Else must be a standard query table,
163       else {
164         String   name = ftdef.getName();
165 
166         // Resolve to full table name
167         TableName table_name = db.resolveTableName(name);
168 
169         if (!db.tableExists(table_name)) {
170           throw new StatementException(
171                          "Table '" + table_name + "' was not found.");
172         }
173 
174         TableName given_name = null;
175         if (alias != null) {
176           given_name = new TableName(alias);
177         }
178         
179         // Get the TableQueryDef object for this table name (aliased).
180         TableQueryDef table_query_def =
181                                    db.getTableQueryDef(table_name, given_name);
182         FromTableDirectSource source = new FromTableDirectSource(db,
183                           table_query_def, unique_key, given_name, table_name);
184         
185         from_set.addTable(source);
186       }
187     }  // while (tables.hasNext())
188 
189     // Set up functions, aliases and exposed variables for this from set,
190 
191     // The list of columns being selected (SelectColumn).
192     ArrayList   columns = select_expression.columns;
193 
194     // For each column being selected
195     for (int i = 0; i < columns.size(); ++i) {
196       SelectColumn col = (SelectColumn) columns.get(i);
197       // Is this a glob?  (eg. Part.* )
198       if (col.glob_name != null) {
199         // Find the columns globbed and add to the 's_col_list' result.
200         if (col.glob_name.equals("*")) {
201           from_set.exposeAllColumns();
202         }
203         else {
204           // Otherwise the glob must be of the form '[table name].*'
205           String   tname =
206                       col.glob_name.substring(0, col.glob_name.indexOf(".*"));
207           TableName tn = TableName.resolve(tname);
208           from_set.exposeAllColumnsFromSource(tn);
209         }
210       }
211       else {
212         // Otherwise must be a standard column reference.  Note that at this
213         // time we aren't sure if a column expression is correlated and is
214         // referencing an outer source.  This means we can't verify if the
215         // column expression is valid or not at this point.
216 
217         // If this column is aliased, add it as a function reference to the
218         // TableExpressionFromSet.
219         String   alias = col.alias;
220         Variable v = col.expression.getVariable();
221         boolean alias_match_v =
222                    (v != null && alias != null &&
223                     from_set.stringCompare(v.getName(), alias));
224         if (alias != null && !alias_match_v) {
225           from_set.addFunctionRef(alias, col.expression);
226           from_set.exposeVariable(new Variable(alias));
227         }
228         else if (v != null) {
229           Variable resolved = from_set.resolveReference(v);
230           if (resolved == null) {
231             from_set.exposeVariable(v);
232           }
233           else {
234             from_set.exposeVariable(resolved);
235           }
236         }
237         else {
238           String   fun_name = col.expression.text().toString();
239           from_set.addFunctionRef(fun_name, col.expression);
240           from_set.exposeVariable(new Variable(fun_name));
241         }
242       }
243 
244     }  // for each column selected
245 
246     return from_set;
247   }
248 
249   /**
250    * Forms a query plan (QueryPlanNode) from the given TableSelectExpression
251    * and TableExpressionFromSet.  The TableSelectExpression describes the
252    * SELECT query (or sub-query), and the TableExpressionFromSet is used to
253    * resolve expression references.
254    * <p>
255    * The 'order_by' argument is a list of ByColumn objects that represent
256    * an optional ORDER BY clause.  If this is null or the list is empty, no
257    * ordering is done.
258    */
259   public static QueryPlanNode formQueryPlan(DatabaseConnection db,
260         TableSelectExpression expression, TableExpressionFromSet from_set,
261         ArrayList   order_by)
262                                                    throws DatabaseException {
263 
264     QueryContext context = new DatabaseQueryContext(db);
265                                                      
266     // ----- Resolve the SELECT list
267 
268     // What we are selecting
269     QuerySelectColumnSet column_set = new QuerySelectColumnSet(from_set);
270 
271     // The list of columns being selected (SelectColumn).
272     ArrayList   columns = expression.columns;
273 
274     // If there are 0 columns selected, then we assume the result should
275     // show all of the columns in the result.
276     boolean do_subset_column = (columns.size() != 0);
277 
278     // For each column being selected
279     for (int i = 0; i < columns.size(); ++i) {
280       SelectColumn col = (SelectColumn) columns.get(i);
281       // Is this a glob?  (eg. Part.* )
282       if (col.glob_name != null) {
283         // Find the columns globbed and add to the 's_col_list' result.
284         if (col.glob_name.equals("*")) {
285           column_set.selectAllColumnsFromAllSources();
286         }
287         else {
288           // Otherwise the glob must be of the form '[table name].*'
289           String   tname =
290                       col.glob_name.substring(0, col.glob_name.indexOf(".*"));
291           TableName tn = TableName.resolve(tname);
292           column_set.selectAllColumnsFromSource(tn);
293         }
294       }
295       else {
296         // Otherwise must be a standard column reference.
297         column_set.selectSingleColumn(col);
298       }
299 
300     }  // for each column selected
301 
302     // Prepare the column_set,
303     column_set.prepare(context);
304 
305     // -----
306 
307     // Resolve any numerical references in the ORDER BY list (eg.
308     // '1' will be a reference to column 1.
309     
310     if (order_by != null) {
311       ArrayList   prepared_col_set = column_set.s_col_list;
312       for (int i = 0; i < order_by.size(); ++i) {
313         ByColumn col = (ByColumn) order_by.get(i);
314         Expression exp = col.exp;
315         if (exp.size() == 1) {
316           Object   last_elem = exp.last();
317           if (last_elem instanceof TObject) {
318             BigNumber bnum = ((TObject) last_elem).toBigNumber();
319             if (bnum.getScale() == 0) {
320               int col_ref = bnum.intValue() - 1;
321               if (col_ref >= 0 && col_ref < prepared_col_set.size()) {
322                 SelectColumn scol =
323                                   (SelectColumn) prepared_col_set.get(col_ref);
324                 col.exp = new Expression(scol.expression);
325               }
326             }
327           }
328         }
329       }
330     }
331 
332     // -----
333     
334     // Set up plans for each table in the from clause of the query.  For
335     // sub-queries, we recurse.
336 
337     QueryTableSetPlanner table_planner = new QueryTableSetPlanner();
338 
339     for (int i = 0; i < from_set.setCount(); ++i) {
340       FromTableInterface table = from_set.getTable(i);
341       if (table instanceof FromTableSubQuerySource) {
342         // This represents a sub-query in the FROM clause
343 
344         FromTableSubQuerySource sq_table = (FromTableSubQuerySource) table;
345         TableSelectExpression sq_expr = sq_table.getTableExpression();
346         TableExpressionFromSet sq_from_set = sq_table.getFromSet();
347 
348         // Form a plan for evaluating the sub-query FROM
349         QueryPlanNode sq_plan = formQueryPlan(db, sq_expr, sq_from_set, null);
350 
351         // The top should always be a SubsetNode,
352         if (sq_plan instanceof QueryPlan.SubsetNode) {
353           QueryPlan.SubsetNode subset_node = (QueryPlan.SubsetNode) sq_plan;
354           subset_node.setGivenName(sq_table.getAliasedName());
355         }
356         else {
357           throw new RuntimeException  ("Top plan is not a SubsetNode!");
358         }
359 
360         table_planner.addTableSource(sq_plan, sq_table);
361       }
362       else if (table instanceof FromTableDirectSource) {
363         // This represents a direct referencable table in the FROM clause
364 
365         FromTableDirectSource ds_table = (FromTableDirectSource) table;
366         TableName given_name = ds_table.getGivenTableName();
367         TableName root_name = ds_table.getRootTableName();
368         String   aliased_name = null;
369         if (!root_name.equals(given_name)) {
370           aliased_name = given_name.getName();
371         }
372 
373         QueryPlanNode ds_plan = ds_table.createFetchQueryPlanNode();
374         table_planner.addTableSource(ds_plan, ds_table);
375       }
376       else {
377         throw new RuntimeException  (
378                      "Unknown table source instance: " + table.getClass());
379       }
380 
381     }
382 
383     // -----
384 
385     // The WHERE and HAVING clauses
386     SearchExpression where_clause = expression.where_clause;
387     SearchExpression having_clause = expression.having_clause;
388 
389     // Look at the join set and resolve the ON Expression to this statement
390     JoiningSet join_set = expression.from_clause.getJoinSet();
391 
392     // Perform a quick scan and see if there are any outer joins in the
393     // expression.
394     boolean all_inner_joins = true;
395     for (int i = 0; i < join_set.getTableCount() - 1; ++i) {
396       int type = join_set.getJoinType(i);
397       if (type != JoiningSet.INNER_JOIN) {
398         all_inner_joins = false;
399       }
400     }
401 
402     // Prepare the joins
403     for (int i = 0; i < join_set.getTableCount() - 1; ++i) {
404       int type = join_set.getJoinType(i);
405       Expression on_expression = join_set.getOnExpression(i);
406 
407       if (all_inner_joins) {
408         // If the whole join set is inner joins then simply move the on
409         // expression (if there is one) to the WHERE clause.
410         if (on_expression != null) {
411           where_clause.appendExpression(on_expression);
412         }
413       }
414       else {
415         // Not all inner joins,
416         if (type == JoiningSet.INNER_JOIN && on_expression == null) {
417           // Regular join with no ON expression, so no preparation necessary
418         }
419         else {
420           // Either an inner join with an ON expression, or an outer join with
421           // ON expression
422           if (on_expression == null) {
423             throw new RuntimeException  ("No ON expression in join.");
424           }
425           // Resolve the on_expression
426           on_expression.prepare(from_set.expressionQualifier());
427           // And set it in the planner
428           table_planner.setJoinInfoBetweenSources(i, type, on_expression);
429         }
430       }
431 
432     }
433 
434     // Prepare the WHERE and HAVING clause, qualifies all variables and
435     // prepares sub-queries.
436     prepareSearchExpression(db, from_set, where_clause);
437     prepareSearchExpression(db, from_set, having_clause);
438 
439     // Any extra AGGREGATE functions that are part of the HAVING clause that
440     // we need to add.  This is a list of a name followed by the expression
441     // that contains the aggregate function.
442     ArrayList   extra_aggregate_functions = new ArrayList  ();
443     Expression new_having_clause = null;
444     if (having_clause.getFromExpression() != null) {
445       new_having_clause =
446             filterHavingClause(having_clause.getFromExpression(),
447                                extra_aggregate_functions, context);
448       having_clause.setFromExpression(new_having_clause);
449     }
450 
451     // Any GROUP BY functions,
452     ArrayList   group_by_functions = new ArrayList  ();
453 
454     // Resolve the GROUP BY variable list references in this from set
455     ArrayList   group_list_in = expression.group_by;
456     int gsz = group_list_in.size();
457     Variable[] group_by_list = new Variable[gsz];
458     for (int i = 0; i < gsz; ++i) {
459       ByColumn by_column = (ByColumn) group_list_in.get(i);
460       Expression exp = by_column.exp;
461       // Prepare the group by expression
462       exp.prepare(from_set.expressionQualifier());
463       // Is the group by variable a complex expression?
464       Variable v = exp.getVariable();
465 
466       Expression group_by_expression;
467       if (v == null) {
468         group_by_expression = exp;
469       }
470       else {
471         // Can we dereference the variable to an expression in the SELECT?
472         group_by_expression = from_set.dereferenceAssignment(v);
473       }
474 
475       if (group_by_expression != null) {
476         if (group_by_expression.hasAggregateFunction(context)) {
477           throw new StatementException("Aggregate expression '" +
478               group_by_expression.text().toString() +
479               "' is not allowed in GROUP BY clause.");
480         }
481         // Complex expression so add this to the function list.
482         int group_by_fun_num = group_by_functions.size();
483         group_by_functions.add(group_by_expression);
484         v = new Variable(GROUP_BY_FUNCTION_TABLE,
485                          "#GROUPBY-" + group_by_fun_num);
486       }
487       group_by_list[i] = v;
488     }
489 
490     // Resolve GROUP MAX variable to a reference in this from set
491     Variable groupmax_column = expression.group_max;
492     if (groupmax_column != null) {
493       Variable v = from_set.resolveReference(groupmax_column);
494       if (v == null) {
495         throw new StatementException("Could find GROUP MAX reference '" +
496                                      groupmax_column + "'");
497       }
498       groupmax_column = v;
499     }
500 
501     // -----
502 
503     // Now all the variables should be resolved and correlated variables set
504     // up as appropriate.
505 
506     // If nothing in the FROM clause then simply evaluate the result of the
507     // select
508     if (from_set.setCount() == 0) {
509       if (column_set.aggregate_count > 0) {
510         throw new StatementException(
511             "Invalid use of aggregate function in select with no FROM clause");
512       }
513       // Make up the lists
514       ArrayList   s_col_list = column_set.s_col_list;
515       int sz = s_col_list.size();
516       String  [] col_names = new String  [sz];
517       Expression[] exp_list = new Expression[sz];
518       Variable[] subset_vars = new Variable[sz];
519       Variable[] aliases = new Variable[sz];
520       for (int i = 0; i < sz; ++i) {
521         SelectColumn scol = (SelectColumn) s_col_list.get(i);
522         exp_list[i] = scol.expression;
523         col_names[i] = scol.internal_name.getName();
524         subset_vars[i] = new Variable(scol.internal_name);
525         aliases[i] = new Variable(scol.resolved_name);
526       }
527 
528       return new QueryPlan.SubsetNode(
529                new QueryPlan.CreateFunctionsNode(
530                  new QueryPlan.SingleRowTableNode(), exp_list, col_names),
531                subset_vars, aliases);
532     }
533 
534     // Plan the where clause.  The returned node is the plan to evaluate the
535     // WHERE clause.
536     QueryPlanNode node =
537                  table_planner.planSearchExpression(expression.where_clause);
538 
539     // Make up the functions list,
540     ArrayList   functions_list = column_set.function_col_list;
541     int fsz = functions_list.size();
542     ArrayList   complete_fun_list = new ArrayList  ();
543     for (int i = 0; i < fsz; ++i) {
544       SelectColumn scol = (SelectColumn) functions_list.get(i);
545       complete_fun_list.add(scol.expression);
546       complete_fun_list.add(scol.internal_name.getName());
547     }
548     for (int i = 0; i < extra_aggregate_functions.size(); ++i) {
549       complete_fun_list.add(extra_aggregate_functions.get(i));
550       complete_fun_list.add("HAVINGAG_" + (i + 1));
551     }
552 
553     int fsz2 = complete_fun_list.size() / 2;
554     Expression[] def_fun_list = new Expression[fsz2];
555     String  [] def_fun_names = new String  [fsz2];
556     for (int i = 0; i < fsz2; ++i) {
557       def_fun_list[i] = (Expression) complete_fun_list.get(i * 2);
558       def_fun_names[i] = (String  ) complete_fun_list.get((i * 2) + 1);
559     }
560 
561     // If there is more than 1 aggregate function or there is a group by
562     // clause, then we must add a grouping plan.
563     if (column_set.aggregate_count > 0 || gsz > 0) {
564 
565       // If there is no GROUP BY clause then assume the entire result is the
566       // group.
567       if (gsz == 0) {
568         node = new QueryPlan.GroupNode(node, groupmax_column,
569                                        def_fun_list, def_fun_names);
570       }
571       else {
572         // Do we have any group by functions that need to be planned first?
573         int gfsz = group_by_functions.size();
574         if (gfsz > 0) {
575           Expression[] group_fun_list = new Expression[gfsz];
576           String  [] group_fun_name = new String  [gfsz];
577           for (int i = 0; i < gfsz; ++i) {
578             group_fun_list[i] = (Expression) group_by_functions.get(i);
579             group_fun_name[i] = "#GROUPBY-" + i;
580           }
581           node = new QueryPlan.CreateFunctionsNode(node,
582                                             group_fun_list, group_fun_name);
583         }
584 
585         // Otherwise we provide the 'group_by_list' argument
586         node = new QueryPlan.GroupNode(node, group_by_list, groupmax_column,
587                                        def_fun_list, def_fun_names);
588 
589       }
590 
591     }
592     else {
593       // Otherwise no grouping is occuring.  We simply need create a function
594       // node with any functions defined in the SELECT.
595       // Plan a FunctionsNode with the functions defined in the SELECT.
596       if (fsz > 0) {
597         node = new QueryPlan.CreateFunctionsNode(node,
598                                                  def_fun_list, def_fun_names);
599       }
600     }
601 
602     // The result column list
603     ArrayList   s_col_list = column_set.s_col_list;
604     int sz = s_col_list.size();
605 
606     // Evaluate the having clause if necessary
607     if (expression.having_clause.getFromExpression() != null) {
608       // Before we evaluate the having expression we must substitute all the
609       // aliased variables.
610       Expression having_expr = having_clause.getFromExpression();
611       substituteAliasedVariables(having_expr, s_col_list);
612 
613       PlanTableSource source = table_planner.getSingleTableSource();
614       source.updatePlan(node);
615       node = table_planner.planSearchExpression(having_clause);
616     }
617 
618     // Do we have a composite select expression to process?
619     QueryPlanNode right_composite = null;
620     if (expression.next_composite != null) {
621       TableSelectExpression composite_expr = expression.next_composite;
622       // Generate the TableExpressionFromSet hierarchy for the expression,
623       TableExpressionFromSet composite_from_set =
624                                    generateFromSet(composite_expr, db);
625 
626       // Form the right plan
627       right_composite =
628           formQueryPlan(db, composite_expr, composite_from_set, null);
629 
630     }
631 
632     // Do we do a final subset column?
633     Variable[] aliases = null;
634     if (do_subset_column) {
635       // Make up the lists
636       Variable[] subset_vars = new Variable[sz];
637       aliases = new Variable[sz];
638       for (int i = 0; i < sz; ++i) {
639         SelectColumn scol = (SelectColumn) s_col_list.get(i);
640         subset_vars[i] = new Variable(scol.internal_name);
641         aliases[i] = new Variable(scol.resolved_name);
642       }
643 
644       // If we are distinct then add the DistinctNode here
645       if (expression.distinct) {
646         node = new QueryPlan.DistinctNode(node, subset_vars);
647       }
648 
649       // Process the ORDER BY?
650       // Note that the ORDER BY has to occur before the subset call, but
651       // after the distinct because distinct can affect the ordering of the
652       // result.
653       if (right_composite == null && order_by != null) {
654         node = planForOrderBy(node, order_by, from_set, s_col_list);
655       }
656       
657       // Rename the columns as specified in the SELECT
658       node = new QueryPlan.SubsetNode(node, subset_vars, aliases);
659 
660     }
661     else {
662       // Process the ORDER BY?
663       if (right_composite == null && order_by != null) {
664         node = planForOrderBy(node, order_by, from_set, s_col_list);
665       }
666     }
667 
668     // Do we have a composite to merge in?
669     if (right_composite != null) {
670       // For the composite
671       node = new QueryPlan.CompositeNode(node, right_composite,
672                   expression.composite_function, expression.is_composite_all);
673       // Final order by?
674       if (order_by != null) {
675         node = planForOrderBy(node, order_by, from_set, s_col_list);
676       }
677       // Ensure a final subset node
678       if (!(node instanceof QueryPlan.SubsetNode) && aliases != null) {
679         node = new QueryPlan.SubsetNode(node, aliases, aliases);
680       }
681 
682     }
683 
684     return node;
685   }
686 
687   /**
688    * Plans an ORDER BY set.  This is given its own function because we may
689    * want to plan this at the end of a number of composite functions.
690    * <p>
691    * NOTE: s_col_list is optional.
692    */
693   public static QueryPlanNode planForOrderBy(QueryPlanNode plan,
694                   ArrayList   order_by, TableExpressionFromSet from_set,
695                   ArrayList   s_col_list)
696                                                    throws DatabaseException {
697 
698     TableName FUNCTION_TABLE = new TableName("FUNCTIONTABLE");
699 
700     // Sort on the ORDER BY clause
701     if (order_by.size() > 0) {
702       int sz = order_by.size();
703       Variable[] order_list = new Variable[sz];
704       boolean[] ascending_list = new boolean[sz];
705 
706       ArrayList   function_orders = new ArrayList  ();
707 
708       for (int i = 0; i < sz; ++i) {
709         ByColumn column = (ByColumn) order_by.get(i);
710         Expression exp = column.exp;
711         ascending_list[i] = column.ascending;
712         Variable v = exp.getVariable();
713         if (v != null) {
714           Variable new_v = from_set.resolveReference(v);
715           if (new_v == null) {
716             throw new StatementException(
717                                    "Can not resolve ORDER BY variable: " + v);
718           }
719           substituteAliasedVariable(new_v, s_col_list);
720 
721           order_list[i] = new_v;
722         }
723         else {
724           // Otherwise we must be ordering by an expression such as
725           // '0 - a'.
726 
727           // Resolve the expression,
728           exp.prepare(from_set.expressionQualifier());
729 
730           // Make sure we substitute any aliased columns in the order by
731           // columns.
732           substituteAliasedVariables(exp, s_col_list);
733 
734           // The new ordering functions are called 'FUNCTIONTABLE.#ORDER-n'
735           // where n is the number of the ordering expression.
736           order_list[i] =
737               new Variable(FUNCTION_TABLE, "#ORDER-" + function_orders.size());
738           function_orders.add(exp);
739         }
740 
741 //        System.out.println(exp);
742 
743       }
744 
745       // If there are functional orderings,
746       // For this we must define a new FunctionTable with the expressions,
747       // then order by those columns, and then use another SubsetNode
748       // query node.
749       int fsz = function_orders.size();
750       if (fsz > 0) {
751         Expression[] funs = new Expression[fsz];
752         String  [] fnames = new String  [fsz];
753         for (int n = 0; n < fsz; ++n) {
754           funs[n] = (Expression) function_orders.get(n);
755           fnames[n] = "#ORDER-" + n;
756         }
757 
758         if (plan instanceof QueryPlan.SubsetNode) {
759           // If the top plan is a QueryPlan.SubsetNode then we use the
760           //   information from it to create a new SubsetNode that
761           //   doesn't include the functional orders we have attached here.
762           QueryPlan.SubsetNode top_subset_node = (QueryPlan.SubsetNode) plan;
763           Variable[] mapped_names = top_subset_node.getNewColumnNames();
764 
765           // Defines the sort functions
766           plan = new QueryPlan.CreateFunctionsNode(plan, funs, fnames);
767           // Then plan the sort
768           plan = new QueryPlan.SortNode(plan, order_list, ascending_list);
769           // Then plan the subset
770           plan = new QueryPlan.SubsetNode(plan, mapped_names, mapped_names);
771         }
772         else {
773           // Defines the sort functions
774           plan = new QueryPlan.CreateFunctionsNode(plan, funs, fnames);
775           // Plan the sort
776           plan = new QueryPlan.SortNode(plan, order_list, ascending_list);
777         }
778 
779       }
780       else {
781         // No functional orders so we only need to sort by the columns
782         // defined.
783         plan = new QueryPlan.SortNode(plan, order_list, ascending_list);
784       }
785 
786     }
787 
788     return plan;
789   }
790 
791   /**
792    * Substitutes any aliased variables in the given expression with the
793    * function name equivalent.  For example, if we have a 'SELECT 3 + 4 Bah'
794    * then resolving on variable Bah will be subsituted to the function column
795    * that represents the result of 3 + 4.
796    */
797   private static void substituteAliasedVariables(
798                                Expression expression, ArrayList   s_col_list) {
799     List   all_vars = expression.allVariables();
800     for (int i = 0; i < all_vars.size(); ++i) {
801       Variable v = (Variable) all_vars.get(i);
802       substituteAliasedVariable(v, s_col_list);
803     }
804   }
805 
806   private static void substituteAliasedVariable(Variable v,
807                                                 ArrayList   s_col_list) {
808     if (s_col_list != null) {
809       int sz = s_col_list.size();
810       for (int n = 0; n < sz; ++n) {
811         SelectColumn scol = (SelectColumn) s_col_list.get(n);
812         if (v.equals(scol.resolved_name)) {
813           v.set(scol.internal_name);
814         }
815       }
816     }
817   }
818 
819 
820 
821 
822 
823   // ---------- Inner classes ----------
824 
825   /**
826    * A container object for the set of SelectColumn objects selected in a
827    * query.
828    */
829   private static class QuerySelectColumnSet {
830 
831     /**
832      * The name of the table where functions are defined.
833      */
834     private static TableName FUNCTION_TABLE_NAME =
835                                               new TableName("FUNCTIONTABLE");
836 
837     /**
838      * The tables we are selecting from.
839      */
840     private TableExpressionFromSet from_set;
841 
842     /**
843      * The list of SelectColumn.
844      */
845     ArrayList   s_col_list;
846 
847     /**
848      * The list of functions in this column set.
849      */
850     ArrayList   function_col_list;
851 
852     /**
853      * The current number of 'FUNCTIONTABLE.' columns in the table.  This is
854      * incremented for each custom column.
855      */
856     private int running_fun_number = 0;
857 
858     /**
859      * The count of aggregate and constant columns included in the result set.
860      * Aggregate columns are, (count(*), avg(cost_of) * 0.75, etc).  Constant
861      * columns are, (9 * 4, 2, (9 * 7 / 4) + 4, etc).
862      */
863     int aggregate_count = 0, constant_count = 0;
864 
865     /**
866      * Constructor.
867      */
868     public QuerySelectColumnSet(TableExpressionFromSet from_set) {
869       this.from_set = from_set;
870       s_col_list = new ArrayList  ();
871       function_col_list = new ArrayList  ();
872     }
873 
874     /**
875      * Adds a single SelectColumn to the list of output columns from the
876      * query.
877      * <p>
878      * Note that at this point the the information in the given SelectColumn
879      * may not be completely qualified.
880      */
881     void selectSingleColumn(SelectColumn col) {
882       s_col_list.add(col);
883     }
884 
885     /**
886      * Adds all columns from the given FromTableInterface object.
887      */
888     void addAllFromTable(FromTableInterface table) {
889       // Select all the tables
890       Variable[] vars = table.allColumns();
891       int s_col_list_max = s_col_list.size();
892       for (int i = 0; i < vars.length; ++i) {
893         // The Variable
894         Variable v = vars[i];
895 
896         // Make up the SelectColumn
897         SelectColumn ncol = new SelectColumn();
898         Expression e = new Expression(v);
899         e.text().append(v.toString());
900         ncol.alias = null;
901         ncol.expression = e;
902         ncol.resolved_name = v;
903         ncol.internal_name = v;
904 
905         // Add to the list of columns selected
906         selectSingleColumn(ncol);
907       }
908     }
909 
910     /**
911      * Adds all column from the given table object.  This is used to set up the
912      * columns that are to be viewed as the result of the select statement.
913      */
914     void selectAllColumnsFromSource(TableName table_name) {
915       // Attempt to find the table in the from set.
916       FromTableInterface table = from_set.findTable(
917                               table_name.getSchema(), table_name.getName());
918       if (table == null) {
919         throw new StatementException(table_name.toString() +
920                                      ".* is not a valid reference.");
921       }
922 
923       addAllFromTable(table);
924     }
925 
926     /**
927      * Sets up this queriable with all columns from all table sources.
928      */
929     void selectAllColumnsFromAllSources() {
930       for (int p = 0; p < from_set.setCount(); ++p) {
931         FromTableInterface table = from_set.getTable(p);
932         addAllFromTable(table);
933       }
934     }
935 
936     /**
937      * Adds a new hidden function into the column set.  This is intended
938      * to be used for implied functions.  For example, a query may have a
939      * function in a GROUP BY clause.  It's desirable to include the function
940      * in the column set but not in the final result.
941      * <p>
942      * Returns an absolute Variable object that can be used to reference
943      * this hidden column.
944      */
945     Variable addHiddenFunction(String   fun_alias, Expression function,
946                                QueryContext context) {
947       SelectColumn scol = new SelectColumn();
948       scol.resolved_name = new Variable(fun_alias);
949       scol.alias = fun_alias;
950       scol.expression = function;
951       scol.internal_name = new Variable(FUNCTION_TABLE_NAME, fun_alias);
952 
953       // If this is an aggregate column then add to aggregate count.
954       if (function.hasAggregateFunction(context)) {
955         ++aggregate_count;
956       }
957       // If this is a constant column then add to constant cound.
958       else if (function.isConstant()) {
959         ++constant_count;
960       }
961 
962       function_col_list.add(scol);
963 
964       return scol.internal_name;
965     }
966 
967     /**
968      * Prepares the given SelectColumn by fully qualifying the expression and
969      * allocating it correctly within this context.
970      */
971     private void prepareSelectColumn(SelectColumn col, QueryContext context)
972                                                   throws DatabaseException {
973       // Check to see if we have any Select statements in the
974       //   Expression.  This is necessary, because we can't have a
975       //   sub-select evaluated during list table downloading.
976       List   exp_elements = col.expression.allElements();
977       for (int n = 0; n < exp_elements.size(); ++n) {
978         if (exp_elements.get(n) instanceof TableSelectExpression) {
979           throw new StatementException(
980                                    "Sub-query not allowed in column list.");
981         }
982       }
983 
984       // First fully qualify the select expression
985       col.expression.prepare(from_set.expressionQualifier());
986 
987       // If the expression isn't a simple variable, then add to
988       // function list.
989       Variable v = col.expression.getVariable();
990       if (v == null) {
991         // This means we have a complex expression.
992 
993         ++running_fun_number;
994         String   agg_str = Integer.toString(running_fun_number);
995 
996         // If this is an aggregate column then add to aggregate count.
997         if (col.expression.hasAggregateFunction(context)) {
998           ++aggregate_count;
999           // Add '_A' code to end of internal name of column to signify this is
1000          // an aggregate column
1001          agg_str += "_A";
1002        }
1003        // If this is a constant column then add to constant cound.
1004        else if (col.expression.isConstant()) {
1005          ++constant_count;
1006        }
1007        else {
1008          // Must be an expression with variable's embedded ( eg.
1009          //   (part_id + 3) * 4, (id * value_of_part), etc )
1010        }
1011        function_col_list.add(col);
1012
1013        col.internal_name = new Variable(FUNCTION_TABLE_NAME, agg_str);
1014        if (col.alias == null) {
1015          col.alias = new String  (col.expression.text());
1016        }
1017        col.resolved_name = new Variable(col.alias);
1018
1019      }
1020      else {
1021        // Not a complex expression
1022        col.internal_name = v;
1023        if (col.alias == null) {
1024          col.resolved_name = v;
1025        }
1026        else {
1027          col.resolved_name = new Variable(col.alias);
1028        }
1029      }
1030
1031    }
1032
1033
1034    /**
1035     * Resolves all variable objects in each column.
1036     */
1037    void prepare(QueryContext context) throws DatabaseException {
1038      // Prepare each of the columns selected.
1039      // NOTE: A side-effect of this is that it qualifies all the Expressions
1040      //   that are functions in TableExpressionFromSet.  After this section,
1041      //   we can dereference variables for their function Expression.
1042      for (int i = 0; i < s_col_list.size(); ++i) {
1043        SelectColumn column = (SelectColumn) s_col_list.get(i);
1044        prepareSelectColumn(column, context);
1045      }
1046    }
1047
1048
1049
1050
1051
1052  }
1053
1054
1055
1056
1057
1058  /**
1059   * A table set planner that maintains a list of table dependence lists and
1060   * progressively constructs a plan tree from the bottom up.
1061   */
1062  private static class QueryTableSetPlanner {
1063
1064    /**
1065     * The list of PlanTableSource objects for each source being planned.
1066     */
1067    private ArrayList   table_list;
1068
1069    /**
1070     * If a join has occurred since the planner was constructed or copied then
1071     * this is set to true.
1072     */
1073    private boolean has_join_occurred;
1074
1075
1076
1077    /**
1078     * Constructor.
1079     */
1080    public QueryTableSetPlanner() {
1081      this.table_list = new ArrayList  ();
1082      has_join_occurred = false;
1083    }
1084
1085    /**
1086     * Add a PlanTableSource to this planner.
1087     */
1088    private void addPlanTableSource(PlanTableSource source) {
1089      table_list.add(source);
1090      has_join_occurred = true;
1091    }
1092
1093    /**
1094     * Returns true if a join has occurred ('table_list' has been modified).
1095     */
1096    public boolean hasJoinOccured() {
1097      return has_join_occurred;
1098    }
1099
1100    /**
1101     * Adds a new table source to the planner given a Plan that 'creates'
1102     * the source, and a FromTableInterface that describes the source created
1103     * by the plan.
1104     */
1105    public void addTableSource(QueryPlanNode plan,
1106                               FromTableInterface from_def) {
1107      Variable[] all_cols = from_def.allColumns();
1108      String  [] unique_names = new String  [] { from_def.getUniqueName() };
1109      addPlanTableSource(new PlanTableSource(plan, all_cols, unique_names));
1110    }
1111
1112    /**
1113     * Returns the index of the given PlanTableSource in the table list.
1114     */
1115    private int indexOfPlanTableSource(PlanTableSource source) {
1116      int sz = table_list.size();
1117      for (int i = 0; i < sz; ++i) {
1118        if (table_list.get(i) == source) {
1119          return i;
1120        }
1121      }
1122      return -1;
1123    }
1124
1125    /**
1126     * Links the last added table source to the previous added table source
1127     * through this joining information.
1128     * <p>
1129     * 'between_index' represents the point in between the table sources that
1130     * the join should be setup for.  For example, to set the join between
1131     * TableSource 0 and 1, use 0 as the between index.  A between index of 3
1132     * represents the join between TableSource index 2 and 2.
1133     */
1134    public void setJoinInfoBetweenSources(
1135                   int between_index, int join_type, Expression on_expr) {
1136      PlanTableSource plan_left =
1137                        (PlanTableSource) table_list.get(between_index);
1138      PlanTableSource plan_right =
1139                        (PlanTableSource) table_list.get(between_index + 1);
1140      plan_left.setRightJoinInfo(plan_right, join_type, on_expr);
1141      plan_right.setLeftJoinInfo(plan_left, join_type, on_expr);
1142    }
1143
1144    /**
1145     * Forms a new PlanTableSource that's the concatination of the given
1146     * two PlanTableSource objects.
1147     */
1148    public static PlanTableSource concatTableSources(
1149            PlanTableSource left, PlanTableSource right, QueryPlanNode plan) {
1150
1151      // Merge the variable list
1152      Variable[] new_var_list = new Variable[left.var_list.length +
1153                                             right.var_list.length];
1154      int i = 0;
1155      for (int n = 0; n < left.var_list.length; ++n) {
1156        new_var_list[i] = left.var_list[n];
1157        ++i;
1158      }
1159      for (int n = 0; n < right.var_list.length; ++n) {
1160        new_var_list[i] = right.var_list[n];
1161        ++i;
1162      }
1163
1164      // Merge the unique table names list
1165      String  [] new_unique_list = new String  [left.unique_names.length +
1166                                            right.unique_names.length];
1167      i = 0;
1168      for (int n = 0; n < left.unique_names.length; ++n) {
1169        new_unique_list[i] = left.unique_names[n];
1170        ++i;
1171      }
1172      for (int n = 0; n < right.unique_names.length; ++n) {
1173        new_unique_list[i] = right.unique_names[n];
1174        ++i;
1175      }
1176
1177      // Return the new table source plan.
1178      return new PlanTableSource(plan, new_var_list, new_unique_list);
1179    }
1180
1181    /**
1182     * Joins two tables when a plan is generated for joining the two tables.
1183     */
1184    public PlanTableSource mergeTables(
1185                  PlanTableSource left, PlanTableSource right,
1186                  QueryPlanNode merge_plan) {
1187
1188      // Remove the sources from the table list.
1189      table_list.remove(left);
1190      table_list.remove(right);
1191      // Add the concatination of the left and right tables.
1192      PlanTableSource c_plan = concatTableSources(left, right, merge_plan);
1193      c_plan.setJoinInfoMergedBetween(left, right);
1194      c_plan.setUpdated();
1195      addPlanTableSource(c_plan);
1196      // Return the name plan
1197      return c_plan;
1198    }
1199
1200    /**
1201     * Finds and returns the PlanTableSource in the list of tables that
1202     * contains the given Variable reference.
1203     */
1204    public PlanTableSource findTableSource(Variable ref) {
1205      int sz = table_list.size();
1206
1207      // If there is only 1 plan then assume the variable is in there.
1208      if (sz == 1) {
1209        return (PlanTableSource) table_list.get(0);
1210      }
1211
1212      for (int i = 0; i < sz; ++i) {
1213        PlanTableSource source = (PlanTableSource) table_list.get(i);
1214        if (source.containsVariable(ref)) {
1215          return source;
1216        }
1217      }
1218      throw new RuntimeException  (
1219                   "Unable to find table with variable reference: " + ref);
1220    }
1221
1222    /**
1223     * Finds a common PlanTableSource that contains the list of variables
1224     * given.  If the list is 0 or there is no common source then null is
1225     * returned.
1226     */
1227    public PlanTableSource findCommonTableSource(List   var_list) {
1228      if (var_list.size() == 0) {
1229        return null;
1230      }
1231
1232      PlanTableSource plan = findTableSource((Variable) var_list.get(0));
1233      int i = 1;
1234      int sz = var_list.size();
1235      while (i < sz) {
1236        PlanTableSource p2 = findTableSource((Variable) var_list.get(i));
1237        if (plan != p2) {
1238          return null;
1239        }
1240        ++i;
1241      }
1242
1243      return plan;
1244    }
1245
1246    /**
1247     * Finds and returns the PlanTableSource in the list of table that
1248     * contains the given unique key name.
1249     */
1250    public PlanTableSource findTableSourceWithUniqueKey(String   key) {
1251      int sz = table_list.size();
1252      for (int i = 0; i < sz; ++i) {
1253        PlanTableSource source = (PlanTableSource) table_list.get(i);
1254        if (source.containsUniqueKey(key)) {
1255          return source;
1256        }
1257      }
1258      throw new RuntimeException  (
1259                          "Unable to find table with unique key: " + key);
1260    }
1261
1262    /**
1263     * Returns the single PlanTableSource for this planner.
1264     */
1265    private PlanTableSource getSingleTableSource() {
1266      if (table_list.size() != 1) {
1267        throw new RuntimeException  ("Not a single table source.");
1268      }
1269      return (PlanTableSource) table_list.get(0);
1270    }
1271
1272    /**
1273     * Sets a CachePointNode with the given key on all of the plan table
1274     * sources in 'table_list'.  Note that this does not change the 'update'
1275     * status of the table sources.  If there is currently a CachePointNode
1276     * on any of the sources then no update is made.
1277     */
1278    private void setCachePoints() {
1279      int sz = table_list.size();
1280      for (int i = 0; i < sz; ++i) {
1281        PlanTableSource plan = (PlanTableSource) table_list.get(i);
1282        if (!(plan.getPlan() instanceof QueryPlan.CachePointNode)) {
1283          plan.plan = new QueryPlan.CachePointNode(plan.getPlan());
1284        }
1285      }
1286    }
1287
1288    /**
1289     * Creates a single PlanTableSource that encapsulates all the given
1290     * variables in a single table.  If this means a table must be joined with
1291     * another using the natural join conditions then this happens here.
1292     * <p>
1293     * The intention of this function is to produce a plan that encapsulates
1294     * all the variables needed to perform a specific evaluation.
1295     * <p>
1296     * Note, this has the potential to cause 'natural join' situations which
1297     * are bad performance.  It is a good idea to perform joins using other
1298     * methods before this is used.
1299     * <p>
1300     * Note, this will change the 'table_list' variable in this class if tables
1301     * are joined.
1302     */
1303    private PlanTableSource joinAllPlansWithVariables(List   all_vars) {
1304      // Collect all the plans that encapsulate these variables.
1305      ArrayList   touched_plans = new ArrayList  ();
1306      int sz = all_vars.size();
1307      for (int i = 0; i < sz; ++i) {
1308        Variable v = (Variable) all_vars.get(i);
1309        PlanTableSource plan = findTableSource(v);
1310        if (!touched_plans.contains(plan)) {
1311          touched_plans.add(plan);
1312        }
1313      }
1314      // Now 'touched_plans' contains a list of PlanTableSource for each
1315      // plan to be joined.
1316
1317      return joinAllPlansToSingleSource(touched_plans);
1318    }
1319
1320    /**
1321     * Returns true if it is possible to naturally join the two plans.  Two
1322     * plans can be joined under the following sitations;
1323     * 1) The left or right plan of the first source points to the second
1324     *    source.
1325     * 2) Either one has no left plan and the other has no right plan, or
1326     *    one has no right plan and the other has no left plan.
1327     */
1328    private int canPlansBeNaturallyJoined(
1329                               PlanTableSource plan1, PlanTableSource plan2) {
1330      if (plan1.left_plan == plan2 || plan1.right_plan == plan2) {
1331        return 0;
1332      }
1333      else if (plan1.left_plan != null && plan2.left_plan != null) {
1334        // This is a left clash
1335        return 2;
1336      }
1337      else if (plan1.right_plan != null && plan2.right_plan != null) {
1338        // This is a right clash
1339        return 1;
1340      }
1341      else if ((plan1.left_plan == null && plan2.right_plan == null) ||
1342               (plan1.right_plan == null && plan2.left_plan == null)) {
1343        // This means a merge between the plans is fine
1344        return 0;
1345      }
1346      else {
1347        // Must be a left and right clash
1348        return 2;
1349      }
1350    }
1351
1352    /**
1353     * Given a list of PlanTableSource objects, this will produce a plan that
1354     * naturally joins all the tables together into a single plan.  The
1355     * join algorithm used is determined by the information in the FROM clause.
1356     * An OUTER JOIN, for example, will join depending on the conditions
1357     * provided in the ON clause.  If no explicit join method is provided then
1358     * a natural join will be planned.
1359     * <p>
1360     * Care should be taken with this because this method can produce natural
1361     * joins which are often optimized out by more appropriate join expressions
1362     * that can be processed before this is called.
1363     * <p>
1364     * Note, this will change the 'table_list' variable in this class if tables
1365     * are joined.
1366     * <p>
1367     * Returns null if no plans are provided.
1368     */
1369    private PlanTableSource joinAllPlansToSingleSource(List   all_plans) {
1370      // If there are no plans then return null
1371      if (all_plans.size() == 0) {
1372        return null;
1373      }
1374      // Return early if there is only 1 table.
1375      else if (all_plans.size() == 1) {
1376        return (PlanTableSource) all_plans.get(0);
1377      }
1378
1379      // Make a working copy of the plan list.
1380      ArrayList   working_plan_list = new ArrayList  (all_plans.size());
1381      for (int i = 0; i < all_plans.size(); ++i) {
1382        working_plan_list.add(all_plans.get(i));
1383      }
1384
1385      // We go through each plan in turn.
1386      while (working_plan_list.size() > 1) {
1387        PlanTableSource left_plan = (PlanTableSource) working_plan_list.get(0);
1388        PlanTableSource right_plan =
1389                                    (PlanTableSource) working_plan_list.get(1);
1390        // First we need to determine if the left and right plan can be
1391        // naturally joined.
1392        int status = canPlansBeNaturallyJoined(left_plan, right_plan);
1393        if (status == 0) {
1394          // Yes they can so join them
1395          PlanTableSource new_plan = naturallyJoinPlans(left_plan, right_plan);
1396          // Remove the left and right plan from the list and add the new plan
1397          working_plan_list.remove(left_plan);
1398          working_plan_list.remove(right_plan);
1399          working_plan_list.add(0, new_plan);
1400        }
1401        else if (status == 1) {
1402          // No we can't because of a right join clash, so we join the left
1403          // plan right in hopes of resolving the clash.
1404          PlanTableSource new_plan =
1405                          naturallyJoinPlans(left_plan, left_plan.right_plan);
1406          working_plan_list.remove(left_plan);
1407          working_plan_list.remove(left_plan.right_plan);
1408          working_plan_list.add(0, new_plan);
1409        }
1410        else if (status == 2) {
1411          // No we can't because of a left join clash, so we join the left
1412          // plan left in hopes of resolving the clash.
1413          PlanTableSource new_plan =
1414                           naturallyJoinPlans(left_plan, left_plan.left_plan);
1415          working_plan_list.remove(left_plan);
1416          working_plan_list.remove(left_plan.left_plan);
1417          working_plan_list.add(0, new_plan);
1418        }
1419        else {
1420          throw new RuntimeException  ("Unknown status: " + status);
1421        }
1422      }
1423
1424      // Return the working plan of the merged tables.
1425      return (PlanTableSource) working_plan_list.get(0);
1426
1427    }
1428
1429    /**
1430     * Naturally joins two PlanTableSource objects in this planner.  When this
1431     * method returns the actual plans will be joined together.  This method
1432     * modifies 'table_list'.
1433     */
1434    private PlanTableSource naturallyJoinPlans(
1435                      PlanTableSource plan1, PlanTableSource plan2) {
1436      int join_type;
1437      Expression on_expr;
1438      PlanTableSource left_plan, right_plan;
1439      // Are the plans linked by common join information?
1440      if (plan1.right_plan == plan2) {
1441        join_type = plan1.right_join_type;
1442        on_expr = plan1.right_on_expr;
1443        left_plan = plan1;
1444        right_plan = plan2;
1445      }
1446      else if (plan1.left_plan == plan2) {
1447        join_type = plan1.left_join_type;
1448        on_expr = plan1.left_on_expr;
1449        left_plan = plan2;
1450        right_plan = plan1;
1451      }
1452      else {
1453        // Assertion - make sure no join clashes!
1454        if ((plan1.left_plan != null && plan2.left_plan != null) ||
1455            (plan1.right_plan != null && plan2.right_plan != null)) {
1456          throw new RuntimeException  (
1457             "Assertion failed - plans can not be naturally join because " +
1458             "the left/right join plans clash.");
1459        }
1460
1461        // Else we must assume a non-dependant join (not an outer join).
1462        // Perform a natural join
1463        QueryPlanNode node = new QueryPlan.NaturalJoinNode(
1464                                           plan1.getPlan(), plan2.getPlan());
1465        return mergeTables(plan1, plan2, node);
1466      }
1467
1468      // This means plan1 and plan2 are linked by a common join and ON
1469      // expression which we evaluate now.
1470      boolean outer_join;
1471      if (join_type == JoiningSet.LEFT_OUTER_JOIN) {
1472        // Mark the left plan
1473        left_plan.updatePlan(new QueryPlan.MarkerNode(
1474                                        left_plan.getPlan(), "OUTER_JOIN"));
1475        outer_join = true;
1476      }
1477      else if (join_type == JoiningSet.RIGHT_OUTER_JOIN) {
1478        // Mark the right plan
1479        right_plan.updatePlan(new QueryPlan.MarkerNode(
1480                                        right_plan.getPlan(), "OUTER_JOIN"));
1481        outer_join = true;
1482      }
1483      else if (join_type == JoiningSet.INNER_JOIN) {
1484        // Inner join with ON expression
1485        outer_join = false;
1486      }
1487      else {
1488        throw new RuntimeException  (
1489                         "Join type (" + join_type + ") is not supported.");
1490      }
1491
1492      // Make a Planner object for joining these plans.
1493      QueryTableSetPlanner planner = new QueryTableSetPlanner();
1494      planner.addPlanTableSource(left_plan.copy());
1495      planner.addPlanTableSource(right_plan.copy());
1496
1497//      planner.printDebugInfo();
1498
1499      // Evaluate the on expression
1500      QueryPlanNode node = planner.logicalEvaluate(on_expr);
1501      // If outer join add the left outer join node
1502      if (outer_join) {
1503        node = new QueryPlan.LeftOuterJoinNode(node, "OUTER_JOIN");
1504      }
1505      // And merge the plans in this set with the new node.
1506      return mergeTables(plan1, plan2, node);
1507
1508//      System.out.println("OUTER JOIN: " + on_expr);
1509//      throw new RuntimeException("PENDING");
1510
1511    }
1512
1513    /**
1514     * Plans all outer joins.
1515     * <p>
1516     * Note, this will change the 'table_list' variable in this class if tables
1517     * are joined.
1518     */
1519    private void planAllOuterJoins() {
1520//      new Error().printStackTrace();
1521
1522      int sz = table_list.size();
1523      if (sz <= 1) {
1524        return;
1525      }
1526
1527      // Make a working copy of the plan list.
1528      ArrayList   working_plan_list = new ArrayList  (sz);
1529      for (int i = 0; i < sz; ++i) {
1530        working_plan_list.add(table_list.get(i));
1531      }
1532
1533//      System.out.println("----");
1534
1535      PlanTableSource plan1 = (PlanTableSource) working_plan_list.get(0);
1536      for (int i = 1; i < sz; ++i) {
1537        PlanTableSource plan2 = (PlanTableSource) working_plan_list.get(i);
1538
1539//        System.out.println("Joining: " + plan1);
1540//        System.out.println("   with: " + plan2);
1541
1542        if (plan1.right_plan == plan2) {
1543          plan1 = naturallyJoinPlans(plan1, plan2);
1544        }
1545        else {
1546          plan1 = plan2;
1547        }
1548      }
1549
1550    }
1551
1552    /**
1553     * Naturally joins all remaining tables sources to make a final single
1554     * plan which is returned.
1555     * <p>
1556     * Note, this will change the 'table_list' variable in this class if tables
1557     * are joined.
1558     */
1559    private PlanTableSource naturalJoinAll() {
1560      int sz = table_list.size();
1561      if (sz == 1) {
1562        return (PlanTableSource) table_list.get(0);
1563      }
1564
1565      // Produce a plan that naturally joins all tables.
1566      return joinAllPlansToSingleSource(table_list);
1567    }
1568
1569    /**
1570     * Convenience class that stores an expression to evaluate for a table.
1571     */
1572    private static class SingleVarPlan {
1573      PlanTableSource table_source;
1574      Variable single_var;
1575      Variable variable;
1576      Expression expression;
1577    }
1578
1579    /**
1580     * Adds a single var plan to the given list.
1581     */
1582    private void addSingleVarPlanTo(ArrayList   list, PlanTableSource table,
1583                     Variable variable, Variable single_var,
1584                     Expression[] exp_parts, Operator op) {
1585      Expression exp = new Expression(exp_parts[0], op, exp_parts[1]);
1586      // Is this source in the list already?
1587      int sz = list.size();
1588      for (int i = 0; i < sz; ++i) {
1589        SingleVarPlan plan = (SingleVarPlan) list.get(i);
1590        if (plan.table_source == table &&
1591            (variable == null || plan.variable.equals(variable))) {
1592          // Append to end of current expression
1593          plan.variable = variable;
1594          plan.expression = new Expression(plan.expression,
1595                                           Operator.get("and"), exp);
1596          return;
1597        }
1598      }
1599      // Didn't find so make a new entry in the list.
1600      SingleVarPlan plan = new SingleVarPlan();
1601      plan.table_source = table;
1602      plan.variable = variable;
1603      plan.single_var = single_var;
1604      plan.expression = exp;
1605      list.add(plan);
1606      return;
1607    }
1608
1609    // ----
1610
1611    // An expression plan for a constant expression.  These are very
1612    // optimizable indeed.
1613    private class ConstantExpressionPlan extends ExpressionPlan {
1614      private Expression expression;
1615      public ConstantExpressionPlan(Expression e) {
1616        expression = e;
1617      }
1618      public void addToPlanTree() {
1619        // Each currently open branch must have this constant expression added
1620        // to it.
1621        for (int n = 0; n < table_list.size(); ++n) {
1622          PlanTableSource plan = (PlanTableSource) table_list.get(n);
1623          plan.updatePlan(new QueryPlan.ConstantSelectNode(
1624                                                plan.getPlan(), expression));
1625        }
1626      }
1627    }
1628
1629    private class SimpleSelectExpressionPlan extends ExpressionPlan {
1630      private Variable single_var;
1631      private Operator op;
1632      private Expression expression;
1633      public SimpleSelectExpressionPlan(Variable v, Operator op,
1634                                        Expression e) {
1635        single_var = v;
1636        this.op = op;
1637        expression = e;
1638      }
1639      public void addToPlanTree() {
1640        // Find the table source for this variable
1641        PlanTableSource table_source = findTableSource(single_var);
1642        table_source.updatePlan(new QueryPlan.SimpleSelectNode(
1643                   table_source.getPlan(), single_var, op, expression));
1644      }
1645    }
1646
1647    private class SimpleSingleExpressionPlan extends ExpressionPlan {
1648      private Variable single_var;
1649      private Expression expression;
1650      public SimpleSingleExpressionPlan(Variable v, Expression e) {
1651        single_var = v;
1652        expression = e;
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.RangeSelectNode(
1658                                        table_source.getPlan(), expression));
1659      }
1660    }
1661
1662    private class ComplexSingleExpressionPlan extends ExpressionPlan {
1663      private Variable single_var;
1664      private Expression expression;
1665      public ComplexSingleExpressionPlan(Variable v, Expression e) {
1666        single_var = v;
1667        expression = e;
1668      }
1669      public void addToPlanTree() {
1670        // Find the table source for this variable
1671        PlanTableSource table_source = findTableSource(single_var);
1672        table_source.updatePlan(new QueryPlan.ExhaustiveSelectNode(
1673                                        table_source.getPlan(), expression));
1674      }
1675    }
1676
1677    private class SimplePatternExpressionPlan extends ExpressionPlan {
1678      private Variable single_var;
1679      private Expression expression;
1680      public SimplePatternExpressionPlan(Variable v, Expression e) {
1681        single_var = v;
1682        expression = e;
1683      }
1684      public void addToPlanTree() {
1685        // Find the table source for this variable
1686        PlanTableSource table_source = findTableSource(single_var);
1687        table_source.updatePlan(new QueryPlan.SimplePatternSelectNode(
1688                                        table_source.getPlan(), expression));
1689      }
1690    }
1691
1692    private class ExhaustiveSelectExpressionPlan extends ExpressionPlan {
1693      private Expression expression;
1694      public ExhaustiveSelectExpressionPlan(Expression e) {
1695        expression = e;
1696      }
1697      public void addToPlanTree() {
1698        // Get all the variables of this expression.
1699        List   all_vars = expression.allVariables();
1700        // Find the table source for this set of variables.
1701        PlanTableSource table_source = joinAllPlansWithVariables(all_vars);
1702        // Perform the exhaustive select
1703        table_source.updatePlan(new QueryPlan.ExhaustiveSelectNode(
1704                                        table_source.getPlan(), expression));
1705      }
1706    }
1707
1708    private class ExhaustiveSubQueryExpressionPlan extends ExpressionPlan {
1709      private List   all_vars;
1710      private Expression expression;
1711      public ExhaustiveSubQueryExpressionPlan(List   vars, Expression e) {
1712        this.all_vars = vars;
1713        this.expression = e;
1714      }
1715      public void addToPlanTree() {
1716        PlanTableSource table_source = joinAllPlansWithVariables(all_vars);
1717        // Update the plan
1718        table_source.updatePlan(new QueryPlan.ExhaustiveSelectNode(
1719                                       table_source.getPlan(), expression));
1720
1721      }
1722    }
1723
1724    private class SimpleSubQueryExpressionPlan extends ExpressionPlan {
1725      private Expression expression;
1726      public SimpleSubQueryExpressionPlan(Expression e) {
1727        this.expression = e;
1728      }
1729      public void addToPlanTree() {
1730        Operator op = (Operator) expression.last();
1731        Expression[] exps = expression.split();
1732        Variable left_var = exps[0].getVariable();
1733        QueryPlanNode right_plan = exps[1].getQueryPlanNode();
1734
1735        // Find the table source for this variable
1736        PlanTableSource table_source = findTableSource(left_var);
1737        // The left branch
1738        QueryPlanNode left_plan = table_source.getPlan();
1739        // Update the plan
1740        table_source.updatePlan(
1741             new QueryPlan.NonCorrelatedAnyAllNode(
1742                   left_plan, right_plan, new Variable[] { left_var }, op));
1743      }
1744    }
1745
1746    private class ExhaustiveJoinExpressionPlan extends ExpressionPlan {
1747      private Expression expression;
1748      public ExhaustiveJoinExpressionPlan(Expression e) {
1749        this.expression = e;
1750      }
1751      public void addToPlanTree() {
1752        // Get all the variables in the expression
1753        List   all_vars = expression.allVariables();
1754        // Merge it into one plan (possibly performing natural joins).
1755        PlanTableSource all_plan = joinAllPlansWithVariables(all_vars);
1756        // And perform the exhaustive select,
1757        all_plan.updatePlan(new QueryPlan.ExhaustiveSelectNode(
1758                                           all_plan.getPlan(), expression));
1759      }
1760    }
1761
1762    private class StandardJoinExpressionPlan extends ExpressionPlan {
1763      private Expression expression;
1764      public StandardJoinExpressionPlan(Expression e) {
1765        this.expression = e;
1766      }
1767      public void addToPlanTree() {
1768
1769        // Get the expression with the multiple variables
1770        Expression[] exps = expression.split();
1771
1772        // Get the list of variables in the left hand and right hand side
1773        Variable lhs_v = exps[0].getVariable();
1774        Variable rhs_v = exps[1].getVariable();
1775        List   lhs_vars = exps[0].allVariables();
1776        List   rhs_vars = exps[1].allVariables();
1777
1778        // Get the operator
1779        Operator op = (Operator) expression.last();
1780
1781        // Get the left and right plan for the variables in the expression.
1782        // Note that these methods may perform natural joins on the table.
1783        PlanTableSource lhs_plan = joinAllPlansWithVariables(lhs_vars);
1784        PlanTableSource rhs_plan = joinAllPlansWithVariables(rhs_vars);
1785
1786        // If the lhs and rhs plans are different (there is a joining
1787        // situation).
1788        if (lhs_plan != rhs_plan) {
1789
1790          // If either the LHS or the RHS is a single variable then we can
1791          // optimize the join.
1792
1793          if (lhs_v != null || rhs_v != null) {
1794            // If rhs_v is a single variable and lhs_v is not then we must
1795            // reverse the expression.
1796            QueryPlan.JoinNode join_node;
1797            if (lhs_v == null && rhs_v != null) {
1798              // Reverse the expressions and the operator
1799              join_node = new QueryPlan.JoinNode(
1800                            rhs_plan.getPlan(), lhs_plan.getPlan(),
1801                            rhs_v, op.reverse(), exps[0]);
1802              mergeTables(rhs_plan, lhs_plan, join_node);
1803            }
1804            else {
1805              // Otherwise, use it as it is.
1806              join_node = new QueryPlan.JoinNode(
1807                            lhs_plan.getPlan(), rhs_plan.getPlan(),
1808                            lhs_v, op, exps[1]);
1809              mergeTables(lhs_plan, rhs_plan, join_node);
1810            }
1811            // Return because we are done
1812            return;
1813          }
1814
1815        } // if lhs and rhs plans are different
1816
1817        // If we get here either both the lhs and rhs are complex expressions
1818        // or the lhs and rhs of the variable are not different plans, or
1819        // the operator is not a conditional.  Either way, we must evaluate
1820        // this via a natural join of the variables involved coupled with an
1821        // exhaustive select.  These types of queries are poor performing.
1822
1823        // Get all the variables in the expression
1824        List   all_vars = expression.allVariables();
1825        // Merge it into one plan (possibly performing natural joins).
1826        PlanTableSource all_plan = joinAllPlansWithVariables(all_vars);
1827        // And perform the exhaustive select,
1828        all_plan.updatePlan(new QueryPlan.ExhaustiveSelectNode(
1829                                           all_plan.getPlan(), expression));
1830      }
1831    }
1832
1833    private class SubLogicExpressionPlan extends ExpressionPlan {
1834      private Expression expression;
1835      public SubLogicExpressionPlan(Expression e) {
1836        this.expression = e;
1837      }
1838      public void addToPlanTree() {
1839        planForExpression(expression);
1840      }
1841    }
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852    /**
1853     * Evaluates a list of constant conditional exressions of the form
1854     * '3 + 2 = 0', 'true = true', etc.
1855     */
1856    void evaluateConstants(ArrayList   constant_vars, ArrayList   evaluate_order) {
1857      // For each constant variable
1858      for (int i = 0; i < constant_vars.size(); ++i) {
1859        Expression expr = (Expression) constant_vars.get(i);
1860        // Add the exression plan
1861        ExpressionPlan exp_plan = new ConstantExpressionPlan(expr);
1862        exp_plan.setOptimizableValue(0f);
1863        evaluate_order.add(exp_plan);
1864      }
1865    }
1866
1867    /**
1868     * Evaluates a list of single variable conditional expressions of the
1869     * form a = 3, a > 1 + 2, a - 2 = 1, 3 = a, concat(a, 'a') = '3a', etc.
1870     * The rule is there must be only one variable, a conditional operator,
1871     * and a constant on one side.
1872     * <p>
1873     * This method takes the list and modifies the plan as necessary.
1874     */
1875    void evaluateSingles(ArrayList   single_vars, ArrayList   evaluate_order) {
1876
1877      // The list of simple expression plans (lhs = single)
1878      ArrayList   simple_plan_list = new ArrayList  ();
1879      // The list of complex function expression plans (lhs = expression)
1880      ArrayList   complex_plan_list = new ArrayList  ();
1881
1882      // For each single variable expression
1883      for (int i = 0; i < single_vars.size(); ++i) {
1884        Expression andexp = (Expression) single_vars.get(i);
1885        // The operator
1886        Operator op = (Operator) andexp.last();
1887
1888        // Split the expression
1889        Expression[] exps = andexp.split();
1890        // The single var
1891        Variable single_var;
1892
1893        // If the operator is a sub-query we must be of the form,
1894        // 'a in ( 1, 2, 3 )'
1895        if (op.isSubQuery()) {
1896          single_var = exps[0].getVariable();
1897          if (single_var != null) {
1898            ExpressionPlan exp_plan = new SimpleSelectExpressionPlan(
1899                                                     single_var, op, exps[1]);
1900            exp_plan.setOptimizableValue(0.2f);
1901            evaluate_order.add(exp_plan);
1902          }
1903          else {
1904            single_var = (Variable) exps[0].allVariables().get(0);
1905            ExpressionPlan exp_plan = new ComplexSingleExpressionPlan(
1906                                                        single_var, andexp);
1907            exp_plan.setOptimizableValue(0.8f);
1908            evaluate_order.add(exp_plan);
1909          }
1910        }
1911        else {
1912          // Put the variable on the LHS, constant on the RHS
1913          List   all_vars = exps[0].allVariables();
1914          if (all_vars.size() == 0) {
1915            // Reverse the expressions and the operator
1916            Expression temp_exp = exps[0];
1917            exps[0] = exps[1];
1918            exps[1] = temp_exp;
1919            op = op.reverse();
1920            single_var = (Variable) exps[0].allVariables().get(0);
1921          }
1922          else {
1923            single_var = (Variable) all_vars.get(0);
1924          }
1925          // The table source
1926          PlanTableSource table_source = findTableSource(single_var);
1927          // Simple LHS?
1928          Variable v = exps[0].getVariable();
1929          if (v != null) {
1930            addSingleVarPlanTo(simple_plan_list, table_source, v,
1931                               single_var, exps, op);
1932          }
1933          else {
1934            // No, complex lhs
1935            addSingleVarPlanTo(complex_plan_list, table_source, null,
1936                               single_var, exps, op);
1937          }
1938        }
1939      }
1940
1941      // We now have a list of simple and complex plans for each table,
1942      int sz = simple_plan_list.size();
1943      for (int i = 0; i < sz; ++i) {
1944        SingleVarPlan var_plan = (SingleVarPlan) simple_plan_list.get(i);
1945        ExpressionPlan exp_plan = new SimpleSingleExpressionPlan(
1946                                   var_plan.single_var, var_plan.expression);
1947        exp_plan.setOptimizableValue(0.2f);
1948        evaluate_order.add(exp_plan);
1949      }
1950
1951      sz = complex_plan_list.size();
1952      for (int i = 0; i < sz; ++i) {
1953        SingleVarPlan var_plan = (SingleVarPlan) complex_plan_list.get(i);
1954        ExpressionPlan exp_plan = new ComplexSingleExpressionPlan(
1955                                   var_plan.single_var, var_plan.expression);
1956        exp_plan.setOptimizableValue(0.8f);
1957        evaluate_order.add(exp_plan);
1958      }
1959
1960    }
1961
1962    /**
1963     * Evaluates a list of expressions that are pattern searches (eg. LIKE,
1964     * NOT LIKE and REGEXP).  Note that the LHS or RHS may be complex
1965     * expressions with variables, but we are guarenteed that there are
1966     * no sub-expressions in the expression.
1967     */
1968    void evaluatePatterns(ArrayList   pattern_exprs, ArrayList   evaluate_order) {
1969
1970      // Split the patterns into simple and complex plans.  A complex plan
1971      // may require that a join occurs.
1972
1973      for (int i = 0; i < pattern_exprs.size(); ++i) {
1974        Expression expr = (Expression) pattern_exprs.get(i);
1975
1976        Expression[] exps = expr.split();
1977        // If the LHS is a single variable and the RHS is a constant then
1978        // the conditions are right for a simple pattern search.
1979        Variable lhs_v = exps[0].getVariable();
1980        if (expr.isConstant()) {
1981          ExpressionPlan expr_plan = new ConstantExpressionPlan(expr);
1982          expr_plan.setOptimizableValue(0f);
1983          evaluate_order.add(expr_plan);
1984        }
1985        else if (lhs_v != null && exps[1].isConstant()) {
1986          ExpressionPlan expr_plan =
1987                                 new SimplePatternExpressionPlan(lhs_v, expr);
1988          expr_plan.setOptimizableValue(0.25f);
1989          evaluate_order.add(expr_plan);
1990        }
1991        else {
1992          // Otherwise we must assume a complex pattern search which may
1993          // require a join.  For example, 'a + b LIKE 'a%'' or
1994          // 'a LIKE b'.  At the very least, this will be an exhaustive
1995          // search and at the worst it will be a join + exhaustive search.
1996          // So we should evaluate these at the end of the evaluation order.
1997          ExpressionPlan expr_plan = new ExhaustiveSelectExpressionPlan(expr);
1998          expr_plan.setOptimizableValue(0.82f);
1999          evaluate_order.add(expr_plan);
2000        }
2001
2002      }
2003
2004    }
2005
2006    /**
2007     * Evaluates a list of expressions containing sub-queries.  Non-correlated
2008     * sub-queries can often be optimized in to fast searches.  Correlated
2009     * queries, or expressions containing multiple sub-queries are put
2010     * through the ExhaustiveSelect plan.
2011     */
2012    void evaluateSubQueries(ArrayList   expressions, ArrayList   evaluate_order) {
2013
2014      // For each sub-query expression
2015      for (int i = 0; i < expressions.size(); ++i) {
2016        Expression andexp = (Expression) expressions.get(i);
2017
2018        boolean is_exhaustive;
2019        Variable left_var = null;
2020        QueryPlanNode right_plan = null;
2021
2022        // Is this an easy sub-query?
2023        Operator op = (Operator) andexp.last();
2024        if (op.isSubQuery()) {
2025          // Split the expression.
2026          Expression[] exps = andexp.split();
2027          // Check that the left is a simple enough variable reference
2028          left_var = exps[0].getVariable();
2029          if (left_var != null) {
2030            // Check that the right is a sub-query plan.
2031            right_plan = exps[1].getQueryPlanNode();
2032            if (right_plan != null) {
2033              // Finally, check if the plan is correlated or not
2034              ArrayList   cv =
2035                    right_plan.discoverCorrelatedVariables(1, new ArrayList  ());
2036//              System.out.println("Right Plan: " + right_plan);
2037//              System.out.println("Correlated variables: " + cv);
2038              if (cv.size() == 0) {
2039                // No correlated variables so we are a standard, non-correlated
2040                // query!
2041                is_exhaustive = false;
2042              }
2043              else {
2044                is_exhaustive = true;
2045              }
2046            }
2047            else {
2048              is_exhaustive = true;
2049            }
2050          }
2051          else {
2052            is_exhaustive = true;
2053          }
2054        }
2055        else {
2056          // Must be an exhaustive sub-query
2057          is_exhaustive = true;
2058        }
2059
2060        // If this is an exhaustive operation,
2061        if (is_exhaustive) {
2062          // This expression could involve multiple variables, so we may need
2063          // to join.
2064          List   all_vars = andexp.allVariables();
2065
2066          // Also find all correlated variables.
2067          List   all_correlated =
2068                      andexp.discoverCorrelatedVariables(0, new ArrayList  ());
2069          int sz = all_correlated.size();
2070
2071          // If there are no variables (and no correlated variables) then this
2072          // must be a constant select, For example, 3 in ( select ... )
2073          if (all_vars.size() == 0 && sz == 0) {
2074            ExpressionPlan expr_plan = new ConstantExpressionPlan(andexp);
2075            expr_plan.setOptimizableValue(0f);
2076            evaluate_order.add(expr_plan);
2077          }
2078          else {
2079
2080            for (int n = 0; n < sz; ++n) {
2081              CorrelatedVariable cv =
2082                                  (CorrelatedVariable) all_correlated.get(n);
2083              all_vars.add(cv.getVariable());
2084            }
2085
2086            // An exhaustive expression plan which might require a join or a
2087            // slow correlated search.  This should be evaluated after the
2088            // multiple variables are processed.
2089            ExpressionPlan exp_plan = new ExhaustiveSubQueryExpressionPlan(
2090                                                           all_vars, andexp);
2091            exp_plan.setOptimizableValue(0.85f);
2092            evaluate_order.add(exp_plan);
2093          }
2094
2095        }
2096        else {
2097
2098          // This is a simple sub-query expression plan with a single LHS
2099          // variable and a single RHS sub-query.
2100          ExpressionPlan exp_plan = new SimpleSubQueryExpressionPlan(andexp);
2101          exp_plan.setOptimizableValue(0.3f);
2102          evaluate_order.add(exp_plan);
2103
2104        }
2105
2106      } // For each 'and' expression
2107
2108    }
2109
2110    /**
2111     * Evaluates a list of expressions containing multiple variable expression.
2112     * For example, 'a = b', 'a > b + c', 'a + 5 * b = 2', etc.  If an
2113     * expression represents a simple join condition then a join plan is
2114     * made to the query plan tree.  If an expression represents a more
2115     * complex joining condition then an exhaustive search must be used.
2116     */
2117    void evaluateMultiples(ArrayList   multi_vars, ArrayList   evaluate_order) {
2118
2119      // FUTURE OPTIMIZATION:
2120      //   This join order planner is a little primitive in design.  It orders
2121      //   optimizable joins first and least optimizable last, but does not
2122      //   take into account other factors that we could use to optimize
2123      //   joins in the future.
2124
2125      // For each single variable expression
2126      for (int i = 0; i < multi_vars.size(); ++i) {
2127
2128        // Get the expression with the multiple variables
2129        Expression expr = (Expression) multi_vars.get(i);
2130        Expression[] exps = expr.split();
2131
2132        // Get the list of variables in the left hand and right hand side
2133        Variable lhs_v = exps[0].getVariable();
2134        Variable rhs_v = exps[1].getVariable();
2135
2136        // Work out how optimizable the join is.
2137        // The calculation is as follows;
2138        // a) If both the lhs and rhs are a single variable then the
2139        //    optimizable value is set to 0.6f.
2140        // b) If only one of lhs or rhs is a single variable then the
2141        //    optimizable value is set to 0.64f.
2142        // c) Otherwise it is set to 0.68f (exhaustive select guarenteed).
2143
2144        if (lhs_v == null && rhs_v == null) {
2145          // Neither lhs or rhs are single vars
2146          ExpressionPlan exp_plan = new ExhaustiveJoinExpressionPlan(expr);
2147          exp_plan.setOptimizableValue(0.68f);
2148          evaluate_order.add(exp_plan);
2149        }
2150        else if (lhs_v != null && rhs_v != null) {
2151          // Both lhs and rhs are a single var (most optimizable type of
2152          // join).
2153          ExpressionPlan exp_plan = new StandardJoinExpressionPlan(expr);
2154          exp_plan.setOptimizableValue(0.60f);
2155          evaluate_order.add(exp_plan);
2156        }
2157        else {
2158          // Either lhs or rhs is a single var
2159          ExpressionPlan exp_plan = new StandardJoinExpressionPlan(expr);
2160          exp_plan.setOptimizableValue(0.64f);
2161          evaluate_order.add(exp_plan);
2162        }
2163
2164      } // for each expression we are 'and'ing against
2165
2166    }
2167
2168    /**
2169     * Evaluates a list of expressions that are sub-expressions themselves.
2170     * This is typically called when we have OR queries in the expression.
2171     */
2172    void evaluateSubLogic(ArrayList   sublogic_exprs, ArrayList   evaluate_order) {
2173
2174each_logic_expr:
2175      for (int i = 0; i < sublogic_exprs.size(); ++i) {
2176        Expression expr = (Expression) sublogic_exprs.get(i);
2177
2178        // Break the expression down to a list of OR expressions,
2179        ArrayList   or_exprs = expr.breakByOperator(new ArrayList  (), "or");
2180
2181        // An optimizations here;
2182
2183        // If all the expressions we are ORing together are in the same table
2184        // then we should execute them before the joins, otherwise they
2185        // should go after the joins.
2186
2187        // The reason for this is because if we can lesson the amount of work a
2188        // join has to do then we should.  The actual time it takes to perform
2189        // an OR search shouldn't change if it is before or after the joins.
2190
2191        PlanTableSource common = null;
2192
2193        for (int n = 0; n < or_exprs.size(); ++n) {
2194          Expression or_expr = (Expression) or_exprs.get(n);
2195          List   vars = or_expr.allVariables();
2196          // If there are no variables then don't bother with this expression
2197          if (vars.size() > 0) {
2198            // Find the common table source (if any)
2199            PlanTableSource ts = findCommonTableSource(vars);
2200            boolean or_after_joins = false;
2201            if (ts == null) {
2202              // No common table, so OR after the joins
2203              or_after_joins = true;
2204            }
2205            else if (common == null) {
2206              common = ts;
2207            }
2208            else if (common != ts) {
2209              // No common table with the vars in this OR list so do this OR
2210              // after the joins.
2211              or_after_joins = true;
2212            }
2213
2214            if (or_after_joins) {
2215              ExpressionPlan exp_plan = new SubLogicExpressionPlan(expr);
2216              exp_plan.setOptimizableValue(0.70f);
2217              evaluate_order.add(exp_plan);
2218              // Continue to the next logic expression
2219              continue each_logic_expr;
2220            }
2221          }
2222        }
2223
2224        // Either we found a common table or there are no variables in the OR.
2225        // Either way we should evaluate this after the join.
2226        ExpressionPlan exp_plan = new SubLogicExpressionPlan(expr);
2227        exp_plan.setOptimizableValue(0.58f);
2228        evaluate_order.add(exp_plan);
2229
2230      }
2231
2232    }
2233
2234
2235    // -----
2236
2237    /**
2238     * Generates a plan to evaluate the given list of expressions
2239     * (logically separated with AND).
2240     */
2241    void planForExpressionList(List   and_list) {
2242
2243      ArrayList   sub_logic_expressions = new ArrayList  ();
2244      // The list of expressions that have a sub-select in them.
2245      ArrayList   sub_query_expressions = new ArrayList  ();
2246      // The list of all constant expressions ( true = true )
2247      ArrayList   constants = new ArrayList  ();
2248      // The list of pattern matching expressions (eg. 't LIKE 'a%')
2249      ArrayList   pattern_expressions = new ArrayList  ();
2250      // The list of all expressions that are a single variable on one
2251      // side, a conditional operator, and a constant on the other side.
2252      ArrayList   single_vars = new ArrayList  ();
2253      // The list of multi variable expressions (possible joins)
2254      ArrayList   multi_vars = new ArrayList  ();
2255
2256      // Separate out each condition type.
2257      for (int i = 0; i < and_list.size(); ++i) {
2258        Object   el = and_list.get(i);
2259        Expression andexp = (Expression) el;
2260        // If we end with a logical operator then we must recurse them
2261        // through this method.
2262        Object   lob = andexp.last();
2263        Operator op;
2264        // If the last is not an operator, then we imply
2265        // '[expression] = true'
2266        if (!(lob instanceof Operator) ||
2267            ((Operator) lob).isMathematical()) {
2268          Operator EQUAL_OP = Operator.get("=");
2269          andexp.addElement(TObject.booleanVal(true));
2270          andexp.addOperator(EQUAL_OP);
2271          op = EQUAL_OP;
2272        }
2273        else {
2274          op = (Operator) lob;
2275        }
2276        // If the last is logical (eg. AND, OR) then we must process the
2277        // sub logic expression
2278        if (op.isLogical()) {
2279          sub_logic_expressions.add(andexp);
2280        }
2281        // Does the expression have a sub-query?  (eg. Another select
2282        //   statement somewhere in it)
2283        else if (andexp.hasSubQuery()) {
2284          sub_query_expressions.add(andexp);
2285        }
2286        else if (op.isPattern()) {
2287          pattern_expressions.add(andexp);
2288        }
2289        else { //if (op.isCondition()) {
2290          // The list of variables in the expression.
2291          List   vars = andexp.allVariables();
2292          if (vars.size() == 0) {
2293            // These are ( 54 + 9 = 9 ), ( "z" > "a" ), ( 9.01 - 2 ), etc
2294            constants.add(andexp);
2295          }
2296          else if (vars.size() == 1) {
2297            // These are ( id = 90 ), ( 'a' < number ), etc
2298            single_vars.add(andexp);
2299          }
2300          else if (vars.size() > 1) {
2301            // These are ( id = part_id ),
2302            // ( cost_of + value_of < sold_at ), ( id = part_id - 10 )
2303            multi_vars.add(andexp);
2304          }
2305          else {
2306            throw new Error  ("Hmm, vars list size is negative!");
2307          }
2308        }
2309      }
2310
2311      // The order in which expression are evaluated,
2312      // (ExpressionPlan)
2313      ArrayList   evaluate_order = new ArrayList  ();
2314
2315      // Evaluate the constants.  These should always be evaluated first
2316      // because they always evaluate to either true or false or null.
2317      evaluateConstants(constants, evaluate_order);
2318
2319      // Evaluate the singles.  If formed well these can be evaluated
2320      // using fast indices.  eg. (a > 9 - 3) is more optimal than
2321      // (a + 3 > 9).
2322      evaluateSingles(single_vars, evaluate_order);
2323
2324      // Evaluate the pattern operators.  Note that some patterns can be
2325      // optimized better than others, but currently we keep this near the
2326      // middle of our evaluation sequence.
2327      evaluatePatterns(pattern_expressions, evaluate_order);
2328
2329      // Evaluate the sub-queries.  These are queries of the form,
2330      // (a IN ( SELECT ... )), (a = ( SELECT ... ) = ( SELECT ... )), etc.
2331      evaluateSubQueries(sub_query_expressions, evaluate_order);
2332
2333      // Evaluate multiple variable expressions.  It's possible these are
2334      // joins.
2335      evaluateMultiples(multi_vars, evaluate_order);
2336
2337      // Lastly evaluate the sub-logic expressions.  These expressions are
2338      // OR type expressions.
2339      evaluateSubLogic(sub_logic_expressions, evaluate_order);
2340
2341
2342
2343      // Sort the evaluation list by how optimizable the expressions are,
2344      Collections.sort(evaluate_order);
2345      // And add each expression to the plan
2346      for (int i = 0; i < evaluate_order.size(); ++i) {
2347        ExpressionPlan plan = (ExpressionPlan) evaluate_order.get(i);
2348        plan.addToPlanTree();
2349      }
2350
2351    }
2352
2353    /**
2354     * Evaluates the search Expression clause and alters the banches of
2355     * the plans in this object as necessary.  Unlike the 'logicalEvaluate'
2356     * method, this does not result in a single QueryPlanNode.  It is the
2357     * responsibility of the callee to join branches as required.
2358     */
2359    void planForExpression(Expression exp) {
2360      if (exp == null) {
2361        return;
2362      }
2363
2364      Object   ob = exp.last();
2365      if (ob instanceof Operator && ((Operator) ob).isLogical()) {
2366        Operator last_op = (Operator) ob;
2367
2368        if (last_op.is("or")) {
2369          // parsing an OR block
2370          // Split left and right of logical operator.
2371          Expression[] exps = exp.split();
2372          // If we are an 'or' then evaluate left and right and union the
2373          // result.
2374
2375          // Before we branch set cache points.
2376          setCachePoints();
2377
2378          // Make copies of the left and right planner
2379          QueryTableSetPlanner left_planner = copy();
2380          QueryTableSetPlanner right_planner = copy();
2381
2382          // Plan the left and right side of the OR
2383          left_planner.planForExpression(exps[0]);
2384          right_planner.planForExpression(exps[1]);
2385
2386          // Fix the left and right planner so that they represent the same
2387          // 'group'.
2388          // The current implementation naturally joins all sources if the
2389          // number of sources is different than the original size.
2390          int left_sz = left_planner.table_list.size();
2391          int right_sz = right_planner.table_list.size();
2392          if (left_sz != right_sz ||
2393              left_planner.hasJoinOccured() ||
2394              right_planner.hasJoinOccured()) {
2395            // Naturally join all in the left and right plan
2396            left_planner.naturalJoinAll();
2397            right_planner.naturalJoinAll();
2398          }
2399
2400          // Union all table sources, but only if they have changed.
2401          ArrayList   left_table_list = left_planner.table_list;
2402          ArrayList   right_table_list = right_planner.table_list;
2403          int sz = left_table_list.size();
2404
2405          // First we must determine the plans that need to be joined in the
2406          // left and right plan.
2407          ArrayList   left_join_list = new ArrayList  ();
2408          ArrayList   right_join_list = new ArrayList  ();
2409          for (int i = 0; i < sz; ++i) {
2410            PlanTableSource left_plan =
2411                                  (PlanTableSource) left_table_list.get(i);
2412            PlanTableSource right_plan =
2413                                 (PlanTableSource) right_table_list.get(i);
2414            if (left_plan.isUpdated() || right_plan.isUpdated()) {
2415              left_join_list.add(left_plan);
2416              right_join_list.add(right_plan);
2417            }
2418          }
2419
2420          // Make sure the plans are joined in the left and right planners
2421          left_planner.joinAllPlansToSingleSource(left_join_list);
2422          right_planner.joinAllPlansToSingleSource(right_join_list);
2423
2424          // Since the planner lists may have changed we update them here.
2425          left_table_list = left_planner.table_list;
2426          right_table_list = right_planner.table_list;
2427          sz = left_table_list.size();
2428
2429          ArrayList   new_table_list = new ArrayList  (sz);
2430
2431          for (int i = 0; i < sz; ++i) {
2432            PlanTableSource left_plan =
2433                                  (PlanTableSource) left_table_list.get(i);
2434            PlanTableSource right_plan =
2435                                 (PlanTableSource) right_table_list.get(i);
2436
2437            PlanTableSource new_plan;
2438
2439            // If left and right plan updated so we need to union them
2440            if (left_plan.isUpdated() || right_plan.isUpdated()) {
2441
2442              // In many causes, the left and right branches will contain
2443              //   identical branches that would best be optimized out.
2444
2445              // Take the left plan, add the logical union to it, and make it
2446              // the plan for this.
2447              QueryPlanNode node = new QueryPlan.LogicalUnionNode(
2448                                   left_plan.getPlan(), right_plan.getPlan());
2449
2450              // Update the plan in this table list
2451              left_plan.updatePlan(node);
2452
2453              new_plan = left_plan;
2454            }
2455            else {
2456              // If the left and right plan didn't update, then use the
2457              // left plan (it doesn't matter if we use left or right because
2458              // they are the same).
2459              new_plan = left_plan;
2460            }
2461
2462            // Add the left plan to the new table list we are creating
2463            new_table_list.add(new_plan);
2464
2465          }
2466
2467          // Set the new table list
2468          table_list = new_table_list;
2469
2470        }
2471
2472        else if (last_op.is("and")) {
2473          // parsing an AND block
2474          // The list of AND expressions that are here
2475          ArrayList   and_list = new ArrayList  ();
2476          and_list = createAndList(and_list, exp);
2477
2478          planForExpressionList(and_list);
2479
2480        }
2481
2482        else {
2483          throw new RuntimeException  ("Unknown logical operator: " + ob);
2484        }
2485
2486      }
2487      else {
2488        // Not a logical expression so just plan for this single expression.
2489        ArrayList   exp_list = new ArrayList  (1);
2490        exp_list.add(exp);
2491        planForExpressionList(exp_list);
2492      }
2493
2494    }
2495
2496    /**
2497     * Evaluates a search Expression clause.  Note that is some cases this
2498     * will generate a plan tree that has many identical branches that can be
2499     * optimized out.
2500     */
2501    QueryPlanNode logicalEvaluate(Expression exp) {
2502
2503//      System.out.println("Logical Evaluate: " + exp);
2504
2505      if (exp == null) {
2506        // Naturally join everything and return the plan.
2507        naturalJoinAll();
2508        // Return the plan
2509        return getSingleTableSource().getPlan();
2510      }
2511
2512      // Plan the expression
2513      planForExpression(exp);
2514
2515      // Naturally join any straggling tables
2516      naturalJoinAll();
2517
2518      // Return the plan
2519      return getSingleTableSource().getPlan();
2520    }
2521
2522
2523
2524
2525    /**
2526     * Given an Expression, this will return a list of expressions that can be
2527     * safely executed as a set of 'and' operations.  For example, an
2528     * expression of 'a=9 and b=c and d=2' would return the list; 'a=9','b=c',
2529     * 'd=2'.
2530     * <p>
2531     * If non 'and' operators are found then the reduction stops.
2532     */
2533    private ArrayList   createAndList(ArrayList   list, Expression exp) {
2534      return exp.breakByOperator(list, "and");
2535    }
2536
2537    /**
2538     * Evalutes the WHERE clause of the table expression.
2539     */
2540    QueryPlanNode planSearchExpression(SearchExpression search_expression) {
2541      // First perform all outer tables.
2542      planAllOuterJoins();
2543
2544      QueryPlanNode node =
2545                     logicalEvaluate(search_expression.getFromExpression());
2546      return node;
2547    }
2548
2549    /**
2550     * Makes an exact duplicate copy (deep clone) of this planner object.
2551     */
2552    private QueryTableSetPlanner copy() {
2553      QueryTableSetPlanner copy = new QueryTableSetPlanner();
2554      int sz = table_list.size();
2555      for (int i = 0; i < sz; ++i) {
2556        copy.table_list.add(((PlanTableSource) table_list.get(i)).copy());
2557      }
2558      // Copy the left and right links in the PlanTableSource
2559      for (int i = 0; i < sz; ++i) {
2560        PlanTableSource src = (PlanTableSource) table_list.get(i);
2561        PlanTableSource mod = (PlanTableSource) copy.table_list.get(i);
2562        // See how the left plan links to which index,
2563        if (src.left_plan != null) {
2564          int n = indexOfPlanTableSource(src.left_plan);
2565          mod.setLeftJoinInfo((PlanTableSource) copy.table_list.get(n),
2566                              src.left_join_type, src.left_on_expr);
2567        }
2568        // See how the right plan links to which index,
2569        if (src.right_plan != null) {
2570          int n = indexOfPlanTableSource(src.right_plan);
2571          mod.setRightJoinInfo((PlanTableSource) copy.table_list.get(n),
2572                               src.right_join_type, src.right_on_expr);
2573        }
2574      }
2575
2576      return copy;
2577    }
2578
2579    void printDebugInfo() {
2580      StringBuffer   buf = new StringBuffer  ();
2581      buf.append("PLANNER:\n");
2582      for (int i = 0; i < table_list.size(); ++i) {
2583        buf.append("TABLE " + i + "\n");
2584        ((PlanTableSource) table_list.get(i)).getPlan().debugString(2, buf);
2585        buf.append("\n");
2586      }
2587      System.out.println(buf);
2588    }
2589
2590
2591  }
2592
2593  /**
2594   * Represents a single table source being planned.
2595   */
2596  private static class PlanTableSource {
2597
2598    /**
2599     * The Plan for this table source.
2600     */
2601    private QueryPlanNode plan;
2602
2603    /**
2604     * The list of fully qualified Variable objects that are accessable within
2605     * this plan.
2606     */
2607    private final Variable[] var_list;
2608
2609    /**
2610     * The list of unique key names of the tables in this plan.
2611     */
2612    private final String  [] unique_names;
2613
2614    /**
2615     * Set to true when this source has been updated from when it was
2616     * constructed or copied.
2617     */
2618    private boolean is_updated;
2619
2620    /**
2621     * How this plan is naturally joined to other plans in the source.  A
2622     * plan either has no dependance, a left or a right dependance, or a left
2623     * and right dependance.
2624     */
2625    PlanTableSource left_plan, right_plan;
2626    int left_join_type, right_join_type;
2627    Expression left_on_expr, right_on_expr;
2628
2629
2630    /**
2631     * Constructor.
2632     */
2633    public PlanTableSource(QueryPlanNode plan, Variable[] var_list,
2634                           String  [] table_unique_names) {
2635      this.plan = plan;
2636      this.var_list = var_list;
2637      this.unique_names = table_unique_names;
2638      left_join_type = -1;
2639      right_join_type = -1;
2640      is_updated = false;
2641    }
2642
2643    /**
2644     * Sets the left join information for this plan.
2645     */
2646    void setLeftJoinInfo(PlanTableSource left_plan,
2647                         int join_type, Expression on_expr) {
2648      this.left_plan = left_plan;
2649      this.left_join_type = join_type;
2650      this.left_on_expr = on_expr;
2651    }
2652
2653    /**
2654     * Sets the right join information for this plan.
2655     */
2656    void setRightJoinInfo(PlanTableSource right_plan,
2657                          int join_type, Expression on_expr) {
2658      this.right_plan = right_plan;
2659      this.right_join_type = join_type;
2660      this.right_on_expr = on_expr;
2661    }
2662
2663    /**
2664     * This is called when two plans are merged together to set up the
2665     * left and right join information for the new plan.  This sets the left
2666     * join info from the left plan and the right join info from the right
2667     * plan.
2668     */
2669    void setJoinInfoMergedBetween(
2670                               PlanTableSource left, PlanTableSource right) {
2671
2672      if (left.right_plan != right) {
2673        if (left.right_plan != null) {
2674          setRightJoinInfo(left.right_plan,
2675                           left.right_join_type, left.right_on_expr);
2676          right_plan.left_plan = this;
2677        }
2678        if (right.left_plan != null) {
2679          setLeftJoinInfo(right.left_plan,
2680                          right.left_join_type, right.left_on_expr);
2681          left_plan.right_plan = this;
2682        }
2683      }
2684      if (left.left_plan != right) {
2685        if (left_plan == null && left.left_plan != null) {
2686          setLeftJoinInfo(left.left_plan,
2687                          left.left_join_type, left.left_on_expr);
2688          left_plan.right_plan = this;
2689        }
2690        if (right_plan == null && right.right_plan != null) {
2691          setRightJoinInfo(right.right_plan,
2692                           right.right_join_type, right.right_on_expr);
2693          right_plan.left_plan = this;
2694        }
2695      }
2696
2697    }
2698
2699    /**
2700     * Returns true if this table source contains the variable reference.
2701     */
2702    public boolean containsVariable(Variable v) {
2703//      System.out.println("Looking for: " + v);
2704      for (int i = 0; i < var_list.length; ++i) {
2705//        System.out.println(var_list[i]);
2706        if (var_list[i].equals(v)) {
2707          return true;
2708        }
2709      }
2710      return false;
2711    }
2712
2713    /**
2714     * Returns true if this table source contains the unique table name
2715     * reference.
2716     */
2717    public boolean containsUniqueKey(String   name) {
2718      for (int i = 0; i < unique_names.length; ++i) {
2719        if (unique_names[i].equals(name)) {
2720          return true;
2721        }
2722      }
2723      return false;
2724    }
2725
2726    /**
2727     * Sets the updated flag.
2728     */
2729    public void setUpdated() {
2730      is_updated = true;
2731    }
2732
2733    /**
2734     * Updates the plan.
2735     */
2736    public void updatePlan(QueryPlanNode node) {
2737      plan = node;
2738      setUpdated();
2739    }
2740
2741    /**
2742     * Returns the plan for this table source.
2743     */
2744    public QueryPlanNode getPlan() {
2745      return plan;
2746    }
2747
2748    /**
2749     * Returns true if the planner was updated.
2750     */
2751    public boolean isUpdated() {
2752      return is_updated;
2753    }
2754
2755    /**
2756     * Makes a copy of this table source.
2757     */
2758    public PlanTableSource copy() {
2759      return new PlanTableSource(plan, var_list, unique_names);
2760    }
2761
2762  }
2763
2764  /**
2765   * An abstract class that represents an expression to be added into a plan.
2766   * Many sets of expressions can be added into the plan tree in any order,
2767   * however it is often desirable to add some more intensive expressions
2768   * higher up the branches.  This object allows us to order expressions by
2769   * optimization value.  More optimizable expressions are put near the leafs
2770   * of the plan tree and least optimizable and put near the top.
2771   */
2772  static abstract class ExpressionPlan implements Comparable   {
2773
2774    /**
2775     * How optimizable an expression is.  A value of 0 indicates most
2776     * optimizable and 1 indicates least optimizable.
2777     */
2778    private float optimizable_value;
2779
2780    /**
2781     * Sets the optimizable value of this plan.
2782     */
2783    public void setOptimizableValue(float v) {
2784      optimizable_value = v;
2785    }
2786
2787    /**
2788     * Returns the optimizable value for this plan.
2789     */
2790    public float getOptimizableValue() {
2791      return optimizable_value;
2792    }
2793
2794    /**
2795     * Adds this expression into the plan tree.
2796     */
2797    public abstract void addToPlanTree();
2798
2799    public int compareTo(Object   ob) {
2800      ExpressionPlan dest_plan = (ExpressionPlan) ob;
2801      float dest_val = dest_plan.optimizable_value;
2802      if (optimizable_value > dest_val) {
2803        return 1;
2804      }
2805      else if (optimizable_value < dest_val) {
2806        return -1;
2807      }
2808      else {
2809        return 0;
2810      }
2811    }
2812
2813  }
2814
2815}
2816
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags