Uploaded image for project: 'Lucene - Core'
  1. Lucene - Core
  2. LUCENE-8041

All Fields.terms(fld) impls should be O(1) not O(log(N))

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Resolved
    • Priority: Major
    • Resolution: Won't Fix
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: None
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      I've seen apps that have a good number of fields – hundreds. The O(log(N)) of TreeMap definitely shows up in a profiler; sometimes 20% of search time, if I recall. There are many Field implementations that are impacted... in part because Fields is the base class of FieldsProducer.

      As an aside, I hope Fields to go away some day; FieldsProducer should be TermsProducer and not have an iterator of fields. If DocValuesProducer doesn't have this then why should the terms index part of our API have it? If we did this then the issue here would be a simple transition to a HashMap.

      Or maybe we can switch to HashMap and relax the definition of Fields.iterator to not necessarily be sorted?

      Perhaps the fix can be a relatively simple conversion over to LinkedHashMap in many cases if we can assume when we initialize these internal maps that we consume them in sorted order to begin with.

        Attachments

        1. LUCENE-8041-LinkedHashMap.patch
          38 kB
          Huy Le
        2. LUCENE-8041.patch
          3 kB
          Nhat Nguyen

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                dsmiley David Smiley
              • Votes:
                3 Vote for this issue
                Watchers:
                10 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: