001/** 002 * 003 * Licensed to the Apache Software Foundation (ASF) under one 004 * or more contributor license agreements. See the NOTICE file 005 * distributed with this work for additional information 006 * regarding copyright ownership. The ASF licenses this file 007 * to you under the Apache License, Version 2.0 (the 008 * "License"); you may not use this file except in compliance 009 * with the License. You may obtain a copy of the License at 010 * 011 * http://www.apache.org/licenses/LICENSE-2.0 012 * 013 * Unless required by applicable law or agreed to in writing, software 014 * distributed under the License is distributed on an "AS IS" BASIS, 015 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 016 * See the License for the specific language governing permissions and 017 * limitations under the License. 018 */ 019 020package org.apache.hadoop.hbase.filter; 021 022import org.apache.hadoop.hbase.Cell; 023import org.apache.hadoop.hbase.CellUtil; 024import org.apache.hadoop.hbase.KeyValueUtil; 025import org.apache.yetus.audience.InterfaceAudience; 026 027import java.io.IOException; 028import java.util.ArrayList; 029import java.util.Collections; 030import java.util.List; 031 032/** 033 * FilterListWithOR represents an ordered list of filters which will be evaluated with an OR 034 * operator. 035 */ 036@InterfaceAudience.Private 037public class FilterListWithOR extends FilterListBase { 038 039 /** 040 * Save previous return code and previous cell for every filter in filter list. For MUST_PASS_ONE, 041 * we use the previous return code to decide whether we should pass current cell encountered to 042 * the filter. For MUST_PASS_ALL, the two list are meaningless. 043 */ 044 private List<ReturnCode> prevFilterRCList = null; 045 private List<Cell> prevCellList = null; 046 047 public FilterListWithOR(List<Filter> filters) { 048 super(filters); 049 prevFilterRCList = new ArrayList<>(Collections.nCopies(filters.size(), null)); 050 prevCellList = new ArrayList<>(Collections.nCopies(filters.size(), null)); 051 subFiltersIncludedCell = new ArrayList<>(Collections.nCopies(filters.size(), false)); 052 } 053 054 @Override 055 public void addFilterLists(List<Filter> filters) { 056 if (checkAndGetReversed(filters, isReversed()) != isReversed()) { 057 throw new IllegalArgumentException("Filters in the list must have the same reversed flag"); 058 } 059 this.filters.addAll(filters); 060 this.subFiltersIncludedCell.addAll(Collections.nCopies(filters.size(), false)); 061 this.prevFilterRCList.addAll(Collections.nCopies(filters.size(), null)); 062 this.prevCellList.addAll(Collections.nCopies(filters.size(), null)); 063 } 064 065 @Override 066 protected String formatLogFilters(List<Filter> logFilters) { 067 return String.format("FilterList OR (%d/%d): %s", logFilters.size(), this.size(), 068 logFilters.toString()); 069 } 070 071 /** 072 * For MUST_PASS_ONE, we cannot make sure that when filter-A in filter list return NEXT_COL then 073 * the next cell passing to filterList will be the first cell in next column, because if filter-B 074 * in filter list return SKIP, then the filter list will return SKIP. In this case, we should pass 075 * the cell following the previous cell, and it's possible that the next cell has the same column 076 * as the previous cell even if filter-A has NEXT_COL returned for the previous cell. So we should 077 * save the previous cell and the return code list when checking previous cell for every filter in 078 * filter list, and verify if currentCell fit the previous return code, if fit then pass the 079 * currentCell to the corresponding filter. (HBASE-17678) <br> 080 * Note that: In StoreScanner level, NEXT_ROW will skip to the next row in current family, and in 081 * RegionScanner level, NEXT_ROW will skip to the next row in current family and switch to the 082 * next family for RegionScanner, INCLUDE_AND_NEXT_ROW is the same. so we should pass current cell 083 * to the filter, if row mismatch or row match but column family mismatch. (HBASE-18368) 084 * @see org.apache.hadoop.hbase.filter.Filter.ReturnCode 085 */ 086 private boolean shouldPassCurrentCellToFilter(Cell prevCell, Cell currentCell, 087 ReturnCode prevCode) throws IOException { 088 if (prevCell == null || prevCode == null) { 089 return true; 090 } 091 switch (prevCode) { 092 case INCLUDE: 093 case SKIP: 094 return true; 095 case SEEK_NEXT_USING_HINT: 096 Cell nextHintCell = getNextCellHint(prevCell); 097 return nextHintCell == null || this.compareCell(currentCell, nextHintCell) >= 0; 098 case NEXT_COL: 099 case INCLUDE_AND_NEXT_COL: 100 // Once row changed, reset() will clear prevCells, so we need not to compare their rows 101 // because rows are the same here. 102 return !CellUtil.matchingColumn(prevCell, currentCell); 103 case NEXT_ROW: 104 case INCLUDE_AND_SEEK_NEXT_ROW: 105 // As described above, rows are definitely the same, so we only compare the family. 106 return !CellUtil.matchingFamily(prevCell, currentCell); 107 default: 108 throw new IllegalStateException("Received code is not valid."); 109 } 110 } 111 112 /** 113 * FilterList with MUST_PASS_ONE choose the minimal forward step among sub-filter in filter list. 114 * Let's call it: The Minimal Step Rule. So if filter-A in filter list return INCLUDE and filter-B 115 * in filter list return INCLUDE_AND_NEXT_COL, then the filter list should return INCLUDE. For 116 * SEEK_NEXT_USING_HINT, it's more special, because we do not know how far it will forward, so we 117 * use SKIP by default.<br/> 118 * <br/> 119 * The jump step will be: 120 * 121 * <pre> 122 * INCLUDE < SKIP < INCLUDE_AND_NEXT_COL < NEXT_COL < INCLUDE_AND_SEEK_NEXT_ROW < NEXT_ROW < SEEK_NEXT_USING_HINT 123 * </pre> 124 * 125 * Here, we have the following map to describe The Minimal Step Rule. if current return code (for 126 * previous sub-filters in filter list) is <strong>ReturnCode</strong>, and current filter returns 127 * <strong>localRC</strong>, then we should return map[ReturnCode][localRC] for the merged result, 128 * according to The Minimal Step Rule.<br/> 129 * 130 * <pre> 131 * LocalCode\ReturnCode INCLUDE INCLUDE_AND_NEXT_COL INCLUDE_AND_SEEK_NEXT_ROW SKIP NEXT_COL NEXT_ROW SEEK_NEXT_USING_HINT 132 * INCLUDE INCLUDE INCLUDE INCLUDE INCLUDE INCLUDE INCLUDE INCLUDE 133 * INCLUDE_AND_NEXT_COL INCLUDE INCLUDE_AND_NEXT_COL INCLUDE_AND_NEXT_COL INCLUDE INCLUDE_AND_NEXT_COL INCLUDE_AND_NEXT_COL INCLUDE 134 * INCLUDE_AND_SEEK_NEXT_ROW INCLUDE INCLUDE_AND_NEXT_COL INCLUDE_AND_SEEK_NEXT_ROW INCLUDE INCLUDE_AND_NEXT_COL INCLUDE_AND_SEEK_NEXT_ROW INCLUDE 135 * SKIP INCLUDE INCLUDE INCLUDE SKIP SKIP SKIP SKIP 136 * NEXT_COL INCLUDE INCLUDE_AND_NEXT_COL INCLUDE_AND_NEXT_COL SKIP NEXT_COL NEXT_COL SKIP 137 * NEXT_ROW INCLUDE INCLUDE_AND_NEXT_COL INCLUDE_AND_SEEK_NEXT_ROW SKIP NEXT_COL NEXT_ROW SKIP 138 * SEEK_NEXT_USING_HINT INCLUDE INCLUDE INCLUDE SKIP SKIP SKIP SEEK_NEXT_USING_HINT 139 * </pre> 140 * 141 * @param rc Return code which is calculated by previous sub-filter(s) in filter list. 142 * @param localRC Return code of the current sub-filter in filter list. 143 * @return Return code which is merged by the return code of previous sub-filter(s) and the return 144 * code of current sub-filter. 145 */ 146 private ReturnCode mergeReturnCode(ReturnCode rc, ReturnCode localRC) { 147 if (rc == null) return localRC; 148 switch (localRC) { 149 case INCLUDE: 150 return ReturnCode.INCLUDE; 151 case INCLUDE_AND_NEXT_COL: 152 if (isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.SKIP, 153 ReturnCode.SEEK_NEXT_USING_HINT)) { 154 return ReturnCode.INCLUDE; 155 } 156 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_NEXT_COL, ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW, 157 ReturnCode.NEXT_COL, ReturnCode.NEXT_ROW)) { 158 return ReturnCode.INCLUDE_AND_NEXT_COL; 159 } 160 break; 161 case INCLUDE_AND_SEEK_NEXT_ROW: 162 if (isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.SKIP, 163 ReturnCode.SEEK_NEXT_USING_HINT)) { 164 return ReturnCode.INCLUDE; 165 } 166 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_NEXT_COL, ReturnCode.NEXT_COL)) { 167 return ReturnCode.INCLUDE_AND_NEXT_COL; 168 } 169 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW, ReturnCode.NEXT_ROW)) { 170 return ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW; 171 } 172 break; 173 case SKIP: 174 if (isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL, 175 ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW)) { 176 return ReturnCode.INCLUDE; 177 } 178 if (isInReturnCodes(rc, ReturnCode.SKIP, ReturnCode.NEXT_COL, ReturnCode.NEXT_ROW, 179 ReturnCode.SEEK_NEXT_USING_HINT)) { 180 return ReturnCode.SKIP; 181 } 182 break; 183 case NEXT_COL: 184 if (isInReturnCodes(rc, ReturnCode.INCLUDE)) { 185 return ReturnCode.INCLUDE; 186 } 187 if (isInReturnCodes(rc, ReturnCode.NEXT_COL, ReturnCode.NEXT_ROW)) { 188 return ReturnCode.NEXT_COL; 189 } 190 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_NEXT_COL, 191 ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW)) { 192 return ReturnCode.INCLUDE_AND_NEXT_COL; 193 } 194 if (isInReturnCodes(rc, ReturnCode.SKIP, ReturnCode.SEEK_NEXT_USING_HINT)) { 195 return ReturnCode.SKIP; 196 } 197 break; 198 case NEXT_ROW: 199 if (isInReturnCodes(rc, ReturnCode.INCLUDE)) { 200 return ReturnCode.INCLUDE; 201 } 202 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_NEXT_COL)) { 203 return ReturnCode.INCLUDE_AND_NEXT_COL; 204 } 205 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW)) { 206 return ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW; 207 } 208 if (isInReturnCodes(rc, ReturnCode.SKIP, ReturnCode.SEEK_NEXT_USING_HINT)) { 209 return ReturnCode.SKIP; 210 } 211 if (isInReturnCodes(rc, ReturnCode.NEXT_COL)) { 212 return ReturnCode.NEXT_COL; 213 } 214 if (isInReturnCodes(rc, ReturnCode.NEXT_ROW)) { 215 return ReturnCode.NEXT_ROW; 216 } 217 break; 218 case SEEK_NEXT_USING_HINT: 219 if (isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL, 220 ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW)) { 221 return ReturnCode.INCLUDE; 222 } 223 if (isInReturnCodes(rc, ReturnCode.SKIP, ReturnCode.NEXT_COL, ReturnCode.NEXT_ROW)) { 224 return ReturnCode.SKIP; 225 } 226 if (isInReturnCodes(rc, ReturnCode.SEEK_NEXT_USING_HINT)) { 227 return ReturnCode.SEEK_NEXT_USING_HINT; 228 } 229 break; 230 } 231 throw new IllegalStateException( 232 "Received code is not valid. rc: " + rc + ", localRC: " + localRC); 233 } 234 235 private void updatePrevFilterRCList(int index, ReturnCode currentRC) { 236 prevFilterRCList.set(index, currentRC); 237 } 238 239 private void updatePrevCellList(int index, Cell currentCell, ReturnCode currentRC) { 240 if (currentCell == null || currentRC == ReturnCode.INCLUDE || currentRC == ReturnCode.SKIP) { 241 // If previous return code is INCLUDE or SKIP, we should always pass the next cell to the 242 // corresponding sub-filter(need not test shouldPassCurrentCellToFilter() method), So we 243 // need not save current cell to prevCellList for saving heap memory. 244 prevCellList.set(index, null); 245 } else { 246 prevCellList.set(index, KeyValueUtil.toNewKeyCell(currentCell)); 247 } 248 } 249 250 @Override 251 public ReturnCode filterCell(Cell c) throws IOException { 252 if (isEmpty()) { 253 return ReturnCode.INCLUDE; 254 } 255 ReturnCode rc = null; 256 boolean everyFilterReturnHint = true; 257 for (int i = 0, n = filters.size(); i < n; i++) { 258 Filter filter = filters.get(i); 259 subFiltersIncludedCell.set(i, false); 260 261 Cell prevCell = this.prevCellList.get(i); 262 ReturnCode prevCode = this.prevFilterRCList.get(i); 263 if (filter.filterAllRemaining() || !shouldPassCurrentCellToFilter(prevCell, c, prevCode)) { 264 everyFilterReturnHint = false; 265 continue; 266 } 267 268 ReturnCode localRC = filter.filterCell(c); 269 270 // Update previous return code and previous cell for filter[i]. 271 updatePrevFilterRCList(i, localRC); 272 updatePrevCellList(i, c, localRC); 273 274 if (localRC != ReturnCode.SEEK_NEXT_USING_HINT) { 275 everyFilterReturnHint = false; 276 } 277 278 rc = mergeReturnCode(rc, localRC); 279 280 // For INCLUDE* case, we need to update the transformed cell. 281 if (isInReturnCodes(localRC, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL, 282 ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW)) { 283 subFiltersIncludedCell.set(i, true); 284 } 285 } 286 287 if (everyFilterReturnHint) { 288 return ReturnCode.SEEK_NEXT_USING_HINT; 289 } else if (rc == null) { 290 // Each sub-filter in filter list got true for filterAllRemaining(). 291 return ReturnCode.SKIP; 292 } else { 293 return rc; 294 } 295 } 296 297 @Override 298 public void reset() throws IOException { 299 for (int i = 0, n = filters.size(); i < n; i++) { 300 filters.get(i).reset(); 301 subFiltersIncludedCell.set(i, false); 302 prevFilterRCList.set(i, null); 303 prevCellList.set(i, null); 304 } 305 } 306 307 @Override 308 public boolean filterRowKey(byte[] rowKey, int offset, int length) throws IOException { 309 if (isEmpty()) { 310 return super.filterRowKey(rowKey, offset, length); 311 } 312 boolean retVal = true; 313 for (int i = 0, n = filters.size(); i < n; i++) { 314 Filter filter = filters.get(i); 315 if (!filter.filterAllRemaining() && !filter.filterRowKey(rowKey, offset, length)) { 316 retVal = false; 317 } 318 } 319 return retVal; 320 } 321 322 @Override 323 public boolean filterRowKey(Cell firstRowCell) throws IOException { 324 if (isEmpty()) { 325 return super.filterRowKey(firstRowCell); 326 } 327 boolean retVal = true; 328 for (int i = 0, n = filters.size(); i < n; i++) { 329 Filter filter = filters.get(i); 330 if (!filter.filterAllRemaining() && !filter.filterRowKey(firstRowCell)) { 331 // Can't just return false here, because there are some filters (such as PrefixFilter) which 332 // will catch the row changed event by filterRowKey(). If we return early here, those 333 // filters will have no chance to update their row state. 334 retVal = false; 335 } 336 } 337 return retVal; 338 } 339 340 @Override 341 public boolean filterAllRemaining() throws IOException { 342 if (isEmpty()) { 343 return super.filterAllRemaining(); 344 } 345 for (int i = 0, n = filters.size(); i < n; i++) { 346 if (!filters.get(i).filterAllRemaining()) { 347 return false; 348 } 349 } 350 return true; 351 } 352 353 @Override 354 public boolean filterRow() throws IOException { 355 if (isEmpty()) { 356 return super.filterRow(); 357 } 358 for (int i = 0, n = filters.size(); i < n; i++) { 359 Filter filter = filters.get(i); 360 if (!filter.filterRow()) { 361 return false; 362 } 363 } 364 return true; 365 } 366 367 @Override 368 public Cell getNextCellHint(Cell currentCell) throws IOException { 369 if (isEmpty()) { 370 return super.getNextCellHint(currentCell); 371 } 372 Cell minKeyHint = null; 373 // If any condition can pass, we need to keep the min hint 374 for (int i = 0, n = filters.size(); i < n; i++) { 375 if (filters.get(i).filterAllRemaining()) { 376 continue; 377 } 378 Cell curKeyHint = filters.get(i).getNextCellHint(currentCell); 379 if (curKeyHint == null) { 380 // If we ever don't have a hint and this is must-pass-one, then no hint 381 return null; 382 } 383 // If this is the first hint we find, set it 384 if (minKeyHint == null) { 385 minKeyHint = curKeyHint; 386 continue; 387 } 388 if (this.compareCell(minKeyHint, curKeyHint) > 0) { 389 minKeyHint = curKeyHint; 390 } 391 } 392 return minKeyHint; 393 } 394}