Include NaN in Parquet stats (again)

[crepererum]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.
After #256 we completely ignore NaNs in parquet statistics. However, there are good reasons to fully order floats and include NaN somewhere:

• Databases usually need it, see sql: NaN = NaN (in Postgres) cockroachdb/cockroach#18860 and if DataFusion wants to follow the Postgres dialect we will have the same issue there
• Other parquet users are interested as well: PARQUET-1222
• Just ignoring NaN is kinda having an implicit NULL for float while we already have a NULL-mask

Describe the solution you'd like
Put NaNs at the end of the float scale, so the order is:

1. -inf
2. "ordinary" numbers
3. +inf
4. NaN

Describe alternatives you've considered
Keeping the status quo (aka current master).

Additional context
.

[NGA-TRAN]

I think a few links to other DBs related documents will help us feel more confident that in the future our customers won't ask us to do differently. A few name: SQL standard (SQL99, ...), PG, Oracle, Snowflake, Vertica.

[crepererum]

Prior Art

PostgreSQL

In most implementations of the “not-a-number” concept, NaN is not considered equal to any other numeric value (including NaN). In order to allow numeric values to be sorted and used in tree-based indexes, PostgreSQL treats NaN values as equal, and greater than all non-NaN values.

https://www.postgresql.org/docs/13/datatype-numeric.html

=> Follows this proposal

CockroachDB

Follows PostgreSQL, see cockroachdb/cockroach#18860

=> Follows this proposal

Oracle

The floating-point value NaN is greater than any other numeric value and is equal to itself.

https://docs.oracle.com/database/121/TTSQL/types.htm#TTSQL165

=> Follows this proposal

Snowflake

Comparison semantics for 'NaN' differ from the IEEE 754 standard in the following ways:

Condition	Snowflake	IEEE 754	Comment
'NaN' = 'NaN'	TRUE	FALSE	In Snowflake, 'NaN' values are all equal.
'NaN' > X where X is any FLOAT value, including infinity (other than NaN itself).	TRUE	FALSE	Snowflake treats 'NaN' as greater than any other FLOAT value, including infinity.

https://docs.snowflake.com/en/sql-reference/data-types-numeric.html#float-float4-float8

=> Follows this proposal

Vertica

Vertica follows the IEEE definition of NaNs (IEEE 754). The SQL standards do not specify how floating point works in detail. [...]

Rules

• -0 == +0
• 1/0 = Infinity
• 0/0 == Nan
• NaN != anything (even NaN)

[...]

Sort Order (Ascending)

• NaN
• -Inf
• numbers
• +Inf
• NULL

https://www.vertica.com/docs/9.2.x/HTML/Content/Authoring/SQLReferenceManual/DataTypes/Numeric/DOUBLEPRECISIONFLOAT.htm

=> Does NOT follow this proposal

SQL Standard

Not open, and scanning through the drafts I've found does not reveal more than "implementation defined". I trust Vertica when they say:

The SQL standards do not specify how floating point works in detail.

https://www.vertica.com/docs/9.2.x/HTML/Content/Authoring/SQLReferenceManual/DataTypes/Numeric/DOUBLEPRECISIONFLOAT.htm

=> Undefined

Rust Std

Normally floats are only partially ordered, but there is some proposed nightly API that orders them:

The values are ordered in following order:

• Negative quiet NaN
• Negative signaling NaN
• Negative infinity
• Negative numbers
• Negative subnormal numbers
• Negative zero
• Positive zero
• Positive subnormal numbers
• Positive numbers
• Positive infinity
• Positive signaling NaN
• Positive quiet NaN

https://doc.rust-lang.org/nightly/std/primitive.f64.html#method.total_cmp

=> Does NOT follow this proposal

Rust ordered-float

NaN is sorted as greater than all other values and equal to itself, in contradiction with the IEEE standard.

https://docs.rs/ordered-float/2.2.0/ordered_float/struct.OrderedFloat.html

=> Follows this proposal

IEEE totalOrder

IEEE apparently also defines some total order. It's a bit more complicated and puts NaNs on both ends based on sign bit, signalling/quiet bit and payload.

=> Does NOT follow this proposal

[alamb]

Some other potentially related prior work: apache/arrow#9416, where @ritchie46 was trying to sort out how to handle NaNa

