Tarun-kishore opened a new issue, #20041:
URL: https://github.com/apache/pinot/issues/20041
### What happens
On a realtime table, a query such as
```sql
SELECT * FROM myTable WHERE ts >= ago('PT1M') AND env <> 'staging'
```
can return rows with `env = 'staging'` when `env` has an inverted index.
These rows are always among the newest rows of a consuming segment, and they
are gone if the same query runs again a moment later. We hit this in production
on a table with a high ingestion rate: a query that excluded one value returned
a few rows with that value whenever rows were ingested while it ran.
The same race affects every filter that reads a bitmap from a mutable index:
- [ ] **Inverted index** (`InvertedIndexFilterOperator`): `<>` and `NOT IN`
return rows with an excluded value. `COUNT(*)` with `<>`, `NOT IN`, `=` or
`IN`, and AND/OR of them, can be off.
- [ ] **H3 index** (`H3IndexFilterOperator`,
`H3InclusionIndexFilterOperator`): `ST_Distance(location, ST_Point(...)) > d`
and `ST_Within(location, polygon) = 0` can return new rows near the point or
inside the polygon.
- [ ] **JSON index** (`JsonMatchFilterOperator`): `COUNT(*)` with
`JSON_MATCH` counts new rows, and `COUNT(*)` with `NOT JSON_MATCH` (computed as
`numDocs` minus that count) undercounts and can drop to 0. ANDed with a
scan-based filter, `JSON_MATCH` also returns the new rows.
- [ ] **Null value vector**, with null handling enabled
(`BitmapBasedFilterOperator`, `BaseColumnFilterOperator`, the always true /
always false leaves): `IS NOT NULL` can return a null row ingested during
planning, and the null counts can be off.
### Why
`FilterPlanNode.run()` reads `numDocs` when the query is planned. The filter
operators read their bitmaps from the indexes later. On a consuming segment,
these bitmaps can hold rows at or above `numDocs`:
- `RealtimeInvertedIndex.getDocIds()`, `MutableH3Index.getDocIds()` and
`MutableNullValueVector.getNullBitmap()` return a copy of the live bitmap.
- `MutableJsonIndexImpl.getMatchingDocIds()` answers from the live posting
lists.
The operators then do one of the following:
- **Flip the bitmap over `[0, numDocs)`** for exclusive predicates. A new
row at or above `numDocs` is outside the flip, so it stays in the result as a
match.
- **Count it.** For example, `getNumMatchingDocs()` returns `numDocs -
cardinality` for exclusive predicates, and `NotFilterOperator` returns
`numDocs` minus the child's count. The planning-time `numDocs` is mixed with a
later state of the index.
- **Hand it to an AND with a scan-based filter**, such as a time range on a
raw column. `AndDocIdSet` passes the bitmap to
`ScanBasedDocIdIterator.applyAnd()`, which iterates it with a
`RangelessBitmapDocIdIterator` that does not stop at `numDocs`.
The inverted index, H3 and JSON bitmaps are read when the query runs, so any
row ingested between planning and execution can show up. The null bitmaps are
read while the operators are built, so only rows ingested during planning can
show up.
### How to reproduce
On a consuming segment with an inverted index on `env` and a raw `ts` column:
1. Plan `SELECT * FROM myTable WHERE ts >= 0 AND ts <= 2000 AND env <>
'staging'`.
2. Index a few more rows with `env = 'staging'`.
3. Run the planned operator. The new staging rows are returned.
The same steps reproduce it for `ST_Distance(location, ST_Point(-122, 37.5,
1)) > 1000` with a new row at `(-122, 37.5)`, and for `COUNT(*)` with `NOT
JSON_MATCH(tags, '"$.env" = ''staging''')` with new staging rows.
### Proposed fix
A leaf filter operator should never hand out a row at or above the `numDocs`
it was built with: limit every bitmap read from a mutable index to `[0,
numDocs)`. On immutable segments, this is one `last()` check per bitmap and
nothing is copied.
I'll open two PRs: one for the inverted index, and one for the H3,
JSON_MATCH and null value vector filters.
### Related
The text index has a similar problem (#17809), handled by #17880 and #18006
with a searchable-doc fence.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
