You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@impala.apache.org by "Todd Lipcon (JIRA)" <ji...@apache.org> on 2018/08/08 21:30:00 UTC
[jira] [Resolved] (IMPALA-7386) CatalogObjectVersionQueue should
not be a queue
[ 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)