001/* 002 * CDDL HEADER START 003 * 004 * The contents of this file are subject to the terms of the 005 * Common Development and Distribution License, Version 1.0 only 006 * (the "License"). You may not use this file except in compliance 007 * with the License. 008 * 009 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt 010 * or http://forgerock.org/license/CDDLv1.0.html. 011 * See the License for the specific language governing permissions 012 * and limitations under the License. 013 * 014 * When distributing Covered Code, include this CDDL HEADER in each 015 * file and include the License file at legal-notices/CDDLv1_0.txt. 016 * If applicable, add the following below this CDDL HEADER, with the 017 * fields enclosed by brackets "[]" replaced with your own identifying 018 * information: 019 * Portions Copyright [yyyy] [name of copyright owner] 020 * 021 * CDDL HEADER END 022 * 023 * 024 * Copyright 2006-2010 Sun Microsystems, Inc. 025 * Portions copyright 2011-2015 ForgeRock AS 026 * 027 */ 028package org.opends.server.backends.jeb; 029 030import java.util.ArrayList; 031import java.util.HashMap; 032import java.util.Map; 033 034import org.opends.server.backends.jeb.AttributeIndex.IndexFilterType; 035import org.opends.server.core.SearchOperation; 036import org.opends.server.types.AttributeType; 037import org.opends.server.types.FilterType; 038import org.opends.server.types.SearchFilter; 039 040import static org.opends.messages.BackendMessages.*; 041 042/** 043 * An index filter is used to apply a search operation to a set of indexes 044 * to generate a set of candidate entries. 045 */ 046public class IndexFilter 047{ 048 /** 049 * Stop processing the filter against the indexes when the 050 * number of candidates is smaller than this value. 051 */ 052 public static final int FILTER_CANDIDATE_THRESHOLD = 10; 053 054 /** 055 * The entry entryContainer holding the attribute indexes. 056 */ 057 private final EntryContainer entryContainer; 058 059 /** 060 * The search operation provides the search base, scope and filter. 061 * It can also be checked periodically for cancellation. 062 */ 063 private final SearchOperation searchOp; 064 065 /** 066 * A string builder to hold a diagnostic string which helps determine 067 * how the indexed contributed to the search operation. 068 */ 069 private final StringBuilder buffer; 070 071 private final DatabaseEnvironmentMonitor monitor; 072 073 /** 074 * Construct an index filter for a search operation. 075 * 076 * @param entryContainer The entry entryContainer. 077 * @param searchOp The search operation to be evaluated. 078 * @param monitor The monitor to gather filter usage stats. 079 * 080 * @param debugBuilder If not null, a diagnostic string will be written 081 * which will help determine how the indexes contributed 082 * to this search. 083 */ 084 public IndexFilter(EntryContainer entryContainer, 085 SearchOperation searchOp, 086 StringBuilder debugBuilder, 087 DatabaseEnvironmentMonitor monitor) 088 { 089 this.entryContainer = entryContainer; 090 this.searchOp = searchOp; 091 this.buffer = debugBuilder; 092 this.monitor = monitor; 093 } 094 095 /** 096 * Evaluate the search operation against the indexes. 097 * 098 * @return A set of entry IDs representing candidate entries. 099 */ 100 public EntryIDSet evaluate() 101 { 102 if (buffer != null) 103 { 104 buffer.append("filter="); 105 } 106 return evaluateFilter(searchOp.getFilter()); 107 } 108 109 /** 110 * Evaluate a search filter against the indexes. 111 * 112 * @param filter The search filter to be evaluated. 113 * @return A set of entry IDs representing candidate entries. 114 */ 115 private EntryIDSet evaluateFilter(SearchFilter filter) 116 { 117 EntryIDSet candidates = evaluate(filter); 118 if (buffer != null) 119 { 120 candidates.toString(buffer); 121 } 122 return candidates; 123 } 124 125 private EntryIDSet evaluate(SearchFilter filter) 126 { 127 switch (filter.getFilterType()) 128 { 129 case AND: 130 if (buffer != null) 131 { 132 buffer.append("(&"); 133 } 134 final EntryIDSet res1 = evaluateLogicalAndFilter(filter); 135 if (buffer != null) 136 { 137 buffer.append(")"); 138 } 139 return res1; 140 141 case OR: 142 if (buffer != null) 143 { 144 buffer.append("(|"); 145 } 146 final EntryIDSet res2 = evaluateLogicalOrFilter(filter); 147 if (buffer != null) 148 { 149 buffer.append(")"); 150 } 151 return res2; 152 153 case EQUALITY: 154 return evaluateFilterWithDiagnostic(IndexFilterType.EQUALITY, filter); 155 156 case GREATER_OR_EQUAL: 157 return evaluateFilterWithDiagnostic(IndexFilterType.GREATER_OR_EQUAL, filter); 158 159 case SUBSTRING: 160 return evaluateFilterWithDiagnostic(IndexFilterType.SUBSTRING, filter); 161 162 case LESS_OR_EQUAL: 163 return evaluateFilterWithDiagnostic(IndexFilterType.LESS_OR_EQUAL, filter); 164 165 case PRESENT: 166 return evaluateFilterWithDiagnostic(IndexFilterType.PRESENCE, filter); 167 168 case APPROXIMATE_MATCH: 169 return evaluateFilterWithDiagnostic(IndexFilterType.APPROXIMATE, filter); 170 171 case EXTENSIBLE_MATCH: 172 if (buffer!= null) 173 { 174 filter.toString(buffer); 175 } 176 return evaluateExtensibleFilter(filter); 177 178 case NOT: 179 default: 180 if (buffer != null) 181 { 182 filter.toString(buffer); 183 } 184 //NYI 185 return new EntryIDSet(); 186 } 187 } 188 189 /** 190 * Evaluate a logical AND search filter against the indexes. 191 * 192 * @param andFilter The AND search filter to be evaluated. 193 * @return A set of entry IDs representing candidate entries. 194 */ 195 private EntryIDSet evaluateLogicalAndFilter(SearchFilter andFilter) 196 { 197 // Start off with an undefined set. 198 EntryIDSet results = new EntryIDSet(); 199 200 // Put the slow range filters (greater-or-equal, less-or-equal) 201 // into a hash map, the faster components (equality, presence, approx) 202 // into one list and the remainder into another list. 203 204 ArrayList<SearchFilter> fastComps = new ArrayList<>(); 205 ArrayList<SearchFilter> otherComps = new ArrayList<>(); 206 HashMap<AttributeType, ArrayList<SearchFilter>> rangeComps = new HashMap<>(); 207 208 for (SearchFilter filter : andFilter.getFilterComponents()) 209 { 210 FilterType filterType = filter.getFilterType(); 211 if (filterType == FilterType.GREATER_OR_EQUAL || 212 filterType == FilterType.LESS_OR_EQUAL) 213 { 214 ArrayList<SearchFilter> rangeList; 215 rangeList = rangeComps.get(filter.getAttributeType()); 216 if (rangeList == null) 217 { 218 rangeList = new ArrayList<>(); 219 rangeComps.put(filter.getAttributeType(), rangeList); 220 } 221 rangeList.add(filter); 222 } 223 else if (filterType == FilterType.EQUALITY || 224 filterType == FilterType.PRESENT || 225 filterType == FilterType.APPROXIMATE_MATCH) 226 { 227 fastComps.add(filter); 228 } 229 else 230 { 231 otherComps.add(filter); 232 } 233 } 234 235 // First, process the fast components. 236 if (evaluateFilters(results, fastComps) 237 // Next, process the other (non-range) components. 238 || evaluateFilters(results, otherComps) 239 // Are there any range component pairs like (cn>=A)(cn<=B) ? 240 || rangeComps.isEmpty()) 241 { 242 return results; 243 } 244 245 // Next, process range component pairs like (cn>=A)(cn<=B). 246 ArrayList<SearchFilter> remainComps = new ArrayList<>(); 247 for (Map.Entry<AttributeType, ArrayList<SearchFilter>> rangeEntry : rangeComps.entrySet()) 248 { 249 ArrayList<SearchFilter> rangeList = rangeEntry.getValue(); 250 if (rangeList.size() == 2) 251 { 252 SearchFilter filter1 = rangeList.get(0); 253 SearchFilter filter2 = rangeList.get(1); 254 255 AttributeIndex attributeIndex = entryContainer.getAttributeIndex(rangeEntry.getKey()); 256 if (attributeIndex == null) 257 { 258 if(monitor.isFilterUseEnabled()) 259 { 260 monitor.updateStats(SearchFilter.createANDFilter(rangeList), 261 INFO_INDEX_FILTER_INDEX_TYPE_DISABLED.get("ordering", rangeEntry.getKey().getNameOrOID())); 262 } 263 continue; 264 } 265 266 EntryIDSet set = attributeIndex.evaluateBoundedRange(filter1, filter2, buffer, monitor); 267 if(monitor.isFilterUseEnabled() && set.isDefined()) 268 { 269 monitor.updateStats(SearchFilter.createANDFilter(rangeList), set.size()); 270 } 271 if (retainAll(results, set)) 272 { 273 return results; 274 } 275 } 276 else 277 { 278 // Add to the remaining range components to be processed. 279 remainComps.addAll(rangeList); 280 } 281 } 282 283 // Finally, process the remaining slow range components. 284 evaluateFilters(results, remainComps); 285 286 return results; 287 } 288 289 private boolean evaluateFilters(EntryIDSet results, ArrayList<SearchFilter> filters) 290 { 291 for (SearchFilter filter : filters) 292 { 293 final EntryIDSet filteredSet = evaluateFilter(filter); 294 if (retainAll(results, filteredSet)) 295 { 296 return true; 297 } 298 } 299 return false; 300 } 301 302 /** 303 * Retain all IDs in a given set that appear in a second set. 304 * 305 * @param a The set of entry IDs to be updated. 306 * @param b Only those IDs that are in this set are retained. 307 * @return true if the number of IDs in the updated set is now below 308 * the filter candidate threshold. 309 */ 310 private boolean retainAll(EntryIDSet a, EntryIDSet b) 311 { 312 a.retainAll(b); 313 314 // We may have reached the point of diminishing returns where 315 // it is quicker to stop now and process the current small number of candidates. 316 return a.isDefined() && a.size() <= FILTER_CANDIDATE_THRESHOLD; 317 } 318 319 /** 320 * Evaluate a logical OR search filter against the indexes. 321 * 322 * @param orFilter The OR search filter to be evaluated. 323 * @return A set of entry IDs representing candidate entries. 324 */ 325 private EntryIDSet evaluateLogicalOrFilter(SearchFilter orFilter) 326 { 327 ArrayList<EntryIDSet> candidateSets = new ArrayList<>(orFilter.getFilterComponents().size()); 328 329 for (SearchFilter filter : orFilter.getFilterComponents()) 330 { 331 EntryIDSet set = evaluateFilter(filter); 332 if (!set.isDefined()) 333 { 334 // There is no point continuing. 335 return set; 336 } 337 candidateSets.add(set); 338 } 339 return EntryIDSet.unionOfSets(candidateSets, false); 340 } 341 342 private EntryIDSet evaluateFilterWithDiagnostic(IndexFilterType indexFilterType, SearchFilter filter) 343 { 344 if (buffer != null) 345 { 346 filter.toString(buffer); 347 } 348 return evaluateFilter(indexFilterType, filter); 349 } 350 351 private EntryIDSet evaluateFilter(IndexFilterType indexFilterType, SearchFilter filter) 352 { 353 AttributeIndex attributeIndex = entryContainer.getAttributeIndex(filter.getAttributeType()); 354 if (attributeIndex != null) 355 { 356 return attributeIndex.evaluateFilter(indexFilterType, filter, buffer, monitor); 357 } 358 359 if (monitor.isFilterUseEnabled()) 360 { 361 monitor.updateStats(filter, INFO_INDEX_FILTER_INDEX_TYPE_DISABLED.get( 362 indexFilterType.toString(), filter.getAttributeType().getNameOrOID())); 363 } 364 return new EntryIDSet(); 365 } 366 367 /** 368 * Evaluate an extensible filter against the indexes. 369 * 370 * @param extensibleFilter The extensible filter to be evaluated. 371 * @return A set of entry IDs representing candidate entries. 372 */ 373 private EntryIDSet evaluateExtensibleFilter(SearchFilter extensibleFilter) 374 { 375 if (extensibleFilter.getDNAttributes()) 376 { 377 // This will always be unindexed since the filter potentially matches 378 // entries containing the specified attribute type as well as any entry 379 // containing the attribute in its DN as part of a superior RDN. 380 return IndexQuery.createNullIndexQuery().evaluate(null); 381 } 382 383 AttributeIndex attributeIndex = entryContainer.getAttributeIndex(extensibleFilter.getAttributeType()); 384 if (attributeIndex != null) 385 { 386 return attributeIndex.evaluateExtensibleFilter(extensibleFilter, buffer, monitor); 387 } 388 return IndexQuery.createNullIndexQuery().evaluate(null); 389 } 390}