[
https://issues.apache.org/jira/browse/IMPALA-7386?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16573929#comment-16573929
]
Todd Lipcon commented on IMPALA-7386:
-------------------------------------
Yea I think the extra memory cost of having the two data structures isn't worth
the efficiency gain for this uncommon operation. Logarithmic updates are
already pretty fast even with millions of objects.
> 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: issues-all-unsubscr...@impala.apache.org
For additional commands, e-mail: issues-all-h...@impala.apache.org
