[HIVE-11638] ExprNodeDesc hashMap accidentally degrades into O(N) instead of O(1)

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 0.14.0, 1.0.1, 1.1.1, 1.2.1, 1.3.0, 2.0.0
• Fix Version/s: 1.3.0, 2.0.0
• Component/s: Logical Optimizer
• Labels: Performance
• Release Note: Use fastest hashmap implementation of ExprNodeDesc lookups
• Assignee: Gopal Vijayaraghavan
• Reporter: Gopal Vijayaraghavan
• Created: 25/Aug/15 06:11
• Updated: 16/Feb/16 23:53
• Resolved: 27/Aug/15 00:30

Description

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.

Issue Links

• is part of: HIVE-11315 Compilation performance issues for large queries
• is related to: HIVE-11627 Reduce the number of accesses to hashmaps in PPD