Java > Open Source Codes > com > mckoi > database > QueryPlan


1 /**
2  * com.mckoi.database.QueryPlan 06 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;
26
27 import java.util.List ;
28 import java.util.ArrayList ;
29
30 /**
31  * Various helper methods for constructing a plan tree, and the plan node
32  * implementations themselves.
33  *
34  * @author Tobias Downer
35  */
36
37 public class QueryPlan {
38
39
40
41
42   /**
43    * Convenience, replaces all elements of the array with clone versions of
44    * themselves.
45    */
46   private static void cloneArray(Variable[] array)
47                                           throws CloneNotSupportedException {
48     if (array != null) {
49       for (int i = 0; i < array.length; ++i) {
50         array[i] = (Variable) array[i].clone();
51       }
52     }
53   }
54
55   /**
56    * Convenience, replaces all elements of the array with clone versions of
57    * themselves.
58    */
59   private static void cloneArray(Expression[] array)
60                                           throws CloneNotSupportedException {
61     if (array != null) {
62       for (int i = 0; i < array.length; ++i) {
63         array[i] = (Expression) array[i].clone();
64       }
65     }
66   }
67
68   private static void indentBuffer(int level, StringBuffer buf) {
69     for (int i = 0; i < level; ++i) {
70       buf.append(' ');
71     }
72   }
73
74
75
76   // ---------- Plan node implementations ----------
77
78   /**
79    * A QueryPlanNode with a single child.
80    */
81   public static abstract class SingleQueryPlanNode implements QueryPlanNode {
82
83     static final long serialVersionUID = -6753991881140638658L;
84
85     /**
86      * The single child node.
87      */
88     protected QueryPlanNode child;
89
90     /**
91      * Constructor.
92      */
93     protected SingleQueryPlanNode(QueryPlanNode child) {
94       this.child = child;
95     }
96
97     /**
98      * Returns the child plan.
99      */
100     public QueryPlanNode child() {
101       return child;
102     }
103
104     /**
105      * Default implementation delegates responsibility to child.
106      */
107     public ArrayList discoverTableNames(ArrayList list) {
108       return child.discoverTableNames(list);
109     }
110
111     /**
112      * Default implementation that discovers correlated variables for the
113      * given offset level.
114      */
115     public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
116       return child.discoverCorrelatedVariables(level, list);
117     }
118
119     /**
120      * Deep clone.
121      */
122     public Object clone() throws CloneNotSupportedException {
123       SingleQueryPlanNode node = (SingleQueryPlanNode) super.clone();
124       node.child = (QueryPlanNode) child.clone();
125       return node;
126     }
127
128     public String titleString() {
129       return getClass().getName();
130     }
131
132     public void debugString(int level, StringBuffer buf) {
133       indentBuffer(level, buf);
134       buf.append(titleString());
135       buf.append('\n');
136       child.debugString(level + 2, buf);
137     }
138
139   }
140
141   /**
142    * A QueryPlanNode that is a branch with two child nodes.
143    */
144   public static abstract class BranchQueryPlanNode implements QueryPlanNode {
145
146     static final long serialVersionUID = 2938130775577221138L;
147
148     /**
149      * The left and right node.
150      */
151     protected QueryPlanNode left, right;
152
153     /**
154      * The Constructor.
155      */
156     protected BranchQueryPlanNode(QueryPlanNode left, QueryPlanNode right) {
157       this.left = left;
158       this.right = right;
159     }
160
161     /**
162      * Returns the left node.
163      */
164     public QueryPlanNode left() {
165       return left;
166     }
167
168     /**
169      * Returns the right node.
170      */
171     public QueryPlanNode right() {
172       return right;
173     }
174
175     /**
176      * Default implementation delegates responsibility to children.
177      */
178     public ArrayList discoverTableNames(ArrayList list) {
179       return right.discoverTableNames(
180                left.discoverTableNames(list));
181     }
182
183     /**
184      * Default implementation that discovers correlated variables for the
185      * given offset level.
186      */
187     public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
188       return right.discoverCorrelatedVariables(level,
189                left.discoverCorrelatedVariables(level, list));
190     }
191
192     /**
193      * Deep clone.
194      */
195     public Object clone() throws CloneNotSupportedException {
196       BranchQueryPlanNode node = (BranchQueryPlanNode) super.clone();
197       node.left = (QueryPlanNode) left.clone();
198       node.right = (QueryPlanNode) right.clone();
199       return node;
200     }
201
202     public String titleString() {
203       return getClass().getName();
204     }
205
206     public void debugString(int level, StringBuffer buf) {
207       indentBuffer(level, buf);
208       buf.append(titleString());
209       buf.append('\n');
210       left.debugString(level + 2, buf);
211       right.debugString(level + 2, buf);
212     }
213
214   }
215
216
217
218
219
220
221   /**
222    * The node for fetching a table from the current transaction. This is
223    * a tree node and has no children.
224    */
225   public static class FetchTableNode implements QueryPlanNode {
226
227     static final long serialVersionUID = 7545493568015241717L;
228
229     /**
230      * The name of the table to fetch.
231      */
232     private TableName table_name;
233
234     /**
235      * The name to alias the table as.
236      */
237     private TableName alias_name;
238
239     public FetchTableNode(TableName table_name, TableName aliased_as) {
240       this.table_name = table_name;
241       this.alias_name = aliased_as;
242     }
243
244     /**
245      * Adds the table name to the list if it's not already in there.
246      */
247     public ArrayList discoverTableNames(ArrayList list) {
248       if (!list.contains(table_name)) {
249         list.add(table_name);
250       }
251       return list;
252     }
253
254     public Table evaluate(QueryContext context) {
255       // MILD HACK: Cast the context to a DatabaseQueryContext
256 DatabaseQueryContext db_context = (DatabaseQueryContext) context;
257       DataTable t = db_context.getTable(table_name);
258       if (alias_name != null) {
259         return new ReferenceTable(t, alias_name);
260       }
261       return t;
262     }
263
264     public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
265       return list;
266     }
267
268     public Object clone() throws CloneNotSupportedException {
269       return super.clone();
270     }
271
272     public String titleString() {
273       return "FETCH: " + table_name + " AS " + alias_name;
274     }
275
276     public void debugString(int level, StringBuffer buf) {
277       indentBuffer(level, buf);
278       buf.append(titleString());
279       buf.append('\n');
280     }
281
282   }
283
284   /**
285    * A node for creating a table with a single row. This table is useful for
286    * queries that have no underlying row. For example, a pure functional
287    * table expression.
288    */
289   public static class SingleRowTableNode implements QueryPlanNode {
290
291     static final long serialVersionUID = -7180494964138911604L;
292
293     public SingleRowTableNode() {
294     }
295
296     public ArrayList discoverTableNames(ArrayList list) {
297       return list;
298     }
299
300     public Table evaluate(QueryContext context) {
301       // MILD HACK: Cast the context to a DatabaseQueryContext
302 DatabaseQueryContext db_context = (DatabaseQueryContext) context;
303       return db_context.getDatabase().getSingleRowTable();
304     }
305
306     public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
307       return list;
308     }
309
310     public Object clone() throws CloneNotSupportedException {
311       return super.clone();
312     }
313
314     public String titleString() {
315       return "SINGLE ROW";
316     }
317
318     public void debugString(int level, StringBuffer buf) {
319       indentBuffer(level, buf);
320       buf.append(titleString());
321       buf.append('\n');
322     }
323
324   }
325
326   /**
327    * The node that fetches a view from the current connection. This is a
328    * tree node that has no children, however the child can be created by
329    * calling the 'createViewChildNode' method. This node can be removed from a
330    * plan tree by calling the 'createViewChildNode' method and substituting this
331    * node with the returned child. For a planner that normalizes and optimizes
332    * plan trees, this is a useful feature.
333    */
334   public static class FetchViewNode implements QueryPlanNode {
335
336     static final long serialVersionUID = -6557333346211179284L;
337     
338     /**
339      * The name of the view to fetch.
340      */
341     private TableName table_name;
342
343     /**
344      * The name to alias the table as.
345      */
346     private TableName alias_name;
347
348     public FetchViewNode(TableName table_name, TableName aliased_as) {
349       this.table_name = table_name;
350       this.alias_name = aliased_as;
351     }
352
353     /**
354      * Returns the QueryPlanNode that resolves to the view. This looks up the
355      * query plan in the context given.
356      */
357     public QueryPlanNode createViewChildNode(QueryContext context) {
358       DatabaseQueryContext db = (DatabaseQueryContext) context;
359       return db.createViewQueryPlanNode(table_name);
360     }
361     
362     /**
363      * Adds the table name to the list if it's not already in there.
364      */
365     public ArrayList discoverTableNames(ArrayList list) {
366       if (!list.contains(table_name)) {
367         list.add(table_name);
368       }
369       return list;
370     }
371
372     public Table evaluate(QueryContext context) {
373
374       // Create the view child node
375 QueryPlanNode node = createViewChildNode(context);
376       // Evaluate the plan
377 Table t = node.evaluate(context);
378
379       if (alias_name != null) {
380         return new ReferenceTable(t, alias_name);
381       }
382       else {
383         return t;
384       }
385       
386     }
387
388     public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
389       return list;
390     }
391
392     public Object clone() throws CloneNotSupportedException {
393       return super.clone();
394     }
395
396     public String titleString() {
397       return "VIEW: " + table_name + " AS " + alias_name;
398     }
399
400     public void debugString(int level, StringBuffer buf) {
401       indentBuffer(level, buf);
402       buf.append(titleString());
403       buf.append('\n');
404     }
405
406   }
407   
408   
409   
410   
411   
412   /**
413    * The node for performing a simple indexed query on a single column of the
414    * child node. Finds the set from the child node that matches the range.
415    * <p>
416    * The given Expression object must conform to a number of rules. It may
417    * reference only one column in the child node. It must consist of only
418    * simple mathemetical and logical operators (<, >, =, <>, >=, <=, AND, OR).
419    * The left side of each mathematical operator must be a variable, and the
420    * right side must be a constant (parameter subsitution or correlated value).
421    * For example;
422    * (col > 10 AND col < 100) OR col > 1000 OR col == 10
423    * <p>
424    * Breaking any of these rules will mean the range select can not happen.
425    */
426   public static class RangeSelectNode extends SingleQueryPlanNode {
427
428     static final long serialVersionUID = -108747827391465748L;
429
430     /**
431      * A simple expression that represents the range to select. See the
432      * class comments for a description for how this expression must be
433      * formed.
434      */
435     private Expression expression;
436
437     public RangeSelectNode(QueryPlanNode child, Expression exp) {
438       super(child);
439       this.expression = exp;
440     }
441
442     /**
443      * Given an Expression, this will return a list of expressions that can be
444      * safely executed as a set of 'and' operations. For example, an
445      * expression of 'a=9 and b=c and d=2' would return the list; 'a=9','b=c',
446      * 'd=2'.
447      * <p>
448      * If non 'and' operators are found then the reduction stops.
449      */
450     private ArrayList createAndList(ArrayList list, Expression exp) {
451       return exp.breakByOperator(list, "and");
452     }
453
454     /**
455      * Updates a range with the given expression.
456      */
457     private void updateRange(QueryContext context, SelectableRangeSet range,
458                              DataTableColumnDef field, Expression e) {
459       Operator op = (Operator) e.last();
460       Expression[] exps = e.split();
461       // Evaluate to an object
462 TObject cell = exps[1].evaluate(null, null, context);
463       
464       // If the evaluated object is not of a comparable type, then it becomes
465 // null.
466 TType field_type = field.getTType();
467       if (!cell.getTType().comparableTypes(field_type)) {
468         cell = new TObject(field_type, null);
469       }
470
471       // Intersect this in the range set
472 range.intersect(op, cell);
473     }
474
475     /**
476      * Calculates a list of SelectableRange objects that represent the range
477      * of the expression.
478      */
479     private void calcRange(final QueryContext context,
480                            final DataTableColumnDef field,
481                            final SelectableRangeSet range,
482                            final Expression exp) {
483       Operator op = (Operator) exp.last();
484       if (op.isLogical()) {
485         if (op.is("and")) {
486           ArrayList and_list = createAndList(new ArrayList (), exp);
487           int sz = and_list.size();
488           for (int i = 0; i < sz; ++i) {
489             updateRange(context, range, field, (Expression) and_list.get(i));
490           }
491         }
492         else if (op.is("or")) {
493           // Split left and right of logical operator.
494 Expression[] exps = exp.split();
495           // Calculate the range of the left and right
496 SelectableRangeSet left = new SelectableRangeSet();
497           calcRange(context, field, left, exps[0]);
498           SelectableRangeSet right = new SelectableRangeSet();
499           calcRange(context, field, right, exps[1]);
500
501           // Union the left and right range with the current range
502 range.union(left);
503           range.union(right);
504         }
505         else {
506           throw new Error ("Unrecognised logical operator.");
507         }
508       }
509       else {
510         // Not an operator so this is the value.
511 updateRange(context, range, field, exp);
512       }
513
514     }
515
516
517     public Table evaluate(QueryContext context) {
518       Table t = child.evaluate(context);
519
520       Expression exp = expression;
521
522       // Assert that all variables in the expression are identical.
523 List all_vars = exp.allVariables();
524       Variable v = null;
525       int sz = all_vars.size();
526       for (int i = 0; i < sz; ++i) {
527         Variable cv = (Variable) all_vars.get(i);
528         if (v != null) {
529           if (!cv.equals(v)) {
530             throw new Error ("Assertion failed: " +
531                             "Range plan does not contain common variable.");
532           }
533         }
534         v = cv;
535       }
536
537       // Find the variable field in the table.
538 int col = t.findFieldName(v);
539       if (col == -1) {
540         throw new Error ("Couldn't find column reference in table: " + v);
541       }
542       DataTableColumnDef field = t.getColumnDefAt(col);
543       // Calculate the range
544 SelectableRangeSet range = new SelectableRangeSet();
545       calcRange(context, field, range, exp);
546
547 // System.out.println("RANGE: ");
548 // System.out.println(range);
549
550       // Select the range from the table
551 SelectableRange[] ranges = range.toSelectableRangeArray();
552       return t.rangeSelect(v, ranges);
553
554     }
555
556     public ArrayList discoverTableNames(ArrayList list) {
557       return expression.discoverTableNames(super.discoverTableNames(list));
558     }
559
560     public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
561 // System.out.println(expression);
562 return expression.discoverCorrelatedVariables(level,
563                super.discoverCorrelatedVariables(level, list));
564     }
565
566     public Object clone() throws CloneNotSupportedException {
567       RangeSelectNode node = (RangeSelectNode) super.clone();
568       node.expression = (Expression) expression.clone();
569       return node;
570     }
571
572     public String titleString() {
573       return "RANGE: " + expression;
574     }
575
576   }
577
578   /**
579    * The node for performing a simple select operation on a table. The simple
580    * select requires a LHS variable, an operator, and an expression
581    * representing the RHS.
582    */
583   public static class SimpleSelectNode extends SingleQueryPlanNode {
584
585     static final long serialVersionUID = 5502157970886270867L;
586
587     /**
588      * The LHS variable.
589      */
590     private Variable left_var;
591
592     /**
593      * The operator to select under (=, <>, >, <, >=, <=).
594      */
595     private Operator op;
596
597     /**
598      * The RHS expression.
599      */
600     private Expression right_expression;
601
602     public SimpleSelectNode(QueryPlanNode child,
603                             Variable left_var, Operator op,
604                             Expression right_expression) {
605       super(child);
606       this.left_var = left_var;
607       this.op = op;
608       this.right_expression = right_expression;
609     }
610
611     public Table evaluate(QueryContext context) {
612       // Solve the child branch result
613 Table table = child.evaluate(context);
614
615       // The select operation.
616 return table.simpleSelect(context,
617                                 left_var, op, right_expression);
618     }
619
620     public ArrayList discoverTableNames(ArrayList list) {
621       return right_expression.discoverTableNames(
622                                          super.discoverTableNames(list));
623     }
624
625     public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
626       return right_expression.discoverCorrelatedVariables(level,
627                super.discoverCorrelatedVariables(level, list));
628     }
629
630     public Object clone() throws CloneNotSupportedException {
631       SimpleSelectNode node = (SimpleSelectNode) super.clone();
632       node.left_var = (Variable) left_var.clone();
633       node.right_expression = (Expression) right_expression.clone();
634       return node;
635     }
636
637     public String titleString() {
638       return "SIMPLE: " + left_var + op + right_expression;
639     }
640
641   }
642
643   /**
644    * The node for performing an equi-select on a group of columns of the
645    * child node. This is a separate node instead of chained
646    * IndexedSelectNode's so that we might exploit multi-column indexes.
647    */
648   public static class MultiColumnEquiSelectNode extends SingleQueryPlanNode {
649
650     static final long serialVersionUID = -1407710412096857588L;
651
652     /**
653      * The list of columns to select the range of.
654      */
655     private Variable[] columns;
656
657     /**
658      * The values of the cells to equi-select (must be constant expressions).
659      */
660     private Expression[] values;
661
662     public MultiColumnEquiSelectNode(QueryPlanNode child,
663                                      Variable[] columns, Expression[] values) {
664       super(child);
665       this.columns = columns;
666       this.values = values;
667     }
668
669     public Table evaluate(QueryContext context) {
670       Table t = child.evaluate(context);
671
672       // PENDING: Exploit multi-column indexes when they are implemented...
673
674       // We select each column in turn
675 Operator EQUALS_OP = Operator.get("=");
676       for (int i = 0; i < columns.length; ++i) {
677         t = t.simpleSelect(context, columns[i], EQUALS_OP, values[i]);
678       }
679
680       return t;
681     }
682
683     public ArrayList discoverTableNames(ArrayList list) {
684       throw new Error ("PENDING");
685     }
686
687     public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
688       throw new Error ("PENDING");
689     }
690
691     public Object clone() throws CloneNotSupportedException {
692       MultiColumnEquiSelectNode node =
693                                  (MultiColumnEquiSelectNode) super.clone();
694       cloneArray(node.columns);
695       cloneArray(node.values);
696       return node;
697     }
698
699   }
700
701   /**
702    * The node for performing a functional select operation on the child node.
703    * Some examples of this type of query are;
704    * CONCAT(a, ' ', b) > 'abba boh'
705    * TONUMBER(DATEFORMAT(a, 'yyyy')) > 2001
706    * LOWER(a) < 'ook'
707    * The reason this is a separate node is because it is possible to exploit
708    * a functional indexes on a table with this node.
709    * <p>
710    * The given expression MUST be of the form;
711    * 'function_expression' 'operator' 'constant'
712    */
713   public static class FunctionalSelectNode extends SingleQueryPlanNode {
714
715     static final long serialVersionUID = -1428022600352236457L;
716
717     /**
718      * The function expression (eg. CONCAT(a, ' ', b) == 'abba bo').
719      */
720     private Expression expression;
721
722     public FunctionalSelectNode(QueryPlanNode child, Expression exp) {
723       super(child);
724       this.expression = exp;
725     }
726
727     public Table evaluate(QueryContext context) {
728       Table t = child.evaluate(context);
729       // NOTE: currently this uses exhaustive select but should exploit
730 // function indexes when they are available.
731 return t.exhaustiveSelect(context, expression);
732     }
733
734     public ArrayList discoverTableNames(ArrayList list) {
735       return expression.discoverTableNames(super.discoverTableNames(list));
736     }
737
738     public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
739       return expression.discoverCorrelatedVariables(level,
740                super.discoverCorrelatedVariables(level, list));
741     }
742
743     public Object clone() throws CloneNotSupportedException {
744       FunctionalSelectNode node = (FunctionalSelectNode) super.clone();
745       node.expression = (Expression) expression.clone();
746       return node;
747     }
748
749   }
750
751   /**
752    * The node for performing a exhaustive select operation on the child node.
753    * This node will iterate through the entire child result and all
754    * results that evaulate to true are included in the result.
755    * <p>
756    * NOTE: The Expression may have correlated sub-queries.
757    */
758   public static class ExhaustiveSelectNode extends SingleQueryPlanNode {
759
760     static final long serialVersionUID = -2005551680157574172L;
761
762     /**
763      * The search expression.
764      */
765     private Expression expression;
766
767     public ExhaustiveSelectNode(QueryPlanNode child, Expression exp) {
768       super(child);
769       this.expression = exp;
770     }
771
772     public Table evaluate(QueryContext context) {
773       Table t = child.evaluate(context);
774       return t.exhaustiveSelect(context, expression);
775     }
776
777     public ArrayList discoverTableNames(ArrayList list) {
778       return expression.discoverTableNames(super.discoverTableNames(list));
779     }
780
781     public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
782       return expression.discoverCorrelatedVariables(level,
783                super.discoverCorrelatedVariables(level, list));
784     }
785
786     public Object clone() throws CloneNotSupportedException {
787       ExhaustiveSelectNode node = (ExhaustiveSelectNode) super.clone();
788       node.expression = (Expression) expression.clone();
789       return node;
790     }
791
792     public String titleString() {
793       return "EXHAUSTIVE: " + expression;
794     }
795
796   }
797
798   /**
799    * The node for evaluating an expression that contains entirely constant
800    * values (no variables).
801    */
802   public static class ConstantSelectNode extends SingleQueryPlanNode {
803
804     static final long serialVersionUID = -4435336817396073146L;
805
806     /**
807      * The search expression.
808      */
809     private Expression expression;
810
811     public ConstantSelectNode(QueryPlanNode child, Expression exp) {
812       super(child);
813       this.expression = exp;
814     }
815
816     public Table evaluate(QueryContext context) {
817       // Evaluate the expression
818 TObject v = expression.evaluate(null, null, context);
819       // If it evaluates to NULL or FALSE then return an empty set
820 if (v.isNull() || v.getObject().equals(Boolean.FALSE)) {
821         return child.evaluate(context).emptySelect();
822       }
823       else {
824         return child.evaluate(context);
825       }
826     }
827
828     public ArrayList discoverTableNames(ArrayList list) {
829       return expression.discoverTableNames(super.discoverTableNames(list));
830     }
831
832     public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
833       return expression.discoverCorrelatedVariables(level,
834                super.discoverCorrelatedVariables(level, list));
835     }
836
837     public Object clone() throws CloneNotSupportedException {
838       ConstantSelectNode node = (ConstantSelectNode) super.clone();
839       node.expression = (Expression) expression.clone();
840       return node;
841     }
842
843     public String titleString() {
844       return "CONSTANT: " + expression;
845     }
846
847   }
848
849   /**
850    * The node for evaluating a simple pattern search on a table which
851    * includes a single left hand variable or constant, a pattern type (LIKE,
852    * NOT LIKE or REGEXP), and a right hand constant (eg. 'T__y'). If the
853    * expression is not in this form then this node will not operate
854    * correctly.
855    */
856   public static class SimplePatternSelectNode extends SingleQueryPlanNode {
857
858     static final long serialVersionUID = -8247282157310682761L;
859
860     /**
861      * The search expression.
862      */
863     private Expression expression;
864
865     public SimplePatternSelectNode(QueryPlanNode child, Expression exp) {
866       super(child);
867       this.expression = exp;
868     }
869
870     public Table evaluate(QueryContext context) {
871       // Evaluate the child
872 Table t = child.evaluate(context);
873       // Perform the pattern search expression on the table.
874 // Split the expression,
875 Expression[] exps = expression.split();
876       Variable lhs_var = exps[0].getVariable();
877       if (lhs_var != null) {
878         // LHS is a simple variable so do a simple select
879 Operator op = (Operator) expression.last();
880         return t.simpleSelect(context, lhs_var, op, exps[1]);
881       }
882       else {
883         // LHS must be a constant so we can just evaluate the expression
884 // and see if we get true, false, null, etc.
885 TObject v = expression.evaluate(null, context);
886         // If it evaluates to NULL or FALSE then return an empty set
887 if (v.isNull() || v.getObject().equals(Boolean.FALSE)) {
888           return t.emptySelect();
889         }
890         else {
891           return t;
892         }
893       }
894     }
895
896     public ArrayList discoverTableNames(ArrayList list) {
897       return expression.discoverTableNames(super.discoverTableNames(list));
898     }
899
900     public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
901       return expression.discoverCorrelatedVariables(level,
902                super.discoverCorrelatedVariables(level, list));
903     }
904
905     public Object clone() throws CloneNotSupportedException {
906       SimplePatternSelectNode node = (SimplePatternSelectNode) super.clone();
907       node.expression = (Expression) expression.clone();
908       return node;
909     }
910
911     public String titleString() {
912       return "PATTERN: " + expression;
913     }
914
915   }
916
917   /**
918    * The node for finding a subset and renaming the columns of the results in
919    * the child node.
920    */
921   public static class SubsetNode extends SingleQueryPlanNode {
922
923     static final long serialVersionUID = 3784462788248510832L;
924
925     /**
926      * The original columns in the child that we are to make the subset of.
927      */
928     private Variable[] original_columns;
929
930     /**
931      * New names to assign the columns.
932      */
933     private Variable[] new_column_names;
934
935
936     public SubsetNode(QueryPlanNode child,
937                       Variable[] original_columns,
938                       Variable[] new_column_names) {
939       super(child);
940       this.original_columns = original_columns;
941       this.new_column_names = new_column_names;
942       
943     }
944
945     public Table evaluate(QueryContext context) {
946       Table t = child.evaluate(context);
947
948       int sz = original_columns.length;
949       int[] col_map = new int[sz];
950
951 // // DEBUG
952 // for (int n = 0; n < t.getColumnCount(); ++n) {
953 // System.out.print(t.getResolvedVariable(n).toTechString());
954 // System.out.print(", ");
955 // }
956 // System.out.println();
957 // // - DEBUG
958
959       for (int i = 0; i < sz; ++i) {
960
961 // // DEBUG
962 // System.out.print(t.getClass() + ".findFieldName(" +
963 // original_columns[i].toTechString() + ") = ");
964 // // - DEBUG
965
966         col_map[i] = t.findFieldName(original_columns[i]);
967
968 // // DEBUG
969 // System.out.println(col_map[i]);
970 // // - DEBUG
971
972       }
973
974       SubsetColumnTable col_table = new SubsetColumnTable(t);
975       col_table.setColumnMap(col_map, new_column_names);
976
977       return col_table;
978     }
979
980     // ---------- Set methods ----------
981
982     /**
983      * Sets the given table name of the resultant table. This is intended
984      * if we want to create a sub-query that has an aliased table name.
985      */
986     public void setGivenName(TableName name) {
987 // given_name = name;
988 if (name != null) {
989         int sz = new_column_names.length;
990         for (int i = 0; i < sz; ++i) {
991           new_column_names[i].setTableName(name);
992         }
993       }
994     }
995
996     // ---------- Get methods ----------
997
998     /**
999      * Returns the list of original columns that represent the mappings from
1000     * the columns in this subset.
1001     */
1002    public Variable[] getOriginalColumns() {
1003      return original_columns;
1004    }
1005
1006    /**
1007     * Returns the list of new column names that represent the new columns
1008     * in this subset.
1009     */
1010    public Variable[] getNewColumnNames() {
1011      return new_column_names;
1012    }
1013
1014    public Object clone() throws CloneNotSupportedException {
1015      SubsetNode node = (SubsetNode) super.clone();
1016      cloneArray(node.original_columns);
1017      cloneArray(node.new_column_names);
1018      return node;
1019    }
1020
1021    public String titleString() {
1022      StringBuffer buf = new StringBuffer ();
1023      buf.append("SUBSET: ");
1024      for (int i = 0; i < new_column_names.length; ++i) {
1025        buf.append(new_column_names[i]);
1026        buf.append("->");
1027        buf.append(original_columns[i]);
1028        buf.append(", ");
1029      }
1030      return new String (buf);
1031    }
1032
1033  }
1034
1035  /**
1036   * The node for performing a distinct operation on the given columns of the
1037   * child node.
1038   */
1039  public static class DistinctNode extends SingleQueryPlanNode {
1040
1041    static final long serialVersionUID = -1538264313804102373L;
1042
1043    /**
1044     * The list of columns to be distinct.
1045     */
1046    private Variable[] columns;
1047
1048    public DistinctNode(QueryPlanNode child, Variable[] columns) {
1049      super(child);
1050      this.columns = columns;
1051    }
1052
1053    public Table evaluate(QueryContext context) {
1054      Table t = child.evaluate(context);
1055      int sz = columns.length;
1056      int[] col_map = new int[sz];
1057      for (int i = 0; i < sz; ++i) {
1058        col_map[i] = t.findFieldName(columns[i]);
1059      }
1060      return t.distinct(col_map);
1061    }
1062
1063    public Object clone() throws CloneNotSupportedException {
1064      DistinctNode node = (DistinctNode) super.clone();
1065      cloneArray(node.columns);
1066      return node;
1067    }
1068
1069    public String titleString() {
1070      StringBuffer buf = new StringBuffer ();
1071      buf.append("DISTINCT: (");
1072      for (int i = 0; i < columns.length; ++i) {
1073        buf.append(columns[i]);
1074        buf.append(", ");
1075      }
1076      buf.append(")");
1077      return new String (buf);
1078    }
1079
1080  }
1081
1082  /**
1083   * The node for performing a sort operation on the given columns of the
1084   * child node.
1085   */
1086  public static class SortNode extends SingleQueryPlanNode {
1087
1088    static final long serialVersionUID = 3644480534542996928L;
1089
1090    /**
1091     * The list of columns to sort.
1092     */
1093    private Variable[] columns;
1094
1095    /**
1096     * Whether to sort the column in ascending or descending order
1097     */
1098    private boolean[] correct_ascending;
1099
1100    public SortNode(QueryPlanNode child, Variable[] columns,
1101                    boolean[] ascending) {
1102      super(child);
1103      this.columns = columns;
1104      this.correct_ascending = ascending;
1105
1106      // How we handle ascending/descending order
1107 // ----------------------------------------
1108 // Internally to the database, all columns are naturally ordered in
1109 // ascending order (start at lowest and end on highest). When a column
1110 // is ordered in descending order, a fast way to achieve this is to take
1111 // the ascending set and reverse it. This works for single columns,
1112 // however some thought is required for handling multiple column. We
1113 // order columns from RHS to LHS. If LHS is descending then this will
1114 // order the RHS incorrectly if we leave as is. Therefore, we must do
1115 // some pre-processing that looks ahead on any descending orders and
1116 // reverses the order of the columns to the right. This pre-processing
1117 // is done in the first pass.
1118
1119      int sz = ascending.length;
1120      for (int n = 0; n < sz - 1; ++n) {
1121        if (!ascending[n]) { // if descending...
1122 // Reverse order of all columns to the right...
1123 for (int p = n + 1; p < sz; ++p) {
1124            ascending[p] = !ascending[p];
1125          }
1126        }
1127      }
1128
1129    }
1130
1131    public Table evaluate(QueryContext context) {
1132      Table t = child.evaluate(context);
1133      // Sort the results by the columns in reverse-safe order.
1134 int sz = correct_ascending.length;
1135      for (int n = sz - 1; n >= 0; --n) {
1136        t = t.orderByColumn(columns[n], correct_ascending[n]);
1137      }
1138      return t;
1139    }
1140
1141    public Object clone() throws CloneNotSupportedException {
1142      SortNode node = (SortNode) super.clone();
1143      cloneArray(node.columns);
1144      return node;
1145    }
1146
1147    public String titleString() {
1148      StringBuffer buf = new StringBuffer ();
1149      buf.append("SORT: (");
1150      for (int i = 0; i < columns.length; ++i) {
1151        buf.append(columns[i]);
1152        if (correct_ascending[i]) {
1153          buf.append(" ASC");
1154        }
1155        else {
1156          buf.append(" DESC");
1157        }
1158        buf.append(", ");
1159      }
1160      buf.append(")");
1161      return new String (buf);
1162    }
1163
1164  }
1165
1166  /**
1167   * The node for performing a grouping operation on the columns of the child
1168   * node. As well as grouping, any aggregate functions must also be defined
1169   * with this plan.
1170   * <p>
1171   * NOTE: The whole child is a group if columns is null.
1172   */
1173  public static class GroupNode extends SingleQueryPlanNode {
1174
1175    static final long serialVersionUID = 7140928678192396348L;
1176
1177    /**
1178     * The columns to group by.
1179     */
1180    private Variable[] columns;
1181
1182    /**
1183     * The group max column.
1184     */
1185    private Variable group_max_column;
1186
1187    /**
1188     * Any aggregate functions (or regular function columns) that are to be
1189     * planned.
1190     */
1191    private Expression[] function_list;
1192
1193    /**
1194     * The list of names to give each function table.
1195     */
1196    private String [] name_list;
1197
1198
1199
1200    /**
1201     * Groups over the given columns from the child.
1202     */
1203    public GroupNode(QueryPlanNode child, Variable[] columns,
1204                     Variable group_max_column,
1205                     Expression[] function_list, String [] name_list) {
1206      super(child);
1207      this.columns = columns;
1208      this.group_max_column = group_max_column;
1209      this.function_list = function_list;
1210      this.name_list = name_list;
1211    }
1212
1213    /**
1214     * Groups over the entire child (always ends in 1 result in set).
1215     */
1216    public GroupNode(QueryPlanNode child, Variable group_max_column,
1217                     Expression[] function_list, String [] name_list) {
1218      this(child, null, group_max_column, function_list, name_list);
1219    }
1220
1221    public Table evaluate(QueryContext context) {
1222      Table child_table = child.evaluate(context);
1223      DatabaseQueryContext db_context = (DatabaseQueryContext) context;
1224      FunctionTable fun_table =
1225         new FunctionTable(child_table, function_list, name_list, db_context);
1226      // If no columns then it is implied the whole table is the group.
1227 if (columns == null) {
1228        fun_table.setWholeTableAsGroup();
1229      }
1230      else {
1231        fun_table.createGroupMatrix(columns);
1232      }
1233      return fun_table.mergeWithReference(group_max_column);
1234    }
1235
1236    public ArrayList discoverTableNames(ArrayList list) {
1237      list = super.discoverTableNames(list);
1238      for (int i = 0; i < function_list.length; ++i) {
1239        list = function_list[i].discoverTableNames(list);
1240      }
1241      return list;
1242    }
1243
1244    public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
1245      list = super.discoverCorrelatedVariables(level, list);
1246      for (int i = 0; i < function_list.length; ++i) {
1247        list = function_list[i].discoverCorrelatedVariables(level, list);
1248      }
1249      return list;
1250    }
1251
1252    public Object clone() throws CloneNotSupportedException {
1253      GroupNode node = (GroupNode) super.clone();
1254      cloneArray(node.columns);
1255      cloneArray(node.function_list);
1256      if (group_max_column != null) {
1257        node.group_max_column = (Variable) group_max_column.clone();
1258      }
1259      else {
1260        node.group_max_column = null;
1261      }
1262      return node;
1263    }
1264
1265    public String titleString() {
1266      StringBuffer buf = new StringBuffer ();
1267      buf.append("GROUP: (");
1268      if (columns == null) {
1269        buf.append("WHOLE TABLE");
1270      }
1271      else {
1272        for (int i = 0; i < columns.length; ++i) {
1273          buf.append(columns[i]);
1274          buf.append(", ");
1275        }
1276      }
1277      buf.append(")");
1278      if (function_list != null) {
1279        buf.append(" FUNS: [");
1280        for (int i = 0; i < function_list.length; ++i) {
1281          buf.append(function_list[i]);
1282          buf.append(", ");
1283        }
1284        buf.append("]");
1285      }
1286      return new String (buf);
1287    }
1288
1289  }
1290
1291  /**
1292   * The node for merging the child node with a set of new function columns
1293   * over the entire result. For example, we may want to add an expression
1294   * 'a + 10' or 'coalesce(a, b, 1)'.
1295   */
1296  public static class CreateFunctionsNode extends SingleQueryPlanNode {
1297
1298    static final long serialVersionUID = -181012844247626327L;
1299
1300    /**
1301     * The list of functions to create.
1302     */
1303    private Expression[] function_list;
1304
1305    /**
1306     * The list of names to give each function table.
1307     */
1308    private String [] name_list;
1309
1310    /**
1311     * Constructor.
1312     */
1313    public CreateFunctionsNode(QueryPlanNode child, Expression[] function_list,
1314                               String [] name_list) {
1315      super(child);
1316      this.function_list = function_list;
1317      this.name_list = name_list;
1318    }
1319
1320    public Table evaluate(QueryContext context) {
1321      Table child_table = child.evaluate(context);
1322      DatabaseQueryContext db_context = (DatabaseQueryContext) context;
1323      FunctionTable fun_table =
1324          new FunctionTable(child_table, function_list, name_list, db_context);
1325      Table t = fun_table.mergeWithReference(null);
1326      return t;
1327    }
1328
1329    public ArrayList discoverTableNames(ArrayList list) {
1330      list = super.discoverTableNames(list);
1331      for (int i = 0; i < function_list.length; ++i) {
1332        list = function_list[i].discoverTableNames(list);
1333      }
1334      return list;
1335    }
1336
1337    public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
1338      list = super.discoverCorrelatedVariables(level, list);
1339      for (int i = 0; i < function_list.length; ++i) {
1340        list = function_list[i].discoverCorrelatedVariables(level, list);
1341      }
1342      return list;
1343    }
1344
1345    public Object clone() throws CloneNotSupportedException {
1346      CreateFunctionsNode node = (CreateFunctionsNode) super.clone();
1347      cloneArray(node.function_list);
1348      return node;
1349    }
1350
1351    public String titleString() {
1352      StringBuffer buf = new StringBuffer ();
1353      buf.append("FUNCTIONS: (");
1354      for (int i = 0; i < function_list.length; ++i) {
1355        buf.append(function_list[i]);
1356        buf.append(", ");
1357      }
1358      buf.append(")");
1359      return new String (buf);
1360    }
1361
1362  }
1363
1364  /**
1365   * A marker node that takes the result of a child and marks it as a name
1366   * that can later be retrieved. This is useful for implementing things
1367   * such as outer joins.
1368   */
1369  public static class MarkerNode extends SingleQueryPlanNode {
1370
1371    static final long serialVersionUID = -8321710589608765270L;
1372
1373    /**
1374     * The name of this mark.
1375     */
1376    private String mark_name;
1377
1378    /**
1379     * Constructor.
1380     */
1381    public MarkerNode(QueryPlanNode child, String mark_name) {
1382      super(child);
1383      this.mark_name = mark_name;
1384    }
1385
1386    public Table evaluate(QueryContext context) {
1387      Table child_table = child.evaluate(context);
1388      context.addMarkedTable(mark_name, child_table);
1389      return child_table;
1390    }
1391
1392    public Object clone() throws CloneNotSupportedException {
1393      return super.clone();
1394    }
1395
1396  }
1397
1398  /**
1399   * A cache point node that only evaluates the child if the result can not
1400   * be found in the cache with the given unique id.
1401   */
1402  public static class CachePointNode extends SingleQueryPlanNode {
1403
1404    static final long serialVersionUID = 7866310557831478639L;
1405
1406    /**
1407     * The unique identifier of this cache point.
1408     */
1409    private long id;
1410
1411    private final static Object GLOB_LOCK = new Object ();
1412    private static int GLOB_ID = 0;
1413
1414    /**
1415     * Constructor.
1416     */
1417    public CachePointNode(QueryPlanNode child) {
1418      super(child);
1419      synchronized (GLOB_LOCK) {
1420        id = (System.currentTimeMillis() << 16) | (GLOB_ID & 0x0FFFF);
1421        ++GLOB_ID;
1422      }
1423    }
1424
1425    public Table evaluate(QueryContext context) {
1426      // Is the result available in the context?
1427 Table child_table = context.getCachedNode(id);
1428      if (child_table == null) {
1429        // No so evaluate the child and cache it
1430 child_table = child.evaluate(context);
1431        context.putCachedNode(id, child_table);
1432      }
1433      return child_table;
1434    }
1435
1436    public Object clone() throws CloneNotSupportedException {
1437      return super.clone();
1438    }
1439
1440    public String titleString() {
1441      return "CACHE: " + id;
1442    }
1443
1444  }
1445
1446
1447
1448
1449
1450
1451
1452
1453  /**
1454   * A branch node for naturally joining two tables together. These branches
1455   * should be optimized out if possible because they result in huge results.
1456   */
1457  public static class NaturalJoinNode extends BranchQueryPlanNode {
1458
1459    static final long serialVersionUID = 942526205653132810L;
1460
1461    public NaturalJoinNode(QueryPlanNode left, QueryPlanNode right) {
1462      super(left, right);
1463    }
1464
1465    public Table evaluate(QueryContext context) {
1466      // Solve the left branch result
1467 Table left_result = left.evaluate(context);
1468      // Solve the Join (natural)
1469 return left_result.join(right.evaluate(context));
1470    }
1471
1472    public String titleString() {
1473      return "NATURAL JOIN";
1474    }
1475
1476  }
1477
1478  /**
1479   * A branch node for equi-joining two tables together given two sets of
1480   * columns. This is a seperate node from a general join operation to allow
1481   * for optimizations with multi-column indexes.
1482   * <p>
1483   * An equi-join is the most common type of join.
1484   * <p>
1485   * At query runtime, this decides the best best way to perform the join,
1486   * either by
1487   */
1488  public static class EquiJoinNode extends BranchQueryPlanNode {
1489
1490    static final long serialVersionUID = 113332589582049607L;
1491
1492    /**
1493     * The columns in the left table.
1494     */
1495    private Variable[] left_columns;
1496
1497    /**
1498     * The columns in the right table.
1499     */
1500    private Variable[] right_columns;
1501
1502    public EquiJoinNode(QueryPlanNode left, QueryPlanNode right,
1503                        Variable[] left_cols, Variable[] right_cols) {
1504      super(left, right);
1505      this.left_columns = left_cols;
1506      this.right_columns = right_cols;
1507    }
1508
1509    public Table evaluate(QueryContext context) {
1510      // Solve the left branch result
1511 Table left_result = left.evaluate(context);
1512      // Solve the right branch result
1513 Table right_result = right.evaluate(context);
1514
1515      // PENDING: This needs to migrate to a better implementation that
1516 // exploits multi-column indexes if one is defined that can be used.
1517
1518      Variable first_left = left_columns[0];
1519      Variable first_right = right_columns[0];
1520
1521      Operator EQUALS_OP = Operator.get("=");
1522
1523      Table result = left_result.simpleJoin(context, right_result,
1524           first_left, EQUALS_OP, new Expression(first_right));
1525
1526      int sz = left_columns.length;
1527      // If there are columns left to equi-join, we resolve the rest with a
1528 // single exhaustive select of the form,
1529 // ( table1.col2 = table2.col2 AND table1.col3 = table2.col3 AND ... )
1530 if (sz > 1) {
1531        // Form the expression
1532 Expression rest_expression = new Expression();
1533        for (int i = 1; i < sz; ++i) {
1534          Variable left_var = left_columns[i];
1535          Variable right_var = right_columns[i];
1536          rest_expression.addElement(left_var);
1537          rest_expression.addElement(right_var);
1538          rest_expression.addOperator(EQUALS_OP);
1539        }
1540        Operator AND_OP = Operator.get("and");
1541        for (int i = 2; i < sz; ++i) {
1542          rest_expression.addOperator(AND_OP);
1543        }
1544        result = result.exhaustiveSelect(context, rest_expression);
1545      }
1546
1547      return result;
1548    }
1549
1550    public Object clone() throws CloneNotSupportedException {
1551      EquiJoinNode node = (EquiJoinNode) super.clone();
1552      cloneArray(node.left_columns);
1553      cloneArray(node.right_columns);
1554      return node;
1555    }
1556
1557  }
1558
1559  /**
1560   * A branch node for a non-equi join between two tables.
1561   * <p>
1562   * NOTE: The cost of a LeftJoin is higher if the right child result is
1563   * greater than the left child result. The plan should be arranged so
1564   * smaller results are on the left.
1565   */
1566  public static class JoinNode extends BranchQueryPlanNode {
1567
1568    static final long serialVersionUID = 4133205808616807832L;
1569
1570    /**
1571     * The variable in the left table to be joined.
1572     */
1573    private Variable left_var;
1574
1575    /**
1576     * The operator to join under (=, <>, >, <, >=, <=).
1577     */
1578    private Operator join_op;
1579
1580    /**
1581     * The expression evaluated on the right table.
1582     */
1583    private Expression right_expression;
1584
1585    public JoinNode(QueryPlanNode left, QueryPlanNode right,
1586                    Variable left_var, Operator join_op,
1587                    Expression right_expression) {
1588      super(left, right);
1589      this.left_var = left_var;
1590      this.join_op = join_op;
1591      this.right_expression = right_expression;
1592    }
1593
1594    public Table evaluate(QueryContext context) {
1595      // Solve the left branch result
1596 Table left_result = left.evaluate(context);
1597      // Solve the right branch result
1598 Table right_result = right.evaluate(context);
1599
1600      // If the right_expression is a simple variable then we have the option
1601 // of optimizing this join by putting the smallest table on the LHS.
1602 Variable rhs_var = right_expression.getVariable();
1603      Variable lhs_var = left_var;
1604      Operator op = join_op;
1605      if (rhs_var != null) {
1606        // We should arrange the expression so the right table is the smallest
1607 // of the sides.
1608 // If the left result is less than the right result
1609 if (left_result.getRowCount() < right_result.getRowCount()) {
1610          // Reverse the join
1611 right_expression = new Expression(lhs_var);
1612          lhs_var = rhs_var;
1613          op = op.reverse();
1614          // Reverse the tables.
1615 Table t = right_result;
1616          right_result = left_result;
1617          left_result = t;
1618        }
1619      }
1620
1621      // The join operation.
1622 return left_result.simpleJoin(context, right_result,
1623                                    lhs_var, op, right_expression);
1624    }
1625
1626    public ArrayList discoverTableNames(ArrayList list) {
1627      return right_expression.discoverTableNames(
1628                                         super.discoverTableNames(list));
1629    }
1630
1631    public ArrayList discoverCorrelatedVariables(int level, ArrayList list) {
1632      return right_expression.discoverCorrelatedVariables(level,
1633               super.discoverCorrelatedVariables(level, list));
1634    }
1635
1636    public Object clone() throws CloneNotSupportedException {
1637      JoinNode node = (JoinNode) super.clone();
1638      node.left_var = (Variable) left_var.clone();
1639      node.right_expression = (Expression) right_expression.clone();
1640      return node;
1641    }
1642
1643    public String titleString() {
1644      return "JOIN: " + left_var + join_op +
1645             right_expression;
1646    }
1647
1648  }
1649
1650  /**
1651   * A branch node for a left outer join. Using this node is a little non-
1652   * intuitive. This node will only work when used in conjuction with
1653   * MarkerNode.
1654   * <p>
1655   * To use - first the complete left table in the join must be marked with a
1656   * name. Then the ON expression is evaluated to a single plan node. Then
1657   * this plan node must be added to result in a left outer join. A tree for
1658   * a left outer join may look as follows;
1659   * <p><pre>
1660   * LeftOuterJoinNode
1661   * |
1662   * Join a = b
1663   * / \
1664   * Marker GetTable T2
1665   * |
1666   * GetTable T1
1667   * </pre>
1668   */
1669  public static class LeftOuterJoinNode extends SingleQueryPlanNode {
1670
1671    static final long serialVersionUID = 8908801499550863492L;
1672
1673    /**
1674     * The name of the mark that points to the left table that represents
1675     * the complete set.
1676     */
1677    private String complete_mark_name;
1678
1679    public LeftOuterJoinNode(QueryPlanNode child, String complete_mark_name) {
1680      super(child);
1681      this.complete_mark_name = complete_mark_name;
1682    }
1683
1684    public Table evaluate(QueryContext context) {
1685      // Evaluate the child branch,
1686 Table result = child.evaluate(context);
1687      // Get the table of the complete mark name,
1688 Table complete_left = context.getMarkedTable(complete_mark_name);
1689
1690      // The rows in 'complete_left' that are outside (not in) the rows in the
1691 // left result.
1692 Table outside = complete_left.outside(result);
1693
1694      // Create an OuterTable
1695 OuterTable outer_table = new OuterTable(result);
1696      outer_table.mergeIn(outside);
1697
1698      // Return the outer table
1699 return outer_table;
1700    }
1701
1702    public String titleString() {
1703      return "LEFT OUTER JOIN";
1704    }
1705
1706  }
1707
1708  /**
1709   * A branch node for a logical union of two tables of identical types. This
1710   * branch can only work if the left and right children have exactly the same
1711   * ancestor tables. If the ancestor tables are different it will fail. This
1712   * node is used for logical OR.
1713   * <p>
1714   * This union does not include duplicated rows.
1715   */
1716  public static class LogicalUnionNode extends BranchQueryPlanNode {
1717
1718    static final long serialVersionUID = -7783166856668779902L;
1719
1720    public LogicalUnionNode(QueryPlanNode left, QueryPlanNode right) {
1721      super(left, right);
1722    }
1723
1724    public Table evaluate(QueryContext context) {
1725      // Solve the left branch result
1726 Table left_result = left.evaluate(context);
1727      // Solve the right branch result
1728 Table right_result = right.evaluate(context);
1729
1730      return left_result.union(right_result);
1731    }
1732
1733    public String titleString() {
1734      return "LOGICAL UNION";
1735    }
1736
1737  }
1738
1739  /**
1740   * A branch node for performing a composite function on two child nodes.
1741   * This branch is used for general UNION, EXCEPT, INTERSECT composites. The
1742   * left and right branch results must have the same number of columns and
1743   * column types.
1744   */
1745  public static class CompositeNode extends BranchQueryPlanNode {
1746
1747    static final long serialVersionUID = -560587816928425857L;
1748
1749    /**
1750     * The composite operation
1751     * (either CompositeTable.UNION, EXCEPT, INTERSECT).
1752     */
1753    private int composite_op;
1754
1755    /**
1756     * If this is true, the composite includes all results from both children,
1757     * otherwise removes deplicates.
1758     */
1759    private boolean all_op;
1760
1761    public CompositeNode(QueryPlanNode left, QueryPlanNode right,
1762                         int composite_op, boolean all_op) {
1763      super(left, right);
1764      this.composite_op = composite_op;
1765      this.all_op = all_op;
1766    }
1767
1768    public Table evaluate(QueryContext context) {
1769      // Solve the left branch result
1770 Table left_result = left.evaluate(context);
1771      // Solve the right branch result
1772 Table right_result = right.evaluate(context);
1773
1774      // Form the composite table
1775 CompositeTable t = new CompositeTable(left_result,
1776                                 new Table[] { left_result, right_result });
1777      t.setupIndexesForCompositeFunction(composite_op, all_op);
1778
1779      return t;
1780    }
1781
1782  }
1783
1784  /**
1785   * A branch node for a non-correlated ANY or ALL sub-query evaluation. This
1786   * node requires a set of columns from the left branch and an operator.
1787   * The right branch represents the non-correlated sub-query.
1788   * <p>
1789   * NOTE: The cost of a SubQuery is higher if the right child result is
1790   * greater than the left child result. The plan should be arranged so
1791   * smaller results are on the left.
1792   */
1793  public static class NonCorrelatedAnyAllNode extends BranchQueryPlanNode {
1794
1795    static final long serialVersionUID = 7480579008259288291L;
1796
1797    /**
1798     * The columns in the left table.
1799     */
1800    private Variable[] left_columns;
1801
1802    /**
1803     * The SubQuery operator, eg. '= ANY', '<> ALL'
1804     */
1805    private Operator sub_query_operator;
1806
1807    public NonCorrelatedAnyAllNode(QueryPlanNode left, QueryPlanNode right,
1808                              Variable[] left_vars, Operator subquery_op) {
1809      super(left, right);
1810      this.left_columns = left_vars;
1811      this.sub_query_operator = subquery_op;
1812    }
1813
1814    public Table evaluate(QueryContext context) {
1815      // Solve the left branch result
1816 Table left_result = left.evaluate(context);
1817      // Solve the right branch result
1818 Table right_result = right.evaluate(context);
1819
1820      // Solve the sub query on the left columns with the right plan and the
1821 // given operator.
1822 return TableFunctions.anyAllNonCorrelated(left_result, left_columns,
1823                                          sub_query_operator, right_result);
1824    }
1825
1826    public Object clone() throws CloneNotSupportedException {
1827      NonCorrelatedAnyAllNode node = (NonCorrelatedAnyAllNode) super.clone();
1828      cloneArray(node.left_columns);
1829      return node;
1830    }
1831
1832    public String titleString() {
1833      StringBuffer buf = new StringBuffer ();
1834      buf.append("NON_CORRELATED: (");
1835      for (int i = 0; i < left_columns.length; ++i) {
1836        buf.append(left_columns[i].toString());
1837      }
1838      buf.append(") ");
1839      buf.append(sub_query_operator.toString());
1840      return new String (buf);
1841    }
1842
1843  }
1844
1845}
1846

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags