You are viewing a plain text version of this content. The canonical link for it is here.

Posted to dev@hive.apache.org by "Csaba Ringhofer (JIRA)" <ji...@apache.org> on 2019/05/27 16:28:00 UTC

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

Csaba Ringhofer created HIVE-21796:
--------------------------------------

             Summary: ArrayWritableObjectInspector.equals can take O(2^nesting_depth) time
                 Key: HIVE-21796
                 URL: https://issues.apache.org/jira/browse/HIVE-21796
             Project: Hive
          Issue Type: Bug
            Reporter: Csaba Ringhofer


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



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)