hive-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Gopal V (JIRA)" <j...@apache.org>
Subject [jira] [Updated] (HIVE-11638) ExprNodeDesc hashMap accidentally degrades into O(N) instead of O(1)
Date Tue, 25 Aug 2015 06:13:45 GMT

     [ https://issues.apache.org/jira/browse/HIVE-11638?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Gopal V updated HIVE-11638:
---------------------------
    Issue Type: Improvement  (was: Bug)

> ExprNodeDesc hashMap accidentally degrades into O(N) instead of O(1)
> --------------------------------------------------------------------
>
>                 Key: HIVE-11638
>                 URL: https://issues.apache.org/jira/browse/HIVE-11638
>             Project: Hive
>          Issue Type: Improvement
>          Components: Logical Optimizer
>    Affects Versions: 0.14.0, 1.0.1, 1.1.1, 1.3.0, 1.2.1, 2.0.0
>            Reporter: Gopal V
>            Assignee: Gopal V
>              Labels: Performance
>         Attachments: HIVE-11638.1.patch
>
>
> Due to the absence of ExprNodeDesc::equals() & the presence of a hashCode(), any
code which computes a Set or HashMap of identical objects ends up with a skewed hashmap which
degrades column lookups from O(1) to O(N) during optimizer passes.
> So, several hundred references to a single column desc will be stored in a single hashbucket,
but since they default to Object::equals(), they are not equal to each other.
> Finalize the equals() method, so that the approach from HIVE-10215 carries over safely.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message