[
https://issues.apache.org/jira/browse/IMPALA-7386?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Todd Lipcon resolved IMPALA-7386.
---------------------------------
Resolution: Fixed
Fix Version/s: Impala 3.1.0
> 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 3.0, Impala 2.12.0
> Reporter: Todd Lipcon
> Assignee: Todd Lipcon
> Priority: Major
> Fix For: Impala 3.1.0
>
>
> 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: [email protected]
For additional commands, e-mail: [email protected]
