1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.hadoop.hbase.filter;
19
20 import org.apache.hadoop.hbase.util.ByteStringer;
21 import com.google.protobuf.InvalidProtocolBufferException;
22
23 import org.apache.hadoop.classification.InterfaceAudience;
24 import org.apache.hadoop.classification.InterfaceStability;
25 import org.apache.hadoop.hbase.Cell;
26 import org.apache.hadoop.hbase.KeyValue;
27 import org.apache.hadoop.hbase.KeyValueUtil;
28 import org.apache.hadoop.hbase.exceptions.DeserializationException;
29 import org.apache.hadoop.hbase.protobuf.generated.FilterProtos;
30 import org.apache.hadoop.hbase.protobuf.generated.HBaseProtos.BytesBytesPair;
31 import org.apache.hadoop.hbase.util.Bytes;
32 import org.apache.hadoop.hbase.util.Pair;
33
34 import java.util.ArrayList;
35 import java.util.Arrays;
36 import java.util.List;
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 @InterfaceAudience.Public
67 @InterfaceStability.Evolving
68 public class FuzzyRowFilter extends FilterBase {
69 private List<Pair<byte[], byte[]>> fuzzyKeysData;
70 private boolean done = false;
71
72 public FuzzyRowFilter(List<Pair<byte[], byte[]>> fuzzyKeysData) {
73 this.fuzzyKeysData = fuzzyKeysData;
74 }
75
76
77 @Override
78 public ReturnCode filterKeyValue(Cell kv) {
79
80 KeyValue v = KeyValueUtil.ensureKeyValue(kv);
81
82 byte[] rowKey = v.getRow();
83
84 SatisfiesCode bestOption = SatisfiesCode.NO_NEXT;
85 for (Pair<byte[], byte[]> fuzzyData : fuzzyKeysData) {
86 SatisfiesCode satisfiesCode =
87 satisfies(rowKey, fuzzyData.getFirst(), fuzzyData.getSecond());
88 if (satisfiesCode == SatisfiesCode.YES) {
89 return ReturnCode.INCLUDE;
90 }
91
92 if (satisfiesCode == SatisfiesCode.NEXT_EXISTS) {
93 bestOption = SatisfiesCode.NEXT_EXISTS;
94 }
95 }
96
97 if (bestOption == SatisfiesCode.NEXT_EXISTS) {
98 return ReturnCode.SEEK_NEXT_USING_HINT;
99 }
100
101
102 done = true;
103 return ReturnCode.NEXT_ROW;
104 }
105
106 @Override
107 public Cell getNextCellHint(Cell currentKV) {
108
109 KeyValue v = KeyValueUtil.ensureKeyValue(currentKV);
110
111 byte[] rowKey = v.getRow();
112 byte[] nextRowKey = null;
113
114 for (Pair<byte[], byte[]> fuzzyData : fuzzyKeysData) {
115 byte[] nextRowKeyCandidate = getNextForFuzzyRule(rowKey,
116 fuzzyData.getFirst(), fuzzyData.getSecond());
117 if (nextRowKeyCandidate == null) {
118 continue;
119 }
120 if (nextRowKey == null || Bytes.compareTo(nextRowKeyCandidate, nextRowKey) < 0) {
121 nextRowKey = nextRowKeyCandidate;
122 }
123 }
124
125 if (nextRowKey == null) {
126
127
128 throw new IllegalStateException("No next row key that satisfies fuzzy exists when" +
129 " getNextKeyHint() is invoked." +
130 " Filter: " + this.toString() +
131 " currentKV: " + currentKV.toString());
132 }
133
134 return KeyValue.createFirstOnRow(nextRowKey);
135 }
136
137 @Override
138 public boolean filterAllRemaining() {
139 return done;
140 }
141
142
143
144
145 public byte [] toByteArray() {
146 FilterProtos.FuzzyRowFilter.Builder builder =
147 FilterProtos.FuzzyRowFilter.newBuilder();
148 for (Pair<byte[], byte[]> fuzzyData : fuzzyKeysData) {
149 BytesBytesPair.Builder bbpBuilder = BytesBytesPair.newBuilder();
150 bbpBuilder.setFirst(ByteStringer.wrap(fuzzyData.getFirst()));
151 bbpBuilder.setSecond(ByteStringer.wrap(fuzzyData.getSecond()));
152 builder.addFuzzyKeysData(bbpBuilder);
153 }
154 return builder.build().toByteArray();
155 }
156
157
158
159
160
161
162
163 public static FuzzyRowFilter parseFrom(final byte [] pbBytes)
164 throws DeserializationException {
165 FilterProtos.FuzzyRowFilter proto;
166 try {
167 proto = FilterProtos.FuzzyRowFilter.parseFrom(pbBytes);
168 } catch (InvalidProtocolBufferException e) {
169 throw new DeserializationException(e);
170 }
171 int count = proto.getFuzzyKeysDataCount();
172 ArrayList<Pair<byte[], byte[]>> fuzzyKeysData= new ArrayList<Pair<byte[], byte[]>>(count);
173 for (int i = 0; i < count; ++i) {
174 BytesBytesPair current = proto.getFuzzyKeysData(i);
175 byte[] keyBytes = current.getFirst().toByteArray();
176 byte[] keyMeta = current.getSecond().toByteArray();
177 fuzzyKeysData.add(new Pair<byte[], byte[]>(keyBytes, keyMeta));
178 }
179 return new FuzzyRowFilter(fuzzyKeysData);
180 }
181
182 @Override
183 public String toString() {
184 final StringBuilder sb = new StringBuilder();
185 sb.append("FuzzyRowFilter");
186 sb.append("{fuzzyKeysData=");
187 for (Pair<byte[], byte[]> fuzzyData : fuzzyKeysData) {
188 sb.append('{').append(Bytes.toStringBinary(fuzzyData.getFirst())).append(":");
189 sb.append(Bytes.toStringBinary(fuzzyData.getSecond())).append('}');
190 }
191 sb.append("}, ");
192 return sb.toString();
193 }
194
195
196
197 static enum SatisfiesCode {
198
199 YES,
200
201 NEXT_EXISTS,
202
203 NO_NEXT
204 }
205
206 static SatisfiesCode satisfies(byte[] row,
207 byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) {
208 return satisfies(row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta);
209 }
210
211 private static SatisfiesCode satisfies(byte[] row, int offset, int length,
212 byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) {
213 if (row == null) {
214
215 return SatisfiesCode.YES;
216 }
217
218 boolean nextRowKeyCandidateExists = false;
219
220 for (int i = 0; i < fuzzyKeyMeta.length && i < length; i++) {
221
222 boolean byteAtPositionFixed = fuzzyKeyMeta[i] == 0;
223 boolean fixedByteIncorrect = byteAtPositionFixed && fuzzyKeyBytes[i] != row[i + offset];
224 if (fixedByteIncorrect) {
225
226 if (nextRowKeyCandidateExists) {
227 return SatisfiesCode.NEXT_EXISTS;
228 }
229
230
231
232
233 boolean rowByteLessThanFixed = (row[i + offset] & 0xFF) < (fuzzyKeyBytes[i] & 0xFF);
234 return rowByteLessThanFixed ? SatisfiesCode.NEXT_EXISTS : SatisfiesCode.NO_NEXT;
235 }
236
237
238
239
240
241
242
243 if (fuzzyKeyMeta[i] == 1 && !isMax(fuzzyKeyBytes[i])) {
244 nextRowKeyCandidateExists = true;
245 }
246 }
247
248 return SatisfiesCode.YES;
249 }
250
251 private static boolean isMax(byte fuzzyKeyByte) {
252 return (fuzzyKeyByte & 0xFF) == 255;
253 }
254
255 static byte[] getNextForFuzzyRule(byte[] row, byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) {
256 return getNextForFuzzyRule(row, 0, row.length, fuzzyKeyBytes, fuzzyKeyMeta);
257 }
258
259
260
261
262
263 private static byte[] getNextForFuzzyRule(byte[] row, int offset, int length,
264 byte[] fuzzyKeyBytes, byte[] fuzzyKeyMeta) {
265
266
267
268
269
270
271
272
273 byte[] result = Arrays.copyOf(fuzzyKeyBytes,
274 length > fuzzyKeyBytes.length ? length : fuzzyKeyBytes.length);
275 int toInc = -1;
276
277 boolean increased = false;
278 for (int i = 0; i < result.length; i++) {
279 if (i >= fuzzyKeyMeta.length || fuzzyKeyMeta[i] == 1) {
280 result[i] = row[offset + i];
281 if (!isMax(row[i])) {
282
283 toInc = i;
284 }
285 } else if (i < fuzzyKeyMeta.length && fuzzyKeyMeta[i] == 0) {
286 if ((row[i + offset] & 0xFF) < (fuzzyKeyBytes[i] & 0xFF)) {
287
288
289 increased = true;
290 break;
291 }
292 if ((row[i + offset] & 0xFF) > (fuzzyKeyBytes[i] & 0xFF)) {
293
294
295
296 break;
297 }
298 }
299 }
300
301 if (!increased) {
302 if (toInc < 0) {
303 return null;
304 }
305 result[toInc]++;
306
307
308
309 for (int i = toInc + 1; i < result.length; i++) {
310 if (i >= fuzzyKeyMeta.length || fuzzyKeyMeta[i] == 1) {
311 result[i] = 0;
312 }
313 }
314 }
315
316 return result;
317 }
318
319
320
321
322
323
324 boolean areSerializedFieldsEqual(Filter o) {
325 if (o == this) return true;
326 if (!(o instanceof FuzzyRowFilter)) return false;
327
328 FuzzyRowFilter other = (FuzzyRowFilter)o;
329 if (this.fuzzyKeysData.size() != other.fuzzyKeysData.size()) return false;
330 for (int i = 0; i < fuzzyKeysData.size(); ++i) {
331 Pair<byte[], byte[]> thisData = this.fuzzyKeysData.get(i);
332 Pair<byte[], byte[]> otherData = other.fuzzyKeysData.get(i);
333 if (!(Bytes.equals(thisData.getFirst(), otherData.getFirst())
334 && Bytes.equals(thisData.getSecond(), otherData.getSecond()))) {
335 return false;
336 }
337 }
338 return true;
339 }
340
341 }