View Javadoc

1   /*
2    * Copyright 2009 The Apache Software Foundation
3    *
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  package org.apache.hadoop.hbase.regionserver;
21  
22  import java.util.ArrayList;
23  import java.util.List;
24  import java.util.NavigableSet;
25  
26  import org.apache.hadoop.hbase.HConstants;
27  import org.apache.hadoop.hbase.util.Bytes;
28  
29  /**
30   * This class is used for the tracking and enforcement of columns and numbers
31   * of versions during the course of a Get or Scan operation, when explicit
32   * column qualifiers have been asked for in the query.
33   *
34   * With a little magic (see {@link ScanQueryMatcher}), we can use this matcher
35   * for both scans and gets.  The main difference is 'next' and 'done' collapse
36   * for the scan case (since we see all columns in order), and we only reset
37   * between rows.
38   *
39   * <p>
40   * This class is utilized by {@link ScanQueryMatcher} through two methods:
41   * <ul><li>{@link #checkColumn} is called when a Put satisfies all other
42   * conditions of the query.  This method returns a {@link org.apache.hadoop.hbase.regionserver.ScanQueryMatcher.MatchCode} to define
43   * what action should be taken.
44   * <li>{@link #update} is called at the end of every StoreFile or memstore.
45   * <p>
46   * This class is NOT thread-safe as queries are never multi-threaded
47   */
48  public class ExplicitColumnTracker implements ColumnTracker {
49  
50    private final int maxVersions;
51    private final List<ColumnCount> columns;
52    private final List<ColumnCount> columnsToReuse;
53    private int index;
54    private ColumnCount column;
55    /** Keeps track of the latest timestamp included for current column.
56     * Used to eliminate duplicates. */
57    private long latestTSOfCurrentColumn;
58  
59    /**
60     * Default constructor.
61     * @param columns columns specified user in query
62     * @param maxVersions maximum versions to return per column
63     */
64    public ExplicitColumnTracker(NavigableSet<byte[]> columns, int maxVersions) {
65      this.maxVersions = maxVersions;
66      this.columns = new ArrayList<ColumnCount>(columns.size());
67      this.columnsToReuse = new ArrayList<ColumnCount>(columns.size());
68      for(byte [] column : columns) {
69        this.columnsToReuse.add(new ColumnCount(column,maxVersions));
70      }
71      reset();
72    }
73  
74    /**
75     * Done when there are no more columns to match against.
76     */
77    public boolean done() {
78      return this.columns.size() == 0;
79    }
80  
81    public ColumnCount getColumnHint() {
82      return this.column;
83    }
84  
85    /**
86     * Checks against the parameters of the query and the columns which have
87     * already been processed by this query.
88     * @param bytes KeyValue buffer
89     * @param offset offset to the start of the qualifier
90     * @param length length of the qualifier
91     * @param timestamp timestamp of the key being checked
92     * @return MatchCode telling ScanQueryMatcher what action to take
93     */
94    public ScanQueryMatcher.MatchCode checkColumn(byte [] bytes, int offset,
95        int length, long timestamp) {
96      do {
97        // No more columns left, we are done with this query
98        if(this.columns.size() == 0) {
99          return ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW; // done_row
100       }
101 
102       // No more columns to match against, done with storefile
103       if(this.column == null) {
104         return ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW; // done_row
105       }
106 
107       // Compare specific column to current column
108       int ret = Bytes.compareTo(column.getBuffer(), column.getOffset(),
109           column.getLength(), bytes, offset, length);
110 
111       // Column Matches. If it is not a duplicate key, decrement versions left
112       // and include.
113       if(ret == 0) {
114         //If column matches, check if it is a duplicate timestamp
115         if (sameAsPreviousTS(timestamp)) {
116           //If duplicate, skip this Key
117           return ScanQueryMatcher.MatchCode.SKIP;
118         }
119         if(this.column.decrement() == 0) {
120           // Done with versions for this column
121           this.columns.remove(this.index);
122           resetTS();
123           if(this.columns.size() == this.index) {
124             // Will not hit any more columns in this storefile
125             this.column = null;
126           } else {
127             this.column = this.columns.get(this.index);
128           }
129         } else {
130           setTS(timestamp);
131         }
132         return ScanQueryMatcher.MatchCode.INCLUDE;
133       }
134 
135       resetTS();
136 
137       if (ret > 0) {
138         // Specified column is smaller than the current, skip to next column.
139         return ScanQueryMatcher.MatchCode.SEEK_NEXT_COL;
140       }
141 
142       // Specified column is bigger than current column
143       // Move down current column and check again
144       if(ret <= -1) {
145         if(++this.index >= this.columns.size()) {
146           // No more to match, do not include, done with storefile
147           return ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW; // done_row
148         }
149         // This is the recursive case.
150         this.column = this.columns.get(this.index);
151       }
152     } while(true);
153   }
154 
155   /**
156    * Called at the end of every StoreFile or memstore.
157    */
158   public void update() {
159     if(this.columns.size() != 0) {
160       this.index = 0;
161       this.column = this.columns.get(this.index);
162     } else {
163       this.index = -1;
164       this.column = null;
165     }
166   }
167 
168   // Called between every row.
169   public void reset() {
170     buildColumnList();
171     this.index = 0;
172     this.column = this.columns.get(this.index);
173     resetTS();
174   }
175 
176   private void resetTS() {
177     latestTSOfCurrentColumn = HConstants.LATEST_TIMESTAMP;
178   }
179 
180   private void setTS(long timestamp) {
181     latestTSOfCurrentColumn = timestamp;
182   }
183 
184   private boolean sameAsPreviousTS(long timestamp) {
185     return timestamp == latestTSOfCurrentColumn;
186   }
187 
188   private void buildColumnList() {
189     this.columns.clear();
190     this.columns.addAll(this.columnsToReuse);
191     for(ColumnCount col : this.columns) {
192       col.setCount(this.maxVersions);
193     }
194   }
195 
196   /**
197    * This method is used to inform the column tracker that we are done with
198    * this column. We may get this information from external filters or
199    * timestamp range and we then need to indicate this information to
200    * tracker. It is required only in case of ExplicitColumnTracker.
201    * @param bytes
202    * @param offset
203    * @param length
204    */
205   public void doneWithColumn(byte [] bytes, int offset, int length) {
206     while (this.column != null) {
207       int compare = Bytes.compareTo(column.getBuffer(), column.getOffset(),
208           column.getLength(), bytes, offset, length);
209       resetTS();
210       if (compare == 0) {
211         this.columns.remove(this.index);
212         if (this.columns.size() == this.index) {
213           // Will not hit any more columns in this storefile
214           this.column = null;
215         } else {
216           this.column = this.columns.get(this.index);
217         }
218         return;
219       } else if ( compare <= -1) {
220         if(++this.index != this.columns.size()) {
221           this.column = this.columns.get(this.index);
222         } else {
223           this.column = null;
224         }
225       } else {
226         return;
227       }
228     }
229   }
230 
231 }