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-unsubscr...@impala.apache.org For additional commands, e-mail: issues-all-h...@impala.apache.org