[HIVE-21796] ArrayWritableObjectInspector.equals can take O(2^nesting_depth) time

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 4.0.0-alpha-1
• Assignee: Zoltan Matyus
• Reporter: Csaba Ringhofer
• Created: 27/May/19 16:27
• Updated: 17/Nov/22 08:50
• Resolved: 12/Jun/19 02:37

Description

The issue came up during an Impala test when we tried to run it with Hive 3.1. The a query hanged: it tried to insert 1 row from a Parquet file with a 99 level nested column to a similar Orc file, and spent its time in ArrayWritableObjectInspector.equals() according to jstack.

The problem seems to be that equals() calls both fields.equals(that.fields) and fieldsByName.equals(that.fieldsByName), and both try to compare all nested fields recursively, which leads to the O(2^nesting_depth) complexity.

The commit that introduced this behavior:
https://github.com/apache/hive/commit/98a25f2d831ab27e174bc99792047eaa8ec08b82#diff-8c6363e90d442f239bc252a104f1bfed

The Impala test:
https://github.com/apache/impala/blob/9ee4a5e1940afa47227a92e0f6fba6d4c9909f63/tests/query_test/test_nested_types.py#L612

Issue Links

• is broken by: HIVE-15130 Fixing shifting index issue related to object inspector caching