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    }