Store Gateway: Lazy posting should mark posting group as lazy if adding too many keys

[yeya24]

Is your proposal related to a problem?

Lazy posting is designed on optimizing data bytes fetched when processing a query in Store Gateway. However, certain expensive label matchers might not get optimized if the posting is not big enough, but can be very problematic if it matches a lot of postings.

For example, a query container_memory_working_set_bytes{namespace="ns", pod!="", env="prod"}.

Different matchers might have posting size like below:

- namespace=ns => 10000, 1 key
- name=container_memory_working_set_bytes => 50000, 1 key
- pod!="" => 2M, 1M keys
- env = prod => 20M, 1 key

pod!="" can be problematic because its total posting size is not big enough so it might not marked as lazy. If it is not lazy, it needs to fetch 1M postings from cache and if cache miss, set 1M postings back to cache. This can cause huge amount of load on external cache servers as well as store gateway itself.

Describe the solution you'd like

Improve lazy posting optimization to not only focus on data size but also number of keys each posting group has. If a posting group matches too many keys, mark the posting group as lazy so no need to fetch each posting individually.

The threshold of too many keys can be configurable but we can start with 100K keys or something like that.

Describe alternatives you've considered

Improve index cache key format for posting. For matchers like pod!="" where a lot of values are matched, it is very inefficient to use one cache item per posting. We can maybe try to cache pod!="" as a whole.