Uploaded image for project: 'OpenDJ'
  1. OpenDJ
  2. OPENDJ-1864

Ordering matching rules should reuse equality indexes where possible


    • Type: Improvement
    • Status: Done
    • Priority: Blocker
    • Resolution: Fixed
    • Affects Version/s: 3.0.0
    • Fix Version/s: 3.0.0, 2.8.0
    • Component/s: backends
    • Labels:


      I thought I'd already created an issue for this, but I can't find it.

      Now that OpenDJ 3 is using the SDK for indexing and filtering we should be able to provide the ability to index an attribute for both equality and ordering using the same index, as long as both matching rules are compatible.

      Let's consider the case where we want to support indexed searches of the "cn" attribute (DirectoryString) for both equality and ordering. This involves two matching rules CaseIgnoreEqualityMatchingRuleImpl and CaseIgnoreOrderingMatchingRuleImpl.

      When we index for equality we invoke CaseIgnoreEqualityMatchingRuleImpl.getIndexers() which returns an indexer which creates an index with ID "equality". However, the ordering matching rule creates an index with ID "ordering". In other words, if we index for both equality and ordering we will end up with two indexes containing the same data because both matching rules have the same normalization algorithm.

      When executing searches the backend constructs an index query derived from the search filter. For each filter element we obtain the associated matching rule and construct an Assertion, from which an index query is created using the method Assertion.createIndexQuery(...). Matching rule implementations use the provided IndexQueryFactory to create the index query, passing in an appropriate index ID to the factory methods, e.g. and ordering matching rule implementation will typically call IndexQueryFactory.createRangeMatchQuery("ordering", ...).

      It is worth pointing out that sometimes we might want to optimize equality indexes by perform key hashing (see OPENDJ-1199). This process results in smaller keys but sacrifices key-order, meaning that the index cannot be used for the sort of range queries required by ordering matching rules and substring matching rules. In this case I suggest that key hashing be implemented as a MatchingRuleImpl decorator which returns a different index ID, e.g. "equalityHash" instead of "equality". This will prevent inappropriate re-use of the index.

      Suggested fix:

      • identify the equality/ordering matching rule pairs where re-use is possible
      • ensure that each matching rule generates an index with the same ID and same content
      • ensure that each matching rule assertion implementation constructs queries against the common index
      • ensure that the backend implementation performs reference counting of indexes to avoid the case where an attribute is indexed for both equality and ordering: disabling equality indexing should not impact ordering indexing.

      Note also how substring indexes can also re-use equality/ordering indexes for initial substring searches. I think this is already supported in the SDK.


          Issue Links



              • Assignee:
                ylecaillez Yannick Lecaillez
                matthew Matthew Swift
                Dev Assignee:
                Yannick Lecaillez
              • Votes:
                0 Vote for this issue
                0 Start watching this issue


                • Created: