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.yetus.audience.InterfaceAudience; 024 025import java.io.IOException; 026import java.util.ArrayList; 027import java.util.Collections; 028import java.util.List; 029import java.util.Objects; 030 031/** 032 * FilterListWithAND represents an ordered list of filters which will be evaluated with an AND 033 * operator. 034 */ 035@InterfaceAudience.Private 036public class FilterListWithAND extends FilterListBase { 037 038 private List<Filter> seekHintFilters = new ArrayList<>(); 039 040 public FilterListWithAND(List<Filter> filters) { 041 super(filters); 042 // For FilterList with AND, when call FL's transformCell(), we should transform cell for all 043 // sub-filters (because all sub-filters return INCLUDE*). So here, fill this array with true. we 044 // keep this in FilterListWithAND for abstracting the transformCell() in FilterListBase. 045 subFiltersIncludedCell = new ArrayList<>(Collections.nCopies(filters.size(), true)); 046 } 047 048 @Override 049 public void addFilterLists(List<Filter> filters) { 050 if (checkAndGetReversed(filters, isReversed()) != isReversed()) { 051 throw new IllegalArgumentException("Filters in the list must have the same reversed flag"); 052 } 053 this.filters.addAll(filters); 054 this.subFiltersIncludedCell.addAll(Collections.nCopies(filters.size(), true)); 055 } 056 057 @Override 058 protected String formatLogFilters(List<Filter> logFilters) { 059 return String.format("FilterList AND (%d/%d): %s", logFilters.size(), this.size(), 060 logFilters.toString()); 061 } 062 063 /** 064 * FilterList with MUST_PASS_ALL choose the maximal forward step among sub-filters in filter list. 065 * Let's call it: The Maximal Step Rule. So if filter-A in filter list return INCLUDE and filter-B 066 * in filter list return INCLUDE_AND_NEXT_COL, then the filter list should return 067 * INCLUDE_AND_NEXT_COL. For SEEK_NEXT_USING_HINT, it's more special, and in method 068 * filterCellWithMustPassAll(), if any sub-filter return SEEK_NEXT_USING_HINT, then our filter 069 * list will return SEEK_NEXT_USING_HINT. so we don't care about the SEEK_NEXT_USING_HINT here. 070 * <br/> 071 * <br/> 072 * The jump step will be: 073 * 074 * <pre> 075 * INCLUDE < SKIP < INCLUDE_AND_NEXT_COL < NEXT_COL < INCLUDE_AND_SEEK_NEXT_ROW < NEXT_ROW < SEEK_NEXT_USING_HINT 076 * </pre> 077 * 078 * Here, we have the following map to describe The Maximal Step Rule. if current return code (for 079 * previous sub-filters in filter list) is <strong>ReturnCode</strong>, and current filter returns 080 * <strong>localRC</strong>, then we should return map[ReturnCode][localRC] for the merged result, 081 * according to The Maximal Step Rule. <br/> 082 * 083 * <pre> 084 * LocalCode\ReturnCode INCLUDE INCLUDE_AND_NEXT_COL INCLUDE_AND_SEEK_NEXT_ROW SKIP NEXT_COL NEXT_ROW SEEK_NEXT_USING_HINT 085 * INCLUDE INCLUDE INCLUDE_AND_NEXT_COL INCLUDE_AND_SEEK_NEXT_ROW SKIP NEXT_COL NEXT_ROW SEEK_NEXT_USING_HINT 086 * 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 087 * 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 088 * SKIP SKIP NEXT_COL NEXT_ROW SKIP NEXT_COL NEXT_ROW SEEK_NEXT_USING_HINT 089 * NEXT_COL NEXT_COL NEXT_COL NEXT_ROW NEXT_COL NEXT_COL NEXT_ROW SEEK_NEXT_USING_HINT 090 * NEXT_ROW NEXT_ROW NEXT_ROW NEXT_ROW NEXT_ROW NEXT_ROW NEXT_ROW SEEK_NEXT_USING_HINT 091 * 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 092 * </pre> 093 * 094 * @param rc Return code which is calculated by previous sub-filter(s) in filter list. 095 * @param localRC Return code of the current sub-filter in filter list. 096 * @return Return code which is merged by the return code of previous sub-filter(s) and the return 097 * code of current sub-filter. 098 */ 099 private ReturnCode mergeReturnCode(ReturnCode rc, ReturnCode localRC) { 100 if (rc == ReturnCode.SEEK_NEXT_USING_HINT) { 101 return ReturnCode.SEEK_NEXT_USING_HINT; 102 } 103 switch (localRC) { 104 case SEEK_NEXT_USING_HINT: 105 return ReturnCode.SEEK_NEXT_USING_HINT; 106 case INCLUDE: 107 return rc; 108 case INCLUDE_AND_NEXT_COL: 109 if (isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL)) { 110 return ReturnCode.INCLUDE_AND_NEXT_COL; 111 } 112 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW)) { 113 return ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW; 114 } 115 if (isInReturnCodes(rc, ReturnCode.SKIP, ReturnCode.NEXT_COL)) { 116 return ReturnCode.NEXT_COL; 117 } 118 if (isInReturnCodes(rc, ReturnCode.NEXT_ROW)) { 119 return ReturnCode.NEXT_ROW; 120 } 121 break; 122 case INCLUDE_AND_SEEK_NEXT_ROW: 123 if (isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL, 124 ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW)) { 125 return ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW; 126 } 127 if (isInReturnCodes(rc, ReturnCode.SKIP, ReturnCode.NEXT_COL, ReturnCode.NEXT_ROW)) { 128 return ReturnCode.NEXT_ROW; 129 } 130 break; 131 case SKIP: 132 if (isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.SKIP)) { 133 return ReturnCode.SKIP; 134 } 135 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_NEXT_COL, ReturnCode.NEXT_COL)) { 136 return ReturnCode.NEXT_COL; 137 } 138 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW, ReturnCode.NEXT_ROW)) { 139 return ReturnCode.NEXT_ROW; 140 } 141 break; 142 case NEXT_COL: 143 if (isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL, ReturnCode.SKIP, 144 ReturnCode.NEXT_COL)) { 145 return ReturnCode.NEXT_COL; 146 } 147 if (isInReturnCodes(rc, ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW, ReturnCode.NEXT_ROW)) { 148 return ReturnCode.NEXT_ROW; 149 } 150 break; 151 case NEXT_ROW: 152 return ReturnCode.NEXT_ROW; 153 } 154 throw new IllegalStateException( 155 "Received code is not valid. rc: " + rc + ", localRC: " + localRC); 156 } 157 158 private boolean isIncludeRelatedReturnCode(ReturnCode rc) { 159 return isInReturnCodes(rc, ReturnCode.INCLUDE, ReturnCode.INCLUDE_AND_NEXT_COL, 160 ReturnCode.INCLUDE_AND_SEEK_NEXT_ROW); 161 } 162 163 @Override 164 public ReturnCode filterCell(Cell c) throws IOException { 165 if (isEmpty()) { 166 return ReturnCode.INCLUDE; 167 } 168 ReturnCode rc = ReturnCode.INCLUDE; 169 this.seekHintFilters.clear(); 170 for (int i = 0, n = filters.size(); i < n; i++) { 171 Filter filter = filters.get(i); 172 if (filter.filterAllRemaining()) { 173 return ReturnCode.NEXT_ROW; 174 } 175 ReturnCode localRC; 176 localRC = filter.filterCell(c); 177 if (localRC == ReturnCode.SEEK_NEXT_USING_HINT) { 178 seekHintFilters.add(filter); 179 } 180 rc = mergeReturnCode(rc, localRC); 181 // Only when rc is INCLUDE* case, we should pass the cell to the following sub-filters. 182 // otherwise we may mess up the global state (such as offset, count..) in the following 183 // sub-filters. (HBASE-20565) 184 if (!isIncludeRelatedReturnCode(rc)) { 185 return rc; 186 } 187 } 188 if (!seekHintFilters.isEmpty()) { 189 return ReturnCode.SEEK_NEXT_USING_HINT; 190 } 191 return rc; 192 } 193 194 @Override 195 public void reset() throws IOException { 196 for (int i = 0, n = filters.size(); i < n; i++) { 197 filters.get(i).reset(); 198 } 199 seekHintFilters.clear(); 200 } 201 202 @Override 203 public boolean filterRowKey(byte[] rowKey, int offset, int length) throws IOException { 204 if (isEmpty()) { 205 return super.filterRowKey(rowKey, offset, length); 206 } 207 boolean retVal = false; 208 for (int i = 0, n = filters.size(); i < n; i++) { 209 Filter filter = filters.get(i); 210 if (filter.filterAllRemaining() || filter.filterRowKey(rowKey, offset, length)) { 211 retVal = true; 212 } 213 } 214 return retVal; 215 } 216 217 @Override 218 public boolean filterRowKey(Cell firstRowCell) throws IOException { 219 if (isEmpty()) { 220 return super.filterRowKey(firstRowCell); 221 } 222 boolean retVal = false; 223 for (int i = 0, n = filters.size(); i < n; i++) { 224 Filter filter = filters.get(i); 225 if (filter.filterAllRemaining() || filter.filterRowKey(firstRowCell)) { 226 // Can't just return true here, because there are some filters (such as PrefixFilter) which 227 // will catch the row changed event by filterRowKey(). If we return early here, those 228 // filters will have no chance to update their row state. 229 retVal = true; 230 } 231 } 232 return retVal; 233 } 234 235 @Override 236 public boolean filterAllRemaining() throws IOException { 237 if (isEmpty()) { 238 return super.filterAllRemaining(); 239 } 240 for (int i = 0, n = filters.size(); i < n; i++) { 241 if (filters.get(i).filterAllRemaining()) { 242 return true; 243 } 244 } 245 return false; 246 } 247 248 @Override 249 public boolean filterRow() throws IOException { 250 if (isEmpty()) { 251 return super.filterRow(); 252 } 253 for (int i = 0, n = filters.size(); i < n; i++) { 254 Filter filter = filters.get(i); 255 if (filter.filterRow()) { 256 return true; 257 } 258 } 259 return false; 260 } 261 262 @Override 263 public Cell getNextCellHint(Cell currentCell) throws IOException { 264 if (isEmpty()) { 265 return super.getNextCellHint(currentCell); 266 } 267 Cell maxHint = null; 268 for (Filter filter : seekHintFilters) { 269 if (filter.filterAllRemaining()) { 270 continue; 271 } 272 Cell curKeyHint = filter.getNextCellHint(currentCell); 273 if (maxHint == null) { 274 maxHint = curKeyHint; 275 continue; 276 } 277 if (this.compareCell(maxHint, curKeyHint) < 0) { 278 maxHint = curKeyHint; 279 } 280 } 281 return maxHint; 282 } 283 284 @Override 285 public boolean equals(Object obj) { 286 if (!(obj instanceof FilterListWithAND)) { 287 return false; 288 } 289 if (this == obj) { 290 return true; 291 } 292 FilterListWithAND f = (FilterListWithAND) obj; 293 return this.filters.equals(f.getFilters()) && this.seekHintFilters.equals(f.seekHintFilters); 294 } 295 296 @Override 297 public int hashCode() { 298 return Objects.hash(this.seekHintFilters, this.filters); 299 } 300}