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 "Tim Armstrong (JIRA)" <ji...@apache.org> on 2018/08/02 00:44:00 UTC
[jira] [Commented] (IMPALA-7386) CatalogObjectVersionQueue should
not be a queue
[ https://issues.apache.org/jira/browse/IMPALA-7386?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16566191#comment-16566191 ]
Tim Armstrong commented on IMPALA-7386:
---------------------------------------
I ran into a similar problem at one point. You can get most operations to be O(1) if you use a HashMap where the value stores the count. You can have a priority queue that holds references into the HashMap to allow O(1) checks for the minimum. The trick is that writers don't remove entries from the priority queue - instead readers of the priority queue lazily remove the entries when they get to the head.
This may be overengineering it though :).
> 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
>
> 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