Repository: VictoriaMetrics/VictoriaMetrics
Pull request #7416 (2024-11-01 18:54:53)

app/vmselect/promql: improve performance of parseCache on systems with many CPU cores
### Describe Your Changes

Parse cache is a pretty simple implementation of cache. It's just a standard map with mutex.
Map with mutex overall has poor performance, plus when the cache overflow occurs, the whole cache locks until 1k elements have been deleted (now it's 10% of 10000 max elements in the cache). To avoid this bottleneck and improve performance of cache on systems with many CPU cores but keep it rather simple, we can implement cache with per bucket locks like it's done in fastcache. The logic and API remain the same. So now each bucket will have a map with approximately 78 elements (with 128 buckets), and overflow will occur now for each bucket, and only 7 elements need to be deleted.
Because exec_test.go has about 10k lines of code, it's better to move the cache into a separate file to add tests and benchmarks for it, because now it does not have them.

```
goos: windows
goarch: amd64
pkg: github.com/VictoriaMetrics/VictoriaMetrics/app/vmselect/promql
cpu: 11th Gen Intel(R) Core(TM) i9-11900K @ 3.50GHz

Current cache implementation performance on 8 cores:
BenchmarkCachePutNoOverFlow-8               1932            618372 ns/op             253 B/op          0 allocs/op
BenchmarkCacheGetNoOverflow-8               6547            211527 ns/op               0 B/op          0 allocs/op
BenchmarkCachePutGetNoOverflow-8            1873            621718 ns/op             261 B/op          0 allocs/op
BenchmarkCachePutOverflow-8                 2262            464328 ns/op              32 B/op          0 allocs/op
BenchmarkCachePutGetOverflow-8              1764            655866 ns/op              38 B/op          0 allocs/op

New cache implementation performance on 8 cores:
BenchmarkCachePutNoOverFlow-8              10408            111412 ns/op               0 B/op          0 allocs/op
BenchmarkCacheGetNoOverflow-8              22407             52809 ns/op               0 B/op          0 allocs/op
BenchmarkCachePutGetNoOverflow-8            6583            168088 ns/op               0 B/op          0 allocs/op
BenchmarkCachePutOverflow-8                 9822            117212 ns/op               2 B/op          0 allocs/op
BenchmarkCachePutGetOverflow-8              6481            175952 ns/op               3 B/op          0 allocs/op

Current cache implementation performance on 16 cores:
BenchmarkCachePutNoOverFlow-16              2331            475307 ns/op             218 B/op          0 allocs/op
BenchmarkCacheGetNoOverflow-16              6069            196905 ns/op               0 B/op          0 allocs/op
BenchmarkCachePutGetNoOverflow-16           1870            644236 ns/op             262 B/op          0 allocs/op
BenchmarkCachePutOverflow-16                2296            509279 ns/op              34 B/op          0 allocs/op
BenchmarkCachePutGetOverflow-16             1726            671510 ns/op              45 B/op          0 allocs/op

New cache implementation performance on 16 cores:
BenchmarkCachePutNoOverFlow-16             13549             82413 ns/op               0 B/op          0 allocs/op
BenchmarkCacheGetNoOverflow-16             30274             38997 ns/op               0 B/op          0 allocs/op
BenchmarkCachePutGetNoOverflow-16           8512            126239 ns/op               0 B/op          0 allocs/op
BenchmarkCachePutOverflow-16               13884             88124 ns/op               1 B/op          0 allocs/op
BenchmarkCachePutGetOverflow-16             7903            131299 ns/op               3 B/op          0 allocs/op
```
From the benchmarks above, we can see that the new implementation is ~5 times faster than the old one.

### Checklist

The following checks are **mandatory**:

- [] My change adheres [VictoriaMetrics contributing guidelines](https://docs.victoriametrics.com/contributing/).


f41gh7:  Hello, sorry for delay. WDYT of making a parsing benchmark with enabled and disable cache? 

 Maybe it's not worth it at all to use this cache and it's better to parse expression each time.
kiriklo: Hello, I included benchmarks for `parsePromQLWithCache()` and `parsePromQLWithoutCache()`. Even with simple queries, there is a significant performance difference between them, as can be seen from the benchmarks below . So cache is here for a reason.

```
goos: windows
goarch: amd64
pkg: github.com/VictoriaMetrics/VictoriaMetrics/app/vmselect/promql
cpu: 11th Gen Intel(R) Core(TM) i9-11900K @ 3.50GHz
BenchmarkParsePromQLWithCacheSimple-8                    4441305               280.2 ns/op             0 B/op          0 allocs/op
BenchmarkParsePromQLWithoutCacheSimple-8                   40227             28816 ns/op           13040 B/op        375 allocs/op
BenchmarkParsePromQLWithCacheSimpleParallel-8            7435629               168.9 ns/op             0 B/op          0 allocs/op
BenchmarkParsePromQLWithoutCacheSimpleParallel-8           98808             12271 ns/op           13040 B/op        375 allocs/op
BenchmarkParsePromQLWithCacheComplex-8                   2962010               414.5 ns/op             0 B/op          0 allocs/op
BenchmarkParsePromQLWithoutCacheComplex-8                   3864            320808 ns/op          139867 B/op       2401 allocs/op
BenchmarkParsePromQLWithCacheComplexParallel-8           9242356               128.0 ns/op             0 B/op          0 allocs/op
BenchmarkParsePromQLWithoutCacheComplexParallel-8           5791            195799 ns/op          139882 B/op       2401 allocs/op
```
f41gh7:  Thanks for the benchmark! We discussed it offline and had an assumption, that parser works fast enough and this cache may not be needed. Looks like it's not true and this cache and your optimization makes a lot of sense. 


Patch:
diff --git a/app/vmselect/promql/exec.go b/app/vmselect/promql/exec.go
index 1c731cb5c..2647f2990 100644
--- a/app/vmselect/promql/exec.go
+++ b/app/vmselect/promql/exec.go
@@ -6,8 +6,6 @@ import (
 	"math"
 	"sort"
 	"strings"
-	"sync"
-	"sync/atomic"
 	"time"
 
 	"github.com/VictoriaMetrics/VictoriaMetrics/app/vmselect/netstorage"
@@ -16,7 +14,6 @@ import (
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/logger"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/querytracer"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/storage"
-	"github.com/VictoriaMetrics/metrics"
 	"github.com/VictoriaMetrics/metricsql"
 )
 
@@ -270,7 +267,7 @@ func getReverseCmpOp(op string) string {
 }
 
 func parsePromQLWithCache(q string) (metricsql.Expr, error) {
-	pcv := parseCacheV.Get(q)
+	pcv := parseCacheV.get(q)
 	if pcv == nil {
 		e, err := metricsql.Parse(q)
 		if err == nil {
@@ -284,7 +281,7 @@ func parsePromQLWithCache(q string) (metricsql.Expr, error) {
 			e:   e,
 			err: err,
 		}
-		parseCacheV.Put(q, pcv)
+		parseCacheV.put(q, pcv)
 	}
 	if pcv.err != nil {
 		return nil, pcv.err
@@ -328,80 +325,3 @@ func escapeDots(s string) string {
 	}
 	return string(result)
 }
-
-var parseCacheV = func() *parseCache {
-	pc := &parseCache{
-		m: make(map[string]*parseCacheValue),
-	}
-	metrics.NewGauge(`vm_cache_requests_total{type="promql/parse"}`, func() float64 {
-		return float64(pc.Requests())
-	})
-	metrics.NewGauge(`vm_cache_misses_total{type="promql/parse"}`, func() float64 {
-		return float64(pc.Misses())
-	})
-	metrics.NewGauge(`vm_cache_entries{type="promql/parse"}`, func() float64 {
-		return float64(pc.Len())
-	})
-	return pc
-}()
-
-const parseCacheMaxLen = 10e3
-
-type parseCacheValue struct {
-	e   metricsql.Expr
-	err error
-}
-
-type parseCache struct {
-	requests atomic.Uint64
-	misses   atomic.Uint64
-
-	m  map[string]*parseCacheValue
-	mu sync.RWMutex
-}
-
-func (pc *parseCache) Requests() uint64 {
-	return pc.requests.Load()
-}
-
-func (pc *parseCache) Misses() uint64 {
-	return pc.misses.Load()
-}
-
-func (pc *parseCache) Len() uint64 {
-	pc.mu.RLock()
-	n := len(pc.m)
-	pc.mu.RUnlock()
-	return uint64(n)
-}
-
-func (pc *parseCache) Get(q string) *parseCacheValue {
-	pc.requests.Add(1)
-
-	pc.mu.RLock()
-	pcv := pc.m[q]
-	pc.mu.RUnlock()
-
-	if pcv == nil {
-		pc.misses.Add(1)
-	}
-	return pcv
-}
-
-func (pc *parseCache) Put(q string, pcv *parseCacheValue) {
-	pc.mu.Lock()
-	overflow := len(pc.m) - parseCacheMaxLen
-	if overflow > 0 {
-		// Remove 10% of items from the cache.
-		overflow = int(float64(len(pc.m)) * 0.1)
-		for k := range pc.m {
-			delete(pc.m, k)
-			overflow--
-			if overflow <= 0 {
-				break
-			}
-		}
-	}
-	pc.m[q] = pcv
-	pc.mu.Unlock()
-}
diff --git a/app/vmselect/promql/parse_cache.go b/app/vmselect/promql/parse_cache.go
new file mode 100644
index 000000000..487f5757c
--- /dev/null
+++ b/app/vmselect/promql/parse_cache.go
@@ -0,0 +1,142 @@
+// Cache for metricsql expressions
+// Based on the fastcache idea of locking buckets in order to avoid whole cache locks.
+// See: https://github.com/VictoriaMetrics/fastcache
+package promql
+
+import (
+	"sync"
+	"sync/atomic"
+
+	"github.com/VictoriaMetrics/metrics"
+	"github.com/VictoriaMetrics/metricsql"
+
+	xxhash "github.com/cespare/xxhash/v2"
+)
+
+var parseCacheV = func() *parseCache {
+	pc := newParseCache()
+	metrics.NewGauge(`vm_cache_requests_total{type="promql/parse"}`, func() float64 {
+		return float64(pc.requests())
+	})
+	metrics.NewGauge(`vm_cache_misses_total{type="promql/parse"}`, func() float64 {
+		return float64(pc.misses())
+	})
+	metrics.NewGauge(`vm_cache_entries{type="promql/parse"}`, func() float64 {
+		return float64(pc.len())
+	})
+	return pc
+}()
+
+const (
+	parseBucketCount = 128
+
+	parseCacheMaxLen int = 10e3
+
+	parseBucketMaxLen int = parseCacheMaxLen / parseBucketCount
+
+	parseBucketFreePercent float64 = 0.1
+)
+
+type parseCacheValue struct {
+	e   metricsql.Expr
+	err error
+}
+
+type parseBucket struct {
+	m        map[string]*parseCacheValue
+	mu       sync.RWMutex
+	requests atomic.Uint64
+	misses   atomic.Uint64
+}
+
+type parseCache struct {
+	buckets [parseBucketCount]parseBucket
+}
+
+func newParseCache() *parseCache {
+	pc := new(parseCache)
+	for i := 0; i < parseBucketCount; i++ {
+		pc.buckets[i] = newParseBucket()
+	}
+	return pc
+}
+
+func (pc *parseCache) put(q string, pcv *parseCacheValue) {
+	h := xxhash.Sum64String(q)
+	idx := h % parseBucketCount
+	pc.buckets[idx].put(q, pcv)
+}
+
+func (pc *parseCache) get(q string) *parseCacheValue {
+	h := xxhash.Sum64String(q)
+	idx := h % parseBucketCount
+	return pc.buckets[idx].get(q)
+}
+
+func (pc *parseCache) requests() uint64 {
+	var n uint64
+	for i := 0; i < parseBucketCount; i++ {
+		n += pc.buckets[i].requests.Load()
+	}
+	return n
+}
+
+func (pc *parseCache) misses() uint64 {
+	var n uint64
+	for i := 0; i < parseBucketCount; i++ {
+		n += pc.buckets[i].misses.Load()
+	}
+	return n
+}
+
+func (pc *parseCache) len() uint64 {
+	var n uint64
+	for i := 0; i < parseBucketCount; i++ {
+		n += pc.buckets[i].len()
+	}
+	return n
+}
+
+func newParseBucket() parseBucket {
+	return parseBucket{
+		m: make(map[string]*parseCacheValue, parseBucketMaxLen),
+	}
+}
+
+func (pb *parseBucket) len() uint64 {
+	pb.mu.RLock()
+	n := len(pb.m)
+	pb.mu.RUnlock()
+	return uint64(n)
+}
+
+func (pb *parseBucket) get(q string) *parseCacheValue {
+	pb.requests.Add(1)
+
+	pb.mu.RLock()
+	pcv := pb.m[q]
+	pb.mu.RUnlock()
+
+	if pcv == nil {
+		pb.misses.Add(1)
+	}
+	return pcv
+}
+
+func (pb *parseBucket) put(q string, pcv *parseCacheValue) {
+	pb.mu.Lock()
+	overflow := len(pb.m) - parseBucketMaxLen
+	if overflow > 0 {
+		// Remove parseBucketDeletePercent*100 % of items from the bucket.
+		overflow = int(float64(len(pb.m)) * parseBucketFreePercent)
+		for k := range pb.m {
+			delete(pb.m, k)
+			overflow--
+			if overflow <= 0 {
+				break
+			}
+		}
+	}
+	pb.m[q] = pcv
+	pb.mu.Unlock()
+}
diff --git a/deployment/docker/Makefile b/deployment/docker/Makefile
index bc1d23068..8bdcc4f1e 100644
--- a/deployment/docker/Makefile
+++ b/deployment/docker/Makefile
@@ -66,6 +66,12 @@ package-via-docker: package-base
 		$(DOCKER_BUILD) \
 			--build-arg src_binary=$(APP_NAME)$(APP_SUFFIX)-prod \
 			--build-arg base_image=$(BASE_IMAGE) \
+			--label "org.opencontainers.image.source=https://github.com/VictoriaMetrics/VictoriaMetrics" \
+			--label "org.opencontainers.image.documentation=https://docs.victoriametrics.com/" \
+			--label "org.opencontainers.image.title=$(APP_NAME)" \
+			--label "org.opencontainers.image.vendor=VictoriaMetrics" \
+			--label "org.opencontainers.image.version=$(PKG_TAG)" \
+			--label "org.opencontainers.image.created=$(shell date -u +"%Y-%m-%dT%H:%M:%SZ")" \
 			--tag $(DOCKER_NAMESPACE)/$(APP_NAME):$(PKG_TAG)$(APP_SUFFIX)$(RACE) \
 			-f app/$(APP_NAME)/deployment/Dockerfile bin)
 
@@ -80,6 +86,12 @@ publish-via-docker:
 		--build-arg certs_image=$(CERTS_IMAGE) \
 		--build-arg root_image=$(ROOT_IMAGE) \
 		--build-arg APP_NAME=$(APP_NAME) \
+		--label "org.opencontainers.image.source=https://github.com/VictoriaMetrics/VictoriaMetrics" \
+		--label "org.opencontainers.image.documentation=https://docs.victoriametrics.com/" \
+		--label "org.opencontainers.image.title=$(APP_NAME)" \
+		--label "org.opencontainers.image.vendor=VictoriaMetrics" \
+		--label "org.opencontainers.image.version=$(PKG_TAG)" \
+		--label "org.opencontainers.image.created=$(shell date -u +"%Y-%m-%dT%H:%M:%SZ")" \
 		--tag $(DOCKER_NAMESPACE)/$(APP_NAME):$(PKG_TAG)$(RACE) \
 		--tag $(DOCKER_NAMESPACE)/$(APP_NAME):$(LATEST_TAG)$(RACE) \
 		-o type=image \
@@ -92,6 +104,12 @@ publish-via-docker:
 		--build-arg certs_image=$(CERTS_IMAGE) \
 		--build-arg root_image=$(ROOT_IMAGE_SCRATCH) \
 		--build-arg APP_NAME=$(APP_NAME) \
+		--label "org.opencontainers.image.source=https://github.com/VictoriaMetrics/VictoriaMetrics" \
+		--label "org.opencontainers.image.documentation=https://docs.victoriametrics.com/" \
+		--label "org.opencontainers.image.title=$(APP_NAME)" \
+		--label "org.opencontainers.image.vendor=VictoriaMetrics" \
+		--label "org.opencontainers.image.version=$(PKG_TAG)" \
+		--label "org.opencontainers.image.created=$(shell date -u +"%Y-%m-%dT%H:%M:%SZ")" \
 		--tag $(DOCKER_NAMESPACE)/$(APP_NAME):$(PKG_TAG)$(RACE)-scratch \
 		--tag $(DOCKER_NAMESPACE)/$(APP_NAME):$(LATEST_TAG)$(RACE)-scratch \
 		-o type=image \
diff --git a/docs/changelog/CHANGELOG.md b/docs/changelog/CHANGELOG.md
index bc2c9d23e..697674e71 100644
--- a/docs/changelog/CHANGELOG.md
+++ b/docs/changelog/CHANGELOG.md
@@ -24,6 +24,7 @@ See also [LTS releases](https://docs.victoriametrics.com/lts-releases/).
 * FEATURE: [vmagent](https://docs.victoriametrics.com/vmagent/) and [Single-node VictoriaMetrics](https://docs.victoriametrics.com/): added `min` and `max` metrics for Datadog Sketches API metrics, changed `_` metric name separator to `.` if metrics are not sanitized for consistency.
 * FEATURE: [Single-node VictoriaMetrics](https://docs.victoriametrics.com/): support `-maxIngestionRate` cmd-line flag to ratelimit samples/sec ingested. See [this issue](https://github.com/VictoriaMetrics/VictoriaMetrics/issues/7377) for details.
 * FEATURE: [vminsert](https://docs.victoriametrics.com/vminsert/): Storage nodes defined in `-storageNode` are now sorted, ensuring that varying node orders across different vminsert instances do not result in inconsistent replication.
+* FEATURE: [vmsingle](https://docs.victoriametrics.com/single-server-victoriametrics/) and `vmselect` in [VictoriaMetrics cluster](https://docs.victoriametrics.com/cluster-victoriametrics/): improve query performance on systems with high number of CPU cores. See [this PR](https://github.com/VictoriaMetrics/VictoriaMetrics/pull/7416) for details.
 
 * BUGFIX: [dashboards](https://github.com/VictoriaMetrics/VictoriaMetrics/blob/master/dashboards): consistently use `vmagent_remotewrite_pending_data_bytes` on vmagent dashboard to represent persistent queue size.
 * BUGFIX: [vmalert](https://docs.victoriametrics.com/vmalert/): fix the auto-generated metrics `ALERTS` and `ALERTS_FOR_STATE` for alerting rules. Previously, metrics might have incorrect labels and affect the restore process. See this [issue](https://github.com/VictoriaMetrics/VictoriaMetrics/issues/7796).
@@ -39,7 +40,8 @@ Released at 2024-12-18
 
 * BUGFIX: [vmsingle](https://docs.victoriametrics.com/single-server-victoriametrics/) properly apply `-relabelConfig` rules for data ingestion protocols. Issue was introduced at [v1.108.0](https://github.com/VictoriaMetrics/VictoriaMetrics/releases/tag/v1.108.0) and only affects vmsingle.
  release. See [this issue](https://github.com/VictoriaMetrics/VictoriaMetrics/issues/7865) for details.
-* BUGFIX: [vmsingle](https://docs.victoriametrics.com/single-server-victoriametrics/), `vmselect` in [VictoriaMetrics cluster](https://docs.victoriametrics.com/cluster-victoriametrics/): make instant query results consistent. VictoriaMetrics detects and adjusts scrape interval and while this is very useful for range queries (i.e. this eliminates gaps on the graph), it may cause instant queries to return a non-empty result when no result is expected. The fix is to disable scrape interval detection and always use the step as the scrape interval in instant queries. This will guarantee that the samples are searched within the (time-step, time] interval. See [this issue](https://github.com/VictoriaMetrics/VictoriaMetrics/issues/5796) for details.
+* BUGFIX: [vmsingle](https://docs.victoriametrics.com/single-server-victoriametrics/), `vmselect` in [VictoriaMetrics cluster](https://docs.victoriametrics.com/cluster-victoriametrics/): make instant query results consistent. VictoriaMetrics detects and adjusts scrape interval and while this is very useful for range queries (i.e. this eliminates gaps on the graph), it may cause instant queries to return a non-empty result when no result is expected. The fix is to disable scrape interval detection and always use the step as the scrape interval in instant queries. This will guarantee that the samples are searched within the (time-step, time] interval. See [this issue](https://github.com/VictoriaMetrics/VictoriaMetrics/issues/
+) for details.
 * BUGFIX: [vmui](https://docs.victoriametrics.com/#vmui): fix cursor reset in query input field. See [this issue](https://github.com/VictoriaMetrics/VictoriaMetrics/issues/7288).
 
 ## [v1.108.0](https://github.com/VictoriaMetrics/VictoriaMetrics/releases/tag/v1.108.0)


Test patch:
diff --git a/app/vmselect/promql/parse_cache_test.go b/app/vmselect/promql/parse_cache_test.go
new file mode 100644
index 000000000..d75cf9452
--- /dev/null
+++ b/app/vmselect/promql/parse_cache_test.go
@@ -0,0 +1,129 @@
+package promql
+
+import (
+	"fmt"
+	"testing"
+
+	"github.com/VictoriaMetrics/metricsql"
+)
+
+func testGetParseCacheValue(q string) *parseCacheValue {
+	e, err := metricsql.Parse(q)
+	return &parseCacheValue{
+		e:   e,
+		err: err,
+	}
+}
+
+func testGenerateQueries(items int) []string {
+	queries := make([]string, items)
+	for i := 0; i < items; i++ {
+		queries[i] = fmt.Sprintf(`node_time_seconds{instance="node%d", job="job%d"}`, i, i)
+	}
+	return queries
+}
+
+func TestParseCache(t *testing.T) {
+	pc := newParseCache()
+	if pc.len() != 0 || pc.misses() != 0 || pc.requests() != 0 {
+		t.Errorf("unexpected pc.Len()=%d, pc.Misses()=%d, pc.Requests()=%d; expected all to be zero.", pc.len(), pc.misses(), pc.requests())
+	}
+
+	q1 := `foo{bar="baz"}`
+	v1 := testGetParseCacheValue(q1)
+
+	q2 := `foo1{bar1="baz1"}`
+	v2 := testGetParseCacheValue(q2)
+
+	pc.put(q1, v1)
+	if pc.len() != 1 {
+		t.Errorf("unexpected value obtained; got %d; want %d", pc.len(), 1)
+	}
+
+	if res := pc.get(q2); res != nil {
+		t.Errorf("unexpected non-empty value obtained from cache: %d ", res)
+	}
+	if pc.len() != 1 {
+		t.Errorf("unexpected value obtained; got %d; want %d", pc.len(), 1)
+	}
+	if miss := pc.misses(); miss != 1 {
+		t.Errorf("unexpected value obtained; got %d; want %d", miss, 1)
+	}
+	if req := pc.requests(); req != 1 {
+		t.Errorf("unexpected value obtained; got %d; want %d", req, 1)
+	}
+
+	pc.put(q2, v2)
+	if pc.len() != 2 {
+		t.Errorf("unexpected value obtained; got %d; want %d", pc.len(), 2)
+	}
+
+	if res := pc.get(q1); res != v1 {
+		t.Errorf("unexpected value obtained; got %v; want %v", res, v1)
+	}
+
+	if res := pc.get(q2); res != v2 {
+		t.Errorf("unexpected value obtained; got %v; want %v", res, v2)
+	}
+
+	pc.put(q2, v2)
+	if pc.len() != 2 {
+		t.Errorf("unexpected value obtained; got %d; want %d", pc.len(), 2)
+	}
+	if miss := pc.misses(); miss != 1 {
+		t.Errorf("unexpected value obtained; got %d; want %d", miss, 1)
+	}
+	if req := pc.requests(); req != 3 {
+		t.Errorf("unexpected value obtained; got %d; want %d", req, 3)
+	}
+
+	if res := pc.get(q2); res != v2 {
+		t.Errorf("unexpected value obtained; got %v; want %v", res, v2)
+	}
+	if pc.len() != 2 {
+		t.Errorf("unexpected value obtained; got %d; want %d", pc.len(), 2)
+	}
+	if miss := pc.misses(); miss != 1 {
+		t.Errorf("unexpected value obtained; got %d; want %d", miss, 1)
+	}
+	if req := pc.requests(); req != 4 {
+		t.Errorf("unexpected value obtained; got %d; want %d", req, 4)
+	}
+}
+
+func TestParseCacheBucketOverflow(t *testing.T) {
+	b := newParseBucket()
+	var expectedLen uint64
+
+	// +2 for overflow and clean up
+	queries := testGenerateQueries(parseBucketMaxLen + 2)
+
+	// Same value for all keys
+	v := testGetParseCacheValue(queries[0])
+
+	// Fill bucket
+	for i := 0; i < parseBucketMaxLen; i++ {
+		b.put(queries[i], v)
+	}
+	expectedLen = uint64(parseBucketMaxLen)
+	if b.len() != expectedLen {
+		t.Errorf("unexpected value obtained; got %v; want %v", b.len(), expectedLen)
+	}
+
+	// Overflow bucket
+	expectedLen = uint64(parseBucketMaxLen + 1)
+	b.put(queries[parseBucketMaxLen], v)
+	if b.len() != uint64(expectedLen) {
+		t.Errorf("unexpected value obtained; got %v; want %v", b.len(), expectedLen)
+	}
+
+	// Clean up;
+	oldLen := b.len()
+	overflow := int(float64(oldLen) * parseBucketFreePercent)
+	expectedLen = oldLen - uint64(overflow) + 1 // +1 for new entry
+
+	b.put(queries[parseBucketMaxLen+1], v)
+	if b.len() != expectedLen {
+		t.Errorf("unexpected value obtained; got %v; want %v", b.len(), expectedLen)
+	}
+}
diff --git a/app/vmselect/promql/parse_cache_timing_test.go b/app/vmselect/promql/parse_cache_timing_test.go
new file mode 100644
index 000000000..bfba83c3d
--- /dev/null
+++ b/app/vmselect/promql/parse_cache_timing_test.go
@@ -0,0 +1,235 @@
+package promql
+
+import (
+	"testing"
+)
+
+func BenchmarkCachePutNoOverFlow(b *testing.B) {
+	const items int = (parseCacheMaxLen / 2)
+	pc := newParseCache()
+
+	queries := testGenerateQueries(items)
+	v := testGetParseCacheValue(queries[0])
+
+	b.ResetTimer()
+	b.ReportAllocs()
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			for i := 0; i < items; i++ {
+				pc.put(queries[i], v)
+			}
+		}
+	})
+	if pc.len() != uint64(items) {
+		b.Errorf("unexpected value obtained; got %d; want %d", pc.len(), items)
+	}
+}
+
+func BenchmarkCacheGetNoOverflow(b *testing.B) {
+	const items int = parseCacheMaxLen / 2
+	pc := newParseCache()
+
+	queries := testGenerateQueries(items)
+	v := testGetParseCacheValue(queries[0])
+
+	for i := 0; i < len(queries); i++ {
+		pc.put(queries[i], v)
+	}
+	b.ResetTimer()
+	b.ReportAllocs()
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			for i := 0; i < items; i++ {
+				if v := pc.get(queries[i]); v == nil {
+					b.Errorf("unexpected nil value obtained from cache for query: %s ", queries[i])
+				}
+			}
+		}
+	})
+}
+
+func BenchmarkCachePutGetNoOverflow(b *testing.B) {
+	const items int = parseCacheMaxLen / 2
+	pc := newParseCache()
+
+	queries := testGenerateQueries(items)
+	v := testGetParseCacheValue(queries[0])
+
+	b.ResetTimer()
+	b.ReportAllocs()
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			for i := 0; i < items; i++ {
+				pc.put(queries[i], v)
+				if res := pc.get(queries[i]); res == nil {
+					b.Errorf("unexpected nil value obtained from cache for query: %s ", queries[i])
+				}
+			}
+		}
+	})
+	if pc.len() != uint64(items) {
+		b.Errorf("unexpected value obtained; got %d; want %d", pc.len(), items)
+	}
+}
+
+func BenchmarkCachePutOverflow(b *testing.B) {
+	const items int = parseCacheMaxLen + (parseCacheMaxLen / 2)
+	c := newParseCache()
+
+	queries := testGenerateQueries(items)
+	v := testGetParseCacheValue(queries[0])
+
+	for i := 0; i < parseCacheMaxLen; i++ {
+		c.put(queries[i], v)
+	}
+
+	b.ReportAllocs()
+	b.ResetTimer()
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			for i := parseCacheMaxLen; i < items; i++ {
+				c.put(queries[i], v)
+			}
+		}
+	})
+	maxElemnts := uint64(parseCacheMaxLen + parseBucketCount)
+	if c.len() > maxElemnts {
+		b.Errorf("cache length is more than expected; got %d, expected %d", c.len(), maxElemnts)
+	}
+}
+
+func BenchmarkCachePutGetOverflow(b *testing.B) {
+	const items int = parseCacheMaxLen + (parseCacheMaxLen / 2)
+	c := newParseCache()
+
+	queries := testGenerateQueries(items)
+	v := testGetParseCacheValue(queries[0])
+
+	for i := 0; i < parseCacheMaxLen; i++ {
+		c.put(queries[i], v)
+	}
+
+	b.ReportAllocs()
+	b.ResetTimer()
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			for i := parseCacheMaxLen; i < items; i++ {
+				c.put(queries[i], v)
+				c.get(queries[i])
+			}
+		}
+	})
+	maxElemnts := uint64(parseCacheMaxLen + parseBucketCount)
+	if c.len() > maxElemnts {
+		b.Errorf("cache length is more than expected; got %d, expected %d", c.len(), maxElemnts)
+	}
+}
+
+var testSimpleQueries = []string{
+	`m{a="b"}`,
+	`{a="b"}`,
+	`m{c="d",a="b"}`,
+	`{a="b",c="d"}`,
+	`m1{a="foo"}`,
+	`m2{a="bar"}`,
+	`m1{b="foo"}`,
+	`m2{b="bar"}`,
+	`m1{a="foo",b="bar"}`,
+	`m2{b="bar",c="x"}`,
+	`{b="bar"}`,
+}
+
+func BenchmarkParsePromQLWithCacheSimple(b *testing.B) {
+	b.ReportAllocs()
+	for i := 0; i < b.N; i++ {
+		for j := 0; j < len(testSimpleQueries); j++ {
+			_, err := parsePromQLWithCache(testSimpleQueries[j])
+			if err != nil {
+				b.Errorf("unexpected error: %s", err)
+			}
+		}
+	}
+}
+
+func BenchmarkParsePromQLWithCacheSimpleParallel(b *testing.B) {
+	b.ReportAllocs()
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			for i := 0; i < len(testSimpleQueries); i++ {
+				_, err := parsePromQLWithCache(testSimpleQueries[i])
+				if err != nil {
+					b.Errorf("unexpected error: %s", err)
+				}
+			}
+		}
+	})
+}
+
+var testComplexQueries = []string{
+	`sort_desc(label_set(2, "foo", "bar") * ignoring(a) (label_set(time(), "foo", "bar") or label_set(10, "foo", "qwert")))`,
+	`sum(a.b{c="d.e",x=~"a.b.+[.a]",y!~"aaa.bb|cc.dd"}) + avg_over_time(1,sum({x=~"aa.bb"}))`,
+	`sort((label_set(time() offset 100s, "foo", "bar"), label_set(time()+10, "foo", "baz") offset 50s) offset 400s)`,
+	`sort(label_map((
+			label_set(time(), "label", "v1"),
+			label_set(time()+100, "label", "v2"),
+			label_set(time()+200, "label", "v3"),
+			label_set(time()+300, "x", "y"),
+			label_set(time()+400, "label", "v4"),
+		), "label", "v1", "foo", "v2", "bar", "", "qwe", "v4", ""))`,
+	`sort(labels_equal((
+			label_set(10, "instance", "qwe", "host", "rty"),
+			label_set(20, "instance", "qwe", "host", "qwe"),
+			label_set(30, "aaa", "bbb", "instance", "foo", "host", "foo"),
+		), "instance", "host"))`,
+	`with (
+			x = (
+				label_set(time() > 1500, "foo", "123.456", "__name__", "aaa"),
+				label_set(-time(), "foo", "bar", "__name__", "bbb"),
+				label_set(-time(), "__name__", "bxs"),
+				label_set(-time(), "foo", "45", "bar", "xs"),
+			)
+		)
+		sort(x + label_value(x, "foo"))`,
+	`label_replace(
+			label_replace(
+				label_replace(time(), "__name__", "x${1}y", "foo", ".*"),
+				"xxx", "foo${1}bar(${1})", "__name__", "(.+)"),
+			"xxx", "AA$1", "xxx", "foox(.+)"
+		)`,
+	`sort_desc(union(
+			label_set(time() > 1400, "__name__", "x", "foo", "bar"),
+			label_set(time() < 1700, "__name__", "y", "foo", "baz")) default 123)`,
+	`sort(histogram_quantile(0.6,
+			label_set(90, "foo", "bar", "le", "10")
+			or label_set(100, "foo", "bar", "le", "30")
+			or label_set(300, "foo", "bar", "le", "+Inf")
+			or label_set(200, "tag", "xx", "le", "10")
+			or label_set(300, "tag", "xx", "le", "30")
+		))`,
+}
+
+func BenchmarkParsePromQLWithCacheComplex(b *testing.B) {
+	b.ReportAllocs()
+	for i := 0; i < b.N; i++ {
+		for j := 0; j < len(testComplexQueries); j++ {
+			_, err := parsePromQLWithCache(testComplexQueries[j])
+			if err != nil {
+				b.Errorf("unexpected error: %s", err)
+			}
+		}
+	}
+}
+
+func BenchmarkParsePromQLWithCacheComplexParallel(b *testing.B) {
+	b.ReportAllocs()
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			for i := 0; i < len(testComplexQueries); i++ {
+				_, err := parsePromQLWithCache(testComplexQueries[i])
+				if err != nil {
+					b.Errorf("unexpected error: %s", err)
+				}
+			}
+		}
+	})
+}