Source code

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.regionserver.querymatcher;
019
020import java.io.IOException;
021import java.util.NavigableSet;
022
023import org.apache.hadoop.hbase.Cell;
024import org.apache.hadoop.hbase.CellUtil;
025import org.apache.hadoop.hbase.PrivateCellUtil;
026import org.apache.hadoop.hbase.KeyValueUtil;
027import org.apache.yetus.audience.InterfaceAudience;
028import org.apache.hadoop.hbase.client.Scan;
029import org.apache.hadoop.hbase.filter.Filter;
030import org.apache.hadoop.hbase.filter.Filter.ReturnCode;
031import org.apache.hadoop.hbase.io.TimeRange;
032import org.apache.hadoop.hbase.regionserver.RegionCoprocessorHost;
033import org.apache.hadoop.hbase.regionserver.ScanInfo;
034import org.apache.hadoop.hbase.util.Pair;
035
036/**
037 * Query matcher for user scan.
038 * <p>
039 * We do not consider mvcc here because
040 * {@link org.apache.hadoop.hbase.regionserver.StoreFileScanner} and
041 * {@link org.apache.hadoop.hbase.regionserver.SegmentScanner} will only return a cell whose mvcc is
042 * less than or equal to given read point. For
043 * {@link org.apache.hadoop.hbase.client.IsolationLevel#READ_UNCOMMITTED}, we just set the read
044 * point to {@link Long#MAX_VALUE}, i.e. still do not need to consider it.
045 */
046@InterfaceAudience.Private
047public abstract class UserScanQueryMatcher extends ScanQueryMatcher {
048
049  protected final boolean hasNullColumn;
050
051  protected final Filter filter;
052
053  protected final byte[] stopRow;
054
055  protected final TimeRange tr;
056
057  private final int versionsAfterFilter;
058
059  private int count = 0;
060
061  private Cell curColCell = null;
062
063  private static Cell createStartKey(Scan scan, ScanInfo scanInfo) {
064    if (scan.includeStartRow()) {
065      return createStartKeyFromRow(scan.getStartRow(), scanInfo);
066    } else {
067      return PrivateCellUtil.createLastOnRow(scan.getStartRow());
068    }
069  }
070
071  protected UserScanQueryMatcher(Scan scan, ScanInfo scanInfo, ColumnTracker columns,
072      boolean hasNullColumn, long oldestUnexpiredTS, long now) {
073    super(createStartKey(scan, scanInfo), scanInfo, columns, oldestUnexpiredTS, now);
074    this.hasNullColumn = hasNullColumn;
075    this.filter = scan.getFilter();
076    if (this.filter != null) {
077      this.versionsAfterFilter =
078          scan.isRaw() ? scan.getMaxVersions() : Math.min(scan.getMaxVersions(),
079            scanInfo.getMaxVersions());
080    } else {
081      this.versionsAfterFilter = 0;
082    }
083    this.stopRow = scan.getStopRow();
084    TimeRange timeRange = scan.getColumnFamilyTimeRange().get(scanInfo.getFamily());
085    if (timeRange == null) {
086      this.tr = scan.getTimeRange();
087    } else {
088      this.tr = timeRange;
089    }
090  }
091
092  @Override
093  public boolean hasNullColumnInQuery() {
094    return hasNullColumn;
095  }
096
097  @Override
098  public boolean isUserScan() {
099    return true;
100  }
101
102  @Override
103  public Filter getFilter() {
104    return filter;
105  }
106
107  @Override
108  public Cell getNextKeyHint(Cell cell) throws IOException {
109    if (filter == null) {
110      return null;
111    } else {
112      return filter.getNextCellHint(cell);
113    }
114  }
115
116  @Override
117  public void beforeShipped() throws IOException {
118    super.beforeShipped();
119    if (curColCell != null) {
120      this.curColCell = KeyValueUtil.toNewKeyCell(this.curColCell);
121    }
122  }
123
124  protected final MatchCode matchColumn(Cell cell, long timestamp, byte typeByte)
125      throws IOException {
126    int tsCmp = tr.compare(timestamp);
127    if (tsCmp > 0) {
128      return MatchCode.SKIP;
129    }
130    if (tsCmp < 0) {
131      return columns.getNextRowOrNextColumn(cell);
132    }
133    // STEP 1: Check if the column is part of the requested columns
134    MatchCode matchCode = columns.checkColumn(cell, typeByte);
135    if (matchCode != MatchCode.INCLUDE) {
136      return matchCode;
137    }
138    /*
139     * STEP 2: check the number of versions needed. This method call returns SKIP, SEEK_NEXT_COL,
140     * INCLUDE, INCLUDE_AND_SEEK_NEXT_COL, or INCLUDE_AND_SEEK_NEXT_ROW.
141     */
142    matchCode = columns.checkVersions(cell, timestamp, typeByte, false);
143    switch (matchCode) {
144      case SKIP:
145        return MatchCode.SKIP;
146      case SEEK_NEXT_COL:
147        return MatchCode.SEEK_NEXT_COL;
148      default:
149        // It means it is INCLUDE, INCLUDE_AND_SEEK_NEXT_COL or INCLUDE_AND_SEEK_NEXT_ROW.
150        assert matchCode == MatchCode.INCLUDE || matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_COL
151            || matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_ROW;
152        break;
153    }
154
155    return filter == null ? matchCode : mergeFilterResponse(cell, matchCode,
156      filter.filterCell(cell));
157  }
158
159  /**
160   * Call this when scan has filter. Decide the desired behavior by checkVersions's MatchCode and
161   * filterCell's ReturnCode. Cell may be skipped by filter, so the column versions in result may be
162   * less than user need. It need to check versions again when filter and columnTracker both include
163   * the cell. <br/>
164   *
165   * <pre>
166   * ColumnChecker                FilterResponse               Desired behavior
167   * INCLUDE                      SKIP                         SKIP
168   * INCLUDE                      NEXT_COL                     SEEK_NEXT_COL or SEEK_NEXT_ROW
169   * INCLUDE                      NEXT_ROW                     SEEK_NEXT_ROW
170   * INCLUDE                      SEEK_NEXT_USING_HINT         SEEK_NEXT_USING_HINT
171   * INCLUDE                      INCLUDE                      INCLUDE
172   * INCLUDE                      INCLUDE_AND_NEXT_COL         INCLUDE_AND_SEEK_NEXT_COL
173   * INCLUDE                      INCLUDE_AND_SEEK_NEXT_ROW    INCLUDE_AND_SEEK_NEXT_ROW
174   * INCLUDE_AND_SEEK_NEXT_COL    SKIP                         SEEK_NEXT_COL
175   * INCLUDE_AND_SEEK_NEXT_COL    NEXT_COL                     SEEK_NEXT_COL or SEEK_NEXT_ROW
176   * INCLUDE_AND_SEEK_NEXT_COL    NEXT_ROW                     SEEK_NEXT_ROW
177   * INCLUDE_AND_SEEK_NEXT_COL    SEEK_NEXT_USING_HINT         SEEK_NEXT_USING_HINT
178   * INCLUDE_AND_SEEK_NEXT_COL    INCLUDE                      INCLUDE_AND_SEEK_NEXT_COL
179   * INCLUDE_AND_SEEK_NEXT_COL    INCLUDE_AND_NEXT_COL         INCLUDE_AND_SEEK_NEXT_COL
180   * INCLUDE_AND_SEEK_NEXT_COL    INCLUDE_AND_SEEK_NEXT_ROW    INCLUDE_AND_SEEK_NEXT_ROW
181   * INCLUDE_AND_SEEK_NEXT_ROW    SKIP                         SEEK_NEXT_ROW
182   * INCLUDE_AND_SEEK_NEXT_ROW    NEXT_COL                     SEEK_NEXT_ROW
183   * INCLUDE_AND_SEEK_NEXT_ROW    NEXT_ROW                     SEEK_NEXT_ROW
184   * INCLUDE_AND_SEEK_NEXT_ROW    SEEK_NEXT_USING_HINT         SEEK_NEXT_USING_HINT
185   * INCLUDE_AND_SEEK_NEXT_ROW    INCLUDE                      INCLUDE_AND_SEEK_NEXT_ROW
186   * INCLUDE_AND_SEEK_NEXT_ROW    INCLUDE_AND_NEXT_COL         INCLUDE_AND_SEEK_NEXT_ROW
187   * INCLUDE_AND_SEEK_NEXT_ROW    INCLUDE_AND_SEEK_NEXT_ROW    INCLUDE_AND_SEEK_NEXT_ROW
188   * </pre>
189   */
190  private final MatchCode mergeFilterResponse(Cell cell, MatchCode matchCode,
191      ReturnCode filterResponse) {
192    switch (filterResponse) {
193      case SKIP:
194        if (matchCode == MatchCode.INCLUDE) {
195          return MatchCode.SKIP;
196        } else if (matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_COL) {
197          return MatchCode.SEEK_NEXT_COL;
198        } else if (matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_ROW) {
199          return MatchCode.SEEK_NEXT_ROW;
200        }
201        break;
202      case NEXT_COL:
203        if (matchCode == MatchCode.INCLUDE || matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_COL) {
204          return columns.getNextRowOrNextColumn(cell);
205        } else if (matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_ROW) {
206          return MatchCode.SEEK_NEXT_ROW;
207        }
208        break;
209      case NEXT_ROW:
210        return MatchCode.SEEK_NEXT_ROW;
211      case SEEK_NEXT_USING_HINT:
212        return MatchCode.SEEK_NEXT_USING_HINT;
213      case INCLUDE:
214        break;
215      case INCLUDE_AND_NEXT_COL:
216        if (matchCode == MatchCode.INCLUDE) {
217          matchCode = MatchCode.INCLUDE_AND_SEEK_NEXT_COL;
218        }
219        break;
220      case INCLUDE_AND_SEEK_NEXT_ROW:
221        matchCode = MatchCode.INCLUDE_AND_SEEK_NEXT_ROW;
222        break;
223      default:
224        throw new RuntimeException("UNEXPECTED");
225    }
226
227    // It means it is INCLUDE, INCLUDE_AND_SEEK_NEXT_COL or INCLUDE_AND_SEEK_NEXT_ROW.
228    assert matchCode == MatchCode.INCLUDE || matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_COL
229        || matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_ROW;
230
231    // We need to make sure that the number of cells returned will not exceed max version in scan
232    // when the match code is INCLUDE* case.
233    if (curColCell == null || !CellUtil.matchingRowColumn(cell, curColCell)) {
234      count = 0;
235      curColCell = cell;
236    }
237    count += 1;
238
239    if (count > versionsAfterFilter) {
240      // when the number of cells exceed max version in scan, we should return SEEK_NEXT_COL match
241      // code, but if current code is INCLUDE_AND_SEEK_NEXT_ROW, we can optimize to choose the max
242      // step between SEEK_NEXT_COL and INCLUDE_AND_SEEK_NEXT_ROW, which is SEEK_NEXT_ROW.
243      if (matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_ROW) {
244        matchCode = MatchCode.SEEK_NEXT_ROW;
245      } else {
246        matchCode = MatchCode.SEEK_NEXT_COL;
247      }
248    }
249    if (matchCode == MatchCode.INCLUDE_AND_SEEK_NEXT_COL || matchCode == MatchCode.SEEK_NEXT_COL) {
250      // Update column tracker to next column, As we use the column hint from the tracker to seek
251      // to next cell (HBASE-19749)
252      columns.doneWithColumn(cell);
253    }
254    return matchCode;
255  }
256
257  protected abstract boolean isGet();
258
259  protected abstract boolean moreRowsMayExistsAfter(int cmpToStopRow);
260
261  @Override
262  public boolean moreRowsMayExistAfter(Cell cell) {
263    // If a 'get' Scan -- we are doing a Get (every Get is a single-row Scan in implementation) --
264    // then we are looking at one row only, the one specified in the Get coordinate..so we know
265    // for sure that there are no more rows on this Scan
266    if (isGet()) {
267      return false;
268    }
269    // If no stopRow, return that there may be more rows. The tests that follow depend on a
270    // non-empty, non-default stopRow so this little test below short-circuits out doing the
271    // following compares.
272    if (this.stopRow == null || this.stopRow.length == 0) {
273      return true;
274    }
275    return moreRowsMayExistsAfter(rowComparator.compareRows(cell, stopRow, 0, stopRow.length));
276  }
277
278  public static UserScanQueryMatcher create(Scan scan, ScanInfo scanInfo,
279      NavigableSet<byte[]> columns, long oldestUnexpiredTS, long now,
280      RegionCoprocessorHost regionCoprocessorHost) throws IOException {
281    boolean hasNullColumn =
282        !(columns != null && columns.size() != 0 && columns.first().length != 0);
283    Pair<DeleteTracker, ColumnTracker> trackers = getTrackers(regionCoprocessorHost, columns,
284        scanInfo, oldestUnexpiredTS, scan);
285    DeleteTracker deleteTracker = trackers.getFirst();
286    ColumnTracker columnTracker = trackers.getSecond();
287    if (scan.isRaw()) {
288      return RawScanQueryMatcher.create(scan, scanInfo, columnTracker, hasNullColumn,
289        oldestUnexpiredTS, now);
290    } else {
291      return NormalUserScanQueryMatcher.create(scan, scanInfo, columnTracker, deleteTracker,
292          hasNullColumn, oldestUnexpiredTS, now);
293    }
294  }
295}