[IMPALA-7386] CatalogObjectVersionQueue should not be a queue

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: Impala 3.0, Impala 2.12.0
• Fix Version/s: Impala 3.1.0
• Component/s: Catalog
• Epic Color: ghx-label-6
• Assignee: Todd Lipcon
• Reporter: Todd Lipcon
• Created: 02/Aug/18 00:29
• Updated: 08/Aug/18 22:04
• Resolved: 08/Aug/18 21:29

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