Uploaded image for project: 'IMPALA'
  1. IMPALA
  2. IMPALA-7386

CatalogObjectVersionQueue should not be a queue

    XMLWordPrintableJSON

Details

    • Bug
    • Status: Resolved
    • Major
    • Resolution: Fixed
    • Impala 3.0, Impala 2.12.0
    • Impala 3.1.0
    • Catalog
    • None
    • ghx-label-6

    Description

      CatalogObjectVersionQueue serves as a data structure to track all of the currently in-use versions of the various objects in the catalog. The main operations it needs are add(version), remove(version), and minVersion(). The current implementation improperly uses a priority queue data structure, which has O runtime for remove(version). Instead we should use a tree-based multiset datastructure which would have O(lgn) behavior for all operations, potentially using a cache to retain O(1) minVersion().

      Attachments

        Activity

          People

            tlipcon Todd Lipcon
            tlipcon Todd Lipcon
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: