Repository: VictoriaMetrics/VictoriaMetrics
Pull request #900 (2020-11-16 15:56:58)

Fixes a typo in readme.md


Patch:
diff --git a/README.md b/README.md
index ef0575dd5..1214efa5b 100644
--- a/README.md
+++ b/README.md
@@ -181,7 +181,7 @@ or [an alternative dashboard for VictoriaMetrics cluster](https://grafana.com/gr
      - `prometheus/api/v1/import/csv` - for importing arbitrary CSV data. See [these docs](https://github.com/VictoriaMetrics/VictoriaMetrics/blob/master/README.md#how-to-import-csv-data) for details.
      - `prometheus/api/v1/import/prometheus` - for importing data in Prometheus exposition format. See [these docs](https://github.com/VictoriaMetrics/VictoriaMetrics/blob/master/README.md#how-to-import-data-in-prometheus-exposition-format) for details.
 
-* URLs for [Prmetheus querying API](https://prometheus.io/docs/prometheus/latest/querying/api/): `http://<vmselect>:8481/select/<accountID>/prometheus/<suffix>`, where:
+* URLs for [Prometheus querying API](https://prometheus.io/docs/prometheus/latest/querying/api/): `http://<vmselect>:8481/select/<accountID>/prometheus/<suffix>`, where:
   - `<accountID>` is an arbitrary number identifying data namespace for the query (aka tenant)
   - `<suffix>` may have the following values:
     - `api/v1/query` - performs [PromQL instant query](https://prometheus.io/docs/prometheus/latest/querying/api/#instant-queries).
@@ -205,6 +205,11 @@ or [an alternative dashboard for VictoriaMetrics cluster](https://grafana.com/gr
       - `metrics/find` - searches Graphite metrics. See [these docs](https://graphite-api.readthedocs.io/en/latest/api.html#metrics-find).
       - `metrics/expand` - expands Graphite metrics. See [these docs](https://graphite-api.readthedocs.io/en/latest/api.html#metrics-expand).
       - `metrics/index.json` - returns all the metric names. See [these docs](https://graphite-api.readthedocs.io/en/latest/api.html#metrics-index-json).
+      - `tags` - returns tag names. See [these docs](https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags).
+      - `tags/<tag_name>` - returns tag values for the given `<tag_name>`. See [these docs](https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags).
+      - `tags/findSeries` - returns series matching the given `expr`. See [these docs](https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags).
+      - `tags/autoComplete/tags` - returns tags matching the given `tagPrefix` and/or `expr`. See [these docs](https://graphite.readthedocs.io/en/stable/tags.html#auto-complete-support).
+      - `tags/autoComplete/values` - returns tag values matching the given `valuePrefix` and/or `expr`. See [these docs](https://graphite.readthedocs.io/en/stable/tags.html#auto-complete-support).
 
 * URL for time series deletion: `http://<vmselect>:8481/delete/<accountID>/prometheus/api/v1/admin/tsdb/delete_series?match[]=<timeseries_selector_for_delete>`.
   Note that the `delete_series` handler should be used only in exceptional cases such as deletion of accidentally ingested incorrect time series. It shouldn't
diff --git a/app/vmselect/graphite/graphite.go b/app/vmselect/graphite/metrics_api.go
similarity index 97%
rename from app/vmselect/graphite/graphite.go
rename to app/vmselect/graphite/metrics_api.go
index 554e0322f..de6796342 100644
--- a/app/vmselect/graphite/graphite.go
+++ b/app/vmselect/graphite/metrics_api.go
@@ -86,10 +86,7 @@ func MetricsFindHandler(startTime time.Time, at *auth.Token, w http.ResponseWrit
 	}
 	paths = deduplicatePaths(paths, delimiter)
 	sortPaths(paths, delimiter)
-	contentType := "application/json; charset=utf-8"
-	if jsonp != "" {
-		contentType = "text/javascript; charset=utf-8"
-	}
+	contentType := getContentType(jsonp)
 	w.Header().Set("Content-Type", contentType)
 	bw := bufferedwriter.Get(w)
 	defer bufferedwriter.Put(bw)
@@ -173,10 +170,7 @@ func MetricsExpandHandler(startTime time.Time, at *auth.Token, w http.ResponseWr
 		}
 		m[query] = paths
 	}
-	contentType := "application/json; charset=utf-8"
-	if jsonp != "" {
-		contentType = "text/javascript; charset=utf-8"
-	}
+	contentType := getContentType(jsonp)
 	w.Header().Set("Content-Type", contentType)
 	if groupByExpr {
 		for _, paths := range m {
@@ -223,10 +217,7 @@ func MetricsIndexHandler(startTime time.Time, at *auth.Token, w http.ResponseWri
 	if err != nil {
 		return fmt.Errorf(`cannot obtain metric names: %w`, err)
 	}
-	contentType := "application/json; charset=utf-8"
-	if jsonp != "" {
-		contentType = "text/javascript; charset=utf-8"
-	}
+	contentType := getContentType(jsonp)
 	w.Header().Set("Content-Type", contentType)
 	bw := bufferedwriter.Get(w)
 	defer bufferedwriter.Put(bw)
@@ -429,3 +420,10 @@ var regexpCache = make(map[regexpCacheKey]*regexpCacheEntry)
 var regexpCacheLock sync.Mutex
 
 const maxRegexpCacheSize = 10000
+
+func getContentType(jsonp string) string {
+	if jsonp == "" {
+		return "application/json; charset=utf-8"
+	}
+	return "text/javascript; charset=utf-8"
+}
diff --git a/app/vmselect/graphite/graphite_test.go b/app/vmselect/graphite/metrics_api_test.go
similarity index 100%
rename from app/vmselect/graphite/graphite_test.go
rename to app/vmselect/graphite/metrics_api_test.go
diff --git a/app/vmselect/graphite/tag_values_response.qtpl b/app/vmselect/graphite/tag_values_response.qtpl
new file mode 100644
index 000000000..497e37689
--- /dev/null
+++ b/app/vmselect/graphite/tag_values_response.qtpl
@@ -0,0 +1,21 @@
+{% stripspace %}
+
+Tags generates response for /tags/<tag_name> handler
+See https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags
+{% func TagValuesResponse(isPartial bool, tagName string, tagValues []string) %}
+{
+	"tag":{%q= tagName %},
+	{% if isPartial %}"is_partial":true,{% endif %}
+	"values":[
+	{% for i, value := range tagValues %}
+		{
+			"count":1,
+			"value":{%q= value %}
+		}
+		{% if i+1 < len(tagValues) %},{% endif %}
+	{% endfor %}
+	]
+}
+{% endfunc %}
+
+{% endstripspace %}
diff --git a/app/vmselect/graphite/tag_values_response.qtpl.go b/app/vmselect/graphite/tag_values_response.qtpl.go
new file mode 100644
index 000000000..747152f8a
--- /dev/null
+++ b/app/vmselect/graphite/tag_values_response.qtpl.go
@@ -0,0 +1,83 @@
+// Code generated by qtc from "tag_values_response.qtpl". DO NOT EDIT.
+// See https://github.com/valyala/quicktemplate for details.
+
+// Tags generates response for /tags/<tag_name> handlerSee https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags
+
+//line app/vmselect/graphite/tag_values_response.qtpl:5
+package graphite
+
+//line app/vmselect/graphite/tag_values_response.qtpl:5
+import (
+	qtio422016 "io"
+
+	qt422016 "github.com/valyala/quicktemplate"
+)
+
+//line app/vmselect/graphite/tag_values_response.qtpl:5
+var (
+	_ = qtio422016.Copy
+	_ = qt422016.AcquireByteBuffer
+)
+
+//line app/vmselect/graphite/tag_values_response.qtpl:5
+func StreamTagValuesResponse(qw422016 *qt422016.Writer, isPartial bool, tagName string, tagValues []string) {
+//line app/vmselect/graphite/tag_values_response.qtpl:5
+	qw422016.N().S(`{"tag":`)
+//line app/vmselect/graphite/tag_values_response.qtpl:7
+	qw422016.N().Q(tagName)
+//line app/vmselect/graphite/tag_values_response.qtpl:7
+	qw422016.N().S(`,`)
+//line app/vmselect/graphite/tag_values_response.qtpl:8
+	if isPartial {
+//line app/vmselect/graphite/tag_values_response.qtpl:8
+		qw422016.N().S(`"is_partial":true,`)
+//line app/vmselect/graphite/tag_values_response.qtpl:8
+	}
+//line app/vmselect/graphite/tag_values_response.qtpl:8
+	qw422016.N().S(`"values":[`)
+//line app/vmselect/graphite/tag_values_response.qtpl:10
+	for i, value := range tagValues {
+//line app/vmselect/graphite/tag_values_response.qtpl:10
+		qw422016.N().S(`{"count":1,"value":`)
+//line app/vmselect/graphite/tag_values_response.qtpl:13
+		qw422016.N().Q(value)
+//line app/vmselect/graphite/tag_values_response.qtpl:13
+		qw422016.N().S(`}`)
+//line app/vmselect/graphite/tag_values_response.qtpl:15
+		if i+1 < len(tagValues) {
+//line app/vmselect/graphite/tag_values_response.qtpl:15
+			qw422016.N().S(`,`)
+//line app/vmselect/graphite/tag_values_response.qtpl:15
+		}
+//line app/vmselect/graphite/tag_values_response.qtpl:16
+	}
+//line app/vmselect/graphite/tag_values_response.qtpl:16
+	qw422016.N().S(`]}`)
+//line app/vmselect/graphite/tag_values_response.qtpl:19
+}
+
+//line app/vmselect/graphite/tag_values_response.qtpl:19
+func WriteTagValuesResponse(qq422016 qtio422016.Writer, isPartial bool, tagName string, tagValues []string) {
+//line app/vmselect/graphite/tag_values_response.qtpl:19
+	qw422016 := qt422016.AcquireWriter(qq422016)
+//line app/vmselect/graphite/tag_values_response.qtpl:19
+	StreamTagValuesResponse(qw422016, isPartial, tagName, tagValues)
+//line app/vmselect/graphite/tag_values_response.qtpl:19
+	qt422016.ReleaseWriter(qw422016)
+//line app/vmselect/graphite/tag_values_response.qtpl:19
+}
+
+//line app/vmselect/graphite/tag_values_response.qtpl:19
+func TagValuesResponse(isPartial bool, tagName string, tagValues []string) string {
+//line app/vmselect/graphite/tag_values_response.qtpl:19
+	qb422016 := qt422016.AcquireByteBuffer()
+//line app/vmselect/graphite/tag_values_response.qtpl:19
+	WriteTagValuesResponse(qb422016, isPartial, tagName, tagValues)
+//line app/vmselect/graphite/tag_values_response.qtpl:19
+	qs422016 := string(qb422016.B)
+//line app/vmselect/graphite/tag_values_response.qtpl:19
+	qt422016.ReleaseByteBuffer(qb422016)
+//line app/vmselect/graphite/tag_values_response.qtpl:19
+	return qs422016
+//line app/vmselect/graphite/tag_values_response.qtpl:19
+}
diff --git a/app/vmselect/graphite/tags_api.go b/app/vmselect/graphite/tags_api.go
new file mode 100644
index 000000000..2c2e45764
--- /dev/null
+++ b/app/vmselect/graphite/tags_api.go
@@ -0,0 +1,378 @@
+package graphite
+
+import (
+	"fmt"
+	"net/http"
+	"regexp"
+	"sort"
+	"strconv"
+	"strings"
+	"time"
+
+	"github.com/VictoriaMetrics/VictoriaMetrics/app/vmselect/bufferedwriter"
+	"github.com/VictoriaMetrics/VictoriaMetrics/app/vmselect/netstorage"
+	"github.com/VictoriaMetrics/VictoriaMetrics/app/vmselect/searchutils"
+	"github.com/VictoriaMetrics/VictoriaMetrics/lib/auth"
+	"github.com/VictoriaMetrics/VictoriaMetrics/lib/storage"
+	"github.com/VictoriaMetrics/metrics"
+)
+
+// TagsAutoCompleteValuesHandler implements /tags/autoComplete/values endpoint from Graphite Tags API.
+//
+// See https://graphite.readthedocs.io/en/stable/tags.html#auto-complete-support
+func TagsAutoCompleteValuesHandler(startTime time.Time, at *auth.Token, w http.ResponseWriter, r *http.Request) error {
+	deadline := searchutils.GetDeadlineForQuery(r, startTime)
+	if err := r.ParseForm(); err != nil {
+		return fmt.Errorf("cannot parse form values: %w", err)
+	}
+	limit, err := getInt(r, "limit")
+	if err != nil {
+		return err
+	}
+	if limit <= 0 {
+		// Use limit=100 by default. See https://graphite.readthedocs.io/en/stable/tags.html#auto-complete-support
+		limit = 100
+	}
+	tag := r.FormValue("tag")
+	if len(tag) == 0 {
+		return fmt.Errorf("missing `tag` query arg")
+	}
+	valuePrefix := r.FormValue("valuePrefix")
+	exprs := r.Form["expr"]
+	var tagValues []string
+	denyPartialResponse := searchutils.GetDenyPartialResponse(r)
+	isPartial := false
+	if len(exprs) == 0 {
+		// Fast path: there are no `expr` filters, so use netstorage.GetGraphiteTagValues.
+		// Escape special chars in tagPrefix as Graphite does.
+		// See https://github.com/graphite-project/graphite-web/blob/3ad279df5cb90b211953e39161df416e54a84948/webapp/graphite/tags/base.py#L228
+		filter := regexp.QuoteMeta(valuePrefix)
+		tagValues, isPartial, err = netstorage.GetGraphiteTagValues(at, denyPartialResponse, tag, filter, limit, deadline)
+		if err != nil {
+			return err
+		}
+	} else {
+		// Slow path: use netstorage.SearchMetricNames for applying `expr` filters.
+		sq, err := getSearchQueryForExprs(at, exprs)
+		if err != nil {
+			return err
+		}
+		mns, isPartialResponse, err := netstorage.SearchMetricNames(at, denyPartialResponse, sq, deadline)
+		if err != nil {
+			return fmt.Errorf("cannot fetch metric names for %q: %w", sq, err)
+		}
+		isPartial = isPartialResponse
+		m := make(map[string]struct{})
+		if tag == "name" {
+			tag = "__name__"
+		}
+		for _, mn := range mns {
+			tagValue := mn.GetTagValue(tag)
+			if len(tagValue) == 0 {
+				continue
+			}
+			m[string(tagValue)] = struct{}{}
+		}
+		if len(valuePrefix) > 0 {
+			for tagValue := range m {
+				if !strings.HasPrefix(tagValue, valuePrefix) {
+					delete(m, tagValue)
+				}
+			}
+		}
+		tagValues = make([]string, 0, len(m))
+		for tagValue := range m {
+			tagValues = append(tagValues, tagValue)
+		}
+		sort.Strings(tagValues)
+		if limit > 0 && limit < len(tagValues) {
+			tagValues = tagValues[:limit]
+		}
+	}
+
+	jsonp := r.FormValue("jsonp")
+	contentType := getContentType(jsonp)
+	w.Header().Set("Content-Type", contentType)
+	bw := bufferedwriter.Get(w)
+	defer bufferedwriter.Put(bw)
+	WriteTagsAutoCompleteResponse(bw, isPartial, tagValues, jsonp)
+	if err := bw.Flush(); err != nil {
+		return err
+	}
+	tagsAutoCompleteValuesDuration.UpdateDuration(startTime)
+	return nil
+}
+
+var tagsAutoCompleteValuesDuration = metrics.NewSummary(`vm_request_duration_seconds{path="/tags/autoComplete/values"}`)
+
+// TagsAutoCompleteTagsHandler implements /tags/autoComplete/tags endpoint from Graphite Tags API.
+//
+// See https://graphite.readthedocs.io/en/stable/tags.html#auto-complete-support
+func TagsAutoCompleteTagsHandler(startTime time.Time, at *auth.Token, w http.ResponseWriter, r *http.Request) error {
+	deadline := searchutils.GetDeadlineForQuery(r, startTime)
+	if err := r.ParseForm(); err != nil {
+		return fmt.Errorf("cannot parse form values: %w", err)
+	}
+	limit, err := getInt(r, "limit")
+	if err != nil {
+		return err
+	}
+	if limit <= 0 {
+		// Use limit=100 by default. See https://graphite.readthedocs.io/en/stable/tags.html#auto-complete-support
+		limit = 100
+	}
+	tagPrefix := r.FormValue("tagPrefix")
+	exprs := r.Form["expr"]
+	denyPartialResponse := searchutils.GetDenyPartialResponse(r)
+	var labels []string
+	isPartial := false
+	if len(exprs) == 0 {
+		// Fast path: there are no `expr` filters, so use netstorage.GetGraphiteTags.
+
+		// Escape special chars in tagPrefix as Graphite does.
+		// See https://github.com/graphite-project/graphite-web/blob/3ad279df5cb90b211953e39161df416e54a84948/webapp/graphite/tags/base.py#L181
+		filter := regexp.QuoteMeta(tagPrefix)
+		labels, isPartial, err = netstorage.GetGraphiteTags(at, denyPartialResponse, filter, limit, deadline)
+		if err != nil {
+			return err
+		}
+	} else {
+		// Slow path: use netstorage.SearchMetricNames for applying `expr` filters.
+		sq, err := getSearchQueryForExprs(at, exprs)
+		if err != nil {
+			return err
+		}
+		mns, isPartialResponse, err := netstorage.SearchMetricNames(at, denyPartialResponse, sq, deadline)
+		if err != nil {
+			return fmt.Errorf("cannot fetch metric names for %q: %w", sq, err)
+		}
+		isPartial = isPartialResponse
+		m := make(map[string]struct{})
+		for _, mn := range mns {
+			m["name"] = struct{}{}
+			for _, tag := range mn.Tags {
+				m[string(tag.Key)] = struct{}{}
+			}
+		}
+		if len(tagPrefix) > 0 {
+			for label := range m {
+				if !strings.HasPrefix(label, tagPrefix) {
+					delete(m, label)
+				}
+			}
+		}
+		labels = make([]string, 0, len(m))
+		for label := range m {
+			labels = append(labels, label)
+		}
+		sort.Strings(labels)
+		if limit > 0 && limit < len(labels) {
+			labels = labels[:limit]
+		}
+	}
+
+	jsonp := r.FormValue("jsonp")
+	contentType := getContentType(jsonp)
+	w.Header().Set("Content-Type", contentType)
+	bw := bufferedwriter.Get(w)
+	defer bufferedwriter.Put(bw)
+	WriteTagsAutoCompleteResponse(bw, isPartial, labels, jsonp)
+	if err := bw.Flush(); err != nil {
+		return err
+	}
+	tagsAutoCompleteTagsDuration.UpdateDuration(startTime)
+	return nil
+}
+
+var tagsAutoCompleteTagsDuration = metrics.NewSummary(`vm_request_duration_seconds{path="/tags/autoComplete/tags"}`)
+
+// TagsFindSeriesHandler implements /tags/findSeries endpoint from Graphite Tags API.
+//
+// See https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags
+func TagsFindSeriesHandler(startTime time.Time, at *auth.Token, w http.ResponseWriter, r *http.Request) error {
+	deadline := searchutils.GetDeadlineForQuery(r, startTime)
+	if err := r.ParseForm(); err != nil {
+		return fmt.Errorf("cannot parse form values: %w", err)
+	}
+	limit, err := getInt(r, "limit")
+	if err != nil {
+		return err
+	}
+	exprs := r.Form["expr"]
+	if len(exprs) == 0 {
+		return fmt.Errorf("expecting at least one `expr` query arg")
+	}
+	sq, err := getSearchQueryForExprs(at, exprs)
+	if err != nil {
+		return err
+	}
+	denyPartialResponse := searchutils.GetDenyPartialResponse(r)
+	mns, isPartial, err := netstorage.SearchMetricNames(at, denyPartialResponse, sq, deadline)
+	if err != nil {
+		return fmt.Errorf("cannot fetch metric names for %q: %w", sq, err)
+	}
+	paths := getCanonicalPaths(mns)
+	if limit > 0 && limit < len(paths) {
+		paths = paths[:limit]
+	}
+
+	w.Header().Set("Content-Type", "application/json; charset=utf-8")
+	bw := bufferedwriter.Get(w)
+	defer bufferedwriter.Put(bw)
+	WriteTagsFindSeriesResponse(bw, isPartial, paths)
+	if err := bw.Flush(); err != nil {
+		return err
+	}
+	tagsFindSeriesDuration.UpdateDuration(startTime)
+	return nil
+}
+
+func getCanonicalPaths(mns []storage.MetricName) []string {
+	paths := make([]string, 0, len(mns))
+	var b []byte
+	var tags []storage.Tag
+	for _, mn := range mns {
+		b = append(b[:0], mn.MetricGroup...)
+		tags = append(tags[:0], mn.Tags...)
+		sort.Slice(tags, func(i, j int) bool {
+			return string(tags[i].Key) < string(tags[j].Key)
+		})
+		for _, tag := range tags {
+			b = append(b, ';')
+			b = append(b, tag.Key...)
+			b = append(b, '=')
+			b = append(b, tag.Value...)
+		}
+		paths = append(paths, string(b))
+	}
+	sort.Strings(paths)
+	return paths
+}
+
+var tagsFindSeriesDuration = metrics.NewSummary(`vm_request_duration_seconds{path="/tags/findSeries"}`)
+
+// TagValuesHandler implements /tags/<tag_name> endpoint from Graphite Tags API.
+//
+// See https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags
+func TagValuesHandler(startTime time.Time, at *auth.Token, tagName string, w http.ResponseWriter, r *http.Request) error {
+	deadline := searchutils.GetDeadlineForQuery(r, startTime)
+	if err := r.ParseForm(); err != nil {
+		return fmt.Errorf("cannot parse form values: %w", err)
+	}
+	limit, err := getInt(r, "limit")
+	if err != nil {
+		return err
+	}
+	filter := r.FormValue("filter")
+	denyPartialResponse := searchutils.GetDenyPartialResponse(r)
+	tagValues, isPartial, err := netstorage.GetGraphiteTagValues(at, denyPartialResponse, tagName, filter, limit, deadline)
+	if err != nil {
+		return err
+	}
+
+	w.Header().Set("Content-Type", "application/json; charset=utf-8")
+	bw := bufferedwriter.Get(w)
+	defer bufferedwriter.Put(bw)
+	WriteTagValuesResponse(bw, isPartial, tagName, tagValues)
+	if err := bw.Flush(); err != nil {
+		return err
+	}
+	tagValuesDuration.UpdateDuration(startTime)
+	return nil
+}
+
+var tagValuesDuration = metrics.NewSummary(`vm_request_duration_seconds{path="/tags/<tag_name>"}`)
+
+// TagsHandler implements /tags endpoint from Graphite Tags API.
+//
+// See https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags
+func TagsHandler(startTime time.Time, at *auth.Token, w http.ResponseWriter, r *http.Request) error {
+	deadline := searchutils.GetDeadlineForQuery(r, startTime)
+	if err := r.ParseForm(); err != nil {
+		return fmt.Errorf("cannot parse form values: %w", err)
+	}
+	limit, err := getInt(r, "limit")
+	if err != nil {
+		return err
+	}
+	filter := r.FormValue("filter")
+	denyPartialResponse := searchutils.GetDenyPartialResponse(r)
+	labels, isPartial, err := netstorage.GetGraphiteTags(at, denyPartialResponse, filter, limit, deadline)
+	if err != nil {
+		return err
+	}
+
+	w.Header().Set("Content-Type", "application/json; charset=utf-8")
+	bw := bufferedwriter.Get(w)
+	defer bufferedwriter.Put(bw)
+	WriteTagsResponse(bw, isPartial, labels)
+	if err := bw.Flush(); err != nil {
+		return err
+	}
+	tagsDuration.UpdateDuration(startTime)
+	return nil
+}
+
+var tagsDuration = metrics.NewSummary(`vm_request_duration_seconds{path="/tags"}`)
+
+func getInt(r *http.Request, argName string) (int, error) {
+	argValue := r.FormValue(argName)
+	if len(argValue) == 0 {
+		return 0, nil
+	}
+	n, err := strconv.Atoi(argValue)
+	if err != nil {
+		return 0, fmt.Errorf("cannot parse %q=%q: %w", argName, argValue, err)
+	}
+	return n, nil
+}
+
+func getSearchQueryForExprs(at *auth.Token, exprs []string) (*storage.SearchQuery, error) {
+	tfs, err := exprsToTagFilters(exprs)
+	if err != nil {
+		return nil, err
+	}
+	ct := time.Now().UnixNano() / 1e6
+	sq := storage.NewSearchQuery(at.AccountID, at.ProjectID, 0, ct, [][]storage.TagFilter{tfs})
+	return sq, nil
+}
+
+func exprsToTagFilters(exprs []string) ([]storage.TagFilter, error) {
+	tfs := make([]storage.TagFilter, 0, len(exprs))
+	for _, expr := range exprs {
+		tf, err := parseFilterExpr(expr)
+		if err != nil {
+			return nil, fmt.Errorf("cannot parse `expr` query arg: %w", err)
+		}
+		tfs = append(tfs, *tf)
+	}
+	return tfs, nil
+}
+
+func parseFilterExpr(s string) (*storage.TagFilter, error) {
+	n := strings.Index(s, "=")
+	if n < 0 {
+		return nil, fmt.Errorf("missing tag value in filter expression %q", s)
+	}
+	tagName := s[:n]
+	tagValue := s[n+1:]
+	isNegative := false
+	if strings.HasSuffix(tagName, "!") {
+		isNegative = true
+		tagName = tagName[:len(tagName)-1]
+	}
+	if tagName == "name" {
+		tagName = ""
+	}
+	isRegexp := false
+	if strings.HasPrefix(tagValue, "~") {
+		isRegexp = true
+		tagValue = "^(?:" + tagValue[1:] + ").*"
+	}
+	return &storage.TagFilter{
+		Key:        []byte(tagName),
+		Value:      []byte(tagValue),
+		IsNegative: isNegative,
+		IsRegexp:   isRegexp,
+	}, nil
+}
diff --git a/app/vmselect/graphite/tags_autocomplete_response.qtpl b/app/vmselect/graphite/tags_autocomplete_response.qtpl
new file mode 100644
index 000000000..900d438cb
--- /dev/null
+++ b/app/vmselect/graphite/tags_autocomplete_response.qtpl
@@ -0,0 +1,16 @@
+{% stripspace %}
+
+TagsAutoCompleteResponse generates responses for /tags/autoComplete/{tags,values} handlers in Graphite Tags API.
+See https://graphite.readthedocs.io/en/stable/tags.html#auto-complete-support
+{% func TagsAutoCompleteResponse(isPartial bool, ss []string, jsonp string) %}
+	{% if jsonp != "" %}{%s= jsonp %}({% endif %}
+	[
+		{% for i, s := range ss %}
+			{%q= s %}
+			{% if i+1 < len(ss) %},{% endif %}
+		{% endfor %}
+	]
+	{% if jsonp != "" %}){% endif %}
+{% endfunc %}
+
+{% endstripspace %}
diff --git a/app/vmselect/graphite/tags_autocomplete_response.qtpl.go b/app/vmselect/graphite/tags_autocomplete_response.qtpl.go
new file mode 100644
index 000000000..f9bec6121
--- /dev/null
+++ b/app/vmselect/graphite/tags_autocomplete_response.qtpl.go
@@ -0,0 +1,81 @@
+// Code generated by qtc from "tags_autocomplete_response.qtpl". DO NOT EDIT.
+// See https://github.com/valyala/quicktemplate for details.
+
+// TagsAutoCompleteResponse generates responses for /tags/autoComplete/{tags,values} handlers in Graphite Tags API.See https://graphite.readthedocs.io/en/stable/tags.html#auto-complete-support
+
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:5
+package graphite
+
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:5
+import (
+	qtio422016 "io"
+
+	qt422016 "github.com/valyala/quicktemplate"
+)
+
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:5
+var (
+	_ = qtio422016.Copy
+	_ = qt422016.AcquireByteBuffer
+)
+
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:5
+func StreamTagsAutoCompleteResponse(qw422016 *qt422016.Writer, isPartial bool, ss []string, jsonp string) {
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:6
+	if jsonp != "" {
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:6
+		qw422016.N().S(jsonp)
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:6
+		qw422016.N().S(`(`)
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:6
+	}
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:6
+	qw422016.N().S(`[`)
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:8
+	for i, s := range ss {
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:9
+		qw422016.N().Q(s)
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:10
+		if i+1 < len(ss) {
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:10
+			qw422016.N().S(`,`)
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:10
+		}
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:11
+	}
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:11
+	qw422016.N().S(`]`)
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:13
+	if jsonp != "" {
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:13
+		qw422016.N().S(`)`)
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:13
+	}
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:14
+}
+
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:14
+func WriteTagsAutoCompleteResponse(qq422016 qtio422016.Writer, isPartial bool, ss []string, jsonp string) {
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:14
+	qw422016 := qt422016.AcquireWriter(qq422016)
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:14
+	StreamTagsAutoCompleteResponse(qw422016, isPartial, ss, jsonp)
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:14
+	qt422016.ReleaseWriter(qw422016)
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:14
+}
+
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:14
+func TagsAutoCompleteResponse(isPartial bool, ss []string, jsonp string) string {
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:14
+	qb422016 := qt422016.AcquireByteBuffer()
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:14
+	WriteTagsAutoCompleteResponse(qb422016, isPartial, ss, jsonp)
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:14
+	qs422016 := string(qb422016.B)
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:14
+	qt422016.ReleaseByteBuffer(qb422016)
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:14
+	return qs422016
+//line app/vmselect/graphite/tags_autocomplete_response.qtpl:14
+}
diff --git a/app/vmselect/graphite/tags_find_series_response.qtpl b/app/vmselect/graphite/tags_find_series_response.qtpl
new file mode 100644
index 000000000..7a25d2fd8
--- /dev/null
+++ b/app/vmselect/graphite/tags_find_series_response.qtpl
@@ -0,0 +1,12 @@
+{% stripspace %}
+
+{% func TagsFindSeriesResponse(isPartial bool, paths []string) %}
+[
+	{% for i, path := range paths %}
+		{%q= path %}
+		{% if i+1 < len(paths) %},{% endif %}
+	{% endfor %}
+]
+{% endfunc %}
+
+{% endstripspace %}
diff --git a/app/vmselect/graphite/tags_find_series_response.qtpl.go b/app/vmselect/graphite/tags_find_series_response.qtpl.go
new file mode 100644
index 000000000..335c8a661
--- /dev/null
+++ b/app/vmselect/graphite/tags_find_series_response.qtpl.go
@@ -0,0 +1,65 @@
+// Code generated by qtc from "tags_find_series_response.qtpl". DO NOT EDIT.
+// See https://github.com/valyala/quicktemplate for details.
+
+//line app/vmselect/graphite/tags_find_series_response.qtpl:3
+package graphite
+
+//line app/vmselect/graphite/tags_find_series_response.qtpl:3
+import (
+	qtio422016 "io"
+
+	qt422016 "github.com/valyala/quicktemplate"
+)
+
+//line app/vmselect/graphite/tags_find_series_response.qtpl:3
+var (
+	_ = qtio422016.Copy
+	_ = qt422016.AcquireByteBuffer
+)
+
+//line app/vmselect/graphite/tags_find_series_response.qtpl:3
+func StreamTagsFindSeriesResponse(qw422016 *qt422016.Writer, isPartial bool, paths []string) {
+//line app/vmselect/graphite/tags_find_series_response.qtpl:3
+	qw422016.N().S(`[`)
+//line app/vmselect/graphite/tags_find_series_response.qtpl:5
+	for i, path := range paths {
+//line app/vmselect/graphite/tags_find_series_response.qtpl:6
+		qw422016.N().Q(path)
+//line app/vmselect/graphite/tags_find_series_response.qtpl:7
+		if i+1 < len(paths) {
+//line app/vmselect/graphite/tags_find_series_response.qtpl:7
+			qw422016.N().S(`,`)
+//line app/vmselect/graphite/tags_find_series_response.qtpl:7
+		}
+//line app/vmselect/graphite/tags_find_series_response.qtpl:8
+	}
+//line app/vmselect/graphite/tags_find_series_response.qtpl:8
+	qw422016.N().S(`]`)
+//line app/vmselect/graphite/tags_find_series_response.qtpl:10
+}
+
+//line app/vmselect/graphite/tags_find_series_response.qtpl:10
+func WriteTagsFindSeriesResponse(qq422016 qtio422016.Writer, isPartial bool, paths []string) {
+//line app/vmselect/graphite/tags_find_series_response.qtpl:10
+	qw422016 := qt422016.AcquireWriter(qq422016)
+//line app/vmselect/graphite/tags_find_series_response.qtpl:10
+	StreamTagsFindSeriesResponse(qw422016, isPartial, paths)
+//line app/vmselect/graphite/tags_find_series_response.qtpl:10
+	qt422016.ReleaseWriter(qw422016)
+//line app/vmselect/graphite/tags_find_series_response.qtpl:10
+}
+
+//line app/vmselect/graphite/tags_find_series_response.qtpl:10
+func TagsFindSeriesResponse(isPartial bool, paths []string) string {
+//line app/vmselect/graphite/tags_find_series_response.qtpl:10
+	qb422016 := qt422016.AcquireByteBuffer()
+//line app/vmselect/graphite/tags_find_series_response.qtpl:10
+	WriteTagsFindSeriesResponse(qb422016, isPartial, paths)
+//line app/vmselect/graphite/tags_find_series_response.qtpl:10
+	qs422016 := string(qb422016.B)
+//line app/vmselect/graphite/tags_find_series_response.qtpl:10
+	qt422016.ReleaseByteBuffer(qb422016)
+//line app/vmselect/graphite/tags_find_series_response.qtpl:10
+	return qs422016
+//line app/vmselect/graphite/tags_find_series_response.qtpl:10
+}
diff --git a/app/vmselect/graphite/tags_response.qtpl b/app/vmselect/graphite/tags_response.qtpl
new file mode 100644
index 000000000..233c2df62
--- /dev/null
+++ b/app/vmselect/graphite/tags_response.qtpl
@@ -0,0 +1,16 @@
+{% stripspace %}
+
+Tags generates response for /tags handler
+See https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags
+{% func TagsResponse(isPartial bool, tags []string) %}
+[
+	{% for i, tag := range tags %}
+		{
+			"tag":{%q= tag %}
+		}
+		{% if i+1 < len(tags) %},{% endif %}
+	{% endfor %}
+]
+{% endfunc %}
+
+{% endstripspace %}
diff --git a/app/vmselect/graphite/tags_response.qtpl.go b/app/vmselect/graphite/tags_response.qtpl.go
new file mode 100644
index 000000000..abc091c6a
--- /dev/null
+++ b/app/vmselect/graphite/tags_response.qtpl.go
@@ -0,0 +1,71 @@
+// Code generated by qtc from "tags_response.qtpl". DO NOT EDIT.
+// See https://github.com/valyala/quicktemplate for details.
+
+// Tags generates response for /tags handlerSee https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags
+
+//line app/vmselect/graphite/tags_response.qtpl:5
+package graphite
+
+//line app/vmselect/graphite/tags_response.qtpl:5
+import (
+	qtio422016 "io"
+
+	qt422016 "github.com/valyala/quicktemplate"
+)
+
+//line app/vmselect/graphite/tags_response.qtpl:5
+var (
+	_ = qtio422016.Copy
+	_ = qt422016.AcquireByteBuffer
+)
+
+//line app/vmselect/graphite/tags_response.qtpl:5
+func StreamTagsResponse(qw422016 *qt422016.Writer, isPartial bool, tags []string) {
+//line app/vmselect/graphite/tags_response.qtpl:5
+	qw422016.N().S(`[`)
+//line app/vmselect/graphite/tags_response.qtpl:7
+	for i, tag := range tags {
+//line app/vmselect/graphite/tags_response.qtpl:7
+		qw422016.N().S(`{"tag":`)
+//line app/vmselect/graphite/tags_response.qtpl:9
+		qw422016.N().Q(tag)
+//line app/vmselect/graphite/tags_response.qtpl:9
+		qw422016.N().S(`}`)
+//line app/vmselect/graphite/tags_response.qtpl:11
+		if i+1 < len(tags) {
+//line app/vmselect/graphite/tags_response.qtpl:11
+			qw422016.N().S(`,`)
+//line app/vmselect/graphite/tags_response.qtpl:11
+		}
+//line app/vmselect/graphite/tags_response.qtpl:12
+	}
+//line app/vmselect/graphite/tags_response.qtpl:12
+	qw422016.N().S(`]`)
+//line app/vmselect/graphite/tags_response.qtpl:14
+}
+
+//line app/vmselect/graphite/tags_response.qtpl:14
+func WriteTagsResponse(qq422016 qtio422016.Writer, isPartial bool, tags []string) {
+//line app/vmselect/graphite/tags_response.qtpl:14
+	qw422016 := qt422016.AcquireWriter(qq422016)
+//line app/vmselect/graphite/tags_response.qtpl:14
+	StreamTagsResponse(qw422016, isPartial, tags)
+//line app/vmselect/graphite/tags_response.qtpl:14
+	qt422016.ReleaseWriter(qw422016)
+//line app/vmselect/graphite/tags_response.qtpl:14
+}
+
+//line app/vmselect/graphite/tags_response.qtpl:14
+func TagsResponse(isPartial bool, tags []string) string {
+//line app/vmselect/graphite/tags_response.qtpl:14
+	qb422016 := qt422016.AcquireByteBuffer()
+//line app/vmselect/graphite/tags_response.qtpl:14
+	WriteTagsResponse(qb422016, isPartial, tags)
+//line app/vmselect/graphite/tags_response.qtpl:14
+	qs422016 := string(qb422016.B)
+//line app/vmselect/graphite/tags_response.qtpl:14
+	qt422016.ReleaseByteBuffer(qb422016)
+//line app/vmselect/graphite/tags_response.qtpl:14
+	return qs422016
+//line app/vmselect/graphite/tags_response.qtpl:14
+}
diff --git a/app/vmselect/main.go b/app/vmselect/main.go
index c2a41ac9c..53bde539e 100644
--- a/app/vmselect/main.go
+++ b/app/vmselect/main.go
@@ -209,6 +209,16 @@ func selectHandler(startTime time.Time, w http.ResponseWriter, r *http.Request,
 			return true
 		}
 	}
+	if strings.HasPrefix(p.Suffix, "graphite/tags/") && !isGraphiteTagsPath(p.Suffix[len("graphite"):]) {
+		tagName := p.Suffix[len("graphite/tags/"):]
+		graphiteTagValuesRequests.Inc()
+		if err := graphite.TagValuesHandler(startTime, at, tagName, w, r); err != nil {
+			graphiteTagValuesErrors.Inc()
+			httpserver.Errorf(w, r, "error in %q: %s", r.URL.Path, err)
+			return true
+		}
+		return true
+	}
 
 	switch p.Suffix {
 	case "prometheus/api/v1/query":
@@ -336,6 +346,40 @@ func selectHandler(startTime time.Time, w http.ResponseWriter, r *http.Request,
 			return true
 		}
 		return true
+	case "graphite/tags":
+		graphiteTagsRequests.Inc()
+		if err := graphite.TagsHandler(startTime, at, w, r); err != nil {
+			graphiteTagsErrors.Inc()
+			httpserver.Errorf(w, r, "error in %q: %s", r.URL.Path, err)
+			return true
+		}
+		return true
+	case "graphite/tags/findSeries":
+		graphiteTagsFindSeriesRequests.Inc()
+		if err := graphite.TagsFindSeriesHandler(startTime, at, w, r); err != nil {
+			graphiteTagsFindSeriesErrors.Inc()
+			httpserver.Errorf(w, r, "error in %q: %s", r.URL.Path, err)
+			return true
+		}
+		return true
+	case "graphite/tags/autoComplete/tags":
+		graphiteTagsAutoCompleteTagsRequests.Inc()
+		httpserver.EnableCORS(w, r)
+		if err := graphite.TagsAutoCompleteTagsHandler(startTime, at, w, r); err != nil {
+			graphiteTagsAutoCompleteTagsErrors.Inc()
+			httpserver.Errorf(w, r, "error in %q: %s", r.URL.Path, err)
+			return true
+		}
+		return true
+	case "graphite/tags/autoComplete/values":
+		graphiteTagsAutoCompleteValuesRequests.Inc()
+		httpserver.EnableCORS(w, r)
+		if err := graphite.TagsAutoCompleteValuesHandler(startTime, at, w, r); err != nil {
+			graphiteTagsAutoCompleteValuesErrors.Inc()
+			httpserver.Errorf(w, r, "error in %q: %s", r.URL.Path, err)
+			return true
+		}
+		return true
 	case "prometheus/api/v1/rules":
 		// Return dumb placeholder
 		rulesRequests.Inc()
@@ -375,6 +419,18 @@ func deleteHandler(startTime time.Time, w http.ResponseWriter, r *http.Request,
 	}
 }
 
+func isGraphiteTagsPath(path string) bool {
+	switch path {
+	// See https://graphite.readthedocs.io/en/stable/tags.html for a list of Graphite Tags API paths.
+	// Do not include `/tags/<tag_name>` here, since this will fool the caller.
+	case "/tags/tagSeries", "/tags/tagMultiSeries", "/tags/findSeries",
+		"/tags/autoComplete/tags", "/tags/autoComplete/values", "/tags/delSeries":
+		return true
+	default:
+		return false
+	}
+}
+
 func sendPrometheusError(w http.ResponseWriter, r *http.Request, err error) {
 	logger.Warnf("error in %q: %s", r.RequestURI, err)
 
@@ -439,6 +495,21 @@ var (
 	graphiteMetricsIndexRequests = metrics.NewCounter(`vm_http_requests_total{path="/select/{}/graphite/metrics/index.json"}`)
 	graphiteMetricsIndexErrors   = metrics.NewCounter(`vm_http_request_errors_total{path="/select/{}/graphite/metrics/index.json"}`)
 
+	graphiteTagsRequests = metrics.NewCounter(`vm_http_requests_total{path="/select/{}/graphite/tags"}`)
+	graphiteTagsErrors   = metrics.NewCounter(`vm_http_request_errors_total{path="/select/{}/graphite/tags"}`)
+
+	graphiteTagValuesRequests = metrics.NewCounter(`vm_http_requests_total{path="/select/{}/graphite/tags/<tag_name>"}`)
+	graphiteTagValuesErrors   = metrics.NewCounter(`vm_http_request_errors_total{path="/select/{}/graphite/tags/<tag_name>"}`)
+
+	graphiteTagsFindSeriesRequests = metrics.NewCounter(`vm_http_requests_total{path="/select/{}/graphite/tags/findSeries"}`)
+	graphiteTagsFindSeriesErrors   = metrics.NewCounter(`vm_http_request_errors_total{path="/select/{}/graphite/tags/findSeries"}`)
+
+	graphiteTagsAutoCompleteTagsRequests = metrics.NewCounter(`vm_http_requests_total{path="/select/{}/graphite/tags/autoComplete/tags"}`)
+	graphiteTagsAutoCompleteTagsErrors   = metrics.NewCounter(`vm_http_request_errors_total{path="/select/{}/graphite/tags/autoComplete/tags"}`)
+
+	graphiteTagsAutoCompleteValuesRequests = metrics.NewCounter(`vm_http_requests_total{path="/select/{}/graphite/tags/autoComplete/values"}`)
+	graphiteTagsAutoCompleteValuesErrors   = metrics.NewCounter(`vm_http_request_errors_total{path="/select/{}/graphite/tags/autoComplete/values"}`)
+
 	rulesRequests    = metrics.NewCounter(`vm_http_requests_total{path="/select/{}/prometheus/api/v1/rules"}`)
 	alertsRequests   = metrics.NewCounter(`vm_http_requests_total{path="/select/{}/prometheus/api/v1/alerts"}`)
 	metadataRequests = metrics.NewCounter(`vm_http_requests_total{path="/select/{}/prometheus/api/v1/metadata"}`)
diff --git a/app/vmselect/netstorage/netstorage.go b/app/vmselect/netstorage/netstorage.go
index 18da7a503..734726b69 100644
--- a/app/vmselect/netstorage/netstorage.go
+++ b/app/vmselect/netstorage/netstorage.go
@@ -6,6 +6,7 @@ import (
 	"fmt"
 	"io"
 	"net/http"
+	"regexp"
 	"runtime"
 	"sort"
 	"strings"
@@ -557,6 +558,35 @@ func GetLabelsOnTimeRange(at *auth.Token, denyPartialResponse bool, tr storage.T
 	return labels, isPartial, nil
 }
 
+// GetGraphiteTags returns Graphite tags until the given deadline.
+func GetGraphiteTags(at *auth.Token, denyPartialResponse bool, filter string, limit int, deadline searchutils.Deadline) ([]string, bool, error) {
+	if deadline.Exceeded() {
+		return nil, false, fmt.Errorf("timeout exceeded before starting the query processing: %s", deadline.String())
+	}
+	labels, isPartial, err := GetLabels(at, denyPartialResponse, deadline)
+	if err != nil {
+		return nil, false, err
+	}
+	// Substitute "__name__" with "name" for Graphite compatibility
+	for i := range labels {
+		if labels[i] == "__name__" {
+			labels[i] = "name"
+			sort.Strings(labels)
+			break
+		}
+	}
+	if len(filter) > 0 {
+		labels, err = applyGraphiteRegexpFilter(filter, labels)
+		if err != nil {
+			return nil, false, err
+		}
+	}
+	if limit > 0 && limit < len(labels) {
+		labels = labels[:limit]
+	}
+	return labels, isPartial, nil
+}
+
 // GetLabels returns labels until the given deadline.
 func GetLabels(at *auth.Token, denyPartialResponse bool, deadline searchutils.Deadline) ([]string, bool, error) {
 	if deadline.Exceeded() {
@@ -693,6 +723,30 @@ func GetLabelValuesOnTimeRange(at *auth.Token, denyPartialResponse bool, labelNa
 	return labelValues, isPartial, nil
 }
 
+// GetGraphiteTagValues returns tag values for the given tagName until the given deadline.
+func GetGraphiteTagValues(at *auth.Token, denyPartialResponse bool, tagName, filter string, limit int, deadline searchutils.Deadline) ([]string, bool, error) {
+	if deadline.Exceeded() {
+		return nil, false, fmt.Errorf("timeout exceeded before starting the query processing: %s", deadline.String())
+	}
+	if tagName == "name" {
+		tagName = ""
+	}
+	tagValues, isPartial, err := GetLabelValues(at, denyPartialResponse, tagName, deadline)
+	if err != nil {
+		return nil, false, err
+	}
+	if len(filter) > 0 {
+		tagValues, err = applyGraphiteRegexpFilter(filter, tagValues)
+		if err != nil {
+			return nil, false, err
+		}
+	}
+	if limit > 0 && limit < len(tagValues) {
+		tagValues = tagValues[:limit]
+	}
+	return tagValues, isPartial, nil
+}
+
 // GetLabelValues returns label values for the given labelName
 // until the given deadline.
 func GetLabelValues(at *auth.Token, denyPartialResponse bool, labelName string, deadline searchutils.Deadline) ([]string, bool, error) {
@@ -1098,7 +1152,6 @@ func GetSeriesCount(at *auth.Token, denyPartialResponse bool, deadline searchuti
 		}
 		isPartial = true
 	}
-
 	return n, isPartial, nil
 }
 
@@ -1184,6 +1237,81 @@ func ExportBlocks(at *auth.Token, sq *storage.SearchQuery, deadline searchutils.
 	return nil
 }
 
+// SearchMetricNames returns all the metric names matching sq until the given deadline.
+func SearchMetricNames(at *auth.Token, denyPartialResponse bool, sq *storage.SearchQuery, deadline searchutils.Deadline) ([]storage.MetricName, bool, error) {
+	if deadline.Exceeded() {
+		return nil, false, fmt.Errorf("timeout exceeded before starting to search metric names: %s", deadline.String())
+	}
+	requestData := sq.Marshal(nil)
+
+	// Send the query to all the storage nodes in parallel.
+	type nodeResult struct {
+		metricNames [][]byte
+		err         error
+	}
+	resultsCh := make(chan nodeResult, len(storageNodes))
+	for _, sn := range storageNodes {
+		go func(sn *storageNode) {
+			sn.searchMetricNamesRequests.Inc()
+			metricNames, err := sn.processSearchMetricNames(requestData, deadline)
+			if err != nil {
+				sn.searchMetricNamesRequestErrors.Inc()
+				err = fmt.Errorf("cannot search metric names on vmstorage %s: %w", sn.connPool.Addr(), err)
+			}
+			resultsCh <- nodeResult{
+				metricNames: metricNames,
+				err:         err,
+			}
+		}(sn)
+	}
+
+	// Collect results.
+	var errors []error
+	metricNames := make(map[string]struct{})
+	for i := 0; i < len(storageNodes); i++ {
+		// There is no need in timer here, since all the goroutines executing
+		// sn.processSearchQuery must be finished until the deadline.
+		nr := <-resultsCh
+		if nr.err != nil {
+			errors = append(errors, nr.err)
+			continue
+		}
+		for _, metricName := range nr.metricNames {
+			metricNames[string(metricName)] = struct{}{}
+		}
+	}
+	isPartial := false
+	if len(errors) > 0 {
+		if len(errors) == len(storageNodes) {
+			// Return only the first error, since it has no sense in returning all errors.
+			return nil, false, errors[0]
+		}
+
+		// Just return partial results.
+		// This allows gracefully degrade vmselect in the case
+		// if certain storageNodes are temporarily unavailable.
+		// Do not return the error, since it may spam logs on busy vmselect
+		// serving high amounts of requests.
+		partialSearchResults.Inc()
+		if denyPartialResponse {
+			return nil, true, errors[0]
+		}
+		isPartial = true
+	}
+
+	// Unmarshal metricNames
+	mns := make([]storage.MetricName, len(metricNames))
+	i := 0
+	for metricName := range metricNames {
+		mn := &mns[i]
+		if err := mn.Unmarshal(bytesutil.ToUnsafeBytes(metricName)); err != nil {
+			return nil, false, fmt.Errorf("cannot unmarshal metric name obtained from vmstorage: %w; metricName=%q", err, metricName)
+		}
+		i++
+	}
+	return mns, isPartial, nil
+}
+
 // ProcessSearchQuery performs sq until the given deadline.
 //
 // Results.RunParallel or Results.Cancel must be called on the returned Results.
@@ -1346,9 +1474,15 @@ type storageNode struct {
 	// The number of errors during requests to seriesCount.
 	seriesCountRequestErrors *metrics.Counter
 
+	// The number of 'search metric names' requests to storageNode.
+	searchMetricNamesRequests *metrics.Counter
+
 	// The number of search requests to storageNode.
 	searchRequests *metrics.Counter
 
+	// The number of 'search metric names' errors to storageNode.
+	searchMetricNamesRequestErrors *metrics.Counter
+
 	// The number of search request errors to storageNode.
 	searchRequestErrors *metrics.Counter
 
@@ -1540,6 +1674,25 @@ func (sn *storageNode) getSeriesCount(accountID, projectID uint32, deadline sear
 	return n, nil
 }
 
+func (sn *storageNode) processSearchMetricNames(requestData []byte, deadline searchutils.Deadline) ([][]byte, error) {
+	var metricNames [][]byte
+	f := func(bc *handshake.BufferedConn) error {
+		mns, err := sn.processSearchMetricNamesOnConn(bc, requestData)
+		if err != nil {
+			return err
+		}
+		metricNames = mns
+		return nil
+	}
+	if err := sn.execOnConn("searchMetricNames_v1", f, deadline); err != nil {
+		// Try again before giving up.
+		if err = sn.execOnConn("searchMetricNames_v1", f, deadline); err != nil {
+			return nil, err
+		}
+	}
+	return metricNames, nil
+}
+
 func (sn *storageNode) processSearchQuery(requestData []byte, fetchData bool, processBlock func(mb *storage.MetricBlock) error, deadline searchutils.Deadline) error {
 	var blocksRead int
 	f := func(bc *handshake.BufferedConn) error {
@@ -2025,6 +2178,42 @@ const maxMetricBlockSize = 1024 * 1024
 // from vmstorage.
 const maxErrorMessageSize = 64 * 1024
 
+func (sn *storageNode) processSearchMetricNamesOnConn(bc *handshake.BufferedConn, requestData []byte) ([][]byte, error) {
+	// Send the requst to sn.
+	if err := writeBytes(bc, requestData); err != nil {
+		return nil, fmt.Errorf("cannot write requestData: %w", err)
+	}
+	if err := bc.Flush(); err != nil {
+		return nil, fmt.Errorf("cannot flush requestData to conn: %w", err)
+	}
+
+	// Read response error.
+	buf, err := readBytes(nil, bc, maxErrorMessageSize)
+	if err != nil {
+		return nil, fmt.Errorf("cannot read error message: %w", err)
+	}
+	if len(buf) > 0 {
+		return nil, newErrRemote(buf)
+	}
+
+	// Read metricNames from response.
+	metricNamesCount, err := readUint64(bc)
+	if err != nil {
+		return nil, fmt.Errorf("cannot read metricNamesCount: %w", err)
+	}
+	metricNames := make([][]byte, metricNamesCount)
+	for i := int64(0); i < int64(metricNamesCount); i++ {
+		buf, err = readBytes(buf[:0], bc, maxMetricNameSize)
+		if err != nil {
+			return nil, fmt.Errorf("cannot read metricName #%d: %w", i+1, err)
+		}
+		metricNames[i] = append(metricNames[i][:0], buf...)
+	}
+	return metricNames, nil
+}
+
+const maxMetricNameSize = 64 * 1024
+
 func (sn *storageNode) processSearchQueryOnConn(bc *handshake.BufferedConn, requestData []byte, fetchData bool, processBlock func(mb *storage.MetricBlock) error) (int, error) {
 	// Send the request to sn.
 	if err := writeBytes(bc, requestData); err != nil {
@@ -2037,11 +2226,8 @@ func (sn *storageNode) processSearchQueryOnConn(bc *handshake.BufferedConn, requ
 		return 0, fmt.Errorf("cannot flush requestData to conn: %w", err)
 	}
 
-	var err error
-	var buf []byte
-
 	// Read response error.
-	buf, err = readBytes(buf[:0], bc, maxErrorMessageSize)
+	buf, err := readBytes(nil, bc, maxErrorMessageSize)
 	if err != nil {
 		return 0, fmt.Errorf("cannot read error message: %w", err)
 	}
@@ -2195,7 +2381,9 @@ func InitStorageNodes(addrs []string) {
 			tsdbStatusRequestErrors:             metrics.NewCounter(fmt.Sprintf(`vm_request_errors_total{action="tsdbStatus", type="rpcClient", name="vmselect", addr=%q}`, addr)),
 			seriesCountRequests:                 metrics.NewCounter(fmt.Sprintf(`vm_requests_total{action="seriesCount", type="rpcClient", name="vmselect", addr=%q}`, addr)),
 			seriesCountRequestErrors:            metrics.NewCounter(fmt.Sprintf(`vm_request_errors_total{action="seriesCount", type="rpcClient", name="vmselect", addr=%q}`, addr)),
+			searchMetricNamesRequests:           metrics.NewCounter(fmt.Sprintf(`vm_requests_total{action="searchMetricNames", type="rpcClient", name="vmselect", addr=%q}`, addr)),
 			searchRequests:                      metrics.NewCounter(fmt.Sprintf(`vm_requests_total{action="search", type="rpcClient", name="vmselect", addr=%q}`, addr)),
+			searchMetricNamesRequestErrors:      metrics.NewCounter(fmt.Sprintf(`vm_request_errors_total{action="searchMetricNames", type="rpcClient", name="vmselect", addr=%q}`, addr)),
 			searchRequestErrors:                 metrics.NewCounter(fmt.Sprintf(`vm_request_errors_total{action="search", type="rpcClient", name="vmselect", addr=%q}`, addr)),
 			metricBlocksRead:                    metrics.NewCounter(fmt.Sprintf(`vm_metric_blocks_read_total{name="vmselect", addr=%q}`, addr)),
 			metricRowsRead:                      metrics.NewCounter(fmt.Sprintf(`vm_metric_rows_read_total{name="vmselect", addr=%q}`, addr)),
@@ -2225,3 +2413,20 @@ var (
 
 // The maximum number of concurrent queries per storageNode.
 const maxConcurrentQueriesPerStorageNode = 100
+
+func applyGraphiteRegexpFilter(filter string, ss []string) ([]string, error) {
+	// Anchor filter regexp to the beginning of the string as Graphite does.
+	// See https://github.com/graphite-project/graphite-web/blob/3ad279df5cb90b211953e39161df416e54a84948/webapp/graphite/tags/localdatabase.py#L157
+	filter = "^(?:" + filter + ")"
+	re, err := regexp.Compile(filter)
+	if err != nil {
+		return nil, fmt.Errorf("cannot parse regexp filter=%q: %w", filter, err)
+	}
+	dst := ss[:0]
+	for _, s := range ss {
+		if re.MatchString(s) {
+			dst = append(dst, s)
+		}
+	}
+	return dst, nil
+}
diff --git a/app/vmselect/prometheus/prometheus.go b/app/vmselect/prometheus/prometheus.go
index 3513920be..79311209e 100644
--- a/app/vmselect/prometheus/prometheus.go
+++ b/app/vmselect/prometheus/prometheus.go
@@ -80,13 +80,7 @@ func FederateHandler(startTime time.Time, at *auth.Token, w http.ResponseWriter,
 	if err != nil {
 		return err
 	}
-	sq := &storage.SearchQuery{
-		AccountID:    at.AccountID,
-		ProjectID:    at.ProjectID,
-		MinTimestamp: start,
-		MaxTimestamp: end,
-		TagFilterss:  tagFilterss,
-	}
+	sq := storage.NewSearchQuery(at.AccountID, at.ProjectID, start, end, tagFilterss)
 	denyPartialResponse := searchutils.GetDenyPartialResponse(r)
 	rss, isPartial, err := netstorage.ProcessSearchQuery(at, denyPartialResponse, sq, true, deadline)
 	if err != nil {
@@ -154,13 +148,7 @@ func ExportCSVHandler(startTime time.Time, at *auth.Token, w http.ResponseWriter
 	if err != nil {
 		return err
 	}
-	sq := &storage.SearchQuery{
-		AccountID:    at.AccountID,
-		ProjectID:    at.ProjectID,
-		MinTimestamp: start,
-		MaxTimestamp: end,
-		TagFilterss:  tagFilterss,
-	}
+	sq := storage.NewSearchQuery(at.AccountID, at.ProjectID, start, end, tagFilterss)
 	w.Header().Set("Content-Type", "text/csv; charset=utf-8")
 	bw := bufferedwriter.Get(w)
 	defer bufferedwriter.Put(bw)
@@ -237,13 +225,7 @@ func ExportNativeHandler(startTime time.Time, at *auth.Token, w http.ResponseWri
 	if err != nil {
 		return err
 	}
-	sq := &storage.SearchQuery{
-		AccountID:    at.AccountID,
-		ProjectID:    at.ProjectID,
-		MinTimestamp: start,
-		MaxTimestamp: end,
-		TagFilterss:  tagFilterss,
-	}
+	sq := storage.NewSearchQuery(at.AccountID, at.ProjectID, start, end, tagFilterss)
 	w.Header().Set("Content-Type", "VictoriaMetrics/native")
 	bw := bufferedwriter.Get(w)
 	defer bufferedwriter.Put(bw)
@@ -394,13 +376,7 @@ func exportHandler(at *auth.Token, w http.ResponseWriter, r *http.Request, match
 	if err != nil {
 		return err
 	}
-	sq := &storage.SearchQuery{
-		AccountID:    at.AccountID,
-		ProjectID:    at.ProjectID,
-		MinTimestamp: start,
-		MaxTimestamp: end,
-		TagFilterss:  tagFilterss,
-	}
+	sq := storage.NewSearchQuery(at.AccountID, at.ProjectID, start, end, tagFilterss)
 	w.Header().Set("Content-Type", contentType)
 	bw := bufferedwriter.Get(w)
 	defer bufferedwriter.Put(bw)
@@ -506,11 +482,7 @@ func DeleteHandler(startTime time.Time, at *auth.Token, r *http.Request) error {
 	if err != nil {
 		return err
 	}
-	sq := &storage.SearchQuery{
-		AccountID:   at.AccountID,
-		ProjectID:   at.ProjectID,
-		TagFilterss: tagFilterss,
-	}
+	sq := storage.NewSearchQuery(at.AccountID, at.ProjectID, 0, 0, tagFilterss)
 	deletedCount, err := netstorage.DeleteSeries(at, sq, deadline)
 	if err != nil {
 		return fmt.Errorf("cannot delete time series matching %q: %w", matches, err)
@@ -655,34 +627,44 @@ func labelValuesWithMatches(at *auth.Token, denyPartialResponse bool, labelName
 	if start >= end {
 		end = start + defaultStep
 	}
-	sq := &storage.SearchQuery{
-		AccountID:    at.AccountID,
-		ProjectID:    at.ProjectID,
-		MinTimestamp: start,
-		MaxTimestamp: end,
-		TagFilterss:  tagFilterss,
-	}
-	rss, isPartial, err := netstorage.ProcessSearchQuery(at, denyPartialResponse, sq, false, deadline)
-	if err != nil {
-		return nil, false, fmt.Errorf("cannot fetch data for %q: %w", sq, err)
-	}
-
+	sq := storage.NewSearchQuery(at.AccountID, at.ProjectID, start, end, tagFilterss)
 	m := make(map[string]struct{})
-	var mLock sync.Mutex
-	err = rss.RunParallel(func(rs *netstorage.Result, workerID uint) error {
-		labelValue := rs.MetricName.GetTagValue(labelName)
-		if len(labelValue) == 0 {
+	isPartial := false
+	if end-start > 24*3600*1000 {
+		// It is cheaper to call SearchMetricNames on time ranges exceeding a day.
+		mns, isPartialResponse, err := netstorage.SearchMetricNames(at, denyPartialResponse, sq, deadline)
+		if err != nil {
+			return nil, false, fmt.Errorf("cannot fetch time series for %q: %w", sq, err)
+		}
+		isPartial = isPartialResponse
+		for _, mn := range mns {
+			labelValue := mn.GetTagValue(labelName)
+			if len(labelValue) == 0 {
+				continue
+			}
+			m[string(labelValue)] = struct{}{}
+		}
+	} else {
+		rss, isPartialResponse, err := netstorage.ProcessSearchQuery(at, denyPartialResponse, sq, false, deadline)
+		if err != nil {
+			return nil, false, fmt.Errorf("cannot fetch data for %q: %w", sq, err)
+		}
+		isPartial = isPartialResponse
+		var mLock sync.Mutex
+		err = rss.RunParallel(func(rs *netstorage.Result, workerID uint) error {
+			labelValue := rs.MetricName.GetTagValue(labelName)
+			if len(labelValue) == 0 {
+				return nil
+			}
+			mLock.Lock()
+			m[string(labelValue)] = struct{}{}
+			mLock.Unlock()
 			return nil
+		})
+		if err != nil {
+			return nil, false, fmt.Errorf("error when data fetching: %w", err)
 		}
-		mLock.Lock()
-		m[string(labelValue)] = struct{}{}
-		mLock.Unlock()
-		return nil
-	})
-	if err != nil {
-		return nil, false, fmt.Errorf("error when data fetching: %w", err)
 	}
-
 	labelValues := make([]string, 0, len(m))
 	for labelValue := range m {
 		labelValues = append(labelValues, labelValue)
@@ -849,35 +831,44 @@ func labelsWithMatches(at *auth.Token, denyPartialResponse bool, matches []strin
 	if start >= end {
 		end = start + defaultStep
 	}
-	sq := &storage.SearchQuery{
-		AccountID:    at.AccountID,
-		ProjectID:    at.ProjectID,
-		MinTimestamp: start,
-		MaxTimestamp: end,
-		TagFilterss:  tagFilterss,
-	}
-	rss, isPartial, err := netstorage.ProcessSearchQuery(at, denyPartialResponse, sq, false, deadline)
-	if err != nil {
-		return nil, false, fmt.Errorf("cannot fetch data for %q: %w", sq, err)
-	}
-
+	sq := storage.NewSearchQuery(at.AccountID, at.ProjectID, start, end, tagFilterss)
 	m := make(map[string]struct{})
-	var mLock sync.Mutex
-	err = rss.RunParallel(func(rs *netstorage.Result, workerID uint) error {
-		mLock.Lock()
-		tags := rs.MetricName.Tags
-		for i := range tags {
-			t := &tags[i]
-			m[string(t.Key)] = struct{}{}
+	isPartial := false
+	if end-start > 24*3600*1000 {
+		// It is cheaper to call SearchMetricNames on time ranges exceeding a day.
+		mns, isPartialResponse, err := netstorage.SearchMetricNames(at, denyPartialResponse, sq, deadline)
+		if err != nil {
+			return nil, false, fmt.Errorf("cannot fetch time series for %q: %w", sq, err)
+		}
+		isPartial = isPartialResponse
+		for _, mn := range mns {
+			for _, tag := range mn.Tags {
+				m[string(tag.Key)] = struct{}{}
+			}
+		}
+		if len(mns) > 0 {
+			m["__name__"] = struct{}{}
+		}
+	} else {
+		rss, isPartialResponse, err := netstorage.ProcessSearchQuery(at, denyPartialResponse, sq, false, deadline)
+		if err != nil {
+			return nil, false, fmt.Errorf("cannot fetch data for %q: %w", sq, err)
+		}
+		isPartial = isPartialResponse
+		var mLock sync.Mutex
+		err = rss.RunParallel(func(rs *netstorage.Result, workerID uint) error {
+			mLock.Lock()
+			for _, tag := range rs.MetricName.Tags {
+				m[string(tag.Key)] = struct{}{}
+			}
+			m["__name__"] = struct{}{}
+			mLock.Unlock()
+			return nil
+		})
+		if err != nil {
+			return nil, false, fmt.Errorf("error when data fetching: %w", err)
 		}
-		m["__name__"] = struct{}{}
-		mLock.Unlock()
-		return nil
-	})
-	if err != nil {
-		return nil, false, fmt.Errorf("error when data fetching: %w", err)
 	}
-
 	labels := make([]string, 0, len(m))
 	for label := range m {
 		labels = append(labels, label)
@@ -944,14 +935,34 @@ func SeriesHandler(startTime time.Time, at *auth.Token, w http.ResponseWriter, r
 	if start >= end {
 		end = start + defaultStep
 	}
-	sq := &storage.SearchQuery{
-		AccountID:    at.AccountID,
-		ProjectID:    at.ProjectID,
-		MinTimestamp: start,
-		MaxTimestamp: end,
-		TagFilterss:  tagFilterss,
-	}
+	sq := storage.NewSearchQuery(at.AccountID, at.ProjectID, start, end, tagFilterss)
 	denyPartialResponse := searchutils.GetDenyPartialResponse(r)
+	if end-start > 24*3600*1000 {
+		// It is cheaper to call SearchMetricNames on time ranges exceeding a day.
+		mns, isPartial, err := netstorage.SearchMetricNames(at, denyPartialResponse, sq, deadline)
+		if err != nil {
+			return fmt.Errorf("cannot fetch time series for %q: %w", sq, err)
+		}
+		w.Header().Set("Content-Type", "application/json; charset=utf-8")
+		bw := bufferedwriter.Get(w)
+		defer bufferedwriter.Put(bw)
+		resultsCh := make(chan *quicktemplate.ByteBuffer)
+		go func() {
+			for i := range mns {
+				bb := quicktemplate.AcquireByteBuffer()
+				writemetricNameObject(bb, &mns[i])
+				resultsCh <- bb
+			}
+			close(resultsCh)
+		}()
+		// WriteSeriesResponse must consume all the data from resultsCh.
+		WriteSeriesResponse(bw, isPartial, resultsCh)
+		if err := bw.Flush(); err != nil {
+			return err
+		}
+		seriesDuration.UpdateDuration(startTime)
+		return nil
+	}
 	rss, isPartial, err := netstorage.ProcessSearchQuery(at, denyPartialResponse, sq, false, deadline)
 	if err != nil {
 		return fmt.Errorf("cannot fetch data for %q: %w", sq, err)
diff --git a/app/vmselect/promql/eval.go b/app/vmselect/promql/eval.go
index 0faeab2fd..b751ee9e3 100644
--- a/app/vmselect/promql/eval.go
+++ b/app/vmselect/promql/eval.go
@@ -671,13 +671,7 @@ func evalRollupFuncWithMetricExpr(ec *EvalConfig, name string, rf rollupFunc,
 	} else {
 		minTimestamp -= ec.Step
 	}
-	sq := &storage.SearchQuery{
-		AccountID:    ec.AuthToken.AccountID,
-		ProjectID:    ec.AuthToken.ProjectID,
-		MinTimestamp: minTimestamp,
-		MaxTimestamp: ec.End,
-		TagFilterss:  [][]storage.TagFilter{tfs},
-	}
+	sq := storage.NewSearchQuery(ec.AuthToken.AccountID, ec.AuthToken.ProjectID, minTimestamp, ec.End, [][]storage.TagFilter{tfs})
 	rss, isPartial, err := netstorage.ProcessSearchQuery(ec.AuthToken, ec.DenyPartialResponse, sq, true, ec.Deadline)
 	if err != nil {
 		return nil, err
diff --git a/app/vmstorage/transport/server.go b/app/vmstorage/transport/server.go
index 41711634d..51bccaba7 100644
--- a/app/vmstorage/transport/server.go
+++ b/app/vmstorage/transport/server.go
@@ -538,6 +538,20 @@ func (ctx *vmselectRequestCtx) readAccountIDProjectID() (uint32, uint32, error)
 	return accountID, projectID, nil
 }
 
+func (ctx *vmselectRequestCtx) readSearchQuery() error {
+	if err := ctx.readDataBufBytes(maxSearchQuerySize); err != nil {
+		return fmt.Errorf("cannot read searchQuery: %w", err)
+	}
+	tail, err := ctx.sq.Unmarshal(ctx.dataBuf)
+	if err != nil {
+		return fmt.Errorf("cannot unmarshal SearchQuery: %w", err)
+	}
+	if len(tail) > 0 {
+		return fmt.Errorf("unexpected non-zero tail left after unmarshaling SearchQuery: (len=%d) %q", len(tail), tail)
+	}
+	return nil
+}
+
 func (ctx *vmselectRequestCtx) readDataBufBytes(maxDataSize int) error {
 	ctx.sizeBuf = bytesutil.Resize(ctx.sizeBuf, 8)
 	if _, err := io.ReadFull(ctx.bc, ctx.sizeBuf); err != nil {
@@ -663,7 +677,9 @@ func (s *Server) processVMSelectRequest(ctx *vmselectRequestCtx) error {
 
 	switch rpcName {
 	case "search_v4":
-		return s.processVMSelectSearchQuery(ctx)
+		return s.processVMSelectSearch(ctx)
+	case "searchMetricNames_v1":
+		return s.processVMSelectSearchMetricNames(ctx)
 	case "labelValuesOnTimeRange_v1":
 		return s.processVMSelectLabelValuesOnTimeRange(ctx)
 	case "labelValues_v2":
@@ -1061,19 +1077,52 @@ func writeTopHeapEntries(ctx *vmselectRequestCtx, a []storage.TopHeapEntry) erro
 // maxSearchQuerySize is the maximum size of SearchQuery packet in bytes.
 const maxSearchQuerySize = 1024 * 1024
 
-func (s *Server) processVMSelectSearchQuery(ctx *vmselectRequestCtx) error {
-	vmselectSearchQueryRequests.Inc()
+func (s *Server) processVMSelectSearchMetricNames(ctx *vmselectRequestCtx) error {
+	vmselectSearchMetricNamesRequests.Inc()
 
-	// Read search query.
-	if err := ctx.readDataBufBytes(maxSearchQuerySize); err != nil {
-		return fmt.Errorf("cannot read searchQuery: %w", err)
+	// Read request.
+	if err := ctx.readSearchQuery(); err != nil {
+		return err
 	}
-	tail, err := ctx.sq.Unmarshal(ctx.dataBuf)
+
+	// Search metric names.
+	if err := ctx.setupTfss(); err != nil {
+		return ctx.writeErrorMessage(err)
+	}
+	tr := storage.TimeRange{
+		MinTimestamp: ctx.sq.MinTimestamp,
+		MaxTimestamp: ctx.sq.MaxTimestamp,
+	}
+	mns, err := s.storage.SearchMetricNames(ctx.tfss, tr, *maxMetricsPerSearch, ctx.deadline)
 	if err != nil {
-		return fmt.Errorf("cannot unmarshal SearchQuery: %w", err)
+		return ctx.writeErrorMessage(err)
 	}
-	if len(tail) > 0 {
-		return fmt.Errorf("unexpected non-zero tail left after unmarshaling SearchQuery: (len=%d) %q", len(tail), tail)
+
+	// Send empty error message to vmselect.
+	if err := ctx.writeString(""); err != nil {
+		return fmt.Errorf("cannot send empty error message: %w", err)
+	}
+
+	// Send response.
+	metricNamesCount := len(mns)
+	if err := ctx.writeUint64(uint64(metricNamesCount)); err != nil {
+		return fmt.Errorf("cannot send metricNamesCount: %w", err)
+	}
+	for i, mn := range mns {
+		ctx.dataBuf = mn.Marshal(ctx.dataBuf[:0])
+		if err := ctx.writeDataBufBytes(); err != nil {
+			return fmt.Errorf("cannot send metricName #%d: %w", i+1, err)
+		}
+	}
+	return nil
+}
+
+func (s *Server) processVMSelectSearch(ctx *vmselectRequestCtx) error {
+	vmselectSearchRequests.Inc()
+
+	// Read request.
+	if err := ctx.readSearchQuery(); err != nil {
+		return err
 	}
 	fetchData, err := ctx.readBool()
 	if err != nil {
@@ -1153,7 +1202,8 @@ var (
 	vmselectLabelEntriesRequests           = metrics.NewCounter("vm_vmselect_label_entries_requests_total")
 	vmselectSeriesCountRequests            = metrics.NewCounter("vm_vmselect_series_count_requests_total")
 	vmselectTSDBStatusRequests             = metrics.NewCounter("vm_vmselect_tsdb_status_requests_total")
-	vmselectSearchQueryRequests            = metrics.NewCounter("vm_vmselect_search_query_requests_total")
+	vmselectSearchMetricNamesRequests      = metrics.NewCounter("vm_vmselect_search_metric_names_requests_total")
+	vmselectSearchRequests                 = metrics.NewCounter("vm_vmselect_search_requests_total")
 	vmselectMetricBlocksRead               = metrics.NewCounter("vm_vmselect_metric_blocks_read_total")
 	vmselectMetricRowsRead                 = metrics.NewCounter("vm_vmselect_metric_rows_read_total")
 )
diff --git a/docs/CHANGELOG.md b/docs/CHANGELOG.md
index 228d103a7..2ffedf4a4 100644
--- a/docs/CHANGELOG.md
+++ b/docs/CHANGELOG.md
@@ -7,6 +7,7 @@
 * FEATURE: vmselect: add `"isPartial":{true|false}` field in JSON output for `/api/v1/*` functions
   from [Prometheus querying API](https://prometheus.io/docs/prometheus/latest/querying/api/). `"isPartial":true` is set if the response contains partial data
   because of a part of `vmstorage` nodes were unavailable during query processing.
+* FEATURE: improve performance for `/api/v1/series`, `/api/v1/labels` and `/api/v1/label/<labelName>/values` on time ranges exceeding one day.
 * FEATURE: vmagent: reduce memory usage when service discovery detects big number of scrape targets and the set of discovered targets changes over time.
   See https://github.com/VictoriaMetrics/VictoriaMetrics/issues/825
 * FEATURE: vmagent: add `-promscrape.dropOriginalLabels` command-line option, which can be used for reducing memory usage when scraping big number of targets.
@@ -20,6 +21,8 @@
 * FEATURE: update Go builder from v1.15.4 to v1.15.5. This should fix [these issues in Go](https://github.com/golang/go/issues?q=milestone%3AGo1.15.5+label%3ACherryPickApproved).
 * FEATURE: added `/internal/force_flush` http handler for flushing recently ingested data from in-memory buffers to persistent storage.
   See [troubleshooting docs](https://victoriametrics.github.io/#troubleshooting) for more details.
+* FEATURE: added [Graphite Tags API](https://graphite.readthedocs.io/en/stable/tags.html) support.
+  See [these docs](https://victoriametrics.github.io/#graphite-tags-api-usage) for details.
 
 * BUGFIX: do not return data points in the end of the selected time range for time series ending in the middle of the selected time range.
   See https://github.com/VictoriaMetrics/VictoriaMetrics/issues/887 and https://github.com/VictoriaMetrics/VictoriaMetrics/issues/845
diff --git a/docs/Cluster-VictoriaMetrics.md b/docs/Cluster-VictoriaMetrics.md
index ef0575dd5..fd98c59c9 100644
--- a/docs/Cluster-VictoriaMetrics.md
+++ b/docs/Cluster-VictoriaMetrics.md
@@ -205,6 +205,11 @@ or [an alternative dashboard for VictoriaMetrics cluster](https://grafana.com/gr
       - `metrics/find` - searches Graphite metrics. See [these docs](https://graphite-api.readthedocs.io/en/latest/api.html#metrics-find).
       - `metrics/expand` - expands Graphite metrics. See [these docs](https://graphite-api.readthedocs.io/en/latest/api.html#metrics-expand).
       - `metrics/index.json` - returns all the metric names. See [these docs](https://graphite-api.readthedocs.io/en/latest/api.html#metrics-index-json).
+      - `tags` - returns tag names. See [these docs](https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags).
+      - `tags/<tag_name>` - returns tag values for the given `<tag_name>`. See [these docs](https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags).
+      - `tags/findSeries` - returns series matching the given `expr`. See [these docs](https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags).
+      - `tags/autoComplete/tags` - returns tags matching the given `tagPrefix` and/or `expr`. See [these docs](https://graphite.readthedocs.io/en/stable/tags.html#auto-complete-support).
+      - `tags/autoComplete/values` - returns tag values matching the given `valuePrefix` and/or `expr`. See [these docs](https://graphite.readthedocs.io/en/stable/tags.html#auto-complete-support).
 
 * URL for time series deletion: `http://<vmselect>:8481/delete/<accountID>/prometheus/api/v1/admin/tsdb/delete_series?match[]=<timeseries_selector_for_delete>`.
   Note that the `delete_series` handler should be used only in exceptional cases such as deletion of accidentally ingested incorrect time series. It shouldn't
diff --git a/docs/Single-server-VictoriaMetrics.md b/docs/Single-server-VictoriaMetrics.md
index dd1d83edf..f581651eb 100644
--- a/docs/Single-server-VictoriaMetrics.md
+++ b/docs/Single-server-VictoriaMetrics.md
@@ -106,7 +106,9 @@ Click on a link in order to read the corresponding case study
 * [How to send data from OpenTSDB-compatible agents](#how-to-send-data-from-opentsdb-compatible-agents)
 * [Prometheus querying API usage](#prometheus-querying-api-usage)
   * [Prometheus querying API enhancements](#prometheus-querying-api-enhancements)
-* [Graphite Metrics API usage](#graphite-metrics-api-usage)
+* [Graphite API usage](#graphite-api-usage)
+  * [Graphite Metrics API usage](#graphite-metrics-api-usage)
+  * [Graphite Tags API usage](#graphite-tags-api-usage)
 * [How to build from sources](#how-to-build-from-sources)
   * [Development build](#development-build)
   * [Production build](#production-build)
@@ -412,6 +414,7 @@ Data sent to VictoriaMetrics via `Graphite plaintext protocol` may be read via t
 
 * [Prometheus querying API](#prometheus-querying-api-usage)
 * Metric names can be explored via [Graphite metrics API](#graphite-metrics-api-usage)
+* Tags can be explored via [Graphite tags API](#graphite-tags-api-usage)
 * [go-graphite/carbonapi](https://github.com/go-graphite/carbonapi/blob/master/cmd/carbonapi/carbonapi.example.prometheus.yaml)
 
 ### How to send data from OpenTSDB-compatible agents
@@ -526,7 +529,15 @@ Additionally VictoriaMetrics provides the following handlers:
 * `/api/v1/status/active_queries` - it returns a list of currently running queries.
 
 
-### Graphite Metrics API usage
+### Graphite API usage
+
+VictoriaMetrics supports the following Graphite APIs:
+
+* Metrics API - see [these docs](#graphite-metrics-api-usage).
+* Tags API - see [these docs](#graphite-tags-api-usage).
+
+
+#### Graphite Metrics API usage
 
 VictoriaMetrics supports the following handlers from [Graphite Metrics API](https://graphite-api.readthedocs.io/en/latest/api.html#the-metrics-api):
 
@@ -540,6 +551,19 @@ VictoriaMetrics accepts the following additional query args at `/metrics/find` a
     that start with `node_`. By default `delimiter=.`.
 
 
+#### Graphite Tags API usage
+
+VictoriaMetrics supports the following handlers from [Graphite Tags API](https://graphite.readthedocs.io/en/stable/tags.html):
+
+* [/tags/tagSeries](https://graphite.readthedocs.io/en/stable/tags.html#adding-series-to-the-tagdb)
+* [/tags/tagMultiSeries](https://graphite.readthedocs.io/en/stable/tags.html#adding-series-to-the-tagdb)
+* [/tags](https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags)
+* [/tags/tag_name](https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags)
+* [/tags/findSeries](https://graphite.readthedocs.io/en/stable/tags.html#exploring-tags)
+* [/tags/autoComplete/tags](https://graphite.readthedocs.io/en/stable/tags.html#auto-complete-support)
+* [/tags/autoComplete/values](https://graphite.readthedocs.io/en/stable/tags.html#auto-complete-support)
+
+
 ### How to build from sources
 
 We recommend using either [binary releases](https://github.com/VictoriaMetrics/VictoriaMetrics/releases) or
diff --git a/lib/protoparser/graphite/parser.go b/lib/protoparser/graphite/parser.go
index e679f9524..c2e20b3d5 100644
--- a/lib/protoparser/graphite/parser.go
+++ b/lib/protoparser/graphite/parser.go
@@ -55,25 +55,21 @@ func (r *Row) reset() {
 	r.Timestamp = 0
 }
 
-func (r *Row) unmarshal(s string, tagsPool []Tag) ([]Tag, error) {
-	r.reset()
-	n := strings.IndexByte(s, ' ')
-	if n < 0 {
-		return tagsPool, fmt.Errorf("cannot find whitespace between metric and value in %q", s)
+// UnmarshalMetricAndTags unmarshals metric and optional tags from s.
+func (r *Row) UnmarshalMetricAndTags(s string, tagsPool []Tag) ([]Tag, error) {
+	if strings.Contains(s, " ") {
+		return tagsPool, fmt.Errorf("unexpected whitespace found in %q", s)
 	}
-	metricAndTags := s[:n]
-	tail := s[n+1:]
-
-	n = strings.IndexByte(metricAndTags, ';')
+	n := strings.IndexByte(s, ';')
 	if n < 0 {
 		// No tags
-		r.Metric = metricAndTags
+		r.Metric = s
 	} else {
 		// Tags found
-		r.Metric = metricAndTags[:n]
+		r.Metric = s[:n]
 		tagsStart := len(tagsPool)
 		var err error
-		tagsPool, err = unmarshalTags(tagsPool, metricAndTags[n+1:])
+		tagsPool, err = unmarshalTags(tagsPool, s[n+1:])
 		if err != nil {
 			return tagsPool, fmt.Errorf("cannot umarshal tags: %w", err)
 		}
@@ -83,6 +79,22 @@ func (r *Row) unmarshal(s string, tagsPool []Tag) ([]Tag, error) {
 	if len(r.Metric) == 0 {
 		return tagsPool, fmt.Errorf("metric cannot be empty")
 	}
+	return tagsPool, nil
+}
+
+func (r *Row) unmarshal(s string, tagsPool []Tag) ([]Tag, error) {
+	r.reset()
+	n := strings.IndexByte(s, ' ')
+	if n < 0 {
+		return tagsPool, fmt.Errorf("cannot find whitespace between metric and value in %q", s)
+	}
+	metricAndTags := s[:n]
+	tail := s[n+1:]
+
+	tagsPool, err := r.UnmarshalMetricAndTags(metricAndTags, tagsPool)
+	if err != nil {
+		return tagsPool, err
+	}
 
 	n = strings.IndexByte(tail, ' ')
 	if n < 0 {
diff --git a/lib/storage/search.go b/lib/storage/search.go
index 3f855f97a..98dabb50e 100644
--- a/lib/storage/search.go
+++ b/lib/storage/search.go
@@ -257,6 +257,17 @@ type SearchQuery struct {
 	TagFilterss  [][]TagFilter
 }
 
+// NewSearchQuery creates new search query for the given args.
+func NewSearchQuery(accountID, projectID uint32, start, end int64, tagFilterss [][]TagFilter) *SearchQuery {
+	return &SearchQuery{
+		AccountID:    accountID,
+		ProjectID:    projectID,
+		MinTimestamp: start,
+		MaxTimestamp: end,
+		TagFilterss:  tagFilterss,
+	}
+}
+
 // TagFilter represents a single tag filter from SearchQuery.
 type TagFilter struct {
 	Key        []byte
diff --git a/lib/storage/storage.go b/lib/storage/storage.go
index fcc5f9bb2..b7b49e8ab 100644
--- a/lib/storage/storage.go
+++ b/lib/storage/storage.go
@@ -859,6 +859,46 @@ func nextRetentionDuration(retentionMonths int) time.Duration {
 	return deadline.Sub(t)
 }
 
+// SearchMetricNames returns metric names matching the given tfss on the given tr.
+func (s *Storage) SearchMetricNames(tfss []*TagFilters, tr TimeRange, maxMetrics int, deadline uint64) ([]MetricName, error) {
+	tsids, err := s.searchTSIDs(tfss, tr, maxMetrics, deadline)
+	if err != nil {
+		return nil, err
+	}
+	if len(tsids) == 0 {
+		return nil, nil
+	}
+	if err = s.prefetchMetricNames(tsids, deadline); err != nil {
+		return nil, err
+	}
+	accountID := tsids[0].AccountID
+	projectID := tsids[0].ProjectID
+	idb := s.idb()
+	is := idb.getIndexSearch(accountID, projectID, deadline)
+	defer idb.putIndexSearch(is)
+	mns := make([]MetricName, 0, len(tsids))
+	var metricName []byte
+	for i := range tsids {
+		metricID := tsids[i].MetricID
+		var err error
+		metricName, err = is.searchMetricName(metricName[:0], metricID)
+		if err != nil {
+			if err == io.EOF {
+				// Skip missing metricName for metricID.
+				// It should be automatically fixed. See indexDB.searchMetricName for details.
+				continue
+			}
+			return nil, fmt.Errorf("error when searching metricName for metricID=%d: %w", metricID, err)
+		}
+		mns = mns[:len(mns)+1]
+		mn := &mns[len(mns)-1]
+		if err = mn.Unmarshal(metricName); err != nil {
+			return nil, fmt.Errorf("cannot unmarshal metricName=%q: %w", metricName, err)
+		}
+	}
+	return mns, nil
+}
+
 // searchTSIDs returns sorted TSIDs for the given tfss and the given tr.
 func (s *Storage) searchTSIDs(tfss []*TagFilters, tr TimeRange, maxMetrics int, deadline uint64) ([]TSID, error) {
 	// Do not cache tfss -> tsids here, since the caching is performed
@@ -1146,7 +1186,6 @@ func (s *Storage) AddRows(mrs []MetricRow, precisionBits uint8) error {
 	if len(mrs) == 0 {
 		return nil
 	}
-	atomic.AddUint64(&rowsAddedTotal, uint64(len(mrs)))
 
 	// Limit the number of concurrent goroutines that may add rows to the storage.
 	// This should prevent from out of memory errors and CPU trashing when too many
@@ -1183,6 +1222,7 @@ func (s *Storage) AddRows(mrs []MetricRow, precisionBits uint8) error {
 
 	<-addRowsConcurrencyCh
 
+	atomic.AddUint64(&rowsAddedTotal, uint64(len(mrs)))
 	return err
 }
 
@@ -1194,6 +1234,69 @@ var (
 	addRowsTimeout       = 30 * time.Second
 )
 
+// RegisterMetricNames registers all the metric names from mns in the indexdb, so they can be queried later.
+//
+// The the MetricRow.Timestamp is used for registering the metric name starting from the given timestamp.
+// Th MetricRow.Value field is ignored.
+func (s *Storage) RegisterMetricNames(mrs []MetricRow) error {
+	var (
+		tsid       TSID
+		mn         MetricName
+		metricName []byte
+	)
+	idb := s.idb()
+	is := idb.getIndexSearch(0, 0, noDeadline)
+	defer idb.putIndexSearch(is)
+	for i := range mrs {
+		mr := &mrs[i]
+		if s.getTSIDFromCache(&tsid, mr.MetricNameRaw) {
+			// Fast path - mr.MetricNameRaw has been already registered.
+			continue
+		}
+
+		// Slow path - register mr.MetricNameRaw.
+		if err := mn.unmarshalRaw(mr.MetricNameRaw); err != nil {
+			return fmt.Errorf("cannot register the metric because cannot unmarshal MetricNameRaw %q: %w", mr.MetricNameRaw, err)
+		}
+		mn.sortTags()
+		metricName = mn.Marshal(metricName[:0])
+		if err := is.GetOrCreateTSIDByName(&tsid, metricName); err != nil {
+			return fmt.Errorf("cannot register the metric because cannot create TSID for metricName %q: %w", metricName, err)
+		}
+		s.putTSIDToCache(&tsid, mr.MetricNameRaw)
+
+		// Register the metric in per-day inverted index.
+		date := uint64(mr.Timestamp) / msecPerDay
+		metricID := tsid.MetricID
+		if s.dateMetricIDCache.Has(date, metricID) {
+			// Fast path: the metric has been already registered in per-day inverted index
+			continue
+		}
+
+		// Slow path: acutally register the metric in per-day inverted index.
+		is.accountID = mn.AccountID
+		is.projectID = mn.ProjectID
+		ok, err := is.hasDateMetricID(date, metricID)
+		if err != nil {
+			return fmt.Errorf("cannot register the metric in per-date inverted index because of error when locating (date=%d, metricID=%d) in database: %w",
+				date, metricID, err)
+		}
+		if !ok {
+			// The (date, metricID) entry is missing in the indexDB. Add it there.
+			if err := is.storeDateMetricID(date, metricID); err != nil {
+				return fmt.Errorf("cannot register the metric in per-date inverted index because of error when storing (date=%d, metricID=%d) in database: %w",
+					date, metricID, err)
+			}
+		}
+		is.accountID = 0
+		is.projectID = 0
+
+		// The metric must be added to cache only after it has been successfully added to indexDB.
+		s.dateMetricIDCache.Set(date, metricID)
+	}
+	return nil
+}
+
 func (s *Storage) add(rows []rawRow, mrs []MetricRow, precisionBits uint8) ([]rawRow, error) {
 	idb := s.idb()
 	rowsLen := len(rows)


Test patch:
diff --git a/lib/protoparser/graphite/parser_test.go b/lib/protoparser/graphite/parser_test.go
index c2dc4373e..b04314f1a 100644
--- a/lib/protoparser/graphite/parser_test.go
+++ b/lib/protoparser/graphite/parser_test.go
@@ -7,6 +7,57 @@ import (
 	"testing"
 )
 
+func TestUnmarshalMetricAndTagsFailure(t *testing.T) {
+	f := func(s string) {
+		t.Helper()
+		var r Row
+		_, err := r.UnmarshalMetricAndTags(s, nil)
+		if err == nil {
+			t.Fatalf("expecting non-nil error for UnmarshalMetricAndTags(%q)", s)
+		}
+	}
+	f("")
+	f(";foo=bar")
+	f(" ")
+	f("foo;bar")
+	f("foo ;bar=baz")
+	f("f oo;bar=baz")
+	f("foo;bar=baz   ")
+	f("foo;bar= baz")
+	f("foo;bar=b az")
+	f("foo;b ar=baz")
+}
+
+func TestUnmarshalMetricAndTagsSuccess(t *testing.T) {
+	f := func(s string, rExpected *Row) {
+		t.Helper()
+		var r Row
+		_, err := r.UnmarshalMetricAndTags(s, nil)
+		if err != nil {
+			t.Fatalf("unexpected error in UnmarshalMetricAndTags(%q): %s", s, err)
+		}
+		if !reflect.DeepEqual(&r, rExpected) {
+			t.Fatalf("unexpected row;\ngot\n%+v\nwant\n%+v", &r, rExpected)
+		}
+	}
+	f("foo", &Row{
+		Metric: "foo",
+	})
+	f("foo;bar=123;baz=aabb", &Row{
+		Metric: "foo",
+		Tags: []Tag{
+			{
+				Key:   "bar",
+				Value: "123",
+			},
+			{
+				Key:   "baz",
+				Value: "aabb",
+			},
+		},
+	})
+}
+
 func TestRowsUnmarshalFailure(t *testing.T) {
 	f := func(s string) {
 		t.Helper()
diff --git a/lib/storage/storage_test.go b/lib/storage/storage_test.go
index 8eb31ea06..93d8c75a9 100644
--- a/lib/storage/storage_test.go
+++ b/lib/storage/storage_test.go
@@ -5,6 +5,7 @@ import (
 	"math/rand"
 	"os"
 	"reflect"
+	"sort"
 	"strings"
 	"testing"
 	"testing/quick"
@@ -704,6 +705,220 @@ func checkTagKeys(tks []string, tksExpected map[string]bool) error {
 	return nil
 }
 
+func TestStorageRegisterMetricNamesSerial(t *testing.T) {
+	path := "TestStorageRegisterMetricNamesSerial"
+	s, err := OpenStorage(path, 0)
+	if err != nil {
+		t.Fatalf("cannot open storage: %s", err)
+	}
+	if err := testStorageRegisterMetricNames(s); err != nil {
+		t.Fatalf("unexpected error: %s", err)
+	}
+	s.MustClose()
+	if err := os.RemoveAll(path); err != nil {
+		t.Fatalf("cannot remove %q: %s", path, err)
+	}
+}
+
+func TestStorageRegisterMetricNamesConcurrent(t *testing.T) {
+	path := "TestStorageRegisterMetricNamesConcurrent"
+	s, err := OpenStorage(path, 0)
+	if err != nil {
+		t.Fatalf("cannot open storage: %s", err)
+	}
+	ch := make(chan error, 3)
+	for i := 0; i < cap(ch); i++ {
+		go func() {
+			ch <- testStorageRegisterMetricNames(s)
+		}()
+	}
+	for i := 0; i < cap(ch); i++ {
+		select {
+		case err := <-ch:
+			if err != nil {
+				t.Fatalf("unexpected error: %s", err)
+			}
+		case <-time.After(10 * time.Second):
+			t.Fatalf("timeout")
+		}
+	}
+	s.MustClose()
+	if err := os.RemoveAll(path); err != nil {
+		t.Fatalf("cannot remove %q: %s", path, err)
+	}
+}
+
+func testStorageRegisterMetricNames(s *Storage) error {
+	const metricsPerAdd = 1e3
+	const addsCount = 10
+	const accountID = 123
+	const projectID = 421
+
+	addIDsMap := make(map[string]struct{})
+	for i := 0; i < addsCount; i++ {
+		var mrs []MetricRow
+		var mn MetricName
+		addID := fmt.Sprintf("%d", i)
+		addIDsMap[addID] = struct{}{}
+		mn.AccountID = accountID
+		mn.ProjectID = projectID
+		mn.Tags = []Tag{
+			{[]byte("job"), []byte("webservice")},
+			{[]byte("instance"), []byte("1.2.3.4")},
+			{[]byte("add_id"), []byte(addID)},
+		}
+		now := timestampFromTime(time.Now())
+		for j := 0; j < metricsPerAdd; j++ {
+			mn.MetricGroup = []byte(fmt.Sprintf("metric_%d", j))
+			metricNameRaw := mn.marshalRaw(nil)
+
+			mr := MetricRow{
+				MetricNameRaw: metricNameRaw,
+				Timestamp:     now,
+			}
+			mrs = append(mrs, mr)
+		}
+		if err := s.RegisterMetricNames(mrs); err != nil {
+			return fmt.Errorf("unexpected error in AddMetrics: %w", err)
+		}
+	}
+	var addIDsExpected []string
+	for k := range addIDsMap {
+		addIDsExpected = append(addIDsExpected, k)
+	}
+	sort.Strings(addIDsExpected)
+
+	// Verify the storage contains the added metric names.
+	s.DebugFlush()
+
+	// Verify that SearchTagKeys returns correct result.
+	tksExpected := []string{
+		"",
+		"add_id",
+		"instance",
+		"job",
+	}
+	tks, err := s.SearchTagKeys(accountID, projectID, 100, noDeadline)
+	if err != nil {
+		return fmt.Errorf("error in SearchTagKeys: %w", err)
+	}
+	sort.Strings(tks)
+	if !reflect.DeepEqual(tks, tksExpected) {
+		return fmt.Errorf("unexpected tag keys returned from SearchTagKeys;\ngot\n%q\nwant\n%q", tks, tksExpected)
+	}
+
+	// Verify that SearchTagKeys returns empty results for incorrect accountID, projectID
+	tks, err = s.SearchTagKeys(accountID+1, projectID+1, 100, noDeadline)
+	if err != nil {
+		return fmt.Errorf("error in SearchTagKeys for incorrect accountID, projectID: %w", err)
+	}
+	if len(tks) > 0 {
+		return fmt.Errorf("SearchTagKeys with incorrect accountID, projectID returns unexpected non-empty result:\n%q", tks)
+	}
+
+	// Verify that SearchTagKeysOnTimeRange returns correct result.
+	now := timestampFromTime(time.Now())
+	start := now - msecPerDay
+	end := now + 60*1000
+	tr := TimeRange{
+		MinTimestamp: start,
+		MaxTimestamp: end,
+	}
+	tks, err = s.SearchTagKeysOnTimeRange(accountID, projectID, tr, 100, noDeadline)
+	if err != nil {
+		return fmt.Errorf("error in SearchTagKeysOnTimeRange: %w", err)
+	}
+	sort.Strings(tks)
+	if !reflect.DeepEqual(tks, tksExpected) {
+		return fmt.Errorf("unexpected tag keys returned from SearchTagKeysOnTimeRange;\ngot\n%q\nwant\n%q", tks, tksExpected)
+	}
+
+	// Verify that SearchTagKeysOnTimeRange returns empty results for incrorrect accountID, projectID
+	tks, err = s.SearchTagKeysOnTimeRange(accountID+1, projectID+1, tr, 100, noDeadline)
+	if err != nil {
+		return fmt.Errorf("error in SearchTagKeysOnTimeRange for incorrect accountID, projectID: %w", err)
+	}
+	if len(tks) > 0 {
+		return fmt.Errorf("SearchTagKeysOnTimeRange with incorrect accountID, projectID returns unexpected non-empty result:\n%q", tks)
+	}
+
+	// Verify that SearchTagValues returns correct result.
+	addIDs, err := s.SearchTagValues(accountID, projectID, []byte("add_id"), addsCount+100, noDeadline)
+	if err != nil {
+		return fmt.Errorf("error in SearchTagValues: %w", err)
+	}
+	sort.Strings(addIDs)
+	if !reflect.DeepEqual(addIDs, addIDsExpected) {
+		return fmt.Errorf("unexpected tag values returned from SearchTagValues;\ngot\n%q\nwant\n%q", addIDs, addIDsExpected)
+	}
+
+	// Verify that SearchTagValues return empty results for incorrect accountID, projectID
+	addIDs, err = s.SearchTagValues(accountID+1, projectID+1, []byte("add_id"), addsCount+100, noDeadline)
+	if err != nil {
+		return fmt.Errorf("error in SearchTagValues for incorrect accountID, projectID: %w", err)
+	}
+	if len(addIDs) > 0 {
+		return fmt.Errorf("SearchTagValues with incorrect accountID, projectID returns unexpected non-empty result:\n%q", addIDs)
+	}
+
+	// Verify that SearchTagValuesOnTimeRange returns correct result.
+	addIDs, err = s.SearchTagValuesOnTimeRange(accountID, projectID, []byte("add_id"), tr, addsCount+100, noDeadline)
+	if err != nil {
+		return fmt.Errorf("error in SearchTagValuesOnTimeRange: %w", err)
+	}
+	sort.Strings(addIDs)
+	if !reflect.DeepEqual(addIDs, addIDsExpected) {
+		return fmt.Errorf("unexpected tag values returned from SearchTagValuesOnTimeRange;\ngot\n%q\nwant\n%q", addIDs, addIDsExpected)
+	}
+
+	// Verify that SearchTagValuesOnTimeRange returns empty results for incorrect accountID, projectID
+	addIDs, err = s.SearchTagValuesOnTimeRange(accountID+1, projectID+1, []byte("addd_id"), tr, addsCount+100, noDeadline)
+	if err != nil {
+		return fmt.Errorf("error in SearchTagValuesOnTimeRange for incorrect accoundID, projectID: %w", err)
+	}
+	if len(addIDs) > 0 {
+		return fmt.Errorf("SearchTagValuesOnTimeRange with incorrect accountID, projectID returns unexpected non-empty result:\n%q", addIDs)
+	}
+
+	// Verify that SearchMetricNames returns correct result.
+	tfs := NewTagFilters(accountID, projectID)
+	if err := tfs.Add([]byte("add_id"), []byte("0"), false, false); err != nil {
+		return fmt.Errorf("unexpected error in TagFilters.Add: %w", err)
+	}
+	mns, err := s.SearchMetricNames([]*TagFilters{tfs}, tr, metricsPerAdd*addsCount*100+100, noDeadline)
+	if err != nil {
+		return fmt.Errorf("error in SearchMetricNames: %w", err)
+	}
+	if len(mns) < metricsPerAdd {
+		return fmt.Errorf("unexpected number of metricNames returned from SearchMetricNames; got %d; want at least %d", len(mns), int(metricsPerAdd))
+	}
+	for i, mn := range mns {
+		addID := mn.GetTagValue("add_id")
+		if string(addID) != "0" {
+			return fmt.Errorf("unexpected addID for metricName #%d; got %q; want %q", i, addID, "0")
+		}
+		job := mn.GetTagValue("job")
+		if string(job) != "webservice" {
+			return fmt.Errorf("unexpected job for metricName #%d; got %q; want %q", i, job, "webservice")
+		}
+	}
+
+	// Verify that SearchMetricNames returns empty results for incorrect accountID, projectID
+	tfs = NewTagFilters(accountID+1, projectID+1)
+	if err := tfs.Add([]byte("add_id"), []byte("0"), false, false); err != nil {
+		return fmt.Errorf("unexpected error in TagFilters.Add: %w", err)
+	}
+	mns, err = s.SearchMetricNames([]*TagFilters{tfs}, tr, metricsPerAdd*addsCount*100+100, noDeadline)
+	if err != nil {
+		return fmt.Errorf("error in SearchMetricNames for incorrect accountID, projectID: %w", err)
+	}
+	if len(mns) > 0 {
+		return fmt.Errorf("SearchMetricNames with incorrect accountID, projectID returns unexpected non-empty result:\n%+v", mns)
+	}
+
+	return nil
+}
+
 func TestStorageAddRowsSerial(t *testing.T) {
 	path := "TestStorageAddRowsSerial"
 	s, err := OpenStorage(path, 0)