ABS() function in WHERE clause gives unexpected results

[mcassels]

Describe the bug
ABS(col - x) in WHERE clause of query sometimes does not filter results correctly. The test file has a float column with high-precision values. We want to use ABS(col - x) < y to do equality comparisons for high-precision float columns.

To Reproduce
datafusion cli example using test parquet file attached:

➜  arrow-datafusion git:(master) ✗ cargo run --bin datafusion-cli
    Finished dev [unoptimized + debuginfo] target(s) in 0.22s
     Running `target/debug/datafusion-cli`
> CREATE EXTERNAL TABLE foo STORED AS PARQUET LOCATION 'test.parquet';
0 rows in set. Query took 0.001 seconds.
> select * from foo;
+--------------------+
| c0                 |
+--------------------+
| 107.0090813093981  |
| 125.51519138755981 |
| 141.83342587451415 |
| 113.65534481251639 |
| 251.10794896957802 |
| 112.08361695028363 |
+--------------------+
6 rows in set. Query took 0.006 seconds.
> select c0, ABS(c0 - 251.10794896957802) from foo;
+--------------------+-------------------------------------------+
| c0                 | abs(c0 Minus Float64(251.10794896957802)) |
+--------------------+-------------------------------------------+
| 107.0090813093981  | 144.0988676601799                         |
| 125.51519138755981 | 125.59275758201821                        |
| 141.83342587451415 | 109.27452309506387                        |
| 113.65534481251639 | 137.45260415706161                        |
| 251.10794896957802 | 0                                         |
| 112.08361695028363 | 139.02433201929438                        |
+--------------------+-------------------------------------------+
6 rows in set. Query took 0.006 seconds.
> select c0, ABS(c0 - 251.10794896957802) from foo where ABS(c0 - 251.10794896957802) < 1;
0 rows in set. Query took 0.005 seconds.
> select c0, ABS(c0 - 251.10794896957802) from foo where ABS(c0 - 251.10794896957802) < 111;
0 rows in set. Query took 0.003 seconds.
> select c0, ABS(c0 - 251.10794896957802) from foo where ABS(c0 - 251.10794896957802) < 150;
+--------------------+-------------------------------------------+
| c0                 | abs(c0 Minus Float64(251.10794896957802)) |
+--------------------+-------------------------------------------+
| 107.0090813093981  | 144.0988676601799                         |
| 125.51519138755981 | 125.59275758201821                        |
| 141.83342587451415 | 109.27452309506387                        |
| 113.65534481251639 | 137.45260415706161                        |
| 251.10794896957802 | 0                                         |
| 112.08361695028363 | 139.02433201929438                        |
+--------------------+-------------------------------------------+
6 rows in set. Query took 0.007 seconds.

Expected behavior
The query

> select c0, ABS(c0 - 251.10794896957802) from foo where ABS(c0 - 251.10794896957802) < 1;

was expected to give the following 1 row:

+--------------------+-------------------------------------------+
| c0                 | abs(c0 Minus Float64(251.10794896957802)) |
+--------------------+-------------------------------------------+
| 251.10794896957802 | 0                                         |

And the query

> select c0, ABS(c0 - 251.10794896957802) from foo where ABS(c0 - 251.10794896957802) < 111;

was expected to give the following 2 rows:

+--------------------+-------------------------------------------+
| c0                 | abs(c0 Minus Float64(251.10794896957802)) |
+--------------------+-------------------------------------------+
| 251.10794896957802 | 0                                         |
| 141.83342587451415 | 109.27452309506387                        |

Additional context
Test parquet: test.parquet.zip

[lvheyang]

I have reproduced this problem. I found the problem is in datafusion/src/physical_optimizer/pruning.rs, the PruningPredicate.

In its comment :

    /// A pruning predicate is one that has been rewritten in terms of
    /// the min and max values of column references and that evaluates
    /// to FALSE if the filter predicate would evaluate FALSE *for
    /// every row* whose values fell within the min / max ranges (aka
    /// could be pruned).

It emphasizes that if the pruning predicate evaluates to FALSE , then the filter should evaluates FALSE for every row

In this case, it built the pruning predicate as abs(c0_min - 251.10794896957802) < 1, unluckily it's not right.

c0_min is 107.0090813093981, this pruning predicate would evaluate False.

But for the row with value 251.10794896957802, this predicate evaluate True.

So it violates the rule in the comment, this causes the whole row group was omitted, so there is no result when compared with 1 or 111.

[lvheyang]

@alamb I think the root problem is some of the scalar functions ( such as abs/ sin/ cos/ pow ) are not monotonous. We cannot prune all the rows when fun(min) < Value or fun(max) > Value is false. Do you have any idea how should we deal with such a situation?

A possible way is to maintain a map, to mark the scalar functions' monotonicity. If the function is not monotonous, we would stop building the pruning predicate. Do you think if it is acceptable?

[alamb]

A possible way is to maintain a map, to mark the scalar functions' monotonicity. If the function is not monotonous, we would stop building the pruning predicate. Do you think if it is acceptable?

