FilterIteratorFactory


1   package prefuse.data.util;
2   
3   import java.util.Comparator  ;
4   import java.util.Iterator  ;
5   
6   import prefuse.data.Table;
7   import prefuse.data.expression.AndPredicate;
8   import prefuse.data.expression.ColumnExpression;
9   import prefuse.data.expression.ComparisonPredicate;
10  import prefuse.data.expression.Expression;
11  import prefuse.data.expression.ExpressionAnalyzer;
12  import prefuse.data.expression.NotPredicate;
13  import prefuse.data.expression.OrPredicate;
14  import prefuse.data.expression.Predicate;
15  import prefuse.data.expression.RangePredicate;
16  import prefuse.data.tuple.TupleSet;
17  import prefuse.util.PrefuseConfig;
18  import prefuse.util.collections.CompositeIntIterator;
19  import prefuse.util.collections.IntIterator;
20  
21  /**
22   * Factory class that creates optimized filter iterators. When possible,
23   * this factory will attempt to create an optimized query plan by using
24   * available indexes, in many incrasing performance by only visiting
25   * the tuples which will pass the filter condition.
26   * 
27   * @author <a HREF="http://jheer.org">jeffrey heer</a>
28   */
29  public class FilterIteratorFactory {
30  
31      private static final int OPTIMIZATION_THRESHOLD
32          = PrefuseConfig.getInt("data.filter.optimizeThreshold");
33      
34      // we can stash our query plan generation and optimization here to deal 
35      // with it all in one spot, and keep the rest of the classes clean
36      
37      /**
38       * Get a filtered iterator over the tuples in the given set,
39       * filtered by the given predicate.
40       * @param ts the TupleSet to iterate over
41       * @param p the filter predicate
42       * @return a filtered iterator over the tuples
43       */
44      public static Iterator   tuples(TupleSet ts, Predicate p) {
45          // no predicate means no filtering
46          if ( p == null )
47              return ts.tuples();
48          
49          // attempt to generate an optimized query plan
50          Iterator   iter = null;
51          if ( ts instanceof Table ) {
52              Table t = (Table)ts;
53              IntIterator ii = getOptimizedIterator(t,p);
54              if ( ii != null )
55                  iter = t.tuples(ii);
56          }
57          
58          // optimization fails, scan the entire table
59          if ( iter == null ) {
60              iter = new FilterIterator(ts.tuples(), p);
61          }
62          
63          return iter;
64      }
65      
66      /**
67       * Get a filtered iterator over the rows in the given table,
68       * filtered by the given predicate.
69       * @param t the Table to iterate over
70       * @param p the filter predicate
71       * @return a filtered iterator over the table rows
72       */
73      public static IntIterator rows(Table t, Predicate p) {
74          // attempt to generate an optimized query plan
75          IntIterator iter = null;
76          iter = getOptimizedIterator(t, p);
77          
78          // optimization fails, scan the entire table
79          if ( iter == null ) {
80              iter = new FilterRowIterator(t.rows(), t, p);
81          }
82          return iter;
83      }
84      
85      /**
86       * Get an optimized iterator over the rows of a table, if possible.
87       * @param t the Table to iterator over
88       * @param p the filter predicate
89       * @return an optimized iterator, or null if no optimization was found
90       */
91      protected static IntIterator getOptimizedIterator(Table t, Predicate p) {
92          if ( t.getRowCount() < OPTIMIZATION_THRESHOLD ) 
93              return null; // avoid overhead for small tables
94          
95          if ( p instanceof ColumnExpression ) {
96              // try to optimize a boolean column
97              return getColumnIterator(t,
98                      ((ColumnExpression)p).getColumnName(), true);
99          }
100         else if ( p instanceof NotPredicate )
101         {
102             // try to optimize the negation a boolean column
103             Predicate pp = ((NotPredicate)p).getPredicate();
104             if ( pp instanceof ColumnExpression ) {
105                 return getColumnIterator(t,
106                         ((ColumnExpression)pp).getColumnName(), false);
107             }
108         }
109         else if ( p instanceof AndPredicate )
110         {
111             // try to optimize an and clause
112             return getAndIterator(t, (AndPredicate)p);
113         }
114         else if ( p instanceof OrPredicate )
115         {
116             // try to optimize an or clause
117             return getOrIterator(t, (OrPredicate)p);
118         }
119         else if ( p instanceof ComparisonPredicate )
120         {
121             // try to optimize a comparison (=, !=, <, > ,etc)
122             return getComparisonIterator(t,(ComparisonPredicate)p);
123         }
124         else if ( p instanceof RangePredicate )
125         {
126             // try to optimize a bounded range of values
127             return getRangeIterator(t, (RangePredicate)p); 
128         }
129         
130         return null;
131     }
132     
133     protected static IntIterator getColumnIterator(
134             Table t, String   field, boolean val)
135     {
136         if ( t.getColumnType(field) != boolean.class )
137             return null; // only works for boolean-valued columns
138         
139         Index index = t.getIndex(field);
140         if ( index == null ) {
141             return null;
142         } else {
143             return index.rows(val);
144         }
145     }
146     
147     protected static IntIterator getOrIterator(Table t, OrPredicate op) {
148         int size = op.size();
149         if ( size > 1 ) {
150             // if all subclauses can be optimized, we can optimize the query
151             IntIterator[] rows = new IntIterator[size];
152             for ( int i=0; i<rows.length; ++i ) {
153                 rows[i] = getOptimizedIterator(t, op.get(i));
154                 
155                 // all clauses must be optimized to avoid linear scan
156                 if ( rows[i] == null ) return null;
157             }
158             // group iterators, and filter for uniqueness
159             return new UniqueRowIterator(new CompositeIntIterator(rows));
160         } else if ( size == 1 ) {
161             // only one clause, optimize for that
162             return getOptimizedIterator(t, op.get(0));
163         } else {
164             // no woman, no cry
165             return null;
166         }
167     }
168     
169     protected static IntIterator getAndIterator(Table t, AndPredicate ap) {
170         // possible TODO: add scoring to select best optimized iterator
171         // for now just work from the end backwards and take the first
172         // optimized iterator we find
173         IntIterator rows = null;
174         Predicate clause = null;
175         for ( int i=ap.size(); --i >= 0; ) {
176             clause = ap.get(i);
177             if ( (rows=getOptimizedIterator(t,clause)) != null )
178                 break;
179         }
180         
181         // exit if we didn't optimize
182         if ( rows == null ) return null;
183         
184         // if only one clause, no extras needed
185         if ( ap.size() == 1 ) return rows;
186         
187         // otherwise get optimized source, run through other clauses
188         return new FilterRowIterator(rows, t, ap.getSubPredicate(clause));
189     }
190     
191     protected static IntIterator getComparisonIterator(Table t, 
192                                            ComparisonPredicate cp)
193     {
194         Expression l = cp.getLeftExpression();
195         Expression r = cp.getRightExpression();
196         int operation = cp.getOperation();
197         
198         // not equals operations aren't handled by the index
199         if ( operation == ComparisonPredicate.NEQ )
200             return null;
201         
202         ColumnExpression col;
203         Expression lit;
204         
205         // make sure columns are of the right type
206         if (l instanceof ColumnExpression && 
207                 !ExpressionAnalyzer.hasDependency(r))
208         {
209             col = (ColumnExpression)l;
210             lit = r;
211         } else if (r instanceof ColumnExpression &&
212                 !ExpressionAnalyzer.hasDependency(l))
213         {
214             col = (ColumnExpression)r;
215             lit = l;
216         } else {
217             return null;
218         }
219         
220         // if table has index of the right type, use it
221         Comparator   cmp = cp.getComparator();
222         Index index = t.getIndex(col.getColumnName());
223         
224         if ( index == null || !cmp.equals(index.getComparator()) )
225             return null;
226         
227         Class   ltype = lit.getClass();
228         if ( ltype == int.class ) {
229             int val = lit.getInt(null); // literal value, so null is safe
230             switch ( operation ) {
231             case ComparisonPredicate.LT:
232                 return index.rows(Integer.MIN_VALUE, val, Index.TYPE_AIE);
233             case ComparisonPredicate.GT:
234                 return index.rows(val, Integer.MAX_VALUE, Index.TYPE_AEI);
235             case ComparisonPredicate.EQ:
236                 return index.rows(val, val, Index.TYPE_AII);
237             case ComparisonPredicate.LTEQ:
238                 return index.rows(Integer.MIN_VALUE, val, Index.TYPE_AII);
239             case ComparisonPredicate.GTEQ:
240                 return index.rows(val, Integer.MAX_VALUE, Index.TYPE_AII);
241             default:
242                 throw new IllegalStateException  (); // should never occur
243             }
244         } else if ( ltype == long.class ) {
245             long val = lit.getLong(null); // literal value, so null is safe
246             switch ( operation ) {
247             case ComparisonPredicate.LT:
248                 return index.rows(Long.MIN_VALUE, val, Index.TYPE_AIE);
249             case ComparisonPredicate.GT:
250                 return index.rows(val, Long.MAX_VALUE, Index.TYPE_AEI);
251             case ComparisonPredicate.EQ:
252                 return index.rows(val, val, Index.TYPE_AII);
253             case ComparisonPredicate.LTEQ:
254                 return index.rows(Long.MIN_VALUE, val, Index.TYPE_AII);
255             case ComparisonPredicate.GTEQ:
256                 return index.rows(val, Long.MAX_VALUE, Index.TYPE_AII);
257             default:
258                 throw new IllegalStateException  (); // should never occur
259             }
260         } else if ( ltype == float.class ) {
261             float val = lit.getFloat(null); // literal value, so null is safe
262             switch ( operation ) {
263             case ComparisonPredicate.LT:
264                 return index.rows(Float.MIN_VALUE, val, Index.TYPE_AIE);
265             case ComparisonPredicate.GT:
266                 return index.rows(val, Float.MAX_VALUE, Index.TYPE_AEI);
267             case ComparisonPredicate.EQ:
268                 return index.rows(val, val, Index.TYPE_AII);
269             case ComparisonPredicate.LTEQ:
270                 return index.rows(Float.MIN_VALUE, val, Index.TYPE_AII);
271             case ComparisonPredicate.GTEQ:
272                 return index.rows(val, Float.MAX_VALUE, Index.TYPE_AII);
273             default:
274                 throw new IllegalStateException  (); // should never occur
275             }
276         } else if ( ltype == double.class ) {
277             double val = lit.getDouble(null); // literal value, so null is safe
278             switch ( operation ) {
279             case ComparisonPredicate.LT:
280                 return index.rows(Double.MIN_VALUE, val, Index.TYPE_AIE);
281             case ComparisonPredicate.GT:
282                 return index.rows(val, Double.MAX_VALUE, Index.TYPE_AEI);
283             case ComparisonPredicate.EQ:
284                 return index.rows(val, val, Index.TYPE_AII);
285             case ComparisonPredicate.LTEQ:
286                 return index.rows(Double.MIN_VALUE, val, Index.TYPE_AII);
287             case ComparisonPredicate.GTEQ:
288                 return index.rows(val, Double.MAX_VALUE, Index.TYPE_AII);
289             default:
290                 throw new IllegalStateException  (); // should never occur
291             }
292         } else {
293             Object   val = lit.get(null); // literal value, so null is safe
294             switch ( operation ) {
295             case ComparisonPredicate.LT:
296                 return index.rows(null, val, Index.TYPE_AIE);
297             case ComparisonPredicate.GT:
298                 return index.rows(val, null, Index.TYPE_AEI);
299             case ComparisonPredicate.EQ:
300                 return index.rows(val, val, Index.TYPE_AII);
301             case ComparisonPredicate.LTEQ:
302                 return index.rows(null, val, Index.TYPE_AII);
303             case ComparisonPredicate.GTEQ:
304                 return index.rows(val, null, Index.TYPE_AII);
305             default:
306                 throw new IllegalStateException  (); // should never occur
307             }
308         }        
309     }
310     
311     protected static IntIterator getRangeIterator(Table t, RangePredicate rp) {
312         ColumnExpression col;
313         Expression l, r;
314         
315         // make sure columns are of the right type
316         if ( !(rp.getMiddleExpression() instanceof ColumnExpression) ||
317                 ExpressionAnalyzer.hasDependency(rp.getLeftExpression()) ||
318                 ExpressionAnalyzer.hasDependency(rp.getRightExpression()) )
319         {
320             return null;
321         }
322         
323         // assign variables
324         col = (ColumnExpression)rp.getMiddleExpression();
325         l = rp.getLeftExpression();
326         r = rp.getRightExpression();
327         
328         // if table has index of the right type, use it
329         Comparator   cmp = rp.getComparator();
330         Index index = t.getIndex(col.getColumnName());
331         
332         if ( index == null || !cmp.equals(index.getComparator()) )
333             return null;
334         
335         int operation = rp.getOperation();
336         Class   ltype = t.getColumnType(col.getColumnName());
337         
338         // TODO safety check literal types
339         
340         // get the index type
341         int indexType;
342         switch ( operation ) {
343         case RangePredicate.IN_IN:
344             indexType = Index.TYPE_AII;
345             break;
346         case RangePredicate.IN_EX:
347             indexType = Index.TYPE_AIE;
348             break;
349         case RangePredicate.EX_IN:
350             indexType = Index.TYPE_AEI;
351             break;
352         case RangePredicate.EX_EX:
353             indexType = Index.TYPE_AEE;
354             break;
355         default:
356             throw new IllegalStateException  (); // should never occur
357         }
358         
359         // get the indexed rows
360         if ( ltype == int.class ) {
361             return index.rows(l.getInt(null), r.getInt(null), indexType);
362         } else if ( ltype == long.class ) {
363             return index.rows(l.getLong(null), r.getLong(null), indexType);
364         } else if ( ltype == float.class ) {
365             return index.rows(l.getFloat(null), r.getFloat(null), indexType);
366         } else if ( ltype == double.class ) {
367             return index.rows(l.getDouble(null), r.getDouble(null), indexType);
368         } else {
369             return index.rows(l.get(null), r.get(null), indexType);
370         }
371     }
372     
373 } // end of class FilterIteratorFactory
374
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags