Don't query very high cardinality labels

[tomwilkie]

(Building on an idea from #209)

We have a common class of query on very-high cardinality metrics (~800k timeseries) which actually only need to read a small number (~500) of those timeseries. These queries usually involve multiple (4) matchers, 1-2 of them match pretty much all timeseries for that metric (like the job matcher), and 1-2 end up filtering it down to the 500 series in the end.

With the previous chunk store, this would pretty much always OOM, as it ended up reading millions of chunk descriptors before intersecting them away. With the series store (#875), these queries no longer OOM, they're just slow, measures in 10s of seconds.

I propose we keep a in-querier-process cache of “matcher effectiveness”, measured as the number of series matched by a matcher that making it into a final result. The idea would be that this would allow us to detect and ignore matchers which match lots of series that don’t survive the intersection.

Or perhaps alternatively we could keep a cache of observed label cardinality and just not read labels beyond a certain size (ignoring those matchers). Eventually if we are forced to ignore all the matchers, we could fail the whole query with a cardinality error.

TLDR: both these proposal involve ignoring matchers and potentially reading more chunks, but avoiding doing very high cardinality queries on the index, saving memory and hopefully decreasing latency.

WDYT?

[bboreham]

We can also use such information on the write side: some labels never affect the result of queries, so are not worth indexing. Examples in a nearby cluster: beta_kubernetes_io_arch, beta_kubernetes_io_os.

Same conclusion but different reason: le in histograms.

Of course it's possible that one day the situation would change, so we'd need logic to adapt.