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(Cell firstRowCell) throws IOException { 204 if (isEmpty()) { 205 return super.filterRowKey(firstRowCell); 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(firstRowCell)) { 211 // Can't just return true here, because there are some filters (such as PrefixFilter) which 212 // will catch the row changed event by filterRowKey(). If we return early here, those 213 // filters will have no chance to update their row state. 214 retVal = true; 215 } 216 } 217 return retVal; 218 } 219 220 @Override 221 public boolean filterAllRemaining() throws IOException { 222 if (isEmpty()) { 223 return super.filterAllRemaining(); 224 } 225 for (int i = 0, n = filters.size(); i < n; i++) { 226 if (filters.get(i).filterAllRemaining()) { 227 return true; 228 } 229 } 230 return false; 231 } 232 233 @Override 234 public boolean filterRow() throws IOException { 235 if (isEmpty()) { 236 return super.filterRow(); 237 } 238 for (int i = 0, n = filters.size(); i < n; i++) { 239 Filter filter = filters.get(i); 240 if (filter.filterRow()) { 241 return true; 242 } 243 } 244 return false; 245 } 246 247 @Override 248 public Cell getNextCellHint(Cell currentCell) throws IOException { 249 if (isEmpty()) { 250 return super.getNextCellHint(currentCell); 251 } 252 Cell maxHint = null; 253 for (Filter filter : seekHintFilters) { 254 if (filter.filterAllRemaining()) { 255 continue; 256 } 257 Cell curKeyHint = filter.getNextCellHint(currentCell); 258 if (maxHint == null) { 259 maxHint = curKeyHint; 260 continue; 261 } 262 if (this.compareCell(maxHint, curKeyHint) < 0) { 263 maxHint = curKeyHint; 264 } 265 } 266 return maxHint; 267 } 268 269 @Override 270 public boolean equals(Object obj) { 271 if (!(obj instanceof FilterListWithAND)) { 272 return false; 273 } 274 if (this == obj) { 275 return true; 276 } 277 FilterListWithAND f = (FilterListWithAND) obj; 278 return this.filters.equals(f.getFilters()) && this.seekHintFilters.equals(f.seekHintFilters); 279 } 280 281 @Override 282 public int hashCode() { 283 return Objects.hash(this.seekHintFilters, this.filters); 284 } 285}