You are viewing a plain text version of this content. The canonical link for it is here.

Posted to issues-all@impala.apache.org by "Todd Lipcon (JIRA)" <ji...@apache.org> on 2018/08/02 00:30:00 UTC

[jira] [Created] (IMPALA-7386) CatalogObjectVersionQueue should not be a queue

Todd Lipcon created IMPALA-7386:
-----------------------------------

             Summary: CatalogObjectVersionQueue should not be a queue
                 Key: IMPALA-7386
                 URL: https://issues.apache.org/jira/browse/IMPALA-7386
             Project: IMPALA
          Issue Type: Bug
          Components: Catalog
    Affects Versions: Impala 2.12.0, Impala 3.0
            Reporter: Todd Lipcon
            Assignee: Todd Lipcon


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(n) 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().



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-all-unsubscribe@impala.apache.org
For additional commands, e-mail: issues-all-help@impala.apache.org