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 010 * trunk/opends/resource/legal-notices/OpenDS.LICENSE 011 * or https://OpenDS.dev.java.net/OpenDS.LICENSE. 012 * See the License for the specific language governing permissions 013 * and limitations under the License. 014 * 015 * When distributing Covered Code, include this CDDL HEADER in each 016 * file and include the License file at 017 * trunk/opends/resource/legal-notices/OpenDS.LICENSE. If applicable, 018 * add the following below this CDDL HEADER, with the fields enclosed 019 * by brackets "[]" replaced with your own identifying information: 020 * Portions Copyright [yyyy] [name of copyright owner] 021 * 022 * CDDL HEADER END 023 * 024 * 025 * Copyright 2006-2008 Sun Microsystems, Inc. 026 */ 027 package org.opends.server.backends.jeb; 028 029 import org.opends.server.core.SearchOperation; 030 import org.opends.server.types.AttributeType; 031 import org.opends.server.types.FilterType; 032 import org.opends.server.types.SearchFilter; 033 034 import java.util.ArrayList; 035 import java.util.HashMap; 036 import java.util.Map; 037 038 /** 039 * An index filter is used to apply a search operation to a set of indexes 040 * to generate a set of candidate entries. 041 */ 042 public class IndexFilter 043 { 044 /** 045 * Stop processing the filter against the indexes when the 046 * number of candidates is smaller than this value. 047 */ 048 public static final int FILTER_CANDIDATE_THRESHOLD = 10; 049 050 /** 051 * The entry entryContainer holding the attribute indexes. 052 */ 053 private EntryContainer entryContainer; 054 055 /** 056 * The search operation provides the search base, scope and filter. 057 * It can also be checked periodically for cancellation. 058 */ 059 private SearchOperation searchOp; 060 061 /** 062 * A string builder to hold a diagnostic string which helps determine 063 * how the indexed contributed to the search operation. 064 */ 065 private StringBuilder buffer; 066 067 /** 068 * Construct an index filter for a search operation. 069 * 070 * @param entryContainer The entry entryContainer. 071 * @param searchOp The search operation to be evaluated. 072 * 073 * @param debugBuilder If not null, a diagnostic string will be written 074 * which will help determine how the indexes contributed 075 * to this search. 076 */ 077 public IndexFilter(EntryContainer entryContainer, 078 SearchOperation searchOp, 079 StringBuilder debugBuilder) 080 { 081 this.entryContainer = entryContainer; 082 this.searchOp = searchOp; 083 this.buffer = debugBuilder; 084 } 085 086 /** 087 * Evaluate the search operation against the indexes. 088 * 089 * @return A set of entry IDs representing candidate entries. 090 */ 091 public EntryIDSet evaluate() 092 { 093 if (buffer != null) 094 { 095 buffer.append("filter="); 096 } 097 return evaluateFilter(searchOp.getFilter()); 098 } 099 100 /** 101 * Evaluate a search filter against the indexes. 102 * 103 * @param filter The search filter to be evaluated. 104 * @return A set of entry IDs representing candidate entries. 105 */ 106 private EntryIDSet evaluateFilter(SearchFilter filter) 107 { 108 EntryIDSet candidates; 109 switch (filter.getFilterType()) 110 { 111 case AND: 112 if (buffer != null) 113 { 114 buffer.append("(&"); 115 } 116 candidates = evaluateLogicalAndFilter(filter); 117 if (buffer != null) 118 { 119 buffer.append(")"); 120 } 121 break; 122 123 case OR: 124 if (buffer != null) 125 { 126 buffer.append("(|"); 127 } 128 candidates = evaluateLogicalOrFilter(filter); 129 if (buffer != null) 130 { 131 buffer.append(")"); 132 } 133 break; 134 135 case EQUALITY: 136 if (buffer != null) 137 { 138 filter.toString(buffer); 139 } 140 candidates = evaluateEqualityFilter(filter); 141 break; 142 143 case GREATER_OR_EQUAL: 144 if (buffer != null) 145 { 146 filter.toString(buffer); 147 } 148 candidates = evaluateGreaterOrEqualFilter(filter); 149 break; 150 151 case SUBSTRING: 152 if (buffer != null) 153 { 154 filter.toString(buffer); 155 } 156 candidates = evaluateSubstringFilter(filter); 157 break; 158 159 case LESS_OR_EQUAL: 160 if (buffer != null) 161 { 162 filter.toString(buffer); 163 } 164 candidates = evaluateLessOrEqualFilter(filter); 165 break; 166 167 case PRESENT: 168 if (buffer != null) 169 { 170 filter.toString(buffer); 171 } 172 candidates = evaluatePresenceFilter(filter); 173 break; 174 175 case APPROXIMATE_MATCH: 176 if (buffer != null) 177 { 178 filter.toString(buffer); 179 } 180 candidates = evaluateApproximateFilter(filter); 181 break; 182 183 case NOT: 184 case EXTENSIBLE_MATCH: 185 default: 186 if (buffer != null) 187 { 188 filter.toString(buffer); 189 } 190 //NYI 191 candidates = new EntryIDSet(); 192 break; 193 } 194 195 if (buffer != null) 196 { 197 candidates.toString(buffer); 198 } 199 return candidates; 200 } 201 202 /** 203 * Evaluate a logical AND search filter against the indexes. 204 * 205 * @param andFilter The AND search filter to be evaluated. 206 * @return A set of entry IDs representing candidate entries. 207 */ 208 private EntryIDSet evaluateLogicalAndFilter(SearchFilter andFilter) 209 { 210 // Start off with an undefined set. 211 EntryIDSet results = new EntryIDSet(); 212 213 // Put the slow range filters (greater-or-equal, less-or-equal) 214 // into a hash map, the faster components (equality, presence, approx) 215 // into one list and the remainder into another list. 216 217 ArrayList<SearchFilter> fastComps = new ArrayList<SearchFilter>(); 218 ArrayList<SearchFilter> otherComps = new ArrayList<SearchFilter>(); 219 HashMap<AttributeType, ArrayList<SearchFilter>> rangeComps = 220 new HashMap<AttributeType, ArrayList<SearchFilter>>(); 221 222 for (SearchFilter filter : andFilter.getFilterComponents()) 223 { 224 FilterType filterType = filter.getFilterType(); 225 if (filterType == FilterType.GREATER_OR_EQUAL || 226 filterType == FilterType.LESS_OR_EQUAL) 227 { 228 ArrayList<SearchFilter> rangeList; 229 rangeList = rangeComps.get(filter.getAttributeType()); 230 if (rangeList == null) 231 { 232 rangeList = new ArrayList<SearchFilter>(); 233 rangeComps.put(filter.getAttributeType(), rangeList); 234 } 235 rangeList.add(filter); 236 } 237 else if (filterType == FilterType.EQUALITY || 238 filterType == FilterType.PRESENT || 239 filterType == FilterType.APPROXIMATE_MATCH) 240 { 241 fastComps.add(filter); 242 } 243 else 244 { 245 otherComps.add(filter); 246 } 247 } 248 249 // First, process the fast components. 250 for (SearchFilter filter : fastComps) 251 { 252 EntryIDSet set = evaluateFilter(filter); 253 254 if (retainAll(results, set)) 255 { 256 return results; 257 } 258 } 259 260 // Next, process the other (non-range) components. 261 for (SearchFilter filter : otherComps) 262 { 263 EntryIDSet set = evaluateFilter(filter); 264 265 if (retainAll(results, set)) 266 { 267 return results; 268 } 269 } 270 271 // Next, process range component pairs like (cn>=A)(cn<=B). 272 273 if (rangeComps.isEmpty()) 274 { 275 return results; 276 } 277 278 ArrayList<SearchFilter> remainComps = new ArrayList<SearchFilter>(); 279 for (Map.Entry<AttributeType, ArrayList<SearchFilter>> rangeEntry : 280 rangeComps.entrySet()) 281 { 282 ArrayList<SearchFilter> rangeList = rangeEntry.getValue(); 283 if (rangeList.size() == 2) 284 { 285 SearchFilter a = rangeList.get(0); 286 SearchFilter b = rangeList.get(1); 287 288 AttributeIndex attributeIndex = 289 entryContainer.getAttributeIndex(rangeEntry.getKey()); 290 if (attributeIndex == null) 291 { 292 continue; 293 } 294 295 if (a.getFilterType() == FilterType.GREATER_OR_EQUAL && 296 b.getFilterType() == FilterType.LESS_OR_EQUAL) 297 { 298 // Like (cn>=A)(cn<=B). 299 EntryIDSet set; 300 set = attributeIndex.evaluateBoundedRange(a.getAssertionValue(), 301 b.getAssertionValue()); 302 303 if (buffer != null) 304 { 305 a.toString(buffer); 306 b.toString(buffer); 307 set.toString(buffer); 308 } 309 310 if (retainAll(results, set)) 311 { 312 return results; 313 } 314 continue; 315 } 316 else if (a.getFilterType() == FilterType.LESS_OR_EQUAL && 317 b.getFilterType() == FilterType.GREATER_OR_EQUAL) 318 { 319 // Like (cn<=A)(cn>=B). 320 EntryIDSet set; 321 set = attributeIndex.evaluateBoundedRange(b.getAssertionValue(), 322 a.getAssertionValue()); 323 324 if (buffer != null) 325 { 326 a.toString(buffer); 327 b.toString(buffer); 328 set.toString(buffer); 329 } 330 331 if (retainAll(results, set)) 332 { 333 return results; 334 } 335 continue; 336 } 337 } 338 339 // Add to the remaining range components to be processed. 340 for (SearchFilter filter : rangeList) 341 { 342 remainComps.add(filter); 343 } 344 } 345 346 // Finally, process the remaining slow range components. 347 for (SearchFilter filter : remainComps) 348 { 349 EntryIDSet set = evaluateFilter(filter); 350 if (retainAll(results, set)) 351 { 352 return results; 353 } 354 } 355 356 return results; 357 } 358 359 /** 360 * Retain all IDs in a given set that appear in a second set. 361 * 362 * @param a The set of entry IDs to be updated. 363 * @param b Only those IDs that are in this set are retained. 364 * @return true if the number of IDs in the updated set is now below 365 * the filter candidate threshold. 366 */ 367 private boolean retainAll(EntryIDSet a, EntryIDSet b) 368 { 369 a.retainAll(b); 370 371 // We may have reached the point of diminishing returns where 372 // it is quicker to stop now and process the current small number of 373 // candidates. 374 if (a.isDefined() && a.size() <= FILTER_CANDIDATE_THRESHOLD) 375 { 376 return true; 377 } 378 379 return false; 380 } 381 382 /** 383 * Evaluate a logical OR search filter against the indexes. 384 * 385 * @param orFilter The OR search filter to be evaluated. 386 * @return A set of entry IDs representing candidate entries. 387 */ 388 private EntryIDSet evaluateLogicalOrFilter(SearchFilter orFilter) 389 { 390 ArrayList<EntryIDSet> candidateSets = new ArrayList<EntryIDSet>( 391 orFilter.getFilterComponents().size()); 392 393 for (SearchFilter filter : orFilter.getFilterComponents()) 394 { 395 EntryIDSet set = evaluateFilter(filter); 396 if (!set.isDefined()) 397 { 398 // There is no point continuing. 399 return set; 400 } 401 candidateSets.add(set); 402 } 403 return EntryIDSet.unionOfSets(candidateSets, false); 404 } 405 406 /** 407 * Evaluate an equality filter against the indexes. 408 * 409 * @param equalityFilter The equality filter to be evaluated. 410 * @return A set of entry IDs representing candidate entries. 411 */ 412 private EntryIDSet evaluateEqualityFilter(SearchFilter equalityFilter) 413 { 414 EntryIDSet candidates; 415 AttributeIndex attributeIndex = 416 entryContainer.getAttributeIndex(equalityFilter.getAttributeType()); 417 if (attributeIndex == null) 418 { 419 candidates = new EntryIDSet(); 420 } 421 else 422 { 423 candidates = 424 attributeIndex.evaluateEqualityFilter(equalityFilter, buffer); 425 } 426 return candidates; 427 } 428 429 /** 430 * Evaluate a presence filter against the indexes. 431 * 432 * @param filter The presence filter to be evaluated. 433 * @return A set of entry IDs representing candidate entries. 434 */ 435 private EntryIDSet evaluatePresenceFilter(SearchFilter filter) 436 { 437 EntryIDSet candidates; 438 AttributeIndex attributeIndex = 439 entryContainer.getAttributeIndex(filter.getAttributeType()); 440 if (attributeIndex == null) 441 { 442 candidates = new EntryIDSet(); 443 } 444 else 445 { 446 candidates = attributeIndex.evaluatePresenceFilter(filter, buffer); 447 } 448 return candidates; 449 } 450 451 /** 452 * Evaluate a greater-or-equal filter against the indexes. 453 * 454 * @param filter The greater-or-equal filter to be evaluated. 455 * @return A set of entry IDs representing candidate entries. 456 */ 457 private EntryIDSet evaluateGreaterOrEqualFilter(SearchFilter filter) 458 { 459 EntryIDSet candidates; 460 AttributeIndex attributeIndex = 461 entryContainer.getAttributeIndex(filter.getAttributeType()); 462 if (attributeIndex == null) 463 { 464 candidates = new EntryIDSet(); 465 } 466 else 467 { 468 candidates = attributeIndex.evaluateGreaterOrEqualFilter(filter, buffer); 469 } 470 return candidates; 471 } 472 473 /** 474 * Evaluate a less-or-equal filter against the indexes. 475 * 476 * @param filter The less-or-equal filter to be evaluated. 477 * @return A set of entry IDs representing candidate entries. 478 */ 479 private EntryIDSet evaluateLessOrEqualFilter(SearchFilter filter) 480 { 481 EntryIDSet candidates; 482 AttributeIndex attributeIndex = 483 entryContainer.getAttributeIndex(filter.getAttributeType()); 484 if (attributeIndex == null) 485 { 486 candidates = new EntryIDSet(); 487 } 488 else 489 { 490 candidates = attributeIndex.evaluateLessOrEqualFilter(filter, buffer); 491 } 492 return candidates; 493 } 494 495 /** 496 * Evaluate a substring filter against the indexes. 497 * 498 * @param filter The substring filter to be evaluated. 499 * @return A set of entry IDs representing candidate entries. 500 */ 501 private EntryIDSet evaluateSubstringFilter(SearchFilter filter) 502 { 503 EntryIDSet candidates; 504 AttributeIndex attributeIndex = 505 entryContainer.getAttributeIndex(filter.getAttributeType()); 506 if (attributeIndex == null) 507 { 508 candidates = new EntryIDSet(); 509 } 510 else 511 { 512 candidates = attributeIndex.evaluateSubstringFilter(filter, buffer); 513 } 514 return candidates; 515 } 516 517 /** 518 * Evaluate an approximate filter against the indexes. 519 * 520 * @param approximateFilter The approximate filter to be evaluated. 521 * @return A set of entry IDs representing candidate entries. 522 */ 523 private EntryIDSet evaluateApproximateFilter(SearchFilter approximateFilter) 524 { 525 EntryIDSet candidates; 526 AttributeIndex attributeIndex = 527 entryContainer.getAttributeIndex(approximateFilter.getAttributeType()); 528 if (attributeIndex == null) 529 { 530 candidates = new EntryIDSet(); 531 } 532 else 533 { 534 candidates = 535 attributeIndex.evaluateApproximateFilter(approximateFilter, buffer); 536 } 537 return candidates; 538 } 539 540 }