[HIVE-5839] BytesRefArrayWritable compareTo violates contract

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 0.11.0, 0.12.0
• Fix Version/s: 0.13.0
• Component/s: Serializers/Deserializers
• Assignee: Xuefu Zhang
• Reporter: Ian Robertson
• Created: 17/Nov/13 19:21
• Updated: 23/Mar/14 17:42
• Resolved: 26/Nov/13 01:52

Description

BytesRefArrayWritable's compareTo violates the compareTo contract from java.lang.Object. Specifically:

• The implementor must ensure sgn(x.compareTo( y )) == -sgn(y.compareTo( x )) for all x and y.

The compareTo implementation on BytesRefArrayWritable does a proper comparison of the sizes of the two instances. However, if the sizes are the same, it proceeds to do a check if both array's have the same constant. If not, it returns 1. This means that if x and y are two BytesRefArrayWritable instances with the same size, but different contents, then x.compareTo( y ) == 1 and y.compareTo( x ) == 1.

Additionally, the comparison of contents is order agnostic. This seems wrong, since order of entries should matter. It is also very inefficient, running at O(n^2), where n is the number of entries.

Issue Links

• links to: https://reviews.apache.org/r/15820/