* Adding TSDB Head Stats like cardinality to Status Page
Signed-off-by: NSharad Gaur <sgaur@splunk.com>

* Moving mutx to Head
Signed-off-by: NSharad Gaur <sgaur@splunk.com>

* Renaming variabls
Signed-off-by: NSharad Gaur <sgaur@splunk.com>

* Renaming variabls and html
Signed-off-by: NSharad Gaur <sgaur@splunk.com>

* Removing unwanted whitespaces
Signed-off-by: NSharad Gaur <sgaur@splunk.com>

* Adding Tests, Banchmarks and Max Heap for Postings Stats
Signed-off-by: NSharad Gaur <sgaur@splunk.com>

* Adding more tests for postingstats and web handler
Signed-off-by: NSharad Gaur <sgaur@splunk.com>

* Adding more tests for postingstats and web handler
Signed-off-by: NSharad Gaur <sgaur@splunk.com>

* Remove generated asset file that is no longer used
Signed-off-by: NChris Marchbanks <csmarchbanks@gmail.com>

* Changing comment and variable name for more readability
Signed-off-by: NSharad Gaur <sgaur@splunk.com>

* Using time.Duration in postings status function and removing refresh button from web page
Signed-off-by: NSharad Gaur <sgaur@splunk.com>

Signed-off-by: NChris Marchbanks <csmarchbanks@gmail.com>

Signed-off-by: NBartek Plotka <bwplotka@gmail.com>

Signed-off-by: NGanesh Vernekar <cs15btech11018@iith.ac.in>

Signed-off-by: NGanesh Vernekar <cs15btech11018@iith.ac.in>

* improvement on postings intersection
Signed-off-by: Nnaivewong <867245430@qq.com>

Improved Merge when all is empty.
Signed-off-by: NBartek Plotka <bwplotka@gmail.com>

This change also uses the latest staticcheck version which comes with
new verifications, hence some clean up in the code.
Signed-off-by: NSimon Pasquier <spasquie@redhat.com>

Avoid a tree of merge objects, which can result in
what I suspect is n^2 calls to Seek when using Without.

With 100k metrics, and a regex of ^$ in BenchmarkHeadPostingForMatchers:

Before:
BenchmarkHeadPostingForMatchers-8              1        51633185216 ns/op      29745528 B/op      200357 allocs/op

After:
BenchmarkHeadPostingForMatchers-8             10         108924996 ns/op 25715025 B/op     101748 allocs/op
Signed-off-by: NBrian Brazil <brian.brazil@robustperception.io>

This saves memory, about a quarter of the size of the postings map
itself with high-cardinality labels (not including the post ids).
Signed-off-by: NBrian Brazil <brian.brazil@robustperception.io>

Signed-off-by: NAlexey Palazhchenko <alexey.palazhchenko@gmail.com>

Fixes https://github.com/prometheus/prometheus/issues/3575Signed-off-by: NGoutham Veeramachaneni <cs14btech11014@iith.ac.in>
Signed-off-by: NGoutham Veeramachaneni <gouthamve@gmail.com>

This allows to insert IDs to postings out of order until
a trigger function is called. This avoids the insertion sort we usually
do which can be very costly since WAL entries are more out of order than
regular adds.

IDs for new series are handed out before the postings are locked. Thus
series are not indexed in order of their IDs, which could result in only
partially sorted postings list.
Iterating over those silently skipped elements as the sort invariant was
violated.

* Test for a previous implematation of Intersect

Before we were moving the postings list everytime we create a new
chained `intersectPostings`. That was causing some postings to be
skipped. This test fails on the older version.
Signed-off-by: NGoutham Veeramachaneni <cs14btech11014@iith.ac.in>

* Advance on Seek only when valid.

Issue:
Before in mergedPostings and others we advance everytime we `Seek`,
which causes issues with `Intersect`.

Take the case, where we have a mergedPostings = m merging, a: {10, 20, 30} and
b: {15, 25, 35}. Everytime we `Seek`, we do a.Seek and b.Seek.

Now if we Intersect m with {21, 22, 23, 30}, we would do Seek({21,22,23}) which
would advance a and b beyond 30.

Fix:
Now we advance only when the seeking value is greater than the current
value, as the definition specifies.

Also, posting 0 will not be a valid posting and will be used to signal
finished or un-initialized PostingsList.
Signed-off-by: NGoutham Veeramachaneni <cs14btech11014@iith.ac.in>

* Add test for Merge+Intersect edgecase.
Signed-off-by: NGoutham Veeramachaneni <cs14btech11014@iith.ac.in>

* Add comments to trivial tests.
Signed-off-by: NGoutham Veeramachaneni <cs14btech11014@iith.ac.in>

* newIntersectPostings and newMergePostings should not advance passed
  postings automatically.
* listPostings and bigEndianPostings should not panic with index out
  of range when At() is called before Next()/Seek().
* Seek() call should advance listPostings/bigEndianPostings.

Signed-off-by: NGoutham Veeramachaneni <cs14btech11014@iith.ac.in>

A bad test was introduced a couple of commits ago which also made
changes to pass the bad test. Fixed the test and revert the changes.
Signed-off-by: NGoutham Veeramachaneni <cs14btech11014@iith.ac.in>

* Renamed mergedPostings to make it consistent across the repo
* Fixed bug with Seek
* Added Tests for Seek
Signed-off-by: NGoutham Veeramachaneni <cs14btech11014@iith.ac.in>