Specify a well-defined sorting order for float and double types

[asfimport]

Currently parquet-format specifies the sort order for floating point numbers as follows:

   *   FLOAT - signed comparison of the represented value
   *   DOUBLE - signed comparison of the represented value

The problem is that the comparison of floating point numbers is only a partial ordering with strange behaviour in specific corner cases. For example, according to IEEE 754, -0 is neither less nor more than <u>0 and comparing NaN to anything always returns false. This ordering is not suitable for statistics. Additionally, the Java implementation already uses a different (total) ordering that handles these cases correctly but differently than the C</u>+ implementations, which leads to interoperability problems.

TypeDefinedOrder for doubles and floats should be deprecated and a new TotalFloatingPointOrder should be introduced. The default for writing doubles and floats would be the new TotalFloatingPointOrder. This ordering should be effective and easy to implement in all programming languages.

Reporter: Zoltan Ivanfi / @zivanfi
Assignee: Micah Kornfield / @emkornfield

Related issues:

• Impala shouldn't write column indexes for float columns until PARQUET-1222 is resolved (Blocked)
• Implement specification-compliant floating point comparison (blocks)
• [parquet-mr] Implement specification-compliant floating point comparison (blocks)
• [C++] Implement specification-compliant floating point comparison (blocks)
• [C++][Dataset] Handle NaNs correctly in Parquet predicate push-down (is related to)
• Ignore float/double statistics in case of NaN (is related to)
• Clarify ambiguous min/max stats for FLOAT/DOUBLE (is related to)

_{Note: This issue was originally created as PARQUET-1222. Please see the migration documentation for further details.}

[asfimport]

Zoltan Ivanfi / @zivanfi:
Moving the design alternatives to this comment so that the JIRA description focuses on the proposed solution:

We should explicitly require implementations to follow a specific comparison logic for these types. The candidates are:

• The Java implementation which looks easy and efficient to implement in any language.

• The IEEE 754 totalOrder predicate which is rather complicated.

• The IEEE 754-2008 min and max operations which may be hard to use for comparison, so components could not use the same sorting order to achieve the smallest possible min/max ranges (although a regular sort would probably result in an almost optimal value order).

• We could simply require NaNs to be ignored for calculating min/max. However, we should also explicitly address -0/+0 values in this case, which probably leads to the option above.

  An additional problem is how to deal with existing data:

• One possibility is to specify legacy rules, like "if the min or max is NaN, it should be ignored" or that "-0 and +0 should be considered equal for min/max purposes".

• Another alternative is to deprecate min_value and max_value and introduce yet_another_min and yet_another_max fields instead (with nicer names, naturally). This could be combined with some legacy rules for the old field.

• Probably the best solution would be to deprecate TypeDefinedOrder for doubles and floats and introduce a new TotalOrder. The legacy rule "if the min or max is NaN, it should be ignored" should apply to TypeDefinedOrder while the new TotalOrder would not have such restrictions. The default for writing doubles and floats would be the new TotalOrder.

[asfimport]

Jim Apple / @jbapple:
I do not think the order proposed matches the IEEE 754 totalOrder. It would be good to match that order so as to avoid creating yet one more thing for users to track. Also, it is possible that the IEEE totalOrder is also faster in some hardware.

I haven't checked, but it is possible that IEEE-754 is actually a lexicographical compare of the bit representations in some endianess or another.

[asfimport]

Zoltan Ivanfi / @zivanfi:
@jbapple The proposed order was intentionally different from IEEE 754 totalOrder, because of the following rules of totalOrder:

        3) If x and y represent the same floating-point datum:
            i) If x and y have negative sign,
            totalOrder(x, y) is true if and only if the exponent of x ≥ the exponent of y
            ii) otherwise
            totalOrder(x, y) is true if and only if the exponent of x ≤ the exponent of y.

This has led me to believe that different bit patterns may correspond to the same numeric value, in which case considering them different would be problematic, as it could lead to row groups being dropped or not based on what bit pattern was used to save the data and what bit pattern is used for looking them up. However, thinking more about it, it seems to me that apart from +0/-0 and the various NaNs, all other bit patterns correspond to different numbers. Since the opposite assumption was the reason for the proposed order, I am removing it for now.

[asfimport]

Ryan Blue / @rdblue:
I think Jim is right. IEEE-754 numbers are ordered correctly if you flip the sign bit and use unsigned, byte-wise comparison. I wrote a spec for encoding HBase keys that used this a while ago.

The reason why rule 3 works is that for normal floating point numbers, the significand must start with a 1. Conceptually, this means that 0.0001 and 0.00001 cannot be represented with the same exponent. Because the exponent basically encodes where the first set bit is in the number, it can be used for sorting. There is also support for very small numbers where the significand doesn't start with 1, but those must use the smallest-possible exponent so sorting still works.

