View Javadoc

1   /**
2    *
3    * Licensed to the Apache Software Foundation (ASF) under one
4    * or more contributor license agreements.  See the NOTICE file
5    * distributed with this work for additional information
6    * regarding copyright ownership.  The ASF licenses this file
7    * to you under the Apache License, Version 2.0 (the
8    * "License"); you may not use this file except in compliance
9    * with the License.  You may obtain a copy of the License at
10   *
11   *     http://www.apache.org/licenses/LICENSE-2.0
12   *
13   * Unless required by applicable law or agreed to in writing, software
14   * distributed under the License is distributed on an "AS IS" BASIS,
15   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16   * See the License for the specific language governing permissions and
17   * limitations under the License.
18   */
19  package org.apache.hadoop.hbase.filter;
20  
21  import java.io.IOException;
22  import java.util.ArrayList;
23  import java.util.Arrays;
24  import java.util.List;
25  
26  import org.apache.hadoop.hbase.Cell;
27  import org.apache.hadoop.hbase.CellComparator;
28  import org.apache.hadoop.hbase.CellUtil;
29  import org.apache.hadoop.hbase.classification.InterfaceAudience;
30  import org.apache.hadoop.hbase.classification.InterfaceStability;
31  import org.apache.hadoop.hbase.exceptions.DeserializationException;
32  import org.apache.hadoop.hbase.protobuf.ProtobufUtil;
33  import org.apache.hadoop.hbase.protobuf.generated.FilterProtos;
34  
35  import com.google.protobuf.InvalidProtocolBufferException;
36  
37  /**
38   * Implementation of {@link Filter} that represents an ordered List of Filters
39   * which will be evaluated with a specified boolean operator {@link Operator#MUST_PASS_ALL}
40   * (<code>AND</code>) or {@link Operator#MUST_PASS_ONE} (<code>OR</code>).
41   * Since you can use Filter Lists as children of Filter Lists, you can create a
42   * hierarchy of filters to be evaluated.
43   *
44   * <br>
45   * {@link Operator#MUST_PASS_ALL} evaluates lazily: evaluation stops as soon as one filter does
46   * not include the KeyValue.
47   *
48   * <br>
49   * {@link Operator#MUST_PASS_ONE} evaluates non-lazily: all filters are always evaluated.
50   *
51   * <br>
52   * Defaults to {@link Operator#MUST_PASS_ALL}.
53   */
54  @InterfaceAudience.Public
55  @InterfaceStability.Stable
56  final public class FilterList extends Filter {
57    /** set operator */
58    @InterfaceAudience.Public
59    @InterfaceStability.Stable
60    public static enum Operator {
61      /** !AND */
62      MUST_PASS_ALL,
63      /** !OR */
64      MUST_PASS_ONE
65    }
66  
67    private static final int MAX_LOG_FILTERS = 5;
68    private Operator operator = Operator.MUST_PASS_ALL;
69    private List<Filter> filters = new ArrayList<Filter>();
70    private Filter seekHintFilter = null;
71  
72    /** Reference Cell used by {@link #transformCell(Cell)} for validation purpose. */
73    private Cell referenceCell = null;
74  
75    /**
76     * When filtering a given Cell in {@link #filterKeyValue(Cell)},
77     * this stores the transformed Cell to be returned by {@link #transformCell(Cell)}.
78     *
79     * Individual filters transformation are applied only when the filter includes the Cell.
80     * Transformations are composed in the order specified by {@link #filters}.
81     */
82    private Cell transformedCell = null;
83  
84    /**
85     * Constructor that takes a set of {@link Filter}s. The default operator
86     * MUST_PASS_ALL is assumed.
87     *
88     * @param rowFilters list of filters
89     */
90    public FilterList(final List<Filter> rowFilters) {
91      if (rowFilters instanceof ArrayList) {
92        this.filters = rowFilters;
93      } else {
94        this.filters = new ArrayList<Filter>(rowFilters);
95      }
96    }
97  
98    /**
99     * Constructor that takes a var arg number of {@link Filter}s. The fefault operator
100    * MUST_PASS_ALL is assumed.
101    * @param rowFilters
102    */
103   public FilterList(final Filter... rowFilters) {
104     this.filters = new ArrayList<Filter>(Arrays.asList(rowFilters));
105   }
106 
107   /**
108    * Constructor that takes an operator.
109    *
110    * @param operator Operator to process filter set with.
111    */
112   public FilterList(final Operator operator) {
113     this.operator = operator;
114   }
115 
116   /**
117    * Constructor that takes a set of {@link Filter}s and an operator.
118    *
119    * @param operator Operator to process filter set with.
120    * @param rowFilters Set of row filters.
121    */
122   public FilterList(final Operator operator, final List<Filter> rowFilters) {
123     this.filters = new ArrayList<Filter>(rowFilters);
124     this.operator = operator;
125   }
126 
127   /**
128    * Constructor that takes a var arg number of {@link Filter}s and an operator.
129    *
130    * @param operator Operator to process filter set with.
131    * @param rowFilters Filters to use
132    */
133   public FilterList(final Operator operator, final Filter... rowFilters) {
134     this.filters = new ArrayList<Filter>(Arrays.asList(rowFilters));
135     this.operator = operator;
136   }
137 
138   /**
139    * Get the operator.
140    *
141    * @return operator
142    */
143   public Operator getOperator() {
144     return operator;
145   }
146 
147   /**
148    * Get the filters.
149    *
150    * @return filters
151    */
152   public List<Filter> getFilters() {
153     return filters;
154   }
155 
156   /**
157    * Add a filter.
158    *
159    * @param filter another filter
160    */
161   public void addFilter(Filter filter) {
162     if (this.isReversed() != filter.isReversed()) {
163       throw new IllegalArgumentException(
164           "Filters in the list must have the same reversed flag, this.reversed="
165               + this.isReversed());
166     }
167     this.filters.add(filter);
168   }
169 
170   @Override
171   public void reset() throws IOException {
172     int listize = filters.size();
173     for (int i = 0; i < listize; i++) {
174       filters.get(i).reset();
175     }
176     seekHintFilter = null;
177   }
178 
179   @Override
180   public boolean filterRowKey(byte[] rowKey, int offset, int length) throws IOException {
181     boolean flag = (this.operator == Operator.MUST_PASS_ONE) ? true : false;
182     int listize = filters.size();
183     for (int i = 0; i < listize; i++) {
184       Filter filter = filters.get(i);
185       if (this.operator == Operator.MUST_PASS_ALL) {
186         if (filter.filterAllRemaining() ||
187             filter.filterRowKey(rowKey, offset, length)) {
188           flag =  true;
189         }
190       } else if (this.operator == Operator.MUST_PASS_ONE) {
191         if (!filter.filterAllRemaining() &&
192             !filter.filterRowKey(rowKey, offset, length)) {
193           flag =  false;
194         }
195       }
196     }
197     return flag;
198   }
199 
200   @Override
201   public boolean filterRowKey(Cell firstRowCell) throws IOException {
202     boolean flag = (this.operator == Operator.MUST_PASS_ONE) ? true : false;
203     int listize = filters.size();
204     for (int i = 0; i < listize; i++) {
205       Filter filter = filters.get(i);
206       if (this.operator == Operator.MUST_PASS_ALL) {
207         if (filter.filterAllRemaining() || filter.filterRowKey(firstRowCell)) {
208           flag = true;
209         }
210       } else if (this.operator == Operator.MUST_PASS_ONE) {
211         if (!filter.filterAllRemaining() && !filter.filterRowKey(firstRowCell)) {
212           flag = false;
213         }
214       }
215     }
216     return flag;
217   }
218 
219   @Override
220   public boolean filterAllRemaining() throws IOException {
221     int listize = filters.size();
222     for (int i = 0; i < listize; i++) {
223       if (filters.get(i).filterAllRemaining()) {
224         if (operator == Operator.MUST_PASS_ALL) {
225           return true;
226         }
227       } else {
228         if (operator == Operator.MUST_PASS_ONE) {
229           return false;
230         }
231       }
232     }
233     return operator == Operator.MUST_PASS_ONE;
234   }
235 
236   @Override
237   public Cell transformCell(Cell c) throws IOException {
238     if (!CellUtil.equals(c, referenceCell)) {
239       throw new IllegalStateException("Reference Cell: " + this.referenceCell + " does not match: "
240           + c);
241     }
242     return this.transformedCell;
243   }
244 
245   @Override
246   @edu.umd.cs.findbugs.annotations.SuppressWarnings(value="SF_SWITCH_FALLTHROUGH",
247     justification="Intentional")
248   public ReturnCode filterKeyValue(Cell c) throws IOException {
249     this.referenceCell = c;
250 
251     // Accumulates successive transformation of every filter that includes the Cell:
252     Cell transformed = c;
253 
254     ReturnCode rc = operator == Operator.MUST_PASS_ONE?
255         ReturnCode.SKIP: ReturnCode.INCLUDE;
256     int listize = filters.size();
257     /*
258      * When all filters in a MUST_PASS_ONE FilterList return a SEEK_USING_NEXT_HINT code,
259      * we should return SEEK_NEXT_USING_HINT from the FilterList to utilize the lowest seek value.
260      * 
261      * The following variable tracks whether any of the Filters returns ReturnCode other than
262      * SEEK_NEXT_USING_HINT for MUST_PASS_ONE FilterList, in which case the optimization would
263      * be skipped.
264      */
265     boolean seenNonHintReturnCode = false;
266     for (int i = 0; i < listize; i++) {
267       Filter filter = filters.get(i);
268       if (operator == Operator.MUST_PASS_ALL) {
269         if (filter.filterAllRemaining()) {
270           return ReturnCode.NEXT_ROW;
271         }
272         ReturnCode code = filter.filterKeyValue(c);
273         switch (code) {
274         // Override INCLUDE and continue to evaluate.
275         case INCLUDE_AND_NEXT_COL:
276           rc = ReturnCode.INCLUDE_AND_NEXT_COL; // FindBugs SF_SWITCH_FALLTHROUGH
277         case INCLUDE:
278           transformed = filter.transformCell(transformed);
279           continue;
280         case SEEK_NEXT_USING_HINT:
281           seekHintFilter = filter;
282           return code;
283         default:
284           return code;
285         }
286       } else if (operator == Operator.MUST_PASS_ONE) {
287         if (filter.filterAllRemaining()) {
288           continue;
289         }
290 
291         ReturnCode localRC = filter.filterKeyValue(c);
292         if (localRC != ReturnCode.SEEK_NEXT_USING_HINT) {
293           seenNonHintReturnCode = true;
294         }
295         switch (localRC) {
296         case INCLUDE:
297           if (rc != ReturnCode.INCLUDE_AND_NEXT_COL) {
298             rc = ReturnCode.INCLUDE;
299           }
300           transformed = filter.transformCell(transformed);
301           break;
302         case INCLUDE_AND_NEXT_COL:
303           rc = ReturnCode.INCLUDE_AND_NEXT_COL;
304           transformed = filter.transformCell(transformed);
305           // must continue here to evaluate all filters
306           break;
307         case NEXT_ROW:
308           break;
309         case SKIP:
310           break;
311         case NEXT_COL:
312           break;
313         case SEEK_NEXT_USING_HINT:
314           break;
315         default:
316           throw new IllegalStateException("Received code is not valid.");
317         }
318       }
319     }
320 
321     // Save the transformed Cell for transform():
322     this.transformedCell = transformed;
323 
324     /*
325      * The seenNonHintReturnCode flag is intended only for Operator.MUST_PASS_ONE branch.
326      * If we have seen non SEEK_NEXT_USING_HINT ReturnCode, respect that ReturnCode.
327      */
328     if (operator == Operator.MUST_PASS_ONE && !seenNonHintReturnCode) {
329       return ReturnCode.SEEK_NEXT_USING_HINT;
330     }
331     return rc;
332   }
333 
334   /**
335    * Filters that never filter by modifying the returned List of Cells can
336    * inherit this implementation that does nothing.
337    *
338    * {@inheritDoc}
339    */
340   @Override
341   public void filterRowCells(List<Cell> cells) throws IOException {
342     int listize = filters.size();
343     for (int i = 0; i < listize; i++) {
344       filters.get(i).filterRowCells(cells);
345     }
346   }
347 
348   @Override
349   public boolean hasFilterRow() {
350     int listize = filters.size();
351     for (int i = 0; i < listize; i++) {
352       if (filters.get(i).hasFilterRow()) {
353         return true;
354       }
355     }
356     return false;
357   }
358 
359   @Override
360   public boolean filterRow() throws IOException {
361     int listize = filters.size();
362     for (int i = 0; i < listize; i++) {
363       Filter filter = filters.get(i);
364       if (operator == Operator.MUST_PASS_ALL) {
365         if (filter.filterRow()) {
366           return true;
367         }
368       } else if (operator == Operator.MUST_PASS_ONE) {
369         if (!filter.filterRow()) {
370           return false;
371         }
372       }
373     }
374     return  operator == Operator.MUST_PASS_ONE;
375   }
376 
377   /**
378    * @return The filter serialized using pb
379    */
380   public byte[] toByteArray() throws IOException {
381     FilterProtos.FilterList.Builder builder =
382       FilterProtos.FilterList.newBuilder();
383     builder.setOperator(FilterProtos.FilterList.Operator.valueOf(operator.name()));
384     int listize = filters.size();
385     for (int i = 0; i < listize; i++) {
386       builder.addFilters(ProtobufUtil.toFilter(filters.get(i)));
387     }
388     return builder.build().toByteArray();
389   }
390 
391   /**
392    * @param pbBytes A pb serialized {@link FilterList} instance
393    * @return An instance of {@link FilterList} made from <code>bytes</code>
394    * @throws DeserializationException
395    * @see #toByteArray
396    */
397   public static FilterList parseFrom(final byte [] pbBytes)
398   throws DeserializationException {
399     FilterProtos.FilterList proto;
400     try {
401       proto = FilterProtos.FilterList.parseFrom(pbBytes);
402     } catch (InvalidProtocolBufferException e) {
403       throw new DeserializationException(e);
404     }
405 
406     List<Filter> rowFilters = new ArrayList<Filter>(proto.getFiltersCount());
407     try {
408       List<org.apache.hadoop.hbase.protobuf.generated.FilterProtos.Filter> filtersList =
409           proto.getFiltersList();
410       int listSize = filtersList.size();
411       for (int i = 0; i < listSize; i++) {
412         rowFilters.add(ProtobufUtil.toFilter(filtersList.get(i)));
413       }
414     } catch (IOException ioe) {
415       throw new DeserializationException(ioe);
416     }
417     return new FilterList(Operator.valueOf(proto.getOperator().name()),rowFilters);
418   }
419 
420   /**
421    * @param other
422    * @return true if and only if the fields of the filter that are serialized
423    * are equal to the corresponding fields in other.  Used for testing.
424    */
425   boolean areSerializedFieldsEqual(Filter other) {
426     if (other == this) return true;
427     if (!(other instanceof FilterList)) return false;
428 
429     FilterList o = (FilterList)other;
430     return this.getOperator().equals(o.getOperator()) &&
431       ((this.getFilters() == o.getFilters())
432       || this.getFilters().equals(o.getFilters()));
433   }
434 
435   @Override
436   public Cell getNextCellHint(Cell currentCell) throws IOException {
437     Cell keyHint = null;
438     if (operator == Operator.MUST_PASS_ALL) {
439       keyHint = seekHintFilter.getNextCellHint(currentCell);
440       return keyHint;
441     }
442 
443     // If any condition can pass, we need to keep the min hint
444     int listize = filters.size();
445     for (int i = 0; i < listize; i++) {
446       if (filters.get(i).filterAllRemaining()) {
447         continue;
448       }
449       Cell curKeyHint = filters.get(i).getNextCellHint(currentCell);
450       if (curKeyHint == null) {
451         // If we ever don't have a hint and this is must-pass-one, then no hint
452         return null;
453       }
454       if (curKeyHint != null) {
455         // If this is the first hint we find, set it
456         if (keyHint == null) {
457           keyHint = curKeyHint;
458           continue;
459         }
460         if (CellComparator.COMPARATOR.compare(keyHint, curKeyHint) > 0) {
461           keyHint = curKeyHint;
462         }
463       }
464     }
465     return keyHint;
466   }
467 
468   @Override
469   public boolean isFamilyEssential(byte[] name) throws IOException {
470     int listize = filters.size();
471     for (int i = 0; i < listize; i++) {
472       if (filters.get(i).isFamilyEssential(name)) {
473         return true;
474       }
475     }
476     return false;
477   }
478 
479   @Override
480   public void setReversed(boolean reversed) {
481     int listize = filters.size();
482     for (int i = 0; i < listize; i++) {
483       filters.get(i).setReversed(reversed);
484     }
485     this.reversed = reversed;
486   }
487 
488   @Override
489   public String toString() {
490     return toString(MAX_LOG_FILTERS);
491   }
492 
493   protected String toString(int maxFilters) {
494     int endIndex = this.filters.size() < maxFilters
495         ? this.filters.size() : maxFilters;
496     return String.format("%s %s (%d/%d): %s",
497         this.getClass().getSimpleName(),
498         this.operator == Operator.MUST_PASS_ALL ? "AND" : "OR",
499         endIndex,
500         this.filters.size(),
501         this.filters.subList(0, endIndex).toString());
502   }
503 }