TableFilter


1   /* Copyright (c) 1995-2000, The Hypersonic SQL Group.
2    * All rights reserved.
3    *
4    * Redistribution and use in source and binary forms, with or without
5    * modification, are permitted provided that the following conditions are met:
6    *
7    * Redistributions of source code must retain the above copyright notice, this
8    * list of conditions and the following disclaimer.
9    *
10   * Redistributions in binary form must reproduce the above copyright notice,
11   * this list of conditions and the following disclaimer in the documentation
12   * and/or other materials provided with the distribution.
13   *
14   * Neither the name of the Hypersonic SQL Group nor the names of its
15   * contributors may be used to endorse or promote products derived from this
16   * software without specific prior written permission.
17   *
18   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21   * ARE DISCLAIMED. IN NO EVENT SHALL THE HYPERSONIC SQL GROUP,
22   * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25   * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29   *
30   * This software consists of voluntary contributions made by many individuals 
31   * on behalf of the Hypersonic SQL Group.
32   *
33   *
34   * For work added by the HSQL Development Group:
35   *
36   * Copyright (c) 2001-2005, The HSQL Development Group
37   * All rights reserved.
38   *
39   * Redistribution and use in source and binary forms, with or without
40   * modification, are permitted provided that the following conditions are met:
41   *
42   * Redistributions of source code must retain the above copyright notice, this
43   * list of conditions and the following disclaimer.
44   *
45   * Redistributions in binary form must reproduce the above copyright notice,
46   * this list of conditions and the following disclaimer in the documentation
47   * and/or other materials provided with the distribution.
48   *
49   * Neither the name of the HSQL Development Group nor the names of its
50   * contributors may be used to endorse or promote products derived from this
51   * software without specific prior written permission.
52   *
53   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
54   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
55   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
56   * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
57   * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
58   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
59   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
60   * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
61   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
62   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
63   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
64   */
65  
66  
67  package org.hsqldb;
68  
69  import org.hsqldb.index.RowIterator;
70  import org.hsqldb.lib.ArrayUtil;
71  import org.hsqldb.lib.HashMappedList;
72  
73  // fredt@users 20030813 - patch 1.7.2 - fix for column comparison within same table bugs #572075 and 722443
74  // fredt@users 20031012 - patch 1.7.2 - better OUTER JOIN implementation
75  // fredt@users 20031026 - patch 1.7.2 - more efficient findfirst - especially for multi-column equijoins
76  // implemented optimisations similart to patch 465542 by hjbush@users
77  
78  /**
79   * This class iterates over table rows to select the rows that fulfil join
80   * or other conditions. It uses indexes if they are availabe.
81   *
82   * Extended in successive versions of HSQLDB.
83   *
84   * @author Thomas Mueller (Hypersonic SQL Group)
85   * @version 1.8.0
86   * @since Hypersonic SQL
87   */
88  final class TableFilter {
89  
90      static final int CONDITION_NONE      = -1;     // not a condition expression
91      static final int CONDITION_UNORDERED = 0;      // not candidate for eStart or eEnd
92      static final int   CONDITION_START_END = 1;    // candidate for eStart and eEnd
93      static final int   CONDITION_START     = 2;    // candidate for eStart
94      static final int   CONDITION_END       = 3;    // candidate for eEnd
95      static final int   CONDITION_OUTER     = 4;    // add to this
96      Table              filterTable;
97      private String       tableAlias;
98      HashMappedList     columnAliases;
99      Index              filterIndex;
100     private Object  []   emptyData;
101     boolean[]          usedColumns;
102     private Expression eStart, eEnd;
103 
104     //
105     Expression eAnd;
106 
107     //
108     boolean      isOuterJoin;                      // table joined with OUTER JOIN
109     boolean      isAssigned;                       // conditions have been assigned to this
110     boolean      isMultiFindFirst;                 // findFirst() uses multi-column index
111     Expression[] findFirstExpressions;             // expressions for column values
112 
113     //
114     private RowIterator it;
115     Object  []            currentData;
116     Row                 currentRow;
117 
118     //
119     Object  [] currentJoinData;
120 
121     // addendum to the result of findFirst() and next() with isOuterJoin==true
122     // when the result is false, it indicates if a non-join condition caused the failure
123     boolean nonJoinIsNull;
124 
125     // indicates current data is empty data produced for an outer join
126     boolean isCurrentOuter;
127 
128     /**
129      * Constructor declaration
130      *
131      *
132      * @param t
133      * @param alias
134      * @param outerjoin
135      */
136     TableFilter(Table t, String   alias, HashMappedList columnList,
137                 boolean outerjoin) {
138 
139         filterTable   = t;
140         tableAlias    = alias == null ? t.getName().name
141                                       : alias;
142         columnAliases = columnList;
143         isOuterJoin   = outerjoin;
144         emptyData     = filterTable.getEmptyRowData();
145         usedColumns   = filterTable.getNewColumnCheckList();
146     }
147 
148     /**
149      * Returns the alias or the table name.
150      * Never returns null;
151      * @return
152      */
153     String   getName() {
154         return tableAlias;
155     }
156 
157     /**
158      * Retrieves this object's filter Table object.
159      *
160      * @return this object's filter Table object
161      */
162     Table getTable() {
163         return filterTable;
164     }
165 
166     /**
167      * Retrieves a CONDITION_XXX code indicating how a condition
168      * expression can be used for a TableFilter.
169      *
170      * @param exprType an expression type code
171      * @return
172      */
173     static int getConditionType(Expression e) {
174 
175         int exprType = e.getType();
176 
177         switch (exprType) {
178 
179             case Expression.NOT_EQUAL :
180             case Expression.LIKE :
181                 return CONDITION_UNORDERED;
182 
183             case Expression.IN : {
184                 return e.isQueryCorrelated ? CONDITION_NONE
185                                            : CONDITION_UNORDERED;
186             }
187             case Expression.IS_NULL :
188             case Expression.EQUAL : {
189                 return CONDITION_START_END;
190             }
191             case Expression.BIGGER :
192             case Expression.BIGGER_EQUAL : {
193                 return CONDITION_START;
194             }
195             case Expression.SMALLER :
196             case Expression.SMALLER_EQUAL : {
197                 return CONDITION_END;
198             }
199             default : {
200 
201                 // not a condition so forget it
202                 return CONDITION_NONE;
203             }
204         }
205     }
206 
207     // TODO: Optimize
208     //
209     // The current way always chooses eStart, eEnd conditions
210     // using first encountered eligible index
211     //
212     // We should check if current index offers better selectivity/access
213     // path than previously assigned iIndex.
214     //
215     // EXAMPLE 1:
216     //
217     // CREATE TABLE t (c1 int, c2 int primary key)
218     // CREATE INDEX I1 ON t(c1)
219     // SELECT
220     //      *
221     // FROM
222     //      t
223     // WHERE
224     //     c1 = | < | <= | >= | > ...
225     // AND
226     //     c2 = | < | <= | >= | > ...
227     //
228     // currently always chooses iIndex / condition (c1/I1), over
229     // index / condition (c2/pk), whereas index / condition (c2/pk)
230     // may well be better, especially if condition on c2 is equality
231     // (condition_start_end) and conditionon(s) on c1 involve range
232     // (condition_start, condition_end, or some composite).
233     //
234     // Currently, the developer/client software must somehow know facts
235     // both about the table, the query and the way HSQLDB forms its
236     // plans and, based on this knowlege, perhaps decide to reverse
237     // order by explicitly issuing instead:
238     //
239     // SELECT
240     //      *
241     // FROM
242     //      t
243     // WHERE
244     //     c2 = | < | <= | >= | > ...
245     // AND
246     //     c1 = | < | <= | >= | > ...
247     //
248     // to get optimal index choice.
249     //
250     // The same thing applies to and is even worse for joins.
251     //
252     // Consider the following (highly artificial, but easy to
253     // understand) case:
254     //
255     // CREATE TABLE T1(ID INTEGER PRIMARY KEY, C1 INTEGER)
256     // CREATE INDEX I1 ON T1(C1)
257     // CREATE TABLE T2(ID INTEGER PRIMARY KEY, C1 INTEGER)
258     // CREATE INDEX I2 ON T2(C1)
259     //
260     // select * from t1, t2 where t1.c1 = t2.c1 and t1.id = t2.id
261     //
262     // Consider the worst value distribution where t1 and t2 are both
263     // 10,000 rows, c1 selectivity is nil (all values are identical)
264     // for both tables, and, say, id values span the range 0..9999
265     // for both tables.
266     //
267     // Then time to completion on 500 MHz Athlon testbed using memory
268     // tables is:
269     //
270     // 10000 row(s) in 309114 ms
271     //
272     // whereas for:
273     //
274     // select * from t1, t2 where t1.id = t2.id and t1.c1 = t2.c1
275     //
276     // time to completion is:
277     //
278     // 10000 row(s) in 471 ms
279     //
280     // Hence, the unoptimized query takes 656 times as long as the
281     // optimized one!!!
282     //
283     // EXAMPLE 2:
284     //
285     // If there are, say, two non-unique candidate indexes,
286     // and some range or equality predicates against
287     // them, preference should be given to the one with
288     // better selectivity (if the total row count of the
289     // table is large, otherwise the overhead of making
290     // the choice is probably large w.r.t. any possible
291     // savings).  Might require maintaining some basic
292     // statistics or performing appropriate index probes
293     // at the time the plan is being generated.
294 
295     /**
296      * Chooses certain query conditions and assigns a copy of them to this
297      * filter. The original condition is set to Expression.TRUE once assigned.
298      *
299      * @param condition
300      *
301      * @throws HsqlException
302      */
303     void setConditions(Session session,
304                        Expression condition) throws HsqlException {
305 
306         setCondition(session, condition);
307 
308         if (filterIndex == null) {
309             filterIndex = filterTable.getPrimaryIndex();
310         }
311 
312         if (filterIndex.getVisibleColumns() == 1 || eStart == null
313                 || eAnd == null || eStart.exprType != Expression.EQUAL) {
314             return;
315         }
316 
317         boolean[]    check    = filterTable.getNewColumnCheckList();
318         Expression[] expr     = new Expression[check.length];
319         int          colindex = eStart.getArg().getColumnNr();
320 
321         check[colindex] = true;
322         expr[colindex]  = eStart.getArg2();
323 
324         eAnd.getEquiJoinColumns(this, check, expr);
325 
326         if (ArrayUtil.containsAllTrueElements(check, filterIndex.colCheck)) {
327             isMultiFindFirst     = true;
328             findFirstExpressions = expr;
329         }
330     }
331 
332     private void setCondition(Session session,
333                               Expression e) throws HsqlException {
334 
335         int        type = e.getType();
336         Expression e1   = e.getArg();
337         Expression e2   = e.getArg2();
338 
339         isAssigned = true;
340 
341         if (type == Expression.AND) {
342             setCondition(session, e1);
343             setCondition(session, e2);
344 
345             return;
346         }
347 
348         if (type == Expression.OR && isOuterJoin && e.isInJoin
349                 && e.outerFilter == this) {
350             addAndCondition(e);
351             e.setTrue();
352 
353             return;
354         }
355 
356         int conditionType = getConditionType(e);
357 
358         if (conditionType == CONDITION_NONE) {
359 
360             // not a condition expression
361             return;
362         }
363 
364 // fredt@users 20030813 - patch 1.7.2 - fix for column comparison within same table bugs #572075 and 722443
365         if (e1.getFilter() == this && e2.getFilter() == this) {
366             conditionType = CONDITION_UNORDERED;
367         } else if (e1.getFilter() == this) {
368             if (!e.isInJoin && isOuterJoin) {
369 
370                 // do not use a where condition on the second table in outer joins
371                 return;
372             }
373 
374             // ok include this
375         } else if ((e2.getFilter() == this)
376                    && (conditionType != CONDITION_UNORDERED)) {
377 
378             // swap and try again to allow index usage
379             e.swapCondition();
380             setCondition(session, e);
381 
382             return;
383         } else if (e1.outerFilter == this) {
384 
385             // fredt - this test is last to allow swapping the terms above
386             conditionType = CONDITION_OUTER;
387         } else {
388 
389             // unrelated: don't include
390             return;
391         }
392 
393 //        Trace.doAssert(e1.getFilter() == this, "setCondition");
394         if (!e2.isResolved()) {
395             return;
396         }
397 
398         // fredt - condition defined in outer but not this one
399         if (e1.outerFilter != null && e1.outerFilter != this) {
400             return;
401         }
402 
403         if (conditionType == CONDITION_UNORDERED) {
404             addAndCondition(e);
405 
406             return;
407         }
408 
409         if (conditionType == CONDITION_OUTER) {
410             addAndCondition(e);
411 
412             return;
413         }
414 
415         int   i     = e1.getColumnNr();
416         Index index = filterTable.getIndexForColumn(session, i);
417 
418         if (index == null || (filterIndex != index && filterIndex != null)) {
419             addAndCondition(e);
420 
421             return;
422         }
423 
424         filterIndex = index;
425 
426         switch (conditionType) {
427 
428             case CONDITION_START_END : {
429 
430                 // candidate for both start and end
431                 if ((eStart != null) || (eEnd != null)) {
432                     addAndCondition(e);
433 
434                     return;
435                 }
436 
437                 eStart = new Expression(e);
438                 eEnd   = eStart;
439 
440                 break;
441             }
442             case CONDITION_START : {
443 
444                 // candidate for start
445                 if (eStart != null) {
446                     addAndCondition(e);
447 
448                     return;
449                 }
450 
451                 eStart = new Expression(e);
452 
453                 break;
454             }
455             case CONDITION_END : {
456 
457                 // candidate for end
458                 if (eEnd != null) {
459                     addAndCondition(e);
460 
461                     return;
462                 }
463 
464                 eEnd = new Expression(e);
465 
466                 break;
467             }
468         }
469 
470         e.setTrue();
471     }
472 
473     /**
474      * Finds the first row in the table (using an index if there is one) and
475      * checks it against the eEnd (range) and eAnd (other conditions)
476      * Expression objects. (fredt)
477      *
478      * @return true if first row was found, else false
479      */
480     boolean findFirst(Session session) throws HsqlException {
481 
482         nonJoinIsNull  = false;
483         isCurrentOuter = false;
484 
485         if (filterIndex == null) {
486             filterIndex = filterTable.getPrimaryIndex();
487         }
488 
489         if (isMultiFindFirst) {
490             boolean convertible = true;
491             int[]   types       = filterTable.getColumnTypes();
492 
493             currentJoinData = filterTable.getEmptyRowData();
494 
495             for (int i = 0; i < findFirstExpressions.length; i++) {
496                 Expression e = findFirstExpressions[i];
497 
498                 if (e != null) {
499                     Object   value = e.getValue(session);
500 
501                     if (Column.compareToTypeRange(value, types[i]) != 0) {
502                         convertible = false;
503 
504                         break;
505                     }
506 
507                     value = Column.convertObject(value, types[i]);
508                     currentJoinData[i] = e.getValue(session, types[i]);
509                 }
510             }
511 
512             it = convertible
513                  ? filterIndex.findFirstRow(session, currentJoinData)
514                  : filterIndex.emptyIterator();
515 
516             if (!it.hasNext()) {
517                 ArrayUtil.clearArray(ArrayUtil.CLASS_CODE_OBJECT,
518                                      currentJoinData, 0,
519                                      currentJoinData.length);
520             }
521         } else if (eStart == null) {
522             it = eEnd == null ? filterIndex.firstRow(session)
523                               : filterIndex.findFirstRowNotNull(session);
524         } else {
525             Object   value      = eStart.getArg2().getValue(session);
526             int    valuetype  = eStart.getArg2().getDataType();
527             int    targettype = eStart.getArg().getDataType();
528 
529             it = getFirstIterator(session, eStart.getType(), value,
530                                   valuetype, filterIndex, targettype);
531         }
532 
533         while (true) {
534             currentRow = it.next();
535 
536             if (currentRow == null) {
537                 break;
538             }
539 
540             currentData = currentRow.getData();
541 
542             if (!(eEnd == null || eEnd.testCondition(session))) {
543                 break;
544             }
545 
546             if (eAnd == null || eAnd.testCondition(session)) {
547                 return true;
548             }
549         }
550 
551         currentRow  = null;
552         currentData = emptyData;
553 
554         return false;
555     }
556 
557     static RowIterator getFirstIterator(Session session, int eType,
558                                         Object   value, int valueType,
559                                         Index index,
560                                         int targetType) throws HsqlException {
561 
562         RowIterator it;
563         int         range = 0;
564 
565         if (targetType != valueType) {
566             range = Column.compareToTypeRange(value, targetType);
567         }
568 
569         if (range == 0) {
570             value = Column.convertObject(value, targetType);
571             it    = index.findFirstRow(session, value, eType);
572         } else {
573             switch (eType) {
574 
575                 case Expression.BIGGER_EQUAL :
576                 case Expression.BIGGER :
577                     if (range < 0) {
578                         it = index.findFirstRowNotNull(session);
579 
580                         break;
581                     }
582                 default :
583                     it = index.emptyIterator();
584             }
585         }
586 
587         return it;
588     }
589 
590     /**
591      * Advances to the next available value. <p>
592      *
593      * @return true if a next value is available upon exit
594      *
595      * @throws HsqlException if a database access error occurs
596      */
597     boolean next(Session session) throws HsqlException {
598 
599         boolean result = false;
600 
601         nonJoinIsNull  = false;
602         isCurrentOuter = false;
603 
604         while (true) {
605             currentRow = it.next();
606 
607             if (currentRow == null) {
608                 break;
609             }
610 
611             currentData = currentRow.getData();
612 
613             if (!(eEnd == null || eEnd.testCondition(session))) {
614                 break;
615             }
616 
617             if (eAnd == null || eAnd.testCondition(session)) {
618                 result = true;
619 
620                 break;
621             }
622         }
623 
624         if (result) {
625             return true;
626         }
627 
628         currentRow  = null;
629         currentData = emptyData;
630 
631         return false;
632     }
633 
634     boolean nextOuter(Session session) throws HsqlException {
635 
636         nonJoinIsNull  = false;
637         isCurrentOuter = true;
638         currentData    = emptyData;
639         currentRow     = null;
640 
641         return eAnd == null || (eAnd.getFilter() != this && eAnd.isInJoin)
642                || eAnd.testCondition(session);
643     }
644 
645     /**
646      * Forms a new conjunction using the given condition and this filter's
647      * pre-existing AND condition, or sets the given condition as this filter's
648      * AND condition when there is no such pre-exisiting object.
649      *
650      * @param e the condition to add
651      */
652     private void addAndCondition(Expression e) {
653 
654         Expression e2 = new Expression(e);
655 
656         if (eAnd == null) {
657             eAnd = e2;
658         } else {
659             Expression and = new Expression(Expression.AND, eAnd, e2);
660 
661             eAnd = and;
662         }
663 
664         e.setTrue();
665     }
666 
667     /**
668      * Removes reference to Index to avoid possible memory leaks after alter
669      * table or drop index
670      */
671     void setAsCheckFilter() {
672         filterIndex = null;
673     }
674 
675 // boucheb@users 20030415 - added for debugging support
676 
677     /**
678      * Retreives a String representation of this obejct. <p>
679      *
680      * The returned String describes this object's table, alias
681      * access mode, index, join mode, Start, End and And conditions.
682      *
683      * @return a String representation of this object
684      */
685     public String   describe(Session session) {
686 
687         StringBuffer   sb;
688         String         temp;
689         Index        index;
690         Index        primaryIndex;
691         int[]        primaryKey;
692         boolean      hidden;
693         boolean      fullScan;
694 
695         sb           = new StringBuffer  ();
696         index        = filterIndex;
697         primaryIndex = filterTable.getPrimaryIndex();
698         primaryKey   = filterTable.getPrimaryKey();
699         hidden       = false;
700         fullScan     = (eStart == null && eEnd == null);
701 
702         if (index == null) {
703             index = primaryIndex;
704         }
705 
706         if (index == primaryIndex && primaryKey.length == 0) {
707             hidden   = true;
708             fullScan = true;
709         }
710 
711         sb.append(super.toString()).append('\n');
712         sb.append("table=[").append(filterTable.getName().name).append("]\n");
713         sb.append("alias=[").append(tableAlias).append("]\n");
714         sb.append("access=[").append(fullScan ? "FULL SCAN"
715                                               : "INDEX PRED").append("]\n");
716         sb.append("index=[");
717         sb.append(index == null ? "NONE"
718                                 : index.getName() == null ? "UNNAMED"
719                                                           : index.getName()
720                                                           .name);
721         sb.append(hidden ? "[HIDDEN]]\n"
722                          : "]\n");
723         sb.append("isOuterJoin=[").append(isOuterJoin).append("]\n");
724 
725         temp = eStart == null ? "null"
726                               : eStart.describe(session);
727 
728         sb.append("eStart=[").append(temp).append("]\n");
729 
730         temp = eEnd == null ? "null"
731                             : eEnd.describe(session);
732 
733         sb.append("eEnd=[").append(temp).append("]\n");
734 
735         temp = eAnd == null ? "null"
736                             : eAnd.describe(session);
737 
738         sb.append("eAnd=[").append(temp).append("]");
739 
740         return sb.toString();
741     }
742 }
743
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags