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

["Yongzhi Chen (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/HIVE-21796?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16857852#comment-16857852 ] 

Yongzhi Chen edited comment on HIVE-21796 at 6/7/19 10:36 AM:
--------------------------------------------------------------

It looks for me that this fix may regress HIVE-15130, the original code compare names, fields and the map( from names to fields). If we remove map comparing, it is possible a name map to the wrong field?  

If we have to remove some checks to improve performance, I think to keep the map check, for names and fields, we only check if their list size equal. 


was (Author: ychena):
It looks for me that this fix may regress HIVE-15130, the original code compare names, fields and the map( from names to fields). If we remove map comparing, it is possible a name map to the wrong field?  

> 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
>            Assignee: Zoltan Matyus
>            Priority: Major
>         Attachments: HIVE-21796.1.patch, HIVE-21796.2.patch, HIVE-21796.3.patch, HIVE-21796.patch, jstack.txt
>
>
> 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)