Expanded Postings Cache can cache wrong results on some edge cases:

[alanprot]

Describe the bug

Queries with a not regex matcher can return wrong results when the expanded postings cache is enabled for the head and we have queries in the "future" (future means that the start/end query timestamp both after the timestamp of the last sample added to the head). In this case, the series that should be removed by the 'not matcher' would possibly be included.

To Reproduce

Lets take for example: sum(httpRequest{code!~"2.*|3.*"})

For such matchers, Prometheus follows these steps:

• Retrieve all series that match __name__=httpRequest, e.g., Series 1, 10, 20, 30, 50.
• Remove (as it a not matcher) the series that match the regex code~="2.*|3.*", Eg: 20 and 30.
• The final result should be: 1, 10, 50 (initial series minus the excluded ones).

The root cause of the issue is that the PostingsForMatchers is returning wrong results for queries "in the future" and this result is being cached. This behavior is not a problem in prometheus as those series would be filtered out anyway later in the code as there is no chunks for the future timestamps but its a problem here as we are caching this and reusing for future calls that may have chunks.

This is still a breach of contract of the exported prometheusPostingsForMatchers function:

// PostingsForMatchers assembles a single postings iterator against the index reader
// based on the given matchers. The resulting postings are not ordered by series.
func PostingsForMatchers(ctx context.Context, ix IndexReader, ms ...*labels.Matcher) (index.Postings, error) {

Root cause of the wrong behavior:

In order to filter out, PostingsForMatchers calls headIndexReader.LabelValues to get all the values of a given label:

• https://github.com/prometheus/prometheus/blob/6d7569113f1ca814f1e149f74176656540043b8d/tsdb/querier.go#L362
  Labels Value returns EMPTY for timestamps in the future:
• https://github.com/prometheus/prometheus/blob/2915b197730e6d0292fb9f4dded0e97150b19e9a/tsdb/head_read.go#L77

This behavior is already "fixed" on upstream prometheus but we dit not pull the latest image yet.

[alanprot]

I created a PR on the smith so we can create fuzzy test for those cases: cortexproject/promqlsmith#142