[alamb]

DataFusion also uses the ordered_float rust crate: https://github.com/apache/arrow-datafusion/blob/master/datafusion/src/physical_plan/group_scalar.rs#L20

The sort kernel appears to use IEEE 754 totalOrder standard
https://github.com/apache/arrow-rs/blob/master/arrow/src/compute/kernels/sort.rs#L30-L50

[jorgecarleitao]

IMO we should use the total order defined in arrow according to IEEE 754 totalOrder, which AFAIK is also used to compute the min and max of an array.

[crepererum]

For what it's worth: With IEEE, if a database built on top of arrow / datafusion uses a dedicated NaN representation, it could archive whatever sorting it wants by picking the "right" NaN (pick a positive one and you get the PostgreSQL behavior).

[alamb]

I think keeping "Nan" as the min/max value in the stats is unlikely going to be useful for query processing, much like storing NULLs as a min/max value is not super helpful). I would personally suggest keeping them out of the statistics and adding additional metadata (like "contains NaNs" or whatever) if that is important information to retain.

If we really want to add NaN to the stats I think it would help to articulate an actual usecase where having a NaN there would be useful

[crepererum]

If we really want to add NaN to the stats I think it would help to articulate an actual usecase where having a NaN there would be useful

The following come to my mind:

• PostgreSQL-style SQL (which IIRC DataFusion follows) allows X == NaN to be queried. For that, "contains NaN" is an important information
• PostgreSQL-style SQL (again for DataFusion) sorts NaNs at the end (aka after +inf) of the spectrum, so at least "contains NaN" would be useful.

However, "contains NaN" only makes sense for Parquet Float and Double and the current parquet standard stat do NOT provide us any way to express this. And since for most query cases the point can be made that NaN shall be included into the total order somewhere, I would rather put that info into min/max instead of creating some convoluted edge case, i.e.

Query processors rely on min/max to figure out the full value range. However for Float and Double (and only for these) there is also this special flag that does not exist for any other data type that tells you about the existence of that one value class.

[jorgecarleitao]

Think about this, this seems to be an issue present in all implementations that use the parquet format. Maybe we should raise this over the parquet mailing list? The question seems to be what do implementations expect from min, max for float types, and whether they themselves use nans, infinites, etc, or not.

Maybe this motivates a clarification on the parquet specification itself?

[alamb]

I am coming at this from a query processing point of view and using statistics to rule out entire row groups (or equivalents). Having a clearly defined sort order for floats is important for sorting, but for statistics I feel like including Nan values in a column effectively "poisons" the effective use

I'll copy / paste my example from https://github.com/influxdata/influxdb_iox/pull/1448#discussion_r628230059. In that case, where your data was like

f
---
1.1
2.1
... (1 Billion other values between 1.1 and 9.9)
Nan
9.9

If you have a predicate that is like f > 10.0 (which does not evaluate to true for the one Nan row) the query engine will have to scan 1 Billion extra rows due to the presence of a single null value

Queries that are specifically looking for Nan I think are much less important to optimize.

I like the idea of getting some consensus on what to do with Nans and statistics on the parquet mailing list

[alamb]

I tried to see what postgres kept for statistics, and it turns out it keeps histograms not just min/max:

alamb=# select * from example;
  a  
-----
   1
   2
   3
 NaN
(4 rows)

alamb=# select * from pg_stats where tablename = 'example';
 schemaname | tablename | attname | inherited | null_frac | avg_width | n_distinct | most_common_vals | most_common_freqs | histogram_bounds | correlation | most_common_elems | most_common_elem_freqs | elem_count_histogram 
------------+-----------+---------+-----------+-----------+-----------+------------+------------------+-------------------+------------------+-------------+-------------------+------------------------+----------------------
 public     | example   | a       | f         |         0 |         8 |         -1 |                  |                   | {1,2,3,NaN}      |           1 |                   |                        | 
(1 row)

[emkornfield]

I believe there is an open issue for Parquet to define consistent ordering here, I'll see if I can dig it up tonight.

[nevi-me]

• Other parquet users are interested as well: PARQUET-1222

@emkornfield is it this one?

[crepererum]

I'm a bit low on resources this week. I can certainly write down the options (which are more than the proposal above) and how the link to use cases and prior art next week and post it to the ticket.