@mcassels and @lvheyang -- thank you for the find -- what you describe sounds correct and what is commonly done in other systems.

[alamb]

FYI @yordan-pavlov

[yordan-pavlov]

@mcassels thank you for reporting this - good find; in the implementation of the pruning predicate there is an assumption that for a predicate expression f(v) OP c, where v is any value in a column chunk and c is a constant / literal, then f(v_min) <= f(v) <= f(v_max) for any value v in that column chunk. What I did not take into account with the initial implementation of the parquet predicate push-down implementation is that this assumption is, sadly, not true for all functions supported by datafusion (obviously the function ABS(c0 - 251.10794896957802) being one example).

As a shorter-term fix, in order to ensure correctness, the predicate push-down feature could be limited to simpler expressions (such as col < literal).

Longer term, in order to support predicate push-down with more complex expressions, there must be a way to find out if the predicate expression satisfies the assumption detailed above (such as having a list of compatible functions as @lvheyang suggested above), without actually evaluating the expression.

Sadly, I don't have time at the moment to work on this, due to things in my personal life.

[lvheyang]

Thank you @yordan-pavlov for your explanation! It's so kind of you.

And I did some other tests, I found some other unexpected behavior. SQL like:

select c0, (250-c0) > 0 from foo

select c0, (250-c0) > 0 from foo where (250-c0) > 0

The first SQL return result:

+--------------------+---------------------------------+
| c0                 | Int64(250) Minus c0 Gt Int64(0) |
+--------------------+---------------------------------+
| 107.0090813093981  | true                            |
| 125.51519138755981 | true                            |
| 141.83342587451415 | true                            |
| 113.65534481251639 | true                            |
| 251.10794896957802 | false                           |
| 112.08361695028363 | true                            |
+--------------------+---------------------------------+

We expected the second SQL to return 5 rows, but actually, it returns an empty set incorrectly.

It is because the pruning predicate is built as: (Int64(250) Minus #c0_max) > Int64(0) which is also incorrect. The negative symbol before col("c0") should have reversed the predicate. So the right pruning predicate should be (Int64(250) Minus #c0_min) > Int64(0)

I plan to go deeper into related code these days and try to find a way to fix it. However, I'm not very familiar with this part, it may cost some time. >_<

[alamb]

@lvheyang given the number of wrong results you have seen, what would you think about adding a config option to disable parquet pruning as a intermediate workaround (so people can turn off pruning temporarily)?

Also, since we use this code in IOx I will be happy to help getting it working correctly

[Dandandan]

To me the idea of @yordan-pavlov to limit the pruning to only simple expressions sounds like a good one to "fix" it in the short time.

Having a config option to completely enable/disable it sounds great too.

[alamb]

I plan to work on this likely Monday unless someone else has already done so in the following 2 PRs:

1. A config option (so we can ensure correct results)
2. Limit to pruning simple expressions

[lvheyang]

@alamb sorry for reply late, it really cost me some time to get clear of how the parquet table works. I proposed a pull request (WIP) and aimed to fulfill the first step in your plan:

1. A config option (so we can ensure correct results)

here is what I have done

1. Put the parquet_pruning option in ExecutionConfig, put the enable_pruning option in ParquetTable, default value of them are both enabled (true).
2. Added a new construction function try_new_with_pruning_config in ParquetTable. Kept the original try_new function and kept the function's behavior (enable pruning)
3. When initializing ParquetExec in ParquetTable::scan, we will build the predicate based on the pruning option.

However, I still have some concerns, let's discuss them on the pull request page. Thanks a lot for your help ~

[lvheyang]

For now I have just found 2 bad cases:

1. select c0, ABS(c0 - 251.10794896957802) from foo where ABS(c0 - 251.10794896957802) < 111;
2. select c0, (250-c0) > 0 from foo where (250-c0) > 0

The common point is that abs(col) and -1 * col reverse the monotonicity of the column. Such complex expressions are really hard to deal with. ><

2. Limit to pruning simple expressions

To accomplish this target, I plan to limit pruning only to such simple expressions

1. column with boolean type
2. simple arithmetic (+ - * /) and comparison (> = < >= <= !=) expression, before we generating predicate, we should normalize the expression to such form:
   • a * left(col) compare right(literal expression) where a > 0
3. compound logical relation (and or not), may consist of one or many expressions

which we may not support by now:

1. scalar functions act on columns
2. expressions with 2 or more columns

This plan is not the final version, it may be changed since encountered some deeper problems.

[alamb]

@lvheyang sounds like a good plan to me

FWIW we have some variation of the "split code in IOx at https://github.com/influxdata/influxdb_iox/blob/main/query/src/predicate.rs#L359-L371 and a version of "find simple expressions" at https://github.com/influxdata/influxdb_iox/blob/main/query/src/predicate.rs#L375-L394 if you want an example of how that might look

a * left(col) I am not sure how common having a a constant is