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.filter; 019 020import java.io.IOException; 021import java.util.ArrayList; 022import java.util.Arrays; 023import java.util.Collections; 024import java.util.List; 025import java.util.Objects; 026import org.apache.hadoop.hbase.Cell; 027import org.apache.yetus.audience.InterfaceAudience; 028 029/** 030 * FilterListWithAND represents an ordered list of filters which will be evaluated with an AND 031 * operator. 032 */ 033@InterfaceAudience.Private 034public class FilterListWithAND extends FilterListBase { 035 036 private List<Filter> seekHintFilters = new ArrayList<>(); 037 private boolean[] hintingFilters; 038 /** 039 * Tracks which sub-filters returned {@code true} from {@link Filter#filterRowKey(Cell)}. Set in 040 * {@code filterRowKey()}, consumed by {@code getHintForRejectedRow()}, cleared only by 041 * {@code reset()} — callers must invoke {@code reset()} between rows to avoid stale state. 042 */ 043 private boolean[] rejectedByFilterRowKey; 044 045 public FilterListWithAND(List<Filter> filters) { 046 super(filters); 047 // For FilterList with AND, when call FL's transformCell(), we should transform cell for all 048 // sub-filters (because all sub-filters return INCLUDE*). So here, fill this array with true. we 049 // keep this in FilterListWithAND for abstracting the transformCell() in FilterListBase. 050 subFiltersIncludedCell = new ArrayList<>(Collections.nCopies(filters.size(), true)); 051 rejectedByFilterRowKey = new boolean[filters.size()]; 052 cacheHintingFilters(); 053 } 054 055 @Override 056 public void addFilterLists(List<Filter> filters) { 057 if (checkAndGetReversed(filters, isReversed()) != isReversed()) { 058 throw new IllegalArgumentException("Filters in the list must have the same reversed flag"); 059 } 060 this.filters.addAll(filters); 061 this.subFiltersIncludedCell.addAll(Collections.nCopies(filters.size(), true)); 062 this.rejectedByFilterRowKey = Arrays.copyOf(this.rejectedByFilterRowKey, this.filters.size()); 063 this.cacheHintingFilters(); 064 } 065 066 @Override 067 protected String formatLogFilters(List<Filter> logFilters) { 068 return String.format("FilterList AND (%d/%d): %s", logFilters.size(), this.size(), 069 logFilters.toString()); 070 } 071 072 /** 073 * As checks for this are in the hot path, we want them as fast as possible, so we are caching the 074 * status in an array. 075 */ 076 private void cacheHintingFilters() { 077 int filtersSize = filters.size(); 078 hintingFilters = new boolean[filtersSize]; 079 for (int i = 0; i < filtersSize; i++) { 080 if (filters.get(i) instanceof HintingFilter) { 081 hintingFilters[i] = true; 082 } 083 } 084 } 085 086 /** 087 * FilterList with MUST_PASS_ALL choose the maximal forward step among sub-filters in filter list. 088 * Let's call it: The Maximal Step Rule. So if filter-A in filter list return INCLUDE and filter-B 089 * in filter list return INCLUDE_AND_NEXT_COL, then the filter list should return 090 * INCLUDE_AND_NEXT_COL. For SEEK_NEXT_USING_HINT, it's more special, and in method 091 * filterCellWithMustPassAll(), if any sub-filter return SEEK_NEXT_USING_HINT, then our filter 092 * list will return SEEK_NEXT_USING_HINT. so we don't care about the SEEK_NEXT_USING_HINT here. 093 * <br/> 094 * <br/> 095 * The jump step will be: 096 * 097 * <pre> 098 * INCLUDE < SKIP < INCLUDE_AND_NEXT_COL < NEXT_COL < INCLUDE_AND_SEEK_NEXT_ROW < NEXT_ROW 099 * < SEEK_NEXT_USING_HINT 100 * </pre> 101 * 102 * Here, we have the following map to describe The Maximal Step Rule. if current return code (for 103 * previous sub-filters in filter list) is <strong>ReturnCode</strong>, and current filter returns 104 * <strong>localRC</strong>, then we should return map[ReturnCode][localRC] for the merged result, 105 * according to The Maximal Step Rule. <br/> 106 * 107 * <pre> 108 * LocalCode\ReturnCode INCLUDE INCLUDE_AND_NEXT_COL INCLUDE_AND_SEEK_NEXT_ROW SKIP NEXT_COL NEXT_ROW SEEK_NEXT_USING_HINT 109 * INCLUDE INCLUDE INCLUDE_AND_NEXT_COL INCLUDE_AND_SEEK_NEXT_ROW SKIP NEXT_COL NEXT_ROW SEEK_NEXT_USING_HINT 110 * INCLUDE_AND_NEXT_COL INCLUDE_AND_NEXT_COL INCLUDE_AND_NEXT_COL INCLUDE_AND_SEEK_NEXT_ROW NEXT_COL NEXT_COL NEXT_ROW SEEK_NEXT_USING_HINT 111 * INCLUDE_AND_SEEK_NEXT_ROW INCLUDE_AND_SEEK_NEXT_ROW INCLUDE_AND_SEEK_NEXT_ROW INCLUDE_AND_SEEK_NEXT_ROW NEXT_ROW NEXT_ROW NEXT_ROW SEEK_NEXT_USING_HINT 112 * SKIP SKIP NEXT_COL NEXT_ROW SKIP NEXT_COL NEXT_ROW SEEK_NEXT_USING_HINT 113 * NEXT_COL NEXT_COL NEXT_COL NEXT_ROW NEXT_COL NEXT_COL NEXT_ROW SEEK_NEXT_USING_HINT 114 * NEXT_ROW NEXT_ROW NEXT_ROW NEXT_ROW NEXT_ROW NEXT_ROW NEXT_ROW SEEK_NEXT_USING_HINT 115 * SEEK_NEXT_USING_HINT SEEK_NEXT_USING_HINT SEEK_NEXT_USING_HINT SEEK_NEXT_USING_HINT SEEK_NEXT_USING_HINT SEEK_NEXT_USING_HINT SEEK_NEXT_USING_HINT SEEK_NEXT_USING_HINT 116 * </pre> 117 * 118 * @param rc Return code which is calculated by previous sub-filter(s) in filter list. 119 * @param localRC Return code of the current sub-filter in filter list. 120 * @return Return code which is merged by the return code of previous sub-filter(s) and the return 121 * code of current sub-filter. 122 */ 123 private ReturnCode mergeReturnCode(ReturnCode rc, ReturnCode localRC) { 124 if (rc == ReturnCode.SEEK_NEXT_USING_HINT) { 125 return ReturnCode.SEEK_NEXT_USING_HINT; 126 } 127 switch (localRC) { 128 case SEEK_NEXT_USING_HINT: 129 return ReturnCode.SEEK_NEXT_USING_HINT; 130 case INCLUDE: 131 return rc; 132 case INCLUDE_AND_NEXT_COL: 133 if (isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL)) { 134 return ReturnCode.INCLUDE_AND_NEXT_COL; 135 } 136 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW)) { 137 return ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW; 138 } 139 if (isInReturnCodes(rc, ReturnCode.SKIP, ReturnCode.NEXT_COL)) { 140 return ReturnCode.NEXT_COL; 141 } 142 if (isInReturnCodes(rc, ReturnCode.NEXT_ROW)) { 143 return ReturnCode.NEXT_ROW; 144 } 145 break; 146 case INCLUDE_AND_SEEK_NEXT_ROW: 147 if ( 148 isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL, 149 ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW) 150 ) { 151 return ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW; 152 } 153 if (isInReturnCodes(rc, ReturnCode.SKIP, ReturnCode.NEXT_COL, ReturnCode.NEXT_ROW)) { 154 return ReturnCode.NEXT_ROW; 155 } 156 break; 157 case SKIP: 158 if (isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.SKIP)) { 159 return ReturnCode.SKIP; 160 } 161 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_NEXT_COL, ReturnCode.NEXT_COL)) { 162 return ReturnCode.NEXT_COL; 163 } 164 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW, ReturnCode.NEXT_ROW)) { 165 return ReturnCode.NEXT_ROW; 166 } 167 break; 168 case NEXT_COL: 169 if ( 170 isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL, ReturnCode.SKIP, 171 ReturnCode.NEXT_COL) 172 ) { 173 return ReturnCode.NEXT_COL; 174 } 175 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW, ReturnCode.NEXT_ROW)) { 176 return ReturnCode.NEXT_ROW; 177 } 178 break; 179 case NEXT_ROW: 180 return ReturnCode.NEXT_ROW; 181 } 182 throw new IllegalStateException( 183 "Received code is not valid. rc: " + rc + ", localRC: " + localRC); 184 } 185 186 private boolean isIncludeRelatedReturnCode(ReturnCode rc) { 187 return isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL, 188 ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW); 189 } 190 191 @Override 192 public ReturnCode filterCell(Cell c) throws IOException { 193 if (isEmpty()) { 194 return ReturnCode.INCLUDE; 195 } 196 ReturnCode rc = ReturnCode.INCLUDE; 197 this.seekHintFilters.clear(); 198 int i = 0; 199 int n = filters.size(); 200 for (; i < n; i++) { 201 Filter filter = filters.get(i); 202 if (filter.filterAllRemaining()) { 203 rc = ReturnCode.NEXT_ROW; 204 // See comment right after this loop 205 break; 206 } 207 ReturnCode localRC; 208 localRC = filter.filterCell(c); 209 if (localRC == ReturnCode.SEEK_NEXT_USING_HINT) { 210 seekHintFilters.add(filter); 211 } 212 rc = mergeReturnCode(rc, localRC); 213 // Only when rc is INCLUDE* case, we should pass the cell to the following sub-filters. 214 // otherwise we may mess up the global state (such as offset, count..) in the following 215 // sub-filters. (HBASE-20565) 216 if (!isIncludeRelatedReturnCode(rc)) { 217 // See comment right after this loop 218 break; 219 } 220 } 221 // We have the preliminary return code. However, if there are remaining uncalled hintingFilters, 222 // they may return hints that allow us to seek ahead and skip reading and processing a lot of 223 // cells. 224 // Process the remaining hinting filters so that we can get all seek hints. 225 // The farthest key is computed in getNextCellHint() 226 if (++i < n) { 227 for (; i < n; i++) { 228 if (hintingFilters[i]) { 229 Filter filter = filters.get(i); 230 if (filter.filterCell(c) == ReturnCode.SEEK_NEXT_USING_HINT) { 231 seekHintFilters.add(filter); 232 } 233 } 234 } 235 } 236 237 if (!seekHintFilters.isEmpty()) { 238 return ReturnCode.SEEK_NEXT_USING_HINT; 239 } 240 return rc; 241 } 242 243 @Override 244 public void reset() throws IOException { 245 for (int i = 0, n = filters.size(); i < n; i++) { 246 filters.get(i).reset(); 247 } 248 seekHintFilters.clear(); 249 Arrays.fill(rejectedByFilterRowKey, false); 250 } 251 252 @Override 253 public boolean filterRowKey(Cell firstRowCell) throws IOException { 254 if (isEmpty()) { 255 return super.filterRowKey(firstRowCell); 256 } 257 Arrays.fill(rejectedByFilterRowKey, false); 258 boolean anyRowKeyFiltered = false; 259 boolean anyHintingPassed = false; 260 for (int i = 0, n = filters.size(); i < n; i++) { 261 Filter filter = filters.get(i); 262 if (filter.filterAllRemaining()) { 263 // We don't need to care about any later filters, as we end the scan immediately. 264 // TODO HBASE-28633 in the normal code path, filterAllRemaining() always gets checked 265 // before filterRowKey(). We should be able to remove this check. 266 return true; 267 } else if (filter.filterRowKey(firstRowCell)) { 268 // Can't just return true here, because there are some filters (such as PrefixFilter) which 269 // will catch the row changed event by filterRowKey(). If we return early here, those 270 // filters will have no chance to update their row state. 271 anyRowKeyFiltered = true; 272 rejectedByFilterRowKey[i] = true; 273 } else if (hintingFilters[i]) { 274 // If filterRowKey returns false and this is a hinting filter, then we must not filter this 275 // rowkey. 276 // Otherwise this sub-filter doesn't get a chance to provide a seek hint, and the scan may 277 // regress into a full scan. 278 anyHintingPassed = true; 279 } 280 } 281 return anyRowKeyFiltered && !anyHintingPassed; 282 } 283 284 @Override 285 public boolean filterAllRemaining() throws IOException { 286 if (isEmpty()) { 287 return super.filterAllRemaining(); 288 } 289 for (int i = 0, n = filters.size(); i < n; i++) { 290 if (filters.get(i).filterAllRemaining()) { 291 return true; 292 } 293 } 294 return false; 295 } 296 297 @Override 298 public boolean filterRow() throws IOException { 299 if (isEmpty()) { 300 return super.filterRow(); 301 } 302 for (int i = 0, n = filters.size(); i < n; i++) { 303 Filter filter = filters.get(i); 304 if (filter.filterRow()) { 305 return true; 306 } 307 } 308 return false; 309 } 310 311 @Override 312 public Cell getNextCellHint(Cell currentCell) throws IOException { 313 if (isEmpty()) { 314 return super.getNextCellHint(currentCell); 315 } 316 Cell maxHint = null; 317 for (Filter filter : seekHintFilters) { 318 if (filter.filterAllRemaining()) { 319 continue; 320 } 321 Cell curKeyHint = filter.getNextCellHint(currentCell); 322 if (maxHint == null) { 323 maxHint = curKeyHint; 324 continue; 325 } 326 if (this.compareCell(maxHint, curKeyHint) < 0) { 327 maxHint = curKeyHint; 328 } 329 } 330 return maxHint; 331 } 332 333 /** 334 * Maximal step: return the farthest hint among sub-filters that actually rejected the row. Only 335 * sub-filters whose {@link Filter#filterRowKey(Cell)} returned {@code true} are consulted, 336 * honouring the per-filter contract. Null hints are ignored; if no rejecting sub-filter provides 337 * a hint, return null. 338 */ 339 @Override 340 public Cell getHintForRejectedRow(Cell firstRowCell) throws IOException { 341 if (isEmpty()) { 342 return super.getHintForRejectedRow(firstRowCell); 343 } 344 Cell maxHint = null; 345 for (int i = 0, n = filters.size(); i < n; i++) { 346 if (!rejectedByFilterRowKey[i]) { 347 continue; 348 } 349 Filter filter = filters.get(i); 350 if (filter.filterAllRemaining()) { 351 continue; 352 } 353 Cell hint = filter.getHintForRejectedRow(firstRowCell); 354 if (hint == null) { 355 continue; 356 } 357 if (maxHint == null || this.compareCell(maxHint, hint) < 0) { 358 maxHint = hint; 359 } 360 } 361 return maxHint; 362 } 363 364 /** Maximal step: return the farthest skip hint among sub-filters. */ 365 @Override 366 public Cell getSkipHint(Cell skippedCell) throws IOException { 367 if (isEmpty()) { 368 return super.getSkipHint(skippedCell); 369 } 370 Cell maxHint = null; 371 for (int i = 0, n = filters.size(); i < n; i++) { 372 Filter filter = filters.get(i); 373 if (filter.filterAllRemaining()) { 374 continue; 375 } 376 Cell hint = filter.getSkipHint(skippedCell); 377 if (hint == null) { 378 continue; 379 } 380 if (maxHint == null || this.compareCell(maxHint, hint) < 0) { 381 maxHint = hint; 382 } 383 } 384 return maxHint; 385 } 386 387 @Override 388 public boolean equals(Object obj) { 389 if (this == obj) { 390 return true; 391 } 392 if (!(obj instanceof FilterListWithAND)) { 393 return false; 394 } 395 FilterListWithAND f = (FilterListWithAND) obj; 396 return this.filters.equals(f.getFilters()) && this.seekHintFilters.equals(f.seekHintFilters); 397 } 398 399 @Override 400 public int hashCode() { 401 return Objects.hash(this.seekHintFilters, this.filters); 402 } 403}