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