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}