001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase;
019
020import java.util.Comparator;
021
022import org.apache.hadoop.hbase.KeyValue.Type;
023import org.apache.hadoop.hbase.util.ByteBufferUtils;
024import org.apache.hadoop.hbase.util.Bytes;
025import org.apache.yetus.audience.InterfaceAudience;
026import org.apache.yetus.audience.InterfaceStability;
027import org.slf4j.Logger;
028import org.slf4j.LoggerFactory;
029
030import org.apache.hbase.thirdparty.com.google.common.primitives.Longs;
031
032/**
033 * Compare two HBase cells.  Do not use this method comparing <code>-ROOT-</code> or
034 * <code>hbase:meta</code> cells.  Cells from these tables need a specialized comparator, one that
035 * takes account of the special formatting of the row where we have commas to delimit table from
036 * regionname, from row.  See KeyValue for how it has a special comparator to do hbase:meta cells
037 * and yet another for -ROOT-.
038 * <p>While using this comparator for {{@link #compareRows(Cell, Cell)} et al, the hbase:meta cells
039 * format should be taken into consideration, for which the instance of this comparator
040 * should be used.  In all other cases the static APIs in this comparator would be enough
041 * <p>HOT methods. We spend a good portion of CPU comparing. Anything that makes the compare
042 * faster will likely manifest at the macro level. See also
043 * {@link BBKVComparator}. Use it when mostly {@link ByteBufferKeyValue}s.
044 * </p>
045 */
046@edu.umd.cs.findbugs.annotations.SuppressWarnings(
047    value="UNKNOWN",
048    justification="Findbugs doesn't like the way we are negating the result of a compare in below")
049@InterfaceAudience.Private
050@InterfaceStability.Evolving
051public class CellComparatorImpl implements CellComparator {
052  static final Logger LOG = LoggerFactory.getLogger(CellComparatorImpl.class);
053
054  /**
055   * Comparator for plain key/values; i.e. non-catalog table key/values. Works on Key portion
056   * of KeyValue only.
057   */
058  public static final CellComparatorImpl COMPARATOR = new CellComparatorImpl();
059
060  /**
061   * A {@link CellComparatorImpl} for <code>hbase:meta</code> catalog table
062   * {@link KeyValue}s.
063   */
064  public static final CellComparatorImpl META_COMPARATOR = new MetaCellComparator();
065
066  @Override
067  public final int compare(final Cell a, final Cell b) {
068    return compare(a, b, false);
069  }
070
071  @Override
072  public int compare(final Cell a, final Cell b, boolean ignoreSequenceid) {
073
074    int diff = 0;
075    // "Peel off" the most common path.
076    if (a instanceof ByteBufferKeyValue && b instanceof ByteBufferKeyValue) {
077      diff = BBKVComparator.compare((ByteBufferKeyValue)a, (ByteBufferKeyValue)b, ignoreSequenceid);
078      if (diff != 0) {
079        return diff;
080      }
081    } else {
082      diff = compareRows(a, b);
083      if (diff != 0) {
084        return diff;
085      }
086
087      diff = compareWithoutRow(a, b);
088      if (diff != 0) {
089        return diff;
090      }
091    }
092
093    // Negate following comparisons so later edits show up first mvccVersion: later sorts first
094    return ignoreSequenceid? diff: Long.compare(b.getSequenceId(), a.getSequenceId());
095  }
096
097  /**
098   * Compares the family and qualifier part of the cell
099   * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
100   */
101  public final int compareColumns(final Cell left, final Cell right) {
102    int diff = compareFamilies(left, right);
103    if (diff != 0) {
104      return diff;
105    }
106    return compareQualifiers(left, right);
107  }
108
109  /**
110   * Compare the families of left and right cell
111   * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
112   */
113  @Override
114  public final int compareFamilies(Cell left, Cell right) {
115    if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) {
116      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
117          ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
118          ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
119          ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength());
120    }
121    if (left instanceof ByteBufferExtendedCell) {
122      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
123          ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
124          right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
125    }
126    if (right instanceof ByteBufferExtendedCell) {
127      // Notice how we flip the order of the compare here. We used to negate the return value but
128      // see what FindBugs says
129      // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO
130      // It suggest flipping the order to get same effect and 'safer'.
131      return ByteBufferUtils.compareTo(
132          left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(),
133          ((ByteBufferExtendedCell)right).getFamilyByteBuffer(),
134          ((ByteBufferExtendedCell)right).getFamilyPosition(), right.getFamilyLength());
135    }
136    return Bytes.compareTo(left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(),
137        right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
138  }
139
140  /**
141   * Compare the qualifiers part of the left and right cells.
142   * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
143   */
144  @Override
145  public final int compareQualifiers(Cell left, Cell right) {
146    if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) {
147      return ByteBufferUtils
148          .compareTo(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
149              ((ByteBufferExtendedCell) left).getQualifierPosition(),
150              left.getQualifierLength(), ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
151              ((ByteBufferExtendedCell) right).getQualifierPosition(),
152              right.getQualifierLength());
153    }
154    if (left instanceof ByteBufferExtendedCell) {
155      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
156          ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
157          right.getQualifierArray(), right.getQualifierOffset(), right.getQualifierLength());
158    }
159    if (right instanceof ByteBufferExtendedCell) {
160      // Notice how we flip the order of the compare here. We used to negate the return value but
161      // see what FindBugs says
162      // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO
163      // It suggest flipping the order to get same effect and 'safer'.
164      return ByteBufferUtils.compareTo(left.getQualifierArray(),
165          left.getQualifierOffset(), left.getQualifierLength(),
166          ((ByteBufferExtendedCell)right).getQualifierByteBuffer(),
167          ((ByteBufferExtendedCell)right).getQualifierPosition(), right.getQualifierLength());
168    }
169    return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(),
170        left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
171        right.getQualifierLength());
172  }
173
174  /**
175   * Compares the rows of the left and right cell.
176   * For the hbase:meta case this method is overridden such that it can handle hbase:meta cells.
177   * The caller should ensure using the appropriate comparator for hbase:meta.
178   * @return 0 if both cells are equal, 1 if left cell is bigger than right, -1 otherwise
179   */
180  @Override
181  public int compareRows(final Cell left, final Cell right) {
182    return compareRows(left, left.getRowLength(), right, right.getRowLength());
183  }
184
185  static int compareRows(final Cell left, int leftRowLength, final Cell right, int rightRowLength) {
186    // left and right can be exactly the same at the beginning of a row
187    if (left == right) {
188      return 0;
189    }
190    if (left instanceof ByteBufferExtendedCell && right instanceof ByteBufferExtendedCell) {
191      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getRowByteBuffer(),
192          ((ByteBufferExtendedCell) left).getRowPosition(), leftRowLength,
193          ((ByteBufferExtendedCell) right).getRowByteBuffer(),
194          ((ByteBufferExtendedCell) right).getRowPosition(), rightRowLength);
195    }
196    if (left instanceof ByteBufferExtendedCell) {
197      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getRowByteBuffer(),
198          ((ByteBufferExtendedCell) left).getRowPosition(), leftRowLength,
199          right.getRowArray(), right.getRowOffset(), rightRowLength);
200    }
201    if (right instanceof ByteBufferExtendedCell) {
202      // Notice how we flip the order of the compare here. We used to negate the return value but
203      // see what FindBugs says
204      // http://findbugs.sourceforge.net/bugDescriptions.html#RV_NEGATING_RESULT_OF_COMPARETO
205      // It suggest flipping the order to get same effect and 'safer'.
206      return ByteBufferUtils.compareTo(left.getRowArray(), left.getRowOffset(), leftRowLength,
207          ((ByteBufferExtendedCell)right).getRowByteBuffer(),
208          ((ByteBufferExtendedCell)right).getRowPosition(), rightRowLength);
209    }
210    return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
211        right.getRowArray(), right.getRowOffset(), right.getRowLength());
212  }
213
214  /**
215   * Compares the row part of the cell with a simple plain byte[] like the
216   * stopRow in Scan. This should be used with context where for hbase:meta
217   * cells the {{@link #META_COMPARATOR} should be used
218   *
219   * @param left
220   *          the cell to be compared
221   * @param right
222   *          the kv serialized byte[] to be compared with
223   * @param roffset
224   *          the offset in the byte[]
225   * @param rlength
226   *          the length in the byte[]
227   * @return 0 if both cell and the byte[] are equal, 1 if the cell is bigger
228   *         than byte[], -1 otherwise
229   */
230  @Override
231  public int compareRows(Cell left, byte[] right, int roffset, int rlength) {
232    if (left instanceof ByteBufferExtendedCell) {
233      return ByteBufferUtils.compareTo(((ByteBufferExtendedCell) left).getRowByteBuffer(),
234          ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(), right,
235          roffset, rlength);
236    }
237    return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(), right,
238        roffset, rlength);
239  }
240
241  @Override
242  public final int compareWithoutRow(final Cell left, final Cell right) {
243    // If the column is not specified, the "minimum" key type appears the
244    // latest in the sorted order, regardless of the timestamp. This is used
245    // for specifying the last key/value in a given row, because there is no
246    // "lexicographically last column" (it would be infinitely long). The
247    // "maximum" key type does not need this behavior.
248    // Copied from KeyValue. This is bad in that we can't do memcmp w/ special rules like this.
249    int lFamLength = left.getFamilyLength();
250    int rFamLength = right.getFamilyLength();
251    int lQualLength = left.getQualifierLength();
252    int rQualLength = right.getQualifierLength();
253    if (lFamLength + lQualLength == 0
254          && left.getTypeByte() == Type.Minimum.getCode()) {
255      // left is "bigger", i.e. it appears later in the sorted order
256      return 1;
257    }
258    if (rFamLength + rQualLength == 0
259        && right.getTypeByte() == Type.Minimum.getCode()) {
260      return -1;
261    }
262    if (lFamLength != rFamLength) {
263      // comparing column family is enough.
264      return compareFamilies(left, right);
265    }
266    // Compare cf:qualifier
267    int diff = compareColumns(left, right);
268    if (diff != 0) {
269      return diff;
270    }
271
272    diff = compareTimestamps(left.getTimestamp(), right.getTimestamp());
273    if (diff != 0) {
274      return diff;
275    }
276
277    // Compare types. Let the delete types sort ahead of puts; i.e. types
278    // of higher numbers sort before those of lesser numbers. Maximum (255)
279    // appears ahead of everything, and minimum (0) appears after
280    // everything.
281    return (0xff & right.getTypeByte()) - (0xff & left.getTypeByte());
282  }
283
284  @Override
285  public int compareTimestamps(final Cell left, final Cell right) {
286    return compareTimestamps(left.getTimestamp(), right.getTimestamp());
287  }
288
289  @Override
290  public int compareTimestamps(final long ltimestamp, final long rtimestamp) {
291    // Swap order we pass into compare so we get DESCENDING order.
292    return Long.compare(rtimestamp, ltimestamp);
293  }
294
295  /**
296   * A {@link CellComparatorImpl} for <code>hbase:meta</code> catalog table
297   * {@link KeyValue}s.
298   */
299  public static class MetaCellComparator extends CellComparatorImpl {
300    // TODO: Do we need a ByteBufferKeyValue version of this?
301    @Override
302    public int compareRows(final Cell left, final Cell right) {
303      return compareRows(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
304          right.getRowArray(), right.getRowOffset(), right.getRowLength());
305    }
306
307    @Override
308    public int compareRows(Cell left, byte[] right, int roffset, int rlength) {
309      return compareRows(left.getRowArray(), left.getRowOffset(), left.getRowLength(), right,
310          roffset, rlength);
311    }
312
313    @Override
314    public int compare(final Cell a, final Cell b, boolean ignoreSequenceid) {
315      int diff = compareRows(a, b);
316      if (diff != 0) {
317        return diff;
318      }
319
320      diff = compareWithoutRow(a, b);
321      if (diff != 0) {
322        return diff;
323      }
324
325      // Negate following comparisons so later edits show up first mvccVersion: later sorts first
326      return ignoreSequenceid? diff: Longs.compare(b.getSequenceId(), a.getSequenceId());
327    }
328
329    private static int compareRows(byte[] left, int loffset, int llength, byte[] right, int roffset,
330        int rlength) {
331      int leftDelimiter = Bytes.searchDelimiterIndex(left, loffset, llength, HConstants.DELIMITER);
332      int rightDelimiter = Bytes
333          .searchDelimiterIndex(right, roffset, rlength, HConstants.DELIMITER);
334      // Compare up to the delimiter
335      int lpart = (leftDelimiter < 0 ? llength : leftDelimiter - loffset);
336      int rpart = (rightDelimiter < 0 ? rlength : rightDelimiter - roffset);
337      int result = Bytes.compareTo(left, loffset, lpart, right, roffset, rpart);
338      if (result != 0) {
339        return result;
340      } else {
341        if (leftDelimiter < 0 && rightDelimiter >= 0) {
342          return -1;
343        } else if (rightDelimiter < 0 && leftDelimiter >= 0) {
344          return 1;
345        } else if (leftDelimiter < 0) {
346          return 0;
347        }
348      }
349      // Compare middle bit of the row.
350      // Move past delimiter
351      leftDelimiter++;
352      rightDelimiter++;
353      int leftFarDelimiter = Bytes.searchDelimiterIndexInReverse(left, leftDelimiter, llength
354          - (leftDelimiter - loffset), HConstants.DELIMITER);
355      int rightFarDelimiter = Bytes.searchDelimiterIndexInReverse(right, rightDelimiter, rlength
356          - (rightDelimiter - roffset), HConstants.DELIMITER);
357      // Now compare middlesection of row.
358      lpart = (leftFarDelimiter < 0 ? llength + loffset : leftFarDelimiter) - leftDelimiter;
359      rpart = (rightFarDelimiter < 0 ? rlength + roffset : rightFarDelimiter) - rightDelimiter;
360      result = Bytes.compareTo(left, leftDelimiter, lpart, right, rightDelimiter, rpart);
361      if (result != 0) {
362        return result;
363      } else {
364        if (leftDelimiter < 0 && rightDelimiter >= 0) {
365          return -1;
366        } else if (rightDelimiter < 0 && leftDelimiter >= 0) {
367          return 1;
368        } else if (leftDelimiter < 0) {
369          return 0;
370        }
371      }
372      // Compare last part of row, the rowid.
373      leftFarDelimiter++;
374      rightFarDelimiter++;
375      result = Bytes.compareTo(left, leftFarDelimiter, llength - (leftFarDelimiter - loffset),
376          right, rightFarDelimiter, rlength - (rightFarDelimiter - roffset));
377      return result;
378    }
379
380    @Override
381    public Comparator getSimpleComparator() {
382      return this;
383    }
384  }
385
386  @Override
387  public Comparator getSimpleComparator() {
388    return new BBKVComparator(this);
389  }
390}