[asfimport]

Zoltan Ivanfi / @zivanfi:
My understanding is that positive numbers are ordered like integers with the same bits, but negative numbers are ordered in the reverse order than integers with the same bits. This is similar to how decimal numbers are ordered, due to consisting of a sign and an absolute value.

[asfimport]

Zoltan Ivanfi / @zivanfi:
Having said that, I also agree that we could use this ordering. However, I think we should define it in terms of how it should behave (probably with lots of examples), instead of just pointing to the IEEE 754 specification, which is not available openly.

[asfimport]

Zoltan Ivanfi / @zivanfi:
I updated this JIRA to distuingish it from PARQUET-1251. To summarize:

• PARQUET-1251 is a "hotfix" that describes a workaround for handling statistics written using the ambiguous specification.
• This JIRA is about specifying a well-defined sort order.

[asfimport]

Antoine Pitrou / @pitrou:
I'll note that Parquet C++ now has the following behaviour:

• signed zeros are properly ordered (ARROW-5562)
• NaNs are ignored when computing min/max (PARQUET-1225); if a page or column chunk only has NaNs, the statistics are unset

[asfimport]

Gabor Szadovszky / @gszadovszky:
@pitrou, I guess what you've described is the write path of the statistics. Because you cannot control other writers I would suggest following the spec for the read path.
Meanwhile, I've done some investigation in the parquet-mr code and the format and there are issues related to this topic.

• We have created the ColumnOrder object and the related field in the format to specify the ordering of the columns and to prepare for the potential solution of this (and similar) issues. We are referencing this field in the Statistics object used for row-group level stats. Meanwhile, we do not reference this in the column indexes. So, in column indexes it is not clear what sorting orders do we want to use and how to handle cases like this. How it is implemented in parquet-cpp?

• Based on the referenced workaround we handle the special floating point values at row-group level in parquet-mr but only for the read path. For the write path we still write these values.

• For column indexes we handle these values but only for the write path and not for the read path.

  So, we have a couple of issues around this topic and it would be great if we would have a final and well defined solution for it.

[asfimport]

Antoine Pitrou / @pitrou:
Some answers after looking through the code:

• parquet-cpp does not read nor write ColumnIndex
• our handling of min_value and max_value on the read path is naive. We use the same comparisons regardless of whether ColumnOrder is present or not. In particular, we use native type-specific greater-or-equal comparison (e.g. floating-point comparison), which is due to fail with NaNs (but will succeed with signed zeros).

[asfimport]

Micah Kornfield / @emkornfield:
I'd propose the following "fix":

• Add a new optional bool value to the statistics struct "contains_nan". When unset, I think we specify the semantics for comparisons relative to -0.0/0.0 and NaN, etc are not well defined and implementations have taken different routes.

• When set, if true, it means the column contains at least one NaN, when set to false it means no NaNs are present. Further when set, it implies the following ordering:
  NaNs are never included in Min/Max statistics in the struct. -0.0, +0.0, are considered two distinct values and are ordered according to sign.

  Thoughts? Should I bring this up on the mailing list?

[asfimport]

Gabor Szadovszky / @gszadovszky:
@emkornfield, I think we do not need to handle NaN values with a boolean to fix this issue. NaN is kind of similar than null values so we may even count them instead of having a boolean but this question is not tightly related to this topic.
What do you think about elevating the current suggestion in the thrift file to specification level for writing/reading FP min/max values?

Because the sorting order is not specified properly for floating point values (relations vs. total ordering) the following compatibility rules should be applied when reading statistics:

• If the min is a NaN, it should be ignored.
• If the max is a NaN, it should be ignored.
• If the min is +0, the row group may contain -0 values as well.
• If the max is -0, the row group may contain +0 values as well.
• When looking for NaN values, min and max should be ignored.
  For writing we shall skip NaN values and use -0 for min and +0 for max any time when a 0 is to be taken into account.

With this solution we cannot do anything clever in case of searching for a NaN but it can be fixed separately. And we also need to double-check whether we really ignore the min/max stats in case of searching for a NaN.

I think it is a good idea to discuss such topics on the mailing list. However, we should also time-box the discussion and go forward with a proposed solution if there are no interests on the mailing list. (Personally, I do not follow the dev list anymore.)

[asfimport]

Antoine Pitrou / @pitrou:
(side note: the ML is mostly a firehose of notifications nowadays, which doesn't make it easy to follow...)

[asfimport]

Antoine Pitrou / @pitrou:
I agree with @gszadovszky for elevating these rules at the specification level.

[asfimport]

Micah Kornfield / @emkornfield:
Elevating the specification level seems fine. I was under the impression the thrift file was the specification? Where do we need to do the PR to elevate them?