You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pinot.apache.org by "ankitsultana (via GitHub)" <gi...@apache.org> on 2024/12/21 07:28:57 UTC
[I] Range Predicates Unable to Avoid Filter Computation Due to Null Column Values [pinot]
ankitsultana opened a new issue, #14694:
URL: https://github.com/apache/pinot/issues/14694
Say we have this column: `event_timestamp`, which may have null values. These values are expected to be in "mostly" non-decreasing order over time.
If we have queries with predicates such as `event_timestamp IS NOT NULL AND event_timestamp BETWEEN x and y`, then because the default value can practically only be an extremal value (0 or MAX_VALUE), we end up unnecessarily computing the range predicate for segments with non-null values in the range `[x, y]`.
At high qps, this starts becoming a bottleneck even with a range index. For queries where the other filters are selective, I am planning to try and disable the range index altogether for one of our tables so we could rely on the Scan based filter which only runs for the filtered out docs.
Another related optimization is to early terminate the `AndFilterOperator` if any of the other filters have turned out empty. To do this, `BlockDocIdSet` can add a new method which can return the cardinality of the underlying docs. This may not always be possible, so the method could also return -1 indicating that cardinality is unknown at the moment.
https://github.com/apache/pinot/blob/1ed25c078de5199095bf1a0cacf55ae2fec93168/pinot-core/src/main/java/org/apache/pinot/core/operator/filter/AndFilterOperator.java#L52-L59
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [I] Range Predicates Unable to Avoid Filter Computation Due to Null Column Values [pinot]
Posted by "richardstartin (via GitHub)" <gi...@apache.org>.
richardstartin commented on issue #14694:
URL: https://github.com/apache/pinot/issues/14694#issuecomment-2558596995
FWIW the data structure underlying the range index allows passing in a RoaringBitmap representing an existing filter, so the range predicate is implicitly intersected with the filter, skipping over any part of the index not in the filter. This could only help here.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [I] Range Predicates Unable to Avoid Filter Computation Due to Null Column Values [pinot]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] closed issue #14694: Range Predicates Unable to Avoid Filter Computation Due to Null Column Values
URL: https://github.com/apache/pinot/issues/14694
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [I] Range Predicates Unable to Avoid Filter Computation Due to Null Column Values [pinot]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on issue #14694:
URL: https://github.com/apache/pinot/issues/14694#issuecomment-4384248392
This issue has been automatically marked as stale because it has not had any activity in the last 150 days. It will be closed in 30 days if no further activity occurs. If this issue is still relevant, please leave a comment to keep it open. Thank you for your contributions!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [I] Range Predicates Unable to Avoid Filter Computation Due to Null Column Values [pinot]
Posted by "richardstartin (via GitHub)" <gi...@apache.org>.
richardstartin commented on issue #14694:
URL: https://github.com/apache/pinot/issues/14694#issuecomment-2558625184
I lie, it turns out that intersection pushdown was never implemented for `between` but I implemented it [here](https://github.com/RoaringBitmap/RoaringBitmap/pull/763) just now, it should be available soon with an upgrade.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [I] Range Predicates Unable to Avoid Filter Computation Due to Null Column Values [pinot]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on issue #14694:
URL: https://github.com/apache/pinot/issues/14694#issuecomment-4627181769
This issue has been closed because it has been inactive for 180 days. If you believe this issue is still relevant, please feel free to reopen it or create a new issue. Thank you!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [I] Range Predicates Unable to Avoid Filter Computation Due to Null Column Values [pinot]
Posted by "gortiz (via GitHub)" <gi...@apache.org>.
gortiz commented on issue #14694:
URL: https://github.com/apache/pinot/issues/14694#issuecomment-2575373273
I think what we actually need to do here is to invest some time to find a proper solution that treats null values natively. They should be understood by dictionaries and min/max values
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [I] Range Predicates Unable to Avoid Filter Computation Due to Null Column Values [pinot]
Posted by "ankitsultana (via GitHub)" <gi...@apache.org>.
ankitsultana commented on issue #14694:
URL: https://github.com/apache/pinot/issues/14694#issuecomment-2558581081
Yeah I realized this needs more context.
### Problem
Consider that we have a Realtime table with a single Kafka partition, that has `event_timestamp` values in increasing order. But `event_timestamp` can also be null occasionally. Visually the segments will look as follows:
**Figure-1:**
```
range of event_timestamp values per segment for only the non-null values
+------------------+------------------+------------------+------------------+
| S0: [0, 1000] | S1: [1000, 2000] | S2: [2000, 3000] | S3: [3000, 4000] |
+------------------+------------------+------------------+------------------+
```
**Figure-2:**
```
range of event_timestamp values per segment when you also consider the default null value (0 in this case)
+------------------+------------------+------------------+------------------+
| S0: [0, 1000] | S1: [0, 2000] | S2: [0, 3000] | S3: [0, 4000] |
+------------------+------------------+------------------+------------------+
```
From a customer perspective, if they have range filters on the `event_timestamp` value (say `event_timestamp BETWEEN 2500 AND 2800`), they usually expect that they will only be evaluating the segments whose min/max values have overlap with the range predicate in the query. And **technically** this is what happens today, but what is easily overlooked is that when you can have nulls in the column, then the default null values end up becoming the min or max of almost every segment, as can be seen in Figure-2.
This means that segment pruning will no longer work and the range predicate will have to be evaluated for every segment. Even with a range index, the **cost of evaluating these predicates ends up dominating the CPU of quite a few workloads I have seen internally**.
<img width="2467" alt="image" src="https://github.com/user-attachments/assets/516dc43e-614a-4554-82f2-3f43fc01cb0e" />
### Factors Affecting Prominence of this Issue
1. When you have a large number of segments
2. When segment pruning via bloom filters, etc. is not sufficient
3. etc. etc.
### Optimizing When Other Selective and/or Efficient Predicates
While segment pruning is not easy to do (see section below), we can still try to limit the number of times the range predicate is evaluated per-query when the other filters are quite selective. Example: `uuid_col1 = uuid1 AND uuid_col2 = uuid2 ... AND event_timestamp BETWEEN x AND y`.
To achieve this, we should short circuit the AndFilter computation when the currently evaluated filters have already let to 0 matching rows. This is something we should do regardless of this issue since it can also help many other cases. (e.g. multiple text_match predicates in a query)
### Possible Long Term Fix?
If we could set the expectation on the users that they should add `event_timestamp IS NOT NULL` to their query alongside their range predicates to achieve better segment pruning, then we might have some possible solutions to implement. But most of the options I can think of will look awkward.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [I] Range Predicates Unable to Avoid Filter Computation Due to Null Column Values [pinot]
Posted by "Jackie-Jiang (via GitHub)" <gi...@apache.org>.
Jackie-Jiang commented on issue #14694:
URL: https://github.com/apache/pinot/issues/14694#issuecomment-2558042145
I don't fully follow. To solve `event_timestamp IS NOT NULL AND event_timestamp BETWEEN x and y`, we do need to evaluate both side right? Or are all value NULL here?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org