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 }