Repository: VictoriaMetrics/VictoriaMetrics
Pull request #3019 (2022-08-24 16:03:05)

Support "HTTP" and "HTTPS" schemes
Some tools generate `ServiceMonitor` resources with uppercase "HTTP" and "HTTPS" schemes. Victoria can and should support those monitors.


Patch:
diff --git a/app/vmctl/influx.go b/app/vmctl/influx.go
index ee2462c5e..8e11d91be 100644
--- a/app/vmctl/influx.go
+++ b/app/vmctl/influx.go
@@ -52,6 +52,7 @@ func (ip *influxProcessor) run(silent, verbose bool) error {
 	if err := barpool.Start(); err != nil {
 		return err
 	}
+	defer barpool.Stop()
 
 	seriesCh := make(chan *influx.Series)
 	errCh := make(chan error)
@@ -96,7 +97,7 @@ func (ip *influxProcessor) run(silent, verbose bool) error {
 	for err := range errCh {
 		return fmt.Errorf("import process failed: %s", err)
 	}
-	barpool.Stop()
+
 	log.Println("Import finished!")
 	log.Print(ip.im.Stats())
 	return nil
diff --git a/app/vmctl/opentsdb.go b/app/vmctl/opentsdb.go
index fdbb7d9c3..78c3275b6 100644
--- a/app/vmctl/opentsdb.go
+++ b/app/vmctl/opentsdb.go
@@ -82,6 +82,9 @@ func (op *otsdbProcessor) run(silent, verbose bool) error {
 		errCh := make(chan error)
 		// we're going to make serieslist * queryRanges queries, so we should represent that in the progress bar
 		bar := pb.StartNew(len(serieslist) * queryRanges)
+		defer func(bar *pb.ProgressBar) {
+			bar.Finish()
+		}(bar)
 		var wg sync.WaitGroup
 		wg.Add(op.otsdbcc)
 		for i := 0; i < op.otsdbcc; i++ {
diff --git a/app/vmctl/prometheus.go b/app/vmctl/prometheus.go
index b5e018c4a..363aa60a6 100644
--- a/app/vmctl/prometheus.go
+++ b/app/vmctl/prometheus.go
@@ -43,6 +43,7 @@ func (pp *prometheusProcessor) run(silent, verbose bool) error {
 	if err := barpool.Start(); err != nil {
 		return err
 	}
+	defer barpool.Stop()
 
 	blockReadersCh := make(chan tsdb.BlockReader)
 	errCh := make(chan error, pp.cc)
@@ -89,7 +90,7 @@ func (pp *prometheusProcessor) run(silent, verbose bool) error {
 	for err := range errCh {
 		return fmt.Errorf("import process failed: %s", err)
 	}
-	barpool.Stop()
+
 	log.Println("Import finished!")
 	log.Print(pp.im.Stats())
 	return nil
diff --git a/app/vmctl/vm_native.go b/app/vmctl/vm_native.go
index 3c2105b18..85b0a9539 100644
--- a/app/vmctl/vm_native.go
+++ b/app/vmctl/vm_native.go
@@ -89,6 +89,7 @@ func (p *vmNativeProcessor) run(ctx context.Context) error {
 		log.Printf("error start process bars pool: %s", err)
 		return err
 	}
+	defer barpool.Stop()
 
 	w := io.Writer(pw)
 	if p.rateLimit > 0 {
@@ -106,7 +107,6 @@ func (p *vmNativeProcessor) run(ctx context.Context) error {
 	}
 	<-sync
 
-	barpool.Stop()
 	log.Println("Import finished!")
 	return nil
 }
diff --git a/app/vmselect/promql/eval.go b/app/vmselect/promql/eval.go
index 63f45cd55..d59770538 100644
--- a/app/vmselect/promql/eval.go
+++ b/app/vmselect/promql/eval.go
@@ -312,7 +312,9 @@ func evalTransformFunc(qt *querytracer.Tracer, ec *EvalConfig, fe *metricsql.Fun
 	}
 	rv, err := tf(tfa)
 	if err != nil {
-		return nil, fmt.Errorf(`cannot evaluate %q: %w`, fe.AppendString(nil), err)
+		return nil, &UserReadableError{
+			Err: fmt.Errorf(`cannot evaluate %q: %w`, fe.AppendString(nil), err),
+		}
 	}
 	return rv, nil
 }
diff --git a/app/vmselect/promql/transform.go b/app/vmselect/promql/transform.go
index a13e53fe9..b2696f775 100644
--- a/app/vmselect/promql/transform.go
+++ b/app/vmselect/promql/transform.go
@@ -825,8 +825,12 @@ func transformHistogramQuantiles(tfa *transformFuncArg) ([]*timeseries, error) {
 	tssOrig := args[len(args)-1]
 	// Calculate quantile individually per each phi.
 	var rvs []*timeseries
-	for _, phiArg := range phiArgs {
-		phiStr := fmt.Sprintf("%g", phiArg[0].Values[0])
+	for i, phiArg := range phiArgs {
+		phis, err := getScalar(phiArg, i)
+		if err != nil {
+			return nil, fmt.Errorf("cannot parse phi: %w", err)
+		}
+		phiStr := fmt.Sprintf("%g", phis[0])
 		tss := copyTimeseries(tssOrig)
 		tfaTmp := &transformFuncArg{
 			ec: tfa.ec,
diff --git a/docs/CHANGELOG.md b/docs/CHANGELOG.md
index 0bb4376b9..651354e69 100644
--- a/docs/CHANGELOG.md
+++ b/docs/CHANGELOG.md
@@ -23,7 +23,8 @@ The following tip changes can be tested by building VictoriaMetrics components f
 
 * FEATURE: return shorter error messages to Grafana and to other clients requesting [/api/v1/query](https://docs.victoriametrics.com/keyConcepts.html#instant-query) and [/api/v1/query_range](https://docs.victoriametrics.com/keyConcepts.html#range-query) endpoints. This should simplify reading these errors by humans. The long error message with full context is still written to logs.
 * FEATURE: add the ability to fine-tune the number of points, which can be generated per each matching time series during [subquery](https://docs.victoriametrics.com/MetricsQL.html#subqueries) evaluation. This can be done with the `-search.maxPointsSubqueryPerTimeseries` command-line flag. See [this feature request](https://github.com/VictoriaMetrics/VictoriaMetrics/issues/2922).
-* FEATURE: improve the performance for `action: keep`, `action: drop`, `action: labelkeep` and `action: labeldrop` relabeling rules for `regex` containing the list of matching values. For example, `regex: "foo|bar|baz"`.
+* FEATURE: [vmagent](https://docs.victoriametrics.com/vmagent.html): improve the performance for relabeling rules with commonly used regular expressions in `regex` and `if` fields such as `some_string`, `prefix.*`, `prefix.+`, `foo|bar|baz`, `.*foo.*` and `.+foo.+`.
+* FEATURE: [vmagent](https://docs.victoriametrics.com/vmagent.html): reduce CPU usage when discovering big number of [Kubernetes targets](https://docs.victoriametrics.com/sd_configs.html#kubernetes_sd_configs) with big number of labels and annotations.
 * FEATURE: [vmagent](https://docs.victoriametrics.com/vmagent.html): add ability to accept [multitenant](https://docs.victoriametrics.com/Cluster-VictoriaMetrics.html#multitenancy) data via OpenTSDB `/api/put` protocol at `/insert/<tenantID>/opentsdb/api/put` http endpoint if [multitenant support](https://docs.victoriametrics.com/vmagent.html#multitenancy) is enabled at `vmagent`. Thanks to @chengjianyun for [the pull request](https://github.com/VictoriaMetrics/VictoriaMetrics/pull/3015).
 * FEATURE: [monitoring](https://docs.victoriametrics.com/#monitoring): expose `vm_hourly_series_limit_max_series`, `vm_hourly_series_limit_current_series`, `vm_daily_series_limit_max_series` and `vm_daily_series_limit_current_series` metrics when `-search.maxHourlySeries` or `-search.maxDailySeries` limits are set. This allows alerting when the number of unique series reaches the configured limits. See [these docs](https://docs.victoriametrics.com/#cardinality-limiter) for details.
 * FEATURE: [VictoriaMetrics cluster](https://docs.victoriametrics.com/Cluster-VictoriaMetrics.html): reduce the amounts of logging at `vmstorage` when `vmselect` connects/disconnects to `vmstorage`.
@@ -43,6 +44,7 @@ The following tip changes can be tested by building VictoriaMetrics components f
 * BUGFIX: prevent from excess CPU usage when the storage enters [read-only mode](https://docs.victoriametrics.com/Cluster-VictoriaMetrics.html#readonly-mode).
 * BUGFIX: improve performance for requests to [/api/v1/labels](https://docs.victoriametrics.com/url-examples.html#apiv1labels) and [/api/v1/label/.../values](https://docs.victoriametrics.com/url-examples.html#apiv1labelvalues) when the filter in the `match[]` query arg matches small number of time series. The performance for this case has been reduced in [v1.78.0](https://docs.victoriametrics.com/CHANGELOG.html#v1780). See [this](https://github.com/VictoriaMetrics/VictoriaMetrics/issues/2978) and [this](https://github.com/VictoriaMetrics/VictoriaMetrics/issues/1533) issues.
 * BUGFIX: increase the default limit on the number of concurrent merges for small parts from 8 to 16. This should help resolving potential issues with heavy data ingestion. See [this comment](https://github.com/VictoriaMetrics/VictoriaMetrics/pull/2673#issuecomment-1218185978) from @lukepalmer .
+* BUGFIX: [MetricsQL](https://docs.victoriametrics.com/MetricsQL.html): fix panic when incorrect arg is passed as `phi` into [histogram_quantiles](https://docs.victoriametrics.com/MetricsQL.html#histogram_quantiles) function. See [this issue](https://github.com/VictoriaMetrics/VictoriaMetrics/issues/3026).
 
 ## [v1.80.0](https://github.com/VictoriaMetrics/VictoriaMetrics/releases/tag/v1.80.0)
 
diff --git a/docs/MetricsQL.md b/docs/MetricsQL.md
index 329b3f15a..fea64ad14 100644
--- a/docs/MetricsQL.md
+++ b/docs/MetricsQL.md
@@ -491,7 +491,7 @@ The list of supported transform functions:
 
 #### histogram_quantiles
 
-`histogram_quantiles("phiLabel", phi1, ..., phiN, buckets)` calculates the given `phi*`-quantiles over the given [histogram buckets](https://valyala.medium.com/improving-histogram-usability-for-prometheus-and-grafana-bc7e5df0e350). `phi*` must be in the range `[0...1]`. Each calculated quantile is returned in a separate time series with the corresponding `{phiLabel="phi*"}` label. See also [histogram_quantile](#histogram_quantile).
+`histogram_quantiles("phiLabel", phi1, ..., phiN, buckets)` calculates the given `phi*`-quantiles over the given [histogram buckets](https://valyala.medium.com/improving-histogram-usability-for-prometheus-and-grafana-bc7e5df0e350). Argument `phi*` must be in the range `[0...1]`. For example, `histogram_quantiles('le', 0.3, 0.5, sum(rate(http_request_duration_seconds_bucket[5m]) by (le))`. Each calculated quantile is returned in a separate time series with the corresponding `{phiLabel="phi*"}` label. See also [histogram_quantile](#histogram_quantile).
 
 #### histogram_share
 
diff --git a/lib/promrelabel/config.go b/lib/promrelabel/config.go
index a7881dbbf..346e0320a 100644
--- a/lib/promrelabel/config.go
+++ b/lib/promrelabel/config.go
@@ -8,6 +8,7 @@ import (
 
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/envtemplate"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/fs"
+	"github.com/VictoriaMetrics/VictoriaMetrics/lib/logger"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/regexutil"
 	"gopkg.in/yaml.v2"
 )
@@ -189,6 +190,13 @@ func ParseRelabelConfigs(rcs []RelabelConfig, relabelDebug bool) (*ParsedConfigs
 var (
 	defaultOriginalRegexForRelabelConfig = regexp.MustCompile(".*")
 	defaultRegexForRelabelConfig         = regexp.MustCompile("^(.*)$")
+	defaultPromRegex                     = func() *regexutil.PromRegex {
+		pr, err := regexutil.NewPromRegex(".*")
+		if err != nil {
+			panic(fmt.Errorf("BUG: unexpected error: %s", err))
+		}
+		return pr
+	}()
 )
 
 func parseRelabelConfig(rc *RelabelConfig) (*parsedRelabelConfig, error) {
@@ -197,27 +205,36 @@ func parseRelabelConfig(rc *RelabelConfig) (*parsedRelabelConfig, error) {
 	if rc.Separator != nil {
 		separator = *rc.Separator
 	}
+	action := strings.ToLower(rc.Action)
+	if action == "" {
+		action = "replace"
+	}
 	targetLabel := rc.TargetLabel
-	regexCompiled := defaultRegexForRelabelConfig
+	regexAnchored := defaultRegexForRelabelConfig
 	regexOriginalCompiled := defaultOriginalRegexForRelabelConfig
-	var regexOrValues []string
-	if rc.Regex != nil {
+	promRegex := defaultPromRegex
+	if rc.Regex != nil && !isDefaultRegex(rc.Regex.S) {
 		regex := rc.Regex.S
 		regexOrig := regex
 		if rc.Action != "replace_all" && rc.Action != "labelmap_all" {
+			regex = regexutil.RemoveStartEndAnchors(regex)
+			regexOrig = regex
 			regex = "^(?:" + regex + ")$"
 		}
 		re, err := regexp.Compile(regex)
 		if err != nil {
 			return nil, fmt.Errorf("cannot parse `regex` %q: %w", regex, err)
 		}
-		regexCompiled = re
+		regexAnchored = re
 		reOriginal, err := regexp.Compile(regexOrig)
 		if err != nil {
 			return nil, fmt.Errorf("cannot parse `regex` %q: %w", regexOrig, err)
 		}
 		regexOriginalCompiled = reOriginal
-		regexOrValues = regexutil.GetOrValues(regexOrig)
+		promRegex, err = regexutil.NewPromRegex(regexOrig)
+		if err != nil {
+			logger.Panicf("BUG: cannot parse already parsed regex %q: %s", regexOrig, err)
+		}
 	}
 	modulus := rc.Modulus
 	replacement := "$1"
@@ -232,10 +249,6 @@ func parseRelabelConfig(rc *RelabelConfig) (*parsedRelabelConfig, error) {
 	if rc.Labels != nil {
 		graphiteLabelRules = newGraphiteLabelRules(rc.Labels)
 	}
-	action := rc.Action
-	if action == "" {
-		action = "replace"
-	}
 	switch action {
 	case "graphite":
 		if graphiteMatchTemplate == nil {
@@ -334,23 +347,31 @@ func parseRelabelConfig(rc *RelabelConfig) (*parsedRelabelConfig, error) {
 		}
 	}
 	return &parsedRelabelConfig{
-		SourceLabels: sourceLabels,
-		Separator:    separator,
-		TargetLabel:  targetLabel,
-		Regex:        regexCompiled,
-		Modulus:      modulus,
-		Replacement:  replacement,
-		Action:       action,
-		If:           rc.If,
+		SourceLabels:  sourceLabels,
+		Separator:     separator,
+		TargetLabel:   targetLabel,
+		RegexAnchored: regexAnchored,
+		Modulus:       modulus,
+		Replacement:   replacement,
+		Action:        action,
+		If:            rc.If,
 
 		graphiteMatchTemplate: graphiteMatchTemplate,
 		graphiteLabelRules:    graphiteLabelRules,
 
+		regex:         promRegex,
 		regexOriginal: regexOriginalCompiled,
-		regexOrValues: regexOrValues,
 
 		hasCaptureGroupInTargetLabel:   strings.Contains(targetLabel, "$"),
 		hasCaptureGroupInReplacement:   strings.Contains(replacement, "$"),
 		hasLabelReferenceInReplacement: strings.Contains(replacement, "{{"),
 	}, nil
 }
+
+func isDefaultRegex(expr string) bool {
+	prefix, suffix := regexutil.Simplify(expr)
+	if prefix != "" {
+		return false
+	}
+	return suffix == ".*"
+}
diff --git a/lib/promrelabel/if_expression.go b/lib/promrelabel/if_expression.go
index 32805cab5..24571b865 100644
--- a/lib/promrelabel/if_expression.go
+++ b/lib/promrelabel/if_expression.go
@@ -3,10 +3,10 @@ package promrelabel
 import (
 	"encoding/json"
 	"fmt"
-	"regexp"
 
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/logger"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/prompbmarshal"
+	"github.com/VictoriaMetrics/VictoriaMetrics/lib/regexutil"
 	"github.com/VictoriaMetrics/metricsql"
 )
 
@@ -105,7 +105,7 @@ type labelFilter struct {
 	value string
 
 	// re contains compiled regexp for `=~` and `!~` op.
-	re *regexp.Regexp
+	re *regexutil.PromRegex
 }
 
 func newLabelFilter(mlf *metricsql.LabelFilter) (*labelFilter, error) {
@@ -115,10 +115,7 @@ func newLabelFilter(mlf *metricsql.LabelFilter) (*labelFilter, error) {
 		value: mlf.Value,
 	}
 	if lf.op == "=~" || lf.op == "!~" {
-		// PromQL regexps are anchored by default.
-		// See https://prometheus.io/docs/prometheus/latest/querying/basics/#time-series-selectors
-		reString := "^(?:" + lf.value + ")$"
-		re, err := regexp.Compile(reString)
+		re, err := regexutil.NewPromRegex(lf.value)
 		if err != nil {
 			return nil, fmt.Errorf("cannot parse regexp for %s: %w", mlf.AppendString(nil), err)
 		}
@@ -134,9 +131,9 @@ func (lf *labelFilter) match(labels []prompbmarshal.Label) bool {
 	case "!=":
 		return !lf.equalValue(labels)
 	case "=~":
-		return lf.equalRegexp(labels)
+		return lf.matchRegexp(labels)
 	case "!~":
-		return !lf.equalRegexp(labels)
+		return !lf.matchRegexp(labels)
 	default:
 		logger.Panicf("BUG: unexpected operation for label filter: %s", lf.op)
 	}
@@ -161,7 +158,7 @@ func (lf *labelFilter) equalValue(labels []prompbmarshal.Label) bool {
 	return false
 }
 
-func (lf *labelFilter) equalRegexp(labels []prompbmarshal.Label) bool {
+func (lf *labelFilter) matchRegexp(labels []prompbmarshal.Label) bool {
 	labelNameMatches := 0
 	for _, label := range labels {
 		if toCanonicalLabelName(label.Name) != lf.label {
diff --git a/lib/promrelabel/relabel.go b/lib/promrelabel/relabel.go
index 01d2a88e2..f03f29ba2 100644
--- a/lib/promrelabel/relabel.go
+++ b/lib/promrelabel/relabel.go
@@ -9,6 +9,7 @@ import (
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/bytesutil"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/logger"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/prompbmarshal"
+	"github.com/VictoriaMetrics/VictoriaMetrics/lib/regexutil"
 	"github.com/cespare/xxhash/v2"
 )
 
@@ -16,20 +17,20 @@ import (
 //
 // See https://prometheus.io/docs/prometheus/latest/configuration/configuration/#relabel_config
 type parsedRelabelConfig struct {
-	SourceLabels []string
-	Separator    string
-	TargetLabel  string
-	Regex        *regexp.Regexp
-	Modulus      uint64
-	Replacement  string
-	Action       string
-	If           *IfExpression
+	SourceLabels  []string
+	Separator     string
+	TargetLabel   string
+	RegexAnchored *regexp.Regexp
+	Modulus       uint64
+	Replacement   string
+	Action        string
+	If            *IfExpression
 
 	graphiteMatchTemplate *graphiteMatchTemplate
 	graphiteLabelRules    []graphiteLabelRule
 
+	regex         *regexutil.PromRegex
 	regexOriginal *regexp.Regexp
-	regexOrValues []string
 
 	hasCaptureGroupInTargetLabel   bool
 	hasCaptureGroupInReplacement   bool
@@ -39,7 +40,8 @@ type parsedRelabelConfig struct {
 // String returns human-readable representation for prc.
 func (prc *parsedRelabelConfig) String() string {
 	return fmt.Sprintf("SourceLabels=%s, Separator=%s, TargetLabel=%s, Regex=%s, Modulus=%d, Replacement=%s, Action=%s, If=%s, graphiteMatchTemplate=%s, graphiteLabelRules=%s",
-		prc.SourceLabels, prc.Separator, prc.TargetLabel, prc.Regex, prc.Modulus, prc.Replacement, prc.Action, prc.If, prc.graphiteMatchTemplate, prc.graphiteLabelRules)
+		prc.SourceLabels, prc.Separator, prc.TargetLabel, prc.regexOriginal, prc.Modulus, prc.Replacement,
+		prc.Action, prc.If, prc.graphiteMatchTemplate, prc.graphiteLabelRules)
 }
 
 // Apply applies pcs to labels starting from the labelsOffset.
@@ -183,7 +185,7 @@ func (prc *parsedRelabelConfig) apply(labels []prompbmarshal.Label, labelsOffset
 			replacement = string(bb.B)
 		}
 		bb.B = concatLabelValues(bb.B[:0], src, prc.SourceLabels, prc.Separator)
-		if prc.Regex == defaultRegexForRelabelConfig && !prc.hasCaptureGroupInTargetLabel {
+		if prc.RegexAnchored == defaultRegexForRelabelConfig && !prc.hasCaptureGroupInTargetLabel {
 			if replacement == "$1" {
 				// Fast path for the rule that copies source label values to destination:
 				// - source_labels: [...]
@@ -201,7 +203,12 @@ func (prc *parsedRelabelConfig) apply(labels []prompbmarshal.Label, labelsOffset
 				return labels
 			}
 		}
-		match := prc.Regex.FindSubmatchIndex(bb.B)
+		if re := prc.regex; re.HasPrefix() && !re.MatchString(bytesutil.ToUnsafeString(bb.B)) {
+			// Fast path - regexp mismatch.
+			relabelBufPool.Put(bb)
+			return labels
+		}
+		match := prc.RegexAnchored.FindSubmatchIndex(bb.B)
 		if match == nil {
 			// Fast path - nothing to replace.
 			relabelBufPool.Put(bb)
@@ -253,7 +260,7 @@ func (prc *parsedRelabelConfig) apply(labels []prompbmarshal.Label, labelsOffset
 		return labels
 	case "keep":
 		// Keep the target if `source_labels` joined with `separator` match the `regex`.
-		if prc.Regex == defaultRegexForRelabelConfig {
+		if prc.RegexAnchored == defaultRegexForRelabelConfig {
 			// Fast path for the case with `if` and without explicitly set `regex`:
 			//
 			// - action: keep
@@ -263,7 +270,7 @@ func (prc *parsedRelabelConfig) apply(labels []prompbmarshal.Label, labelsOffset
 		}
 		bb := relabelBufPool.Get()
 		bb.B = concatLabelValues(bb.B[:0], src, prc.SourceLabels, prc.Separator)
-		keep := prc.matchString(bytesutil.ToUnsafeString(bb.B))
+		keep := prc.regex.MatchString(bytesutil.ToUnsafeString(bb.B))
 		relabelBufPool.Put(bb)
 		if !keep {
 			return labels[:labelsOffset]
@@ -271,7 +278,7 @@ func (prc *parsedRelabelConfig) apply(labels []prompbmarshal.Label, labelsOffset
 		return labels
 	case "drop":
 		// Drop the target if `source_labels` joined with `separator` don't match the `regex`.
-		if prc.Regex == defaultRegexForRelabelConfig {
+		if prc.RegexAnchored == defaultRegexForRelabelConfig {
 			// Fast path for the case with `if` and without explicitly set `regex`:
 			//
 			// - action: drop
@@ -281,7 +288,7 @@ func (prc *parsedRelabelConfig) apply(labels []prompbmarshal.Label, labelsOffset
 		}
 		bb := relabelBufPool.Get()
 		bb.B = concatLabelValues(bb.B[:0], src, prc.SourceLabels, prc.Separator)
-		drop := prc.matchString(bytesutil.ToUnsafeString(bb.B))
+		drop := prc.regex.MatchString(bytesutil.ToUnsafeString(bb.B))
 		relabelBufPool.Put(bb)
 		if drop {
 			return labels[:labelsOffset]
@@ -297,8 +304,7 @@ func (prc *parsedRelabelConfig) apply(labels []prompbmarshal.Label, labelsOffset
 		return setLabelValue(labels, labelsOffset, prc.TargetLabel, value)
 	case "labelmap":
 		// Replace label names with the `replacement` if they match `regex`
-		for i := range src {
-			label := &src[i]
+		for _, label := range src {
 			labelName, ok := prc.replaceFullString(label.Name, prc.Replacement, prc.hasCaptureGroupInReplacement)
 			if ok {
 				labels = setLabelValue(labels, labelsOffset, labelName, label.Value)
@@ -315,20 +321,20 @@ func (prc *parsedRelabelConfig) apply(labels []prompbmarshal.Label, labelsOffset
 	case "labeldrop":
 		// Drop labels with names matching the `regex`
 		dst := labels[:labelsOffset]
-		for i := range src {
-			label := &src[i]
-			if !prc.matchString(label.Name) {
-				dst = append(dst, *label)
+		re := prc.regex
+		for _, label := range src {
+			if !re.MatchString(label.Name) {
+				dst = append(dst, label)
 			}
 		}
 		return dst
 	case "labelkeep":
 		// Keep labels with names matching the `regex`
 		dst := labels[:labelsOffset]
-		for i := range src {
-			label := &src[i]
-			if prc.matchString(label.Name) {
-				dst = append(dst, *label)
+		re := prc.regex
+		for _, label := range src {
+			if re.MatchString(label.Name) {
+				dst = append(dst, label)
 			}
 		}
 		return dst
@@ -386,13 +392,17 @@ func (prc *parsedRelabelConfig) replaceFullString(s, replacement string, hasCapt
 			}
 		}
 	}
+	if re := prc.regex; re.HasPrefix() && !re.MatchString(s) {
+		// Fast path - regex mismatch
+		return s, false
+	}
 	// Slow path - regexp processing
-	match := prc.Regex.FindStringSubmatchIndex(s)
+	match := prc.RegexAnchored.FindStringSubmatchIndex(s)
 	if match == nil {
 		return s, false
 	}
 	bb := relabelBufPool.Get()
-	bb.B = prc.Regex.ExpandString(bb.B[:0], replacement, s, match)
+	bb.B = prc.RegexAnchored.ExpandString(bb.B[:0], replacement, s, match)
 	result := string(bb.B)
 	relabelBufPool.Put(bb)
 	return result, true
@@ -413,39 +423,9 @@ func (prc *parsedRelabelConfig) replaceStringSubmatches(s, replacement string, h
 	return re.ReplaceAllString(s, replacement), true
 }
 
-func (prc *parsedRelabelConfig) matchString(s string) bool {
-	if len(prc.regexOrValues) > 0 {
-		for _, orValue := range prc.regexOrValues {
-			if s == orValue {
-				return true
-			}
-		}
-		return false
-	}
-	prefix, complete := prc.regexOriginal.LiteralPrefix()
-	if complete {
-		return prefix == s
-	}
-	if !strings.HasPrefix(s, prefix) {
-		return false
-	}
-	reStr := prc.regexOriginal.String()
-	if strings.HasPrefix(reStr, prefix) {
-		// Fast path for `foo.*` and `bar.+` regexps
-		reSuffix := reStr[len(prefix):]
-		switch reSuffix {
-		case ".+", "(.+)":
-			return len(s) > len(prefix)
-		case ".*", "(.*)":
-			return true
-		}
-	}
-	return prc.Regex.MatchString(s)
-}
-
 func (prc *parsedRelabelConfig) expandCaptureGroups(template, source string, match []int) string {
 	bb := relabelBufPool.Get()
-	bb.B = prc.Regex.ExpandString(bb.B[:0], template, source, match)
+	bb.B = prc.RegexAnchored.ExpandString(bb.B[:0], template, source, match)
 	s := string(bb.B)
 	relabelBufPool.Put(bb)
 	return s
diff --git a/lib/promscrape/config.go b/lib/promscrape/config.go
index cbb5c654a..d193b4b8f 100644
--- a/lib/promscrape/config.go
+++ b/lib/promscrape/config.go
@@ -4,16 +4,15 @@ import (
 	"encoding/json"
 	"flag"
 	"fmt"
-	"github.com/VictoriaMetrics/VictoriaMetrics/lib/auth"
 	"net/url"
 	"path/filepath"
 	"sort"
 	"strconv"
 	"strings"
 	"sync"
-	"sync/atomic"
 	"time"
 
+	"github.com/VictoriaMetrics/VictoriaMetrics/lib/auth"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/bytesutil"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/cgroup"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/envtemplate"
@@ -35,6 +34,7 @@ import (
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/promscrape/discovery/kubernetes"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/promscrape/discovery/openstack"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/promscrape/discovery/yandexcloud"
+	"github.com/VictoriaMetrics/VictoriaMetrics/lib/promscrape/discoveryutils"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/promutils"
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/proxy"
 	"github.com/VictoriaMetrics/metrics"
@@ -904,7 +904,7 @@ func getScrapeWorkConfig(sc *ScrapeConfig, baseDir string, globalCfg *GlobalConf
 	if metricsPath == "" {
 		metricsPath = "/metrics"
 	}
-	scheme := sc.Scheme
+	scheme := strings.ToLower(sc.Scheme)
 	if scheme == "" {
 		scheme = "http"
 	}
@@ -1330,37 +1330,11 @@ func (swc *scrapeWorkConfig) getScrapeWork(target string, extraLabels, metaLabel
 func internLabelStrings(labels []prompbmarshal.Label) {
 	for i := range labels {
 		label := &labels[i]
-		label.Name = internString(label.Name)
-		label.Value = internString(label.Value)
+		label.Name = discoveryutils.InternString(label.Name)
+		label.Value = discoveryutils.InternString(label.Value)
 	}
 }
 
-func internString(s string) string {
-	m := internStringsMap.Load().(*sync.Map)
-	if v, ok := m.Load(s); ok {
-		sp := v.(*string)
-		return *sp
-	}
-	// Make a new copy for s in order to remove references from possible bigger string s refers to.
-	sCopy := string(append([]byte{}, s...))
-	m.Store(sCopy, &sCopy)
-	n := atomic.AddUint64(&internStringsMapLen, 1)
-	if n > 100e3 {
-		atomic.StoreUint64(&internStringsMapLen, 0)
-		internStringsMap.Store(&sync.Map{})
-	}
-	return sCopy
-}
-
-var (
-	internStringsMap    atomic.Value
-	internStringsMapLen uint64
-)
-
-func init() {
-	internStringsMap.Store(&sync.Map{})
-}
-
 func getParamsFromLabels(labels []prompbmarshal.Label, paramsOrig map[string][]string) map[string][]string {
 	// See https://www.robustperception.io/life-of-a-label
 	m := make(map[string][]string)
diff --git a/lib/promscrape/discovery/consul/service_node.go b/lib/promscrape/discovery/consul/service_node.go
index ba33913ba..23f3a0003 100644
--- a/lib/promscrape/discovery/consul/service_node.go
+++ b/lib/promscrape/discovery/consul/service_node.go
@@ -94,16 +94,13 @@ func (sn *ServiceNode) appendTargetLabels(ms []map[string]string, serviceName, t
 	m["__meta_consul_tags"] = tagSeparator + strings.Join(sn.Service.Tags, tagSeparator) + tagSeparator
 
 	for k, v := range sn.Node.Meta {
-		key := discoveryutils.SanitizeLabelName(k)
-		m["__meta_consul_metadata_"+key] = v
+		m[discoveryutils.SanitizeLabelName("__meta_consul_metadata_"+k)] = v
 	}
 	for k, v := range sn.Service.Meta {
-		key := discoveryutils.SanitizeLabelName(k)
-		m["__meta_consul_service_metadata_"+key] = v
+		m[discoveryutils.SanitizeLabelName("__meta_consul_service_metadata_"+k)] = v
 	}
 	for k, v := range sn.Node.TaggedAddresses {
-		key := discoveryutils.SanitizeLabelName(k)
-		m["__meta_consul_tagged_address_"+key] = v
+		m[discoveryutils.SanitizeLabelName("__meta_consul_tagged_address_"+k)] = v
 	}
 	ms = append(ms, m)
 	return ms
diff --git a/lib/promscrape/discovery/docker/container.go b/lib/promscrape/discovery/docker/container.go
index a8ff92f8b..43444f045 100644
--- a/lib/promscrape/discovery/docker/container.go
+++ b/lib/promscrape/discovery/docker/container.go
@@ -107,7 +107,7 @@ func addCommonLabels(m map[string]string, c *container, networkLabels map[string
 	m["__meta_docker_container_name"] = c.Names[0]
 	m["__meta_docker_container_network_mode"] = c.HostConfig.NetworkMode
 	for k, v := range c.Labels {
-		m["__meta_docker_container_label_"+discoveryutils.SanitizeLabelName(k)] = v
+		m[discoveryutils.SanitizeLabelName("__meta_docker_container_label_"+k)] = v
 	}
 	for k, v := range networkLabels {
 		m[k] = v
diff --git a/lib/promscrape/discovery/docker/network.go b/lib/promscrape/discovery/docker/network.go
index 8df47e531..075fae9d7 100644
--- a/lib/promscrape/discovery/docker/network.go
+++ b/lib/promscrape/discovery/docker/network.go
@@ -53,7 +53,7 @@ func getNetworkLabelsByNetworkID(networks []network) map[string]map[string]strin
 			"__meta_docker_network_scope":    network.Scope,
 		}
 		for k, v := range network.Labels {
-			m["__meta_docker_network_label_"+discoveryutils.SanitizeLabelName(k)] = v
+			m[discoveryutils.SanitizeLabelName("__meta_docker_network_label_"+k)] = v
 		}
 		ms[network.ID] = m
 	}
diff --git a/lib/promscrape/discovery/dockerswarm/network.go b/lib/promscrape/discovery/dockerswarm/network.go
index 27bb748cb..8fe12f058 100644
--- a/lib/promscrape/discovery/dockerswarm/network.go
+++ b/lib/promscrape/discovery/dockerswarm/network.go
@@ -53,7 +53,7 @@ func getNetworkLabelsByNetworkID(networks []network) map[string]map[string]strin
 			"__meta_dockerswarm_network_scope":    network.Scope,
 		}
 		for k, v := range network.Labels {
-			m["__meta_dockerswarm_network_label_"+discoveryutils.SanitizeLabelName(k)] = v
+			m[discoveryutils.SanitizeLabelName("__meta_dockerswarm_network_label_"+k)] = v
 		}
 		ms[network.ID] = m
 	}
diff --git a/lib/promscrape/discovery/dockerswarm/nodes.go b/lib/promscrape/discovery/dockerswarm/nodes.go
index c6db715f2..592141e0f 100644
--- a/lib/promscrape/discovery/dockerswarm/nodes.go
+++ b/lib/promscrape/discovery/dockerswarm/nodes.go
@@ -80,7 +80,7 @@ func addNodeLabels(nodes []node, port int) []map[string]string {
 			"__meta_dockerswarm_node_status":                node.Status.State,
 		}
 		for k, v := range node.Spec.Labels {
-			m["__meta_dockerswarm_node_label_"+discoveryutils.SanitizeLabelName(k)] = v
+			m[discoveryutils.SanitizeLabelName("__meta_dockerswarm_node_label_"+k)] = v
 		}
 		ms = append(ms, m)
 	}
diff --git a/lib/promscrape/discovery/dockerswarm/services.go b/lib/promscrape/discovery/dockerswarm/services.go
index 5c26ad167..ac52eb3a8 100644
--- a/lib/promscrape/discovery/dockerswarm/services.go
+++ b/lib/promscrape/discovery/dockerswarm/services.go
@@ -96,7 +96,7 @@ func addServicesLabels(services []service, networksLabels map[string]map[string]
 			"__meta_dockerswarm_service_updating_status":         service.UpdateStatus.State,
 		}
 		for k, v := range service.Spec.Labels {
-			commonLabels["__meta_dockerswarm_service_label_"+discoveryutils.SanitizeLabelName(k)] = v
+			commonLabels[discoveryutils.SanitizeLabelName("__meta_dockerswarm_service_label_"+k)] = v
 		}
 		for _, vip := range service.Endpoint.VirtualIPs {
 			// skip services without virtual address.
diff --git a/lib/promscrape/discovery/dockerswarm/tasks.go b/lib/promscrape/discovery/dockerswarm/tasks.go
index d58953763..9e17825ee 100644
--- a/lib/promscrape/discovery/dockerswarm/tasks.go
+++ b/lib/promscrape/discovery/dockerswarm/tasks.go
@@ -87,7 +87,7 @@ func addTasksLabels(tasks []task, nodesLabels, servicesLabels []map[string]strin
 			"__meta_dockerswarm_task_state":         task.Status.State,
 		}
 		for k, v := range task.Spec.ContainerSpec.Labels {
-			commonLabels["__meta_dockerswarm_container_label_"+discoveryutils.SanitizeLabelName(k)] = v
+			commonLabels[discoveryutils.SanitizeLabelName("__meta_dockerswarm_container_label_"+k)] = v
 		}
 		var svcPorts []portConfig
 		for i, v := range services {
diff --git a/lib/promscrape/discovery/ec2/instance.go b/lib/promscrape/discovery/ec2/instance.go
index c111aaf30..9cacb2506 100644
--- a/lib/promscrape/discovery/ec2/instance.go
+++ b/lib/promscrape/discovery/ec2/instance.go
@@ -186,8 +186,7 @@ func (inst *Instance) appendTargetLabels(ms []map[string]string, ownerID string,
 		if len(t.Key) == 0 || len(t.Value) == 0 {
 			continue
 		}
-		name := discoveryutils.SanitizeLabelName(t.Key)
-		m["__meta_ec2_tag_"+name] = t.Value
+		m[discoveryutils.SanitizeLabelName("__meta_ec2_tag_"+t.Key)] = t.Value
 	}
 	ms = append(ms, m)
 	return ms
diff --git a/lib/promscrape/discovery/eureka/eureka.go b/lib/promscrape/discovery/eureka/eureka.go
index 86a372259..f2390f6d4 100644
--- a/lib/promscrape/discovery/eureka/eureka.go
+++ b/lib/promscrape/discovery/eureka/eureka.go
@@ -139,11 +139,11 @@ func addInstanceLabels(apps *applications) []map[string]string {
 			if len(instance.DataCenterInfo.Name) > 0 {
 				m["__meta_eureka_app_instance_datacenterinfo_name"] = instance.DataCenterInfo.Name
 				for _, tag := range instance.DataCenterInfo.Metadata.Items {
-					m["__meta_eureka_app_instance_datacenterinfo_metadata_"+discoveryutils.SanitizeLabelName(tag.XMLName.Local)] = tag.Content
+					m[discoveryutils.SanitizeLabelName("__meta_eureka_app_instance_datacenterinfo_metadata_"+tag.XMLName.Local)] = tag.Content
 				}
 			}
 			for _, tag := range instance.Metadata.Items {
-				m["__meta_eureka_app_instance_metadata_"+discoveryutils.SanitizeLabelName(tag.XMLName.Local)] = tag.Content
+				m[discoveryutils.SanitizeLabelName("__meta_eureka_app_instance_metadata_"+tag.XMLName.Local)] = tag.Content
 			}
 			ms = append(ms, m)
 		}
diff --git a/lib/promscrape/discovery/gce/instance.go b/lib/promscrape/discovery/gce/instance.go
index 65ad7bdd7..2c16a9c37 100644
--- a/lib/promscrape/discovery/gce/instance.go
+++ b/lib/promscrape/discovery/gce/instance.go
@@ -150,8 +150,7 @@ func (inst *Instance) appendTargetLabels(ms []map[string]string, project, tagSep
 		"__meta_gce_zone":            inst.Zone,
 	}
 	for _, iface := range inst.NetworkInterfaces {
-		ifaceName := discoveryutils.SanitizeLabelName(iface.Name)
-		m["__meta_gce_interface_ipv4_"+ifaceName] = iface.NetworkIP
+		m[discoveryutils.SanitizeLabelName("__meta_gce_interface_ipv4_"+iface.Name)] = iface.NetworkIP
 	}
 	if len(inst.Tags.Items) > 0 {
 		// We surround the separated list with the separator as well. This way regular expressions
@@ -159,12 +158,10 @@ func (inst *Instance) appendTargetLabels(ms []map[string]string, project, tagSep
 		m["__meta_gce_tags"] = tagSeparator + strings.Join(inst.Tags.Items, tagSeparator) + tagSeparator
 	}
 	for _, item := range inst.Metadata.Items {
-		key := discoveryutils.SanitizeLabelName(item.Key)
-		m["__meta_gce_metadata_"+key] = item.Value
+		m[discoveryutils.SanitizeLabelName("__meta_gce_metadata_"+item.Key)] = item.Value
 	}
 	for _, label := range inst.Labels {
-		name := discoveryutils.SanitizeLabelName(label.Name)
-		m["__meta_gce_label_"+name] = label.Value
+		m[discoveryutils.SanitizeLabelName("__meta_gce_label_"+label.Name)] = label.Value
 	}
 	if len(iface.AccessConfigs) > 0 {
 		ac := iface.AccessConfigs[0]
diff --git a/lib/promscrape/discovery/kubernetes/common_types.go b/lib/promscrape/discovery/kubernetes/common_types.go
index be93bbb4a..c2479ca19 100644
--- a/lib/promscrape/discovery/kubernetes/common_types.go
+++ b/lib/promscrape/discovery/kubernetes/common_types.go
@@ -28,14 +28,12 @@ type ListMeta struct {
 
 func (om *ObjectMeta) registerLabelsAndAnnotations(prefix string, m map[string]string) {
 	for _, lb := range om.Labels {
-		ln := discoveryutils.SanitizeLabelName(lb.Name)
-		m[prefix+"_label_"+ln] = lb.Value
-		m[prefix+"_labelpresent_"+ln] = "true"
+		m[discoveryutils.SanitizeLabelName(prefix+"_label_"+lb.Name)] = lb.Value
+		m[discoveryutils.SanitizeLabelName(prefix+"_labelpresent_"+lb.Name)] = "true"
 	}
 	for _, a := range om.Annotations {
-		an := discoveryutils.SanitizeLabelName(a.Name)
-		m[prefix+"_annotation_"+an] = a.Value
-		m[prefix+"_annotationpresent_"+an] = "true"
+		m[discoveryutils.SanitizeLabelName(prefix+"_annotation_"+a.Name)] = a.Value
+		m[discoveryutils.SanitizeLabelName(prefix+"_annotationpresent_"+a.Name)] = "true"
 	}
 }
 
diff --git a/lib/promscrape/discovery/kubernetes/endpointslice.go b/lib/promscrape/discovery/kubernetes/endpointslice.go
index f4a2a07ac..8e376865c 100644
--- a/lib/promscrape/discovery/kubernetes/endpointslice.go
+++ b/lib/promscrape/discovery/kubernetes/endpointslice.go
@@ -151,8 +151,8 @@ func getEndpointSliceLabels(eps *EndpointSlice, addr string, ea Endpoint, epp En
 		m["__meta_kubernetes_endpointslice_endpoint_hostname"] = ea.Hostname
 	}
 	for k, v := range ea.Topology {
-		m["__meta_kubernetes_endpointslice_endpoint_topology_"+discoveryutils.SanitizeLabelName(k)] = v
-		m["__meta_kubernetes_endpointslice_endpoint_topology_present_"+discoveryutils.SanitizeLabelName(k)] = "true"
+		m[discoveryutils.SanitizeLabelName("__meta_kubernetes_endpointslice_endpoint_topology_"+k)] = v
+		m[discoveryutils.SanitizeLabelName("__meta_kubernetes_endpointslice_endpoint_topology_present_"+k)] = "true"
 	}
 	return m
 }
diff --git a/lib/promscrape/discovery/kubernetes/node.go b/lib/promscrape/discovery/kubernetes/node.go
index 2f9605bf3..812c7f301 100644
--- a/lib/promscrape/discovery/kubernetes/node.go
+++ b/lib/promscrape/discovery/kubernetes/node.go
@@ -104,8 +104,7 @@ func (n *Node) getTargetLabels(gw *groupWatcher) []map[string]string {
 			continue
 		}
 		addrTypesUsed[a.Type] = true
-		ln := discoveryutils.SanitizeLabelName(a.Type)
-		m["__meta_kubernetes_node_address_"+ln] = a.Address
+		m[discoveryutils.SanitizeLabelName("__meta_kubernetes_node_address_"+a.Type)] = a.Address
 	}
 	return []map[string]string{m}
 }
diff --git a/lib/promscrape/discovery/openstack/instance.go b/lib/promscrape/discovery/openstack/instance.go
index 0d020b6a0..5f628d420 100644
--- a/lib/promscrape/discovery/openstack/instance.go
+++ b/lib/promscrape/discovery/openstack/instance.go
@@ -57,7 +57,7 @@ func addInstanceLabels(servers []server, port int) []map[string]string {
 			"__meta_openstack_instance_flavor": server.Flavor.ID,
 		}
 		for k, v := range server.Metadata {
-			m["__meta_openstack_tag_"+discoveryutils.SanitizeLabelName(k)] = v
+			m[discoveryutils.SanitizeLabelName("__meta_openstack_tag_"+k)] = v
 		}
 		// Traverse server.Addresses in alphabetical order of pool name
 		// in order to return targets in deterministic order.
diff --git a/lib/promscrape/discovery/yandexcloud/instance.go b/lib/promscrape/discovery/yandexcloud/instance.go
index a887745aa..f78036596 100644
--- a/lib/promscrape/discovery/yandexcloud/instance.go
+++ b/lib/promscrape/discovery/yandexcloud/instance.go
@@ -51,7 +51,7 @@ func addInstanceLabels(instances []instance) []map[string]string {
 			"__meta_yandexcloud_folder_id":                        server.FolderID,
 		}
 		for k, v := range server.Labels {
-			m["__meta_yandexcloud_instance_label_"+discoveryutils.SanitizeLabelName(k)] = v
+			m[discoveryutils.SanitizeLabelName("__meta_yandexcloud_instance_label_"+k)] = v
 		}
 
 		for _, ni := range server.NetworkInterfaces {
diff --git a/lib/promscrape/discoveryutils/internstring.go b/lib/promscrape/discoveryutils/internstring.go
new file mode 100644
index 000000000..42f429d96
--- /dev/null
+++ b/lib/promscrape/discoveryutils/internstring.go
@@ -0,0 +1,35 @@
+package discoveryutils
+
+import (
+	"sync"
+	"sync/atomic"
+)
+
+// InternString returns interned s.
+//
+// This may be needed for reducing the amounts of allocated memory.
+func InternString(s string) string {
+	m := internStringsMap.Load().(*sync.Map)
+	if v, ok := m.Load(s); ok {
+		sp := v.(*string)
+		return *sp
+	}
+	// Make a new copy for s in order to remove references from possible bigger string s refers to.
+	sCopy := string(append([]byte{}, s...))
+	m.Store(sCopy, &sCopy)
+	n := atomic.AddUint64(&internStringsMapLen, 1)
+	if n > 100e3 {
+		atomic.StoreUint64(&internStringsMapLen, 0)
+		internStringsMap.Store(&sync.Map{})
+	}
+	return sCopy
+}
+
+var (
+	internStringsMap    atomic.Value
+	internStringsMapLen uint64
+)
+
+func init() {
+	internStringsMap.Store(&sync.Map{})
+}
diff --git a/lib/promscrape/discoveryutils/utils.go b/lib/promscrape/discoveryutils/utils.go
index cd0d103c9..9ee10d0cc 100644
--- a/lib/promscrape/discoveryutils/utils.go
+++ b/lib/promscrape/discoveryutils/utils.go
@@ -6,6 +6,8 @@ import (
 	"regexp"
 	"sort"
 	"strconv"
+	"sync"
+	"sync/atomic"
 
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/prompbmarshal"
 )
@@ -15,13 +17,44 @@ import (
 //
 // This has been copied from Prometheus sources at util/strutil/strconv.go
 func SanitizeLabelName(name string) string {
-	return invalidLabelCharRE.ReplaceAllString(name, "_")
+	m := sanitizedLabelNames.Load().(*sync.Map)
+	v, ok := m.Load(name)
+	if ok {
+		// Fast path - the sanitized label name is found in the cache.
+		sp := v.(*string)
+		return *sp
+	}
+	// Slow path - sanitize name and store it in the cache.
+	sanitizedName := invalidLabelCharRE.ReplaceAllString(name, "_")
+	// Make a copy of name in order to limit memory usage to the name length,
+	// since the name may point to bigger string.
+	s := string(append([]byte{}, name...))
+	if sanitizedName == name {
+		// point sanitizedName to just allocated s, since it may point to name,
+		// which, in turn, can point to bigger string.
+		sanitizedName = s
+	}
+	sp := &sanitizedName
+	m.Store(s, sp)
+	n := atomic.AddUint64(&sanitizedLabelNamesLen, 1)
+	if n > 100e3 {
+		atomic.StoreUint64(&sanitizedLabelNamesLen, 0)
+		sanitizedLabelNames.Store(&sync.Map{})
+	}
+	return sanitizedName
 }
 
 var (
+	sanitizedLabelNames    atomic.Value
+	sanitizedLabelNamesLen uint64
+
 	invalidLabelCharRE = regexp.MustCompile(`[^a-zA-Z0-9_]`)
 )
 
+func init() {
+	sanitizedLabelNames.Store(&sync.Map{})
+}
+
 // JoinHostPort returns host:port.
 //
 // Host may be dns name, ipv4 or ipv6 address.
diff --git a/lib/regexutil/promregex.go b/lib/regexutil/promregex.go
new file mode 100644
index 000000000..96e39ec96
--- /dev/null
+++ b/lib/regexutil/promregex.go
@@ -0,0 +1,126 @@
+package regexutil
+
+import (
+	"regexp"
+	"strings"
+)
+
+// PromRegex implements an optimized string matching for Prometheus-like regex.
+//
+// The following regexs are optimized:
+//
+// - plain string such as "foobar"
+// - alternate strings such as "foo|bar|baz"
+// - prefix match such as "foo.*" or "foo.+"
+// - substring match such as ".*foo.*" or ".+bar.+"
+type PromRegex struct {
+	// prefix contains literal prefix for regex.
+	// For example, prefix="foo" for regex="foo(a|b)"
+	prefix string
+
+	// Suffix contains regex suffix left after removing the prefix.
+	// For example, suffix="a|b" for regex="foo(a|b)"
+	suffix string
+
+	// substrDotStar contains literal string for regex suffix=".*string.*"
+	substrDotStar string
+
+	// substrDotPlus contains literal string for regex suffix=".+string.+"
+	substrDotPlus string
+
+	// orValues contains or values for the suffix regex.
+	// For example, orValues contain ["foo","bar","baz"] for regex suffix="foo|bar|baz"
+	orValues []string
+
+	// reSuffix contains an anchored regexp built from suffix:
+	// "^(?:suffix)$"
+	reSuffix *regexp.Regexp
+}
+
+// NewPromRegex returns PromRegex for the given expr.
+func NewPromRegex(expr string) (*PromRegex, error) {
+	if _, err := regexp.Compile(expr); err != nil {
+		return nil, err
+	}
+	prefix, suffix := Simplify(expr)
+	orValues := GetOrValues(suffix)
+	substrDotStar := getSubstringLiteral(suffix, ".*")
+	substrDotPlus := getSubstringLiteral(suffix, ".+")
+	// It is expected that Optimize returns valid regexp in suffix, so use MustCompile here.
+	// Anchor suffix to the beginning and the end of the matching string.
+	suffixExpr := "^(?:" + suffix + ")$"
+	reSuffix := regexp.MustCompile(suffixExpr)
+	pr := &PromRegex{
+		prefix:        prefix,
+		suffix:        suffix,
+		substrDotStar: substrDotStar,
+		substrDotPlus: substrDotPlus,
+		orValues:      orValues,
+		reSuffix:      reSuffix,
+	}
+	return pr, nil
+}
+
+// HasPrefix returns true if pr contains non-empty literal prefix.
+//
+// For example, if pr is "foo(bar|baz)", then the prefix is "foo",
+// so HasPrefix() returns true.
+func (pr *PromRegex) HasPrefix() bool {
+	return len(pr.prefix) > 0
+}
+
+// MatchString retruns true if s matches pr.
+//
+// The pr is automatically anchored to the beginning and to the end
+// of the matching string with '^' and '$'.
+func (pr *PromRegex) MatchString(s string) bool {
+	if !strings.HasPrefix(s, pr.prefix) {
+		// Fast path - s has another prefix than pr.
+		return false
+	}
+	s = s[len(pr.prefix):]
+	if len(pr.orValues) > 0 {
+		// Fast path - pr contains only alternate strings such as 'foo|bar|baz'
+		for _, v := range pr.orValues {
+			if s == v {
+				return true
+			}
+		}
+		return false
+	}
+	if pr.substrDotStar != "" {
+		// Fast path - pr contains ".*someText.*"
+		return strings.Contains(s, pr.substrDotStar)
+	}
+	if pr.substrDotPlus != "" {
+		// Fast path - pr contains ".+someText.+"
+		n := strings.Index(s, pr.substrDotPlus)
+		return n > 0 && n+len(pr.substrDotPlus) < len(s)
+	}
+	switch pr.suffix {
+	case ".*":
+		// Fast path - the pr contains "prefix.*"
+		return true
+	case ".+":
+		// Fast path - the pr contains "prefix.+"
+		return len(s) > 0
+	}
+	// Fall back to slow path by matching the original regexp.
+	return pr.reSuffix.MatchString(s)
+}
+
+func getSubstringLiteral(expr, prefixSuffix string) string {
+	if !strings.HasPrefix(expr, prefixSuffix) {
+		return ""
+	}
+	expr = expr[len(prefixSuffix):]
+	if !strings.HasSuffix(expr, prefixSuffix) {
+		return ""
+	}
+	expr = expr[:len(expr)-len(prefixSuffix)]
+	prefix, suffix := Simplify(expr)
+	if suffix != "" {
+		return ""
+	}
+	return prefix
+}
diff --git a/lib/regexutil/regexutil.go b/lib/regexutil/regexutil.go
index 0589b16a6..ca218098f 100644
--- a/lib/regexutil/regexutil.go
+++ b/lib/regexutil/regexutil.go
@@ -1,27 +1,52 @@
 package regexutil
 
 import (
+	"fmt"
 	"regexp/syntax"
 	"sort"
-
-	"github.com/VictoriaMetrics/VictoriaMetrics/lib/logger"
+	"strings"
 )
 
+// RemoveStartEndAnchors removes '^' at the start of expr and '$' at the end of the expr.
+func RemoveStartEndAnchors(expr string) string {
+	for strings.HasPrefix(expr, "^") {
+		expr = expr[1:]
+	}
+	for strings.HasSuffix(expr, "$") {
+		expr = expr[:len(expr)-1]
+	}
+	return expr
+}
+
 // GetOrValues returns "or" values from the given regexp expr.
 //
-// E.g. it returns ["foo", "bar"] for "foo|bar" regexp.
-// It returns an empty list if it is impossible to extract "or" values from the regexp.
+// It ignores start and end anchors ('^') and ('$') at the start and the end of expr.
+// It returns ["foo", "bar"] for "foo|bar" regexp.
+// It returns ["foo"] for "foo" regexp.
 // It returns [""] for "" regexp.
+// It returns an empty list if it is impossible to extract "or" values from the regexp.
 func GetOrValues(expr string) []string {
-	sre, err := syntax.Parse(expr, syntax.Perl)
+	expr = RemoveStartEndAnchors(expr)
+	prefix, tailExpr := Simplify(expr)
+	if tailExpr == "" {
+		return []string{prefix}
+	}
+	sre, err := syntax.Parse(tailExpr, syntax.Perl)
 	if err != nil {
-		logger.Panicf("BUG: unexpected error when parsing verified expr=%q: %s", expr, err)
+		panic(fmt.Errorf("BUG: unexpected error when parsing verified tailExpr=%q: %w", tailExpr, err))
 	}
 	orValues := getOrValuesExt(sre)
 
 	// Sort orValues for faster index seek later
 	sort.Strings(orValues)
 
+	if len(prefix) > 0 {
+		// Add prefix to orValues
+		for i, orValue := range orValues {
+			orValues[i] = prefix + orValue
+		}
+	}
+
 	return orValues
 }
 
@@ -36,8 +61,6 @@ func getOrValuesExt(sre *syntax.Regexp) []string {
 		return []string{string(sre.Rune)}
 	case syntax.OpEmptyMatch:
 		return []string{""}
-	case syntax.OpBeginText, syntax.OpEndText:
-		return []string{""}
 	case syntax.OpAlternate:
 		a := make([]string, 0, len(sre.Sub))
 		for _, reSub := range sre.Sub {
@@ -75,6 +98,9 @@ func getOrValuesExt(sre *syntax.Regexp) []string {
 		if len(prefixes) == 0 {
 			return nil
 		}
+		if len(sre.Sub) == 1 {
+			return prefixes
+		}
 		sre.Sub = sre.Sub[1:]
 		suffixes := getOrValuesExt(sre)
 		if len(suffixes) == 0 {
@@ -105,3 +131,129 @@ func isLiteral(sre *syntax.Regexp) bool {
 }
 
 const maxOrValues = 100
+
+// Simplify simplifies the given expr.
+//
+// It returns plaintext prefix and the remaining regular expression
+// with dropped '^' and '$' anchors at the beginning and the end
+// of the regular expression.
+//
+// The function removes capturing parens from the expr,
+// so it cannot be used when capturing parens are necessary.
+func Simplify(expr string) (string, string) {
+	sre, err := syntax.Parse(expr, syntax.Perl)
+	if err != nil {
+		// Cannot parse the regexp. Return it all as prefix.
+		return expr, ""
+	}
+	sre = simplifyRegexp(sre, false)
+	if sre == emptyRegexp {
+		return "", ""
+	}
+	if isLiteral(sre) {
+		return string(sre.Rune), ""
+	}
+	var prefix string
+	if sre.Op == syntax.OpConcat {
+		sub0 := sre.Sub[0]
+		if isLiteral(sub0) {
+			prefix = string(sub0.Rune)
+			sre.Sub = sre.Sub[1:]
+			if len(sre.Sub) == 0 {
+				return prefix, ""
+			}
+			sre = simplifyRegexp(sre, true)
+		}
+	}
+	if _, err := syntax.Compile(sre); err != nil {
+		// Cannot compile the regexp. Return it all as prefix.
+		return expr, ""
+	}
+	s := sre.String()
+	s = strings.ReplaceAll(s, "(?:)", "")
+	s = strings.ReplaceAll(s, "(?-s:.)", ".")
+	s = strings.ReplaceAll(s, "(?-m:$)", "$")
+	return prefix, s
+}
+
+func simplifyRegexp(sre *syntax.Regexp, hasPrefix bool) *syntax.Regexp {
+	s := sre.String()
+	for {
+		sre = simplifyRegexpExt(sre, hasPrefix, false)
+		sre = sre.Simplify()
+		if sre.Op == syntax.OpBeginText || sre.Op == syntax.OpEndText {
+			sre = emptyRegexp
+		}
+		sNew := sre.String()
+		if sNew == s {
+			return sre
+		}
+		var err error
+		sre, err = syntax.Parse(sNew, syntax.Perl)
+		if err != nil {
+			panic(fmt.Errorf("BUG: cannot parse simplified regexp %q: %w", sNew, err))
+		}
+		s = sNew
+	}
+}
+
+func simplifyRegexpExt(sre *syntax.Regexp, hasPrefix, hasSuffix bool) *syntax.Regexp {
+	switch sre.Op {
+	case syntax.OpCapture:
+		// Substitute all the capture regexps with non-capture regexps.
+		sre.Op = syntax.OpAlternate
+		sre.Sub[0] = simplifyRegexpExt(sre.Sub[0], hasPrefix, hasSuffix)
+		if sre.Sub[0] == emptyRegexp {
+			return emptyRegexp
+		}
+		return sre
+	case syntax.OpStar, syntax.OpPlus, syntax.OpQuest, syntax.OpRepeat:
+		sre.Sub[0] = simplifyRegexpExt(sre.Sub[0], hasPrefix, hasSuffix)
+		if sre.Sub[0] == emptyRegexp {
+			return emptyRegexp
+		}
+		return sre
+	case syntax.OpAlternate:
+		// Do not remove empty captures from OpAlternate, since this may break regexp.
+		for i, sub := range sre.Sub {
+			sre.Sub[i] = simplifyRegexpExt(sub, hasPrefix, hasSuffix)
+		}
+		return sre
+	case syntax.OpConcat:
+		subs := sre.Sub[:0]
+		for i, sub := range sre.Sub {
+			sub = simplifyRegexpExt(sub, hasPrefix || len(subs) > 0, hasSuffix || i+1 < len(sre.Sub))
+			if sub != emptyRegexp {
+				subs = append(subs, sub)
+			}
+		}
+		sre.Sub = subs
+		// Remove anchros from the beginning and the end of regexp, since they
+		// will be added later.
+		if !hasPrefix {
+			for len(sre.Sub) > 0 && sre.Sub[0].Op == syntax.OpBeginText {
+				sre.Sub = sre.Sub[1:]
+			}
+		}
+		if !hasSuffix {
+			for len(sre.Sub) > 0 && sre.Sub[len(sre.Sub)-1].Op == syntax.OpEndText {
+				sre.Sub = sre.Sub[:len(sre.Sub)-1]
+			}
+		}
+		if len(sre.Sub) == 0 {
+			return emptyRegexp
+		}
+		if len(sre.Sub) == 1 {
+			return sre.Sub[0]
+		}
+		return sre
+	case syntax.OpEmptyMatch:
+		return emptyRegexp
+	default:
+		return sre
+	}
+}
+
+var emptyRegexp = &syntax.Regexp{
+	Op: syntax.OpEmptyMatch,
+}
diff --git a/lib/storage/metric_name.go b/lib/storage/metric_name.go
index caadae88a..76fee6549 100644
--- a/lib/storage/metric_name.go
+++ b/lib/storage/metric_name.go
@@ -66,8 +66,8 @@ func (tag *Tag) copyFrom(src *Tag) {
 	tag.Value = append(tag.Value[:0], src.Value...)
 }
 
-func marshalTagValueNoTrailingTagSeparator(dst, src []byte) []byte {
-	dst = marshalTagValue(dst, src)
+func marshalTagValueNoTrailingTagSeparator(dst []byte, src string) []byte {
+	dst = marshalTagValue(dst, bytesutil.ToUnsafeBytes(src))
 	// Remove trailing tagSeparatorChar
 	return dst[:len(dst)-1]
 }
diff --git a/lib/storage/tag_filters.go b/lib/storage/tag_filters.go
index 7b547ae25..99c8ee171 100644
--- a/lib/storage/tag_filters.go
+++ b/lib/storage/tag_filters.go
@@ -363,7 +363,7 @@ func (tf *tagFilter) InitFromGraphiteQuery(commonPrefix, query []byte, paths []s
 	tf.regexpPrefix = prefix
 	tf.prefix = append(tf.prefix[:0], commonPrefix...)
 	tf.prefix = marshalTagValue(tf.prefix, nil)
-	tf.prefix = marshalTagValueNoTrailingTagSeparator(tf.prefix, []byte(prefix))
+	tf.prefix = marshalTagValueNoTrailingTagSeparator(tf.prefix, prefix)
 	tf.orSuffixes = append(tf.orSuffixes[:0], orSuffixes...)
 	tf.reSuffixMatch, tf.matchCost = newMatchFuncForOrSuffixes(orSuffixes)
 }
@@ -419,15 +419,15 @@ func (tf *tagFilter) Init(commonPrefix, key, value []byte, isNegative, isRegexp
 	tf.prefix = append(tf.prefix, commonPrefix...)
 	tf.prefix = marshalTagValue(tf.prefix, key)
 
-	var expr []byte
-	prefix := tf.value
+	var expr string
+	prefix := bytesutil.ToUnsafeString(tf.value)
 	if tf.isRegexp {
-		prefix, expr = getRegexpPrefix(tf.value)
+		prefix, expr = simplifyRegexp(prefix)
 		if len(expr) == 0 {
 			tf.value = append(tf.value[:0], prefix...)
 			tf.isRegexp = false
 		} else {
-			tf.regexpPrefix = string(prefix)
+			tf.regexpPrefix = prefix
 		}
 	}
 	tf.prefix = marshalTagValueNoTrailingTagSeparator(tf.prefix, prefix)
@@ -508,22 +508,22 @@ func RegexpCacheMisses() uint64 {
 	return regexpCache.Misses()
 }
 
-func getRegexpFromCache(expr []byte) (*regexpCacheValue, error) {
-	if rcv := regexpCache.GetEntry(bytesutil.ToUnsafeString(expr)); rcv != nil {
+func getRegexpFromCache(expr string) (*regexpCacheValue, error) {
+	if rcv := regexpCache.GetEntry(expr); rcv != nil {
 		// Fast path - the regexp found in the cache.
 		return rcv.(*regexpCacheValue), nil
 	}
 	// Slow path - build the regexp.
-	exprOrig := string(expr)
+	exprOrig := expr
 
-	expr = []byte(tagCharsRegexpEscaper.Replace(exprOrig))
+	expr = tagCharsRegexpEscaper.Replace(exprOrig)
 	exprStr := fmt.Sprintf("^(%s)$", expr)
 	re, err := regexp.Compile(exprStr)
 	if err != nil {
 		return nil, fmt.Errorf("invalid regexp %q: %w", exprStr, err)
 	}
 
-	sExpr := string(expr)
+	sExpr := expr
 	orValues := regexutil.GetOrValues(sExpr)
 	var reMatch func(b []byte) bool
 	var reCost uint64
@@ -835,22 +835,28 @@ func (rcv *regexpCacheValue) SizeBytes() int {
 	return rcv.sizeBytes
 }
 
-func getRegexpPrefix(b []byte) ([]byte, []byte) {
-	// Fast path - search the prefix in the cache.
-	if ps := prefixesCache.GetEntry(bytesutil.ToUnsafeString(b)); ps != nil {
+func simplifyRegexp(expr string) (string, string) {
+	// It is safe to pass the expr constructed via bytesutil.ToUnsafeString()
+	// to GetEntry() here.
+	if ps := prefixesCache.GetEntry(expr); ps != nil {
+		// Fast path - the simplified expr is found in the cache.
 		ps := ps.(*prefixSuffix)
 		return ps.prefix, ps.suffix
 	}
 
-	// Slow path - extract the regexp prefix from b.
-	prefix, suffix := extractRegexpPrefix(b)
+	// Slow path - simplify the expr.
+
+	// Make a copy of expr before using it,
+	// since it may be constructed via bytesutil.ToUnsafeString()
+	expr = string(append([]byte{}, expr...))
+	prefix, suffix := regexutil.Simplify(expr)
 
 	// Put the prefix and the suffix to the cache.
 	ps := &prefixSuffix{
 		prefix: prefix,
 		suffix: suffix,
 	}
-	prefixesCache.PutEntry(string(b), ps)
+	prefixesCache.PutEntry(expr, ps)
 
 	return prefix, suffix
 }
@@ -897,120 +903,11 @@ func RegexpPrefixesCacheMisses() uint64 {
 }
 
 type prefixSuffix struct {
-	prefix []byte
-	suffix []byte
+	prefix string
+	suffix string
 }
 
 // SizeBytes implements lrucache.Entry interface
 func (ps *prefixSuffix) SizeBytes() int {
-	return cap(ps.prefix) + cap(ps.suffix) + int(unsafe.Sizeof(*ps))
-}
-
-func extractRegexpPrefix(b []byte) ([]byte, []byte) {
-	sre, err := syntax.Parse(string(b), syntax.Perl)
-	if err != nil {
-		// Cannot parse the regexp. Return it all as prefix.
-		return b, nil
-	}
-	sre = simplifyRegexp(sre)
-	if sre == emptyRegexp {
-		return nil, nil
-	}
-	if isLiteral(sre) {
-		return []byte(string(sre.Rune)), nil
-	}
-	var prefix []byte
-	if sre.Op == syntax.OpConcat {
-		sub0 := sre.Sub[0]
-		if isLiteral(sub0) {
-			prefix = []byte(string(sub0.Rune))
-			sre.Sub = sre.Sub[1:]
-			if len(sre.Sub) == 0 {
-				return nil, nil
-			}
-		}
-	}
-	if _, err := syntax.Compile(sre); err != nil {
-		// Cannot compile the regexp. Return it all as prefix.
-		return b, nil
-	}
-	return prefix, []byte(sre.String())
-}
-
-func simplifyRegexp(sre *syntax.Regexp) *syntax.Regexp {
-	s := sre.String()
-	for {
-		sre = simplifyRegexpExt(sre, false, false)
-		sre = sre.Simplify()
-		if sre.Op == syntax.OpBeginText || sre.Op == syntax.OpEndText {
-			sre = emptyRegexp
-		}
-		sNew := sre.String()
-		if sNew == s {
-			return sre
-		}
-		var err error
-		sre, err = syntax.Parse(sNew, syntax.Perl)
-		if err != nil {
-			logger.Panicf("BUG: cannot parse simplified regexp %q: %s", sNew, err)
-		}
-		s = sNew
-	}
-}
-
-func simplifyRegexpExt(sre *syntax.Regexp, hasPrefix, hasSuffix bool) *syntax.Regexp {
-	switch sre.Op {
-	case syntax.OpCapture:
-		// Substitute all the capture regexps with non-capture regexps.
-		sre.Op = syntax.OpAlternate
-		sre.Sub[0] = simplifyRegexpExt(sre.Sub[0], hasPrefix, hasSuffix)
-		if sre.Sub[0] == emptyRegexp {
-			return emptyRegexp
-		}
-		return sre
-	case syntax.OpStar, syntax.OpPlus, syntax.OpQuest, syntax.OpRepeat:
-		sre.Sub[0] = simplifyRegexpExt(sre.Sub[0], hasPrefix, hasSuffix)
-		if sre.Sub[0] == emptyRegexp {
-			return emptyRegexp
-		}
-		return sre
-	case syntax.OpAlternate:
-		// Do not remove empty captures from OpAlternate, since this may break regexp.
-		for i, sub := range sre.Sub {
-			sre.Sub[i] = simplifyRegexpExt(sub, hasPrefix, hasSuffix)
-		}
-		return sre
-	case syntax.OpConcat:
-		subs := sre.Sub[:0]
-		for i, sub := range sre.Sub {
-			if sub = simplifyRegexpExt(sub, i > 0, i+1 < len(sre.Sub)); sub != emptyRegexp {
-				subs = append(subs, sub)
-			}
-		}
-		sre.Sub = subs
-		// Remove anchros from the beginning and the end of regexp, since they
-		// will be added later.
-		if !hasPrefix {
-			for len(sre.Sub) > 0 && sre.Sub[0].Op == syntax.OpBeginText {
-				sre.Sub = sre.Sub[1:]
-			}
-		}
-		if !hasSuffix {
-			for len(sre.Sub) > 0 && sre.Sub[len(sre.Sub)-1].Op == syntax.OpEndText {
-				sre.Sub = sre.Sub[:len(sre.Sub)-1]
-			}
-		}
-		if len(sre.Sub) == 0 {
-			return emptyRegexp
-		}
-		return sre
-	case syntax.OpEmptyMatch:
-		return emptyRegexp
-	default:
-		return sre
-	}
-}
-
-var emptyRegexp = &syntax.Regexp{
-	Op: syntax.OpEmptyMatch,
+	return len(ps.prefix) + len(ps.suffix) + int(unsafe.Sizeof(*ps))
 }


Test patch:
diff --git a/app/vmselect/promql/exec_test.go b/app/vmselect/promql/exec_test.go
index d80b709b6..171aae0dc 100644
--- a/app/vmselect/promql/exec_test.go
+++ b/app/vmselect/promql/exec_test.go
@@ -7932,6 +7932,7 @@ func TestExecError(t *testing.T) {
 	f(`limit_offet(1, (alias(1,"foo"),alias(2,"bar")), 10)`)
 	f(`round(1, 1 or label_set(2, "xx", "foo"))`)
 	f(`histogram_quantile(1 or label_set(2, "xx", "foo"), 1)`)
+	f(`histogram_quantiles("foo", 1 or label_set(2, "xxx", "foo"), 2)`)
 	f(`label_set(1, 2, 3)`)
 	f(`label_set(1, "foo", (label_set(1, "foo", bar") or label_set(2, "xxx", "yy")))`)
 	f(`label_set(1, "foo", 3)`)
diff --git a/lib/promrelabel/config_test.go b/lib/promrelabel/config_test.go
index 7cbbf7484..18066c1e2 100644
--- a/lib/promrelabel/config_test.go
+++ b/lib/promrelabel/config_test.go
@@ -126,7 +126,7 @@ func TestParsedConfigsString(t *testing.T) {
 			TargetLabel:  "foo",
 			SourceLabels: []string{"aaa"},
 		},
-	}, "[SourceLabels=[aaa], Separator=;, TargetLabel=foo, Regex=^(.*)$, Modulus=0, Replacement=$1, Action=replace, If=, "+
+	}, "[SourceLabels=[aaa], Separator=;, TargetLabel=foo, Regex=.*, Modulus=0, Replacement=$1, Action=replace, If=, "+
 		"graphiteMatchTemplate=<nil>, graphiteLabelRules=[]], relabelDebug=false")
 	var ie IfExpression
 	if err := ie.Parse("{foo=~'bar'}"); err != nil {
@@ -141,7 +141,7 @@ func TestParsedConfigsString(t *testing.T) {
 			},
 			If: &ie,
 		},
-	}, "[SourceLabels=[], Separator=;, TargetLabel=, Regex=^(.*)$, Modulus=0, Replacement=$1, Action=graphite, If={foo=~'bar'}, "+
+	}, "[SourceLabels=[], Separator=;, TargetLabel=, Regex=.*, Modulus=0, Replacement=$1, Action=graphite, If={foo=~'bar'}, "+
 		"graphiteMatchTemplate=foo.*.bar, graphiteLabelRules=[replaceTemplate=$1-zz, targetLabel=job]], relabelDebug=false")
 	f([]RelabelConfig{
 		{
@@ -150,7 +150,7 @@ func TestParsedConfigsString(t *testing.T) {
 			TargetLabel:  "x",
 			If:           &ie,
 		},
-	}, "[SourceLabels=[foo bar], Separator=;, TargetLabel=x, Regex=^(.*)$, Modulus=0, Replacement=$1, Action=replace, If={foo=~'bar'}, "+
+	}, "[SourceLabels=[foo bar], Separator=;, TargetLabel=x, Regex=.*, Modulus=0, Replacement=$1, Action=replace, If={foo=~'bar'}, "+
 		"graphiteMatchTemplate=<nil>, graphiteLabelRules=[]], relabelDebug=false")
 }
 
@@ -174,13 +174,14 @@ func TestParseRelabelConfigsSuccess(t *testing.T) {
 	}, &ParsedConfigs{
 		prcs: []*parsedRelabelConfig{
 			{
-				SourceLabels: []string{"foo", "bar"},
-				Separator:    ";",
-				TargetLabel:  "xxx",
-				Regex:        defaultRegexForRelabelConfig,
-				Replacement:  "$1",
-				Action:       "replace",
+				SourceLabels:  []string{"foo", "bar"},
+				Separator:     ";",
+				TargetLabel:   "xxx",
+				RegexAnchored: defaultRegexForRelabelConfig,
+				Replacement:   "$1",
+				Action:        "replace",
 
+				regex:                        defaultPromRegex,
 				regexOriginal:                defaultOriginalRegexForRelabelConfig,
 				hasCaptureGroupInReplacement: true,
 			},
@@ -455,3 +456,21 @@ func TestParseRelabelConfigsFailure(t *testing.T) {
 		})
 	})
 }
+
+func TestIsDefaultRegex(t *testing.T) {
+	f := func(s string, resultExpected bool) {
+		t.Helper()
+		result := isDefaultRegex(s)
+		if result != resultExpected {
+			t.Fatalf("unexpected result for isDefaultRegex(%q); got %v; want %v", s, result, resultExpected)
+		}
+	}
+	f("", false)
+	f("foo", false)
+	f(".+", false)
+	f("a.*", false)
+	f(".*", true)
+	f("(.*)", true)
+	f("^.*$", true)
+	f("(?:.*)", true)
+}
diff --git a/lib/promrelabel/relabel_test.go b/lib/promrelabel/relabel_test.go
index 64f90bd84..ba40e5f26 100644
--- a/lib/promrelabel/relabel_test.go
+++ b/lib/promrelabel/relabel_test.go
@@ -1,6 +1,7 @@
 package promrelabel
 
 import (
+	"fmt"
 	"testing"
 
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/prompbmarshal"
@@ -727,21 +728,12 @@ func TestFillLabelReferences(t *testing.T) {
 	f(`{{bar}}-aa{{__name__}}.{{bar}}{{non-existing-label}}`, `foo{bar="baz"}`, `baz-aafoo.baz`)
 }
 
-func TestRegexpMatchStringSuccess(t *testing.T) {
+func TestRegexMatchStringSuccess(t *testing.T) {
 	f := func(pattern, s string) {
 		t.Helper()
-		rc := &RelabelConfig{
-			Action: "labeldrop",
-			Regex: &MultiLineRegex{
-				S: pattern,
-			},
-		}
-		prc, err := parseRelabelConfig(rc)
-		if err != nil {
-			t.Fatalf("unexpected error in parseRelabelConfig: %s", err)
-		}
-		if !prc.matchString(s) {
-			t.Fatalf("unexpected matchString(%q) result; got false; want true", s)
+		prc := newTestRegexRelabelConfig(pattern)
+		if !prc.regex.MatchString(s) {
+			t.Fatalf("unexpected MatchString(%q) result; got false; want true", s)
 		}
 	}
 	f("", "")
@@ -760,18 +752,9 @@ func TestRegexpMatchStringSuccess(t *testing.T) {
 func TestRegexpMatchStringFailure(t *testing.T) {
 	f := func(pattern, s string) {
 		t.Helper()
-		rc := &RelabelConfig{
-			Action: "labeldrop",
-			Regex: &MultiLineRegex{
-				S: pattern,
-			},
-		}
-		prc, err := parseRelabelConfig(rc)
-		if err != nil {
-			t.Fatalf("unexpected error in parseRelabelConfig: %s", err)
-		}
-		if prc.matchString(s) {
-			t.Fatalf("unexpected matchString(%q) result; got true; want false", s)
+		prc := newTestRegexRelabelConfig(pattern)
+		if prc.regex.MatchString(s) {
+			t.Fatalf("unexpected MatchString(%q) result; got true; want false", s)
 		}
 	}
 	f("", "foo")
@@ -784,3 +767,17 @@ func TestRegexpMatchStringFailure(t *testing.T) {
 	f("foo.+", "foo")
 	f("^foo$", "foobar")
 }
+
+func newTestRegexRelabelConfig(pattern string) *parsedRelabelConfig {
+	rc := &RelabelConfig{
+		Action: "labeldrop",
+		Regex: &MultiLineRegex{
+			S: pattern,
+		},
+	}
+	prc, err := parseRelabelConfig(rc)
+	if err != nil {
+		panic(fmt.Errorf("unexpected error in parseRelabelConfig: %s", err))
+	}
+	return prc
+}
diff --git a/lib/promrelabel/relabel_timing_test.go b/lib/promrelabel/relabel_timing_test.go
index 3bf61babd..6e7d55d19 100644
--- a/lib/promrelabel/relabel_timing_test.go
+++ b/lib/promrelabel/relabel_timing_test.go
@@ -8,56 +8,203 @@ import (
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/prompbmarshal"
 )
 
-func BenchmarkMatchRegexOrValuesMatchOptimized(b *testing.B) {
-	const pattern = "foo|bar|baz|abc"
+func BenchmarkMatchRegexPrefixDotPlusMatchOptimized(b *testing.B) {
+	const pattern = "^foo.+$"
+	const s = "foobar"
+	prc := newTestRegexRelabelConfig(pattern)
+	b.ReportAllocs()
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			if !prc.regex.MatchString(s) {
+				panic(fmt.Errorf("unexpected string mismatch for pattern=%q, s=%q", pattern, s))
+			}
+		}
+	})
+}
+
+func BenchmarkMatchRegexPrefixDotPlusMatchUnoptimized(b *testing.B) {
+	const pattern = "^foo.+$"
+	const s = "foobar"
+	re := regexp.MustCompile(pattern)
+	b.ReportAllocs()
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			if !re.MatchString(s) {
+				panic(fmt.Errorf("unexpected string mismatch for pattern=%q, s=%q", pattern, s))
+			}
+		}
+	})
+}
+
+func BenchmarkMatchRegexPrefixDotPlusMismatchOptimized(b *testing.B) {
+	const pattern = "^foo.+$"
+	const s = "xfoobar"
+	prc := newTestRegexRelabelConfig(pattern)
+	b.ReportAllocs()
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			if prc.regex.MatchString(s) {
+				panic(fmt.Errorf("unexpected string match for pattern=%q, s=%q", pattern, s))
+			}
+		}
+	})
+}
+
+func BenchmarkMatchRegexPrefixDotPlusMismatchUnoptimized(b *testing.B) {
+	const pattern = "^foo.+$"
+	const s = "xfoobar"
+	re := regexp.MustCompile(pattern)
+	b.ReportAllocs()
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			if re.MatchString(s) {
+				panic(fmt.Errorf("unexpected string match for pattern=%q, s=%q", pattern, s))
+			}
+		}
+	})
+}
+
+func BenchmarkMatchRegexPrefixDotStarMatchOptimized(b *testing.B) {
+	const pattern = "^foo.*$"
+	const s = "foobar"
+	prc := newTestRegexRelabelConfig(pattern)
+	b.ReportAllocs()
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			if !prc.regex.MatchString(s) {
+				panic(fmt.Errorf("unexpected string mismatch for pattern=%q, s=%q", pattern, s))
+			}
+		}
+	})
+}
+
+func BenchmarkMatchRegexPrefixDotStarMatchUnoptimized(b *testing.B) {
+	const pattern = "^foo.*$"
+	const s = "foobar"
+	re := regexp.MustCompile(pattern)
+	b.ReportAllocs()
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			if !re.MatchString(s) {
+				panic(fmt.Errorf("unexpected string mismatch for pattern=%q, s=%q", pattern, s))
+			}
+		}
+	})
+}
+
+func BenchmarkMatchRegexPrefixDotStarMismatchOptimized(b *testing.B) {
+	const pattern = "^foo.*$"
+	const s = "xfoobar"
+	prc := newTestRegexRelabelConfig(pattern)
+	b.ReportAllocs()
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			if prc.regex.MatchString(s) {
+				panic(fmt.Errorf("unexpected string match for pattern=%q, s=%q", pattern, s))
+			}
+		}
+	})
+}
+
+func BenchmarkMatchRegexPrefixDotStarMismatchUnoptimized(b *testing.B) {
+	const pattern = "^foo.*$"
+	const s = "xfoobar"
+	re := regexp.MustCompile(pattern)
+	b.ReportAllocs()
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			if re.MatchString(s) {
+				panic(fmt.Errorf("unexpected string match for pattern=%q, s=%q", pattern, s))
+			}
+		}
+	})
+}
+
+func BenchmarkMatchRegexSingleValueMatchOptimized(b *testing.B) {
+	const pattern = "^foo$"
 	const s = "foo"
-	rc := &RelabelConfig{
-		Action: "labeldrop",
-		Regex: &MultiLineRegex{
-			S: pattern,
-		},
-	}
-	prc, err := parseRelabelConfig(rc)
-	if err != nil {
-		panic(fmt.Errorf("unexpected error in parseRelabelConfig: %s", err))
-	}
+	prc := newTestRegexRelabelConfig(pattern)
 	b.ReportAllocs()
 	b.SetBytes(1)
 	b.RunParallel(func(pb *testing.PB) {
 		for pb.Next() {
-			if !prc.matchString(s) {
+			if !prc.regex.MatchString(s) {
 				panic(fmt.Errorf("unexpected string mismatch for pattern=%q, s=%q", pattern, s))
 			}
 		}
 	})
 }
 
-func BenchmarkMatchRegexOrValuesMismatchOptimized(b *testing.B) {
-	const pattern = "foo|bar|baz|abc"
-	const s = "qwert"
-	rc := &RelabelConfig{
-		Action: "labeldrop",
-		Regex: &MultiLineRegex{
-			S: pattern,
-		},
-	}
-	prc, err := parseRelabelConfig(rc)
-	if err != nil {
-		panic(fmt.Errorf("unexpected error in parseRelabelConfig: %s", err))
-	}
+func BenchmarkMatchRegexSingleValueMatchUnoptimized(b *testing.B) {
+	const pattern = "^foo$"
+	const s = "foo"
+	re := regexp.MustCompile(pattern)
+	b.ReportAllocs()
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			if !re.MatchString(s) {
+				panic(fmt.Errorf("unexpected string mismatch for pattern=%q, s=%q", pattern, s))
+			}
+		}
+	})
+}
+
+func BenchmarkMatchRegexSingleValueMismatchOptimized(b *testing.B) {
+	const pattern = "^foo$"
+	const s = "bar"
+	prc := newTestRegexRelabelConfig(pattern)
 	b.ReportAllocs()
 	b.SetBytes(1)
 	b.RunParallel(func(pb *testing.PB) {
 		for pb.Next() {
-			if prc.matchString(s) {
+			if prc.regex.MatchString(s) {
 				panic(fmt.Errorf("unexpected string match for pattern=%q, s=%q", pattern, s))
 			}
 		}
 	})
 }
 
+func BenchmarkMatchRegexSingleValueMismatchUnoptimized(b *testing.B) {
+	const pattern = "^foo$"
+	const s = "bar"
+	re := regexp.MustCompile(pattern)
+	b.ReportAllocs()
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			if re.MatchString(s) {
+				panic(fmt.Errorf("unexpected string match for pattern=%q, s=%q", pattern, s))
+			}
+		}
+	})
+}
+
+func BenchmarkMatchRegexOrValuesMatchOptimized(b *testing.B) {
+	const pattern = "^(foo|bar|baz|abc)$"
+	const s = "foo"
+	prc := newTestRegexRelabelConfig(pattern)
+	b.ReportAllocs()
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			if !prc.regex.MatchString(s) {
+				panic(fmt.Errorf("unexpected string mismatch for pattern=%q, s=%q", pattern, s))
+			}
+		}
+	})
+}
+
 func BenchmarkMatchRegexOrValuesMatchUnoptimized(b *testing.B) {
-	const pattern = "foo|bar|baz|abc"
+	const pattern = "^(foo|bar|baz|abc)$"
 	const s = "foo"
 	re := regexp.MustCompile(pattern)
 	b.ReportAllocs()
@@ -71,8 +218,23 @@ func BenchmarkMatchRegexOrValuesMatchUnoptimized(b *testing.B) {
 	})
 }
 
+func BenchmarkMatchRegexOrValuesMismatchOptimized(b *testing.B) {
+	const pattern = "^(foo|bar|baz|abc)"
+	const s = "qwert"
+	prc := newTestRegexRelabelConfig(pattern)
+	b.ReportAllocs()
+	b.SetBytes(1)
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			if prc.regex.MatchString(s) {
+				panic(fmt.Errorf("unexpected string match for pattern=%q, s=%q", pattern, s))
+			}
+		}
+	})
+}
+
 func BenchmarkMatchRegexOrValuesMismatchUnoptimized(b *testing.B) {
-	const pattern = "foo|bar|baz|abc"
+	const pattern = "^(foo|bar|baz|abc)$"
 	const s = "qwert"
 	re := regexp.MustCompile(pattern)
 	b.ReportAllocs()
@@ -335,7 +497,7 @@ func BenchmarkApplyRelabelConfigs(b *testing.B) {
 		pcs := mustParseRelabelConfigs(`
 - action: drop
   source_labels: [id]
-  regex: yes
+  regex: "yes"
 `)
 		labelsOrig := []prompbmarshal.Label{
 			{
@@ -422,7 +584,7 @@ func BenchmarkApplyRelabelConfigs(b *testing.B) {
 		pcs := mustParseRelabelConfigs(`
 - action: keep
   source_labels: [id]
-  regex: yes
+  regex: "yes"
 `)
 		labelsOrig := []prompbmarshal.Label{
 			{
diff --git a/lib/promscrape/config_test.go b/lib/promscrape/config_test.go
index 9455d97aa..7a728b428 100644
--- a/lib/promscrape/config_test.go
+++ b/lib/promscrape/config_test.go
@@ -17,44 +17,6 @@ import (
 	"github.com/VictoriaMetrics/VictoriaMetrics/lib/proxy"
 )
 
-func TestInternStringSerial(t *testing.T) {
-	if err := testInternString(t); err != nil {
-		t.Fatalf("unexpected error: %s", err)
-	}
-}
-
-func TestInternStringConcurrent(t *testing.T) {
-	concurrency := 5
-	resultCh := make(chan error, concurrency)
-	for i := 0; i < concurrency; i++ {
-		go func() {
-			resultCh <- testInternString(t)
-		}()
-	}
-	timer := time.NewTimer(5 * time.Second)
-	for i := 0; i < concurrency; i++ {
-		select {
-		case err := <-resultCh:
-			if err != nil {
-				t.Fatalf("unexpected error: %s", err)
-			}
-		case <-timer.C:
-			t.Fatalf("timeout")
-		}
-	}
-}
-
-func testInternString(t *testing.T) error {
-	for i := 0; i < 1000; i++ {
-		s := fmt.Sprintf("foo_%d", i)
-		s1 := internString(s)
-		if s != s1 {
-			return fmt.Errorf("unexpected string returned from internString; got %q; want %q", s1, s)
-		}
-	}
-	return nil
-}
-
 func TestMergeLabels(t *testing.T) {
 	f := func(swc *scrapeWorkConfig, target string, extraLabels, metaLabels map[string]string, resultExpected string) {
 		t.Helper()
diff --git a/lib/promscrape/discoveryutils/internstring_test.go b/lib/promscrape/discoveryutils/internstring_test.go
new file mode 100644
index 000000000..9a4b72c3b
--- /dev/null
+++ b/lib/promscrape/discoveryutils/internstring_test.go
@@ -0,0 +1,45 @@
+package discoveryutils
+
+import (
+	"fmt"
+	"testing"
+	"time"
+)
+
+func TestInternStringSerial(t *testing.T) {
+	if err := testInternString(t); err != nil {
+		t.Fatalf("unexpected error: %s", err)
+	}
+}
+
+func TestInternStringConcurrent(t *testing.T) {
+	concurrency := 5
+	resultCh := make(chan error, concurrency)
+	for i := 0; i < concurrency; i++ {
+		go func() {
+			resultCh <- testInternString(t)
+		}()
+	}
+	timer := time.NewTimer(5 * time.Second)
+	for i := 0; i < concurrency; i++ {
+		select {
+		case err := <-resultCh:
+			if err != nil {
+				t.Fatalf("unexpected error: %s", err)
+			}
+		case <-timer.C:
+			t.Fatalf("timeout")
+		}
+	}
+}
+
+func testInternString(t *testing.T) error {
+	for i := 0; i < 1000; i++ {
+		s := fmt.Sprintf("foo_%d", i)
+		s1 := InternString(s)
+		if s != s1 {
+			return fmt.Errorf("unexpected string returned from internString; got %q; want %q", s1, s)
+		}
+	}
+	return nil
+}
diff --git a/lib/promscrape/config_timing_test.go b/lib/promscrape/discoveryutils/internstring_timing_test.go
similarity index 88%
rename from lib/promscrape/config_timing_test.go
rename to lib/promscrape/discoveryutils/internstring_timing_test.go
index a4c38aef8..18877c9a9 100644
--- a/lib/promscrape/config_timing_test.go
+++ b/lib/promscrape/discoveryutils/internstring_timing_test.go
@@ -1,4 +1,4 @@
-package promscrape
+package discoveryutils
 
 import (
 	"fmt"
@@ -15,7 +15,7 @@ func BenchmarkInternString(b *testing.B) {
 	b.RunParallel(func(pb *testing.PB) {
 		for pb.Next() {
 			for _, s := range a {
-				sResult := internString(s)
+				sResult := InternString(s)
 				if sResult != s {
 					panic(fmt.Sprintf("unexpected string obtained; got %q; want %q", sResult, s))
 				}
diff --git a/lib/promscrape/discoveryutils/utils_test.go b/lib/promscrape/discoveryutils/utils_test.go
new file mode 100644
index 000000000..21bf3100a
--- /dev/null
+++ b/lib/promscrape/discoveryutils/utils_test.go
@@ -0,0 +1,56 @@
+package discoveryutils
+
+import (
+	"fmt"
+	"testing"
+	"time"
+)
+
+func TestSanitizeLabelNameSerial(t *testing.T) {
+	if err := testSanitizeLabelName(); err != nil {
+		t.Fatalf("unexpected error: %s", err)
+	}
+}
+
+func TestSanitizeLabelNameParallel(t *testing.T) {
+	goroutines := 5
+	ch := make(chan error, goroutines)
+	for i := 0; i < goroutines; i++ {
+		go func() {
+			ch <- testSanitizeLabelName()
+		}()
+	}
+	tch := time.After(5 * time.Second)
+	for i := 0; i < goroutines; i++ {
+		select {
+		case <-tch:
+			t.Fatalf("timeout!")
+		case err := <-ch:
+			if err != nil {
+				t.Fatalf("unexpected error: %s", err)
+			}
+		}
+	}
+}
+
+func testSanitizeLabelName() error {
+	f := func(name, expectedSanitizedName string) error {
+		for i := 0; i < 5; i++ {
+			sanitizedName := SanitizeLabelName(name)
+			if sanitizedName != expectedSanitizedName {
+				return fmt.Errorf("unexpected sanitized label name %q; got %q; want %q", name, sanitizedName, expectedSanitizedName)
+			}
+		}
+		return nil
+	}
+	if err := f("", ""); err != nil {
+		return err
+	}
+	if err := f("foo", "foo"); err != nil {
+		return err
+	}
+	if err := f("foo-bar/baz", "foo_bar_baz"); err != nil {
+		return err
+	}
+	return nil
+}
diff --git a/lib/promscrape/discoveryutils/utils_timing_test.go b/lib/promscrape/discoveryutils/utils_timing_test.go
new file mode 100644
index 000000000..f128cf2b7
--- /dev/null
+++ b/lib/promscrape/discoveryutils/utils_timing_test.go
@@ -0,0 +1,21 @@
+package discoveryutils
+
+import (
+	"fmt"
+	"testing"
+)
+
+func BenchmarkSanitizeLabelName(b *testing.B) {
+	labelName := "foo-bar/baz/aaaa+bbb"
+	expectedLabelNameSanitized := "foo_bar_baz_aaaa_bbb"
+	b.SetBytes(1)
+	b.ReportAllocs()
+	b.RunParallel(func(pb *testing.PB) {
+		for pb.Next() {
+			labelNameSanitized := SanitizeLabelName(labelName)
+			if labelNameSanitized != expectedLabelNameSanitized {
+				panic(fmt.Errorf("unexpected sanitized label name; got %q; want %q", labelNameSanitized, expectedLabelNameSanitized))
+			}
+		}
+	})
+}
diff --git a/lib/regexutil/promregex_test.go b/lib/regexutil/promregex_test.go
new file mode 100644
index 000000000..20a04312a
--- /dev/null
+++ b/lib/regexutil/promregex_test.go
@@ -0,0 +1,92 @@
+package regexutil
+
+import (
+	"regexp"
+	"testing"
+)
+
+func TestPromRegexParseFailure(t *testing.T) {
+	f := func(expr string) {
+		t.Helper()
+		pr, err := NewPromRegex(expr)
+		if err == nil {
+			t.Fatalf("expecting non-nil error for expr=%s", expr)
+		}
+		if pr != nil {
+			t.Fatalf("expecting nil pr for expr=%s", expr)
+		}
+	}
+	f("fo[bar")
+	f("foo(bar")
+}
+
+func TestPromRegex(t *testing.T) {
+	f := func(expr, s string, resultExpected bool) {
+		t.Helper()
+		pr, err := NewPromRegex(expr)
+		if err != nil {
+			t.Fatalf("unexpected error: %s", err)
+		}
+		result := pr.MatchString(s)
+		if result != resultExpected {
+			t.Fatalf("unexpected result when matching %s against %s; got %v; want %v", expr, s, result, resultExpected)
+		}
+
+		// Make sure the result is the same for regular regexp
+		exprAnchored := "^(?:" + expr + ")$"
+		re := regexp.MustCompile(exprAnchored)
+		result = re.MatchString(s)
+		if result != resultExpected {
+			t.Fatalf("unexpected result when matching %s against %s during sanity check; got %v; want %v", exprAnchored, s, result, resultExpected)
+		}
+	}
+	f("", "", true)
+	f("", "foo", false)
+	f("foo", "", false)
+	f(".*", "", true)
+	f(".*", "foo", true)
+	f(".+", "", false)
+	f(".+", "foo", true)
+	f("foo.*", "bar", false)
+	f("foo.*", "foo", true)
+	f("foo.*", "foobar", true)
+	f("foo.+", "bar", false)
+	f("foo.+", "foo", false)
+	f("foo.+", "foobar", true)
+	f("foo|bar", "", false)
+	f("foo|bar", "a", false)
+	f("foo|bar", "foo", true)
+	f("foo|bar", "bar", true)
+	f("foo|bar", "foobar", false)
+	f("foo(bar|baz)", "a", false)
+	f("foo(bar|baz)", "foobar", true)
+	f("foo(bar|baz)", "foobaz", true)
+	f("foo(bar|baz)", "foobaza", false)
+	f("foo(bar|baz)", "foobal", false)
+	f("^foo|b(ar)$", "foo", true)
+	f("^foo|b(ar)$", "bar", true)
+	f("^foo|b(ar)$", "ar", false)
+	f(".*foo.*", "foo", true)
+	f(".*foo.*", "afoobar", true)
+	f(".*foo.*", "abc", false)
+	f("foo.*bar.*", "foobar", true)
+	f("foo.*bar.*", "foo_bar_", true)
+	f("foo.*bar.*", "foobaz", false)
+	f(".+foo.+", "foo", false)
+	f(".+foo.+", "afoobar", true)
+	f(".+foo.+", "afoo", false)
+	f(".+foo.+", "abc", false)
+	f("foo.+bar.+", "foobar", false)
+	f("foo.+bar.+", "foo_bar_", true)
+	f("foo.+bar.+", "foobaz", false)
+	f(".+foo.*", "foo", false)
+	f(".+foo.*", "afoo", true)
+	f(".+foo.*", "afoobar", true)
+	f(".*(a|b).*", "a", true)
+	f(".*(a|b).*", "ax", true)
+	f(".*(a|b).*", "xa", true)
+	f(".*(a|b).*", "xay", true)
+	f(".*(a|b).*", "xzy", false)
+	f("^(?:true)$", "true", true)
+	f("^(?:true)$", "false", false)
+}
diff --git a/lib/regexutil/promregex_timing_test.go b/lib/regexutil/promregex_timing_test.go
new file mode 100644
index 000000000..d2705822d
--- /dev/null
+++ b/lib/regexutil/promregex_timing_test.go
@@ -0,0 +1,111 @@
+package regexutil
+
+import (
+	"fmt"
+	"regexp"
+	"testing"
+)
+
+func BenchmarkPromRegexMatchString(b *testing.B) {
+	b.Run("unpotimized-noprefix-match", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "xbar.*|baz", "xbarz", true)
+	})
+	b.Run("unpotimized-noprefix-mismatch", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "xbar.*|baz", "zfoobarz", false)
+	})
+	b.Run("unpotimized-prefix-match", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "foo(bar.*|baz)", "foobarz", true)
+	})
+	b.Run("unpotimized-prefix-mismatch", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "foo(bar.*|baz)", "zfoobarz", false)
+	})
+	b.Run("dot-star-match", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, ".*", "foo", true)
+	})
+	b.Run("dot-plus-match", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, ".+", "foo", true)
+	})
+	b.Run("dot-plus-mismatch", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, ".+", "", false)
+	})
+	b.Run("literal-match", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "foo", "foo", true)
+	})
+	b.Run("literal-mismatch", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "foo", "bar", false)
+	})
+	b.Run("prefix-dot-star-match", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "foo.*", "foobar", true)
+	})
+	b.Run("prefix-dot-star-mismatch", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "foo.*", "afoobar", false)
+	})
+	b.Run("prefix-dot-plus-match", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "foo.+", "foobar", true)
+	})
+	b.Run("prefix-dot-plus-mismatch", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "foo.+", "afoobar", false)
+	})
+	b.Run("or-values-match", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "foo|bar|baz", "baz", true)
+	})
+	b.Run("or-values-mismatch", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "foo|bar|baz", "abaz", false)
+	})
+	b.Run("prefix-or-values-match", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "x(foo|bar|baz)", "xbaz", true)
+	})
+	b.Run("prefix-or-values-mismatch", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "x(foo|bar|baz)", "abaz", false)
+	})
+	b.Run("substring-dot-star-match", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, ".*foo.*", "afoobar", true)
+	})
+	b.Run("substring-dot-star-mismatch", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, ".*foo.*", "abarbaz", false)
+	})
+	b.Run("substring-dot-plus-match", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, ".+foo.+", "afoobar", true)
+	})
+	b.Run("substring-dot-plus-mismatch", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, ".+foo.+", "abarbaz", false)
+	})
+	b.Run("prefix-substring-dot-star-match", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "a.*foo.*", "afoobar", true)
+	})
+	b.Run("prefix-substring-dot-star-mismatch", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "a.*foo.*", "abarbaz", false)
+	})
+	b.Run("prefix-substring-dot-plus-match", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "a.+foo.+", "abfoobar", true)
+	})
+	b.Run("prefix-substring-dot-plus-mismatch", func(b *testing.B) {
+		benchmarkPromRegexMatchString(b, "a.+foo.+", "abarbaz", false)
+	})
+}
+
+func benchmarkPromRegexMatchString(b *testing.B, expr, s string, resultExpected bool) {
+	pr, err := NewPromRegex(expr)
+	if err != nil {
+		panic(fmt.Errorf("unexpected error: %s", err))
+	}
+	re := regexp.MustCompile("^(?:" + expr + ")$")
+	f := func(b *testing.B, matchString func(s string) bool) {
+		b.SetBytes(1)
+		b.ReportAllocs()
+		b.RunParallel(func(pb *testing.PB) {
+			for pb.Next() {
+				result := matchString(s)
+				if result != resultExpected {
+					panic(fmt.Errorf("unexpected result when matching %s against %s; got %v; want %v", s, expr, result, resultExpected))
+				}
+			}
+		})
+	}
+	b.Run("PromRegex", func(b *testing.B) {
+		f(b, pr.MatchString)
+	})
+	b.Run("StandardRegex", func(b *testing.B) {
+		f(b, re.MatchString)
+	})
+}
diff --git a/lib/regexutil/regexutil_test.go b/lib/regexutil/regexutil_test.go
index 99a91acb3..8755ccc7f 100644
--- a/lib/regexutil/regexutil_test.go
+++ b/lib/regexutil/regexutil_test.go
@@ -23,6 +23,7 @@ func TestGetOrValues(t *testing.T) {
 	f("foo.*", nil)
 	f(".*", nil)
 	f("foo|.*", nil)
+	f("(fo((o)))|(bar)", []string{"bar", "foo"})
 	f("foobar", []string{"foobar"})
 	f("z|x|c", []string{"c", "x", "z"})
 	f("foo|bar", []string{"bar", "foo"})
@@ -41,8 +42,71 @@ func TestGetOrValues(t *testing.T) {
 	f("^foo|bar$", []string{"bar", "foo"})
 	f("^(foo|bar)$", []string{"bar", "foo"})
 	f("^a(foo|b(?:a|r))$", []string{"aba", "abr", "afoo"})
-	// This is incorrect conversion, because the regexp matches nothing.
-	// It is OK for now, since such regexps are uncommon in practice.
-	// TODO: properly handle this case.
-	f("^a(^foo|bar$)z$", []string{"abarz", "afooz"})
+	f("^a(foo$|b(?:a$|r))$", []string{"aba", "abr", "afoo"})
+	f("^a(^foo|bar$)z$", nil)
+}
+
+func TestSimplify(t *testing.T) {
+	f := func(s, expectedPrefix, expectedSuffix string) {
+		t.Helper()
+		prefix, suffix := Simplify(s)
+		if prefix != expectedPrefix {
+			t.Fatalf("unexpected prefix for s=%q; got %q; want %q", s, prefix, expectedPrefix)
+		}
+		if suffix != expectedSuffix {
+			t.Fatalf("unexpected suffix for s=%q; got %q; want %q", s, suffix, expectedSuffix)
+		}
+	}
+
+	f("", "", "")
+	f("^", "", "")
+	f("$", "", "")
+	f("^()$", "", "")
+	f("^(?:)$", "", "")
+	f("^foo|^bar$|baz", "", "foo|ba[rz]")
+	f("^(foo$|^bar)$", "", "foo|bar")
+	f("^a(foo$|bar)$", "a", "foo|bar")
+	f("^a(^foo|bar$)z$", "a", "(?:\\Afoo|bar$)z")
+	f("foobar", "foobar", "")
+	f("foo$|^foobar", "foo", "|bar")
+	f("^(foo$|^foobar)$", "foo", "|bar")
+	f("foobar|foobaz", "fooba", "[rz]")
+	f("(fo|(zar|bazz)|x)", "", "fo|zar|bazz|x")
+	f("(тестЧЧ|тест)", "тест", "ЧЧ|")
+	f("foo(bar|baz|bana)", "fooba", "[rz]|na")
+	f("^foobar|foobaz", "fooba", "[rz]")
+	f("^foobar|^foobaz$", "fooba", "[rz]")
+	f("foobar|foobaz", "fooba", "[rz]")
+	f("(?:^foobar|^foobaz)aa.*", "fooba", "[rz]aa.*")
+	f("foo[bar]+", "foo", "[a-br]+")
+	f("foo[a-z]+", "foo", "[a-z]+")
+	f("foo[bar]*", "foo", "[a-br]*")
+	f("foo[a-z]*", "foo", "[a-z]*")
+	f("foo[x]+", "foo", "x+")
+	f("foo[^x]+", "foo", "[^x]+")
+	f("foo[x]*", "foo", "x*")
+	f("foo[^x]*", "foo", "[^x]*")
+	f("foo[x]*bar", "foo", "x*bar")
+	f("fo\\Bo[x]*bar?", "fo", "\\Box*bar?")
+	f("foo.+bar", "foo", ".+bar")
+	f("a(b|c.*).+", "a", "(?:b|c.*).+")
+	f("ab|ac", "a", "[b-c]")
+	f("(?i)xyz", "", "(?i:XYZ)")
+	f("(?i)foo|bar", "", "(?i:FOO)|(?i:BAR)")
+	f("(?i)up.+x", "", "(?i:UP).+(?i:X)")
+	f("(?smi)xy.*z$", "", "(?i:XY)(?s:.)*(?i:Z)(?m:$)")
+
+	// test invalid regexps
+	f("a(", "a(", "")
+	f("a[", "a[", "")
+	f("a[]", "a[]", "")
+	f("a{", "a{", "")
+	f("a{}", "a{}", "")
+	f("invalid(regexp", "invalid(regexp", "")
+
+	// The transformed regexp mustn't match aba
+	f("a?(^ba|c)", "", "a?(?:\\Aba|c)")
+
+	// The transformed regexp mustn't match barx
+	f("(foo|bar$)x*", "", "(?:foo|bar$)x*")
 }
diff --git a/lib/storage/tag_filters_test.go b/lib/storage/tag_filters_test.go
index b9fedec63..fbc3e6f71 100644
--- a/lib/storage/tag_filters_test.go
+++ b/lib/storage/tag_filters_test.go
@@ -675,26 +675,11 @@ func TestGetCommonPrefix(t *testing.T) {
 	f([]string{"foo1", "foo2", "foo34"}, "foo")
 }
 
-func TestExtractRegexpPrefix(t *testing.T) {
-	f := func(s string, expectedPrefix, expectedSuffix string) {
-		t.Helper()
-		prefix, suffix := extractRegexpPrefix([]byte(s))
-		if string(prefix) != expectedPrefix {
-			t.Fatalf("unexpected prefix for %q; got %q; want %q", s, prefix, expectedPrefix)
-		}
-		if string(suffix) != expectedSuffix {
-			t.Fatalf("unexpected suffix for %q; got %q; want %q", s, suffix, expectedSuffix)
-		}
-	}
-	f("", "", "")
-	f("foobar", "foobar", "")
-}
-
 func TestGetRegexpFromCache(t *testing.T) {
 	f := func(s string, orValuesExpected, expectedMatches, expectedMismatches []string, suffixExpected string) {
 		t.Helper()
 		for i := 0; i < 3; i++ {
-			rcv, err := getRegexpFromCache([]byte(s))
+			rcv, err := getRegexpFromCache(s)
 			if err != nil {
 				t.Fatalf("unexpected error for s=%q: %s", s, err)
 			}
@@ -764,7 +749,7 @@ func TestTagFilterMatchSuffix(t *testing.T) {
 	var tf tagFilter
 
 	tvNoTrailingTagSeparator := func(s string) string {
-		return string(marshalTagValueNoTrailingTagSeparator(nil, []byte(s)))
+		return string(marshalTagValueNoTrailingTagSeparator(nil, s))
 	}
 	init := func(value string, isNegative, isRegexp bool, expectedPrefix string) {
 		t.Helper()
@@ -1145,75 +1130,75 @@ func TestTagFilterMatchSuffix(t *testing.T) {
 	})
 }
 
-func TestGetRegexpPrefix(t *testing.T) {
-	f := func(t *testing.T, s, expectedPrefix, expectedSuffix string) {
+func TestSimplifyRegexp(t *testing.T) {
+	f := func(s, expectedPrefix, expectedSuffix string) {
 		t.Helper()
 
-		prefix, suffix := getRegexpPrefix([]byte(s))
-		if string(prefix) != expectedPrefix {
+		prefix, suffix := simplifyRegexp(s)
+		if prefix != expectedPrefix {
 			t.Fatalf("unexpected prefix for s=%q; got %q; want %q", s, prefix, expectedPrefix)
 		}
-		if string(suffix) != expectedSuffix {
+		if suffix != expectedSuffix {
 			t.Fatalf("unexpected suffix for s=%q; got %q; want %q", s, suffix, expectedSuffix)
 		}
 
 		// Get the prefix from cache.
-		prefix, suffix = getRegexpPrefix([]byte(s))
-		if string(prefix) != expectedPrefix {
+		prefix, suffix = simplifyRegexp(s)
+		if prefix != expectedPrefix {
 			t.Fatalf("unexpected prefix for s=%q; got %q; want %q", s, prefix, expectedPrefix)
 		}
-		if string(suffix) != expectedSuffix {
+		if suffix != expectedSuffix {
 			t.Fatalf("unexpected suffix for s=%q; got %q; want %q", s, suffix, expectedSuffix)
 		}
 	}
 
-	f(t, "", "", "")
-	f(t, "^", "", "")
-	f(t, "$", "", "")
-	f(t, "^()$", "", "")
-	f(t, "^(?:)$", "", "")
-	f(t, "foobar", "foobar", "")
-	f(t, "foo$|^foobar", "foo", "(?:(?:)|bar)")
-	f(t, "^(foo$|^foobar)$", "foo", "(?:(?:)|bar)")
-	f(t, "foobar|foobaz", "fooba", "[rz]")
-	f(t, "(fo|(zar|bazz)|x)", "", "fo|zar|bazz|x")
-	f(t, "(тестЧЧ|тест)", "тест", "(?:ЧЧ|(?:))")
-	f(t, "foo(bar|baz|bana)", "fooba", "(?:[rz]|na)")
-	f(t, "^foobar|foobaz", "fooba", "[rz]")
-	f(t, "^foobar|^foobaz$", "fooba", "[rz]")
-	f(t, "foobar|foobaz", "fooba", "[rz]")
-	f(t, "(?:^foobar|^foobaz)aa.*", "fooba", "[rz]aa(?-s:.)*")
-	f(t, "foo[bar]+", "foo", "[a-br]+")
-	f(t, "foo[a-z]+", "foo", "[a-z]+")
-	f(t, "foo[bar]*", "foo", "[a-br]*")
-	f(t, "foo[a-z]*", "foo", "[a-z]*")
-	f(t, "foo[x]+", "foo", "x+")
-	f(t, "foo[^x]+", "foo", "[^x]+")
-	f(t, "foo[x]*", "foo", "x*")
-	f(t, "foo[^x]*", "foo", "[^x]*")
-	f(t, "foo[x]*bar", "foo", "x*bar")
-	f(t, "fo\\Bo[x]*bar?", "fo", "\\Box*bar?")
-	f(t, "foo.+bar", "foo", "(?-s:.)+bar")
-	f(t, "a(b|c.*).+", "a", "(?:b|c(?-s:.)*)(?-s:.)+")
-	f(t, "ab|ac", "a", "[b-c]")
-	f(t, "(?i)xyz", "", "(?i:XYZ)")
-	f(t, "(?i)foo|bar", "", "(?i:FOO)|(?i:BAR)")
-	f(t, "(?i)up.+x", "", "(?i:UP)(?-s:.)+(?i:X)")
-	f(t, "(?smi)xy.*z$", "", "(?i:XY)(?s:.)*(?i:Z)(?m:$)")
+	f("", "", "")
+	f("^", "", "")
+	f("$", "", "")
+	f("^()$", "", "")
+	f("^(?:)$", "", "")
+	f("foobar", "foobar", "")
+	f("foo$|^foobar", "foo", "|bar")
+	f("^(foo$|^foobar)$", "foo", "|bar")
+	f("foobar|foobaz", "fooba", "[rz]")
+	f("(fo|(zar|bazz)|x)", "", "fo|zar|bazz|x")
+	f("(тестЧЧ|тест)", "тест", "ЧЧ|")
+	f("foo(bar|baz|bana)", "fooba", "[rz]|na")
+	f("^foobar|foobaz", "fooba", "[rz]")
+	f("^foobar|^foobaz$", "fooba", "[rz]")
+	f("foobar|foobaz", "fooba", "[rz]")
+	f("(?:^foobar|^foobaz)aa.*", "fooba", "[rz]aa.*")
+	f("foo[bar]+", "foo", "[a-br]+")
+	f("foo[a-z]+", "foo", "[a-z]+")
+	f("foo[bar]*", "foo", "[a-br]*")
+	f("foo[a-z]*", "foo", "[a-z]*")
+	f("foo[x]+", "foo", "x+")
+	f("foo[^x]+", "foo", "[^x]+")
+	f("foo[x]*", "foo", "x*")
+	f("foo[^x]*", "foo", "[^x]*")
+	f("foo[x]*bar", "foo", "x*bar")
+	f("fo\\Bo[x]*bar?", "fo", "\\Box*bar?")
+	f("foo.+bar", "foo", ".+bar")
+	f("a(b|c.*).+", "a", "(?:b|c.*).+")
+	f("ab|ac", "a", "[b-c]")
+	f("(?i)xyz", "", "(?i:XYZ)")
+	f("(?i)foo|bar", "", "(?i:FOO)|(?i:BAR)")
+	f("(?i)up.+x", "", "(?i:UP).+(?i:X)")
+	f("(?smi)xy.*z$", "", "(?i:XY)(?s:.)*(?i:Z)(?m:$)")
 
 	// test invalid regexps
-	f(t, "a(", "a(", "")
-	f(t, "a[", "a[", "")
-	f(t, "a[]", "a[]", "")
-	f(t, "a{", "a{", "")
-	f(t, "a{}", "a{}", "")
-	f(t, "invalid(regexp", "invalid(regexp", "")
+	f("a(", "a(", "")
+	f("a[", "a[", "")
+	f("a[]", "a[]", "")
+	f("a{", "a{", "")
+	f("a{}", "a{}", "")
+	f("invalid(regexp", "invalid(regexp", "")
 
 	// The transformed regexp mustn't match aba
-	f(t, "a?(^ba|c)", "", "a?(?:\\Aba|c)")
+	f("a?(^ba|c)", "", "a?(?:\\Aba|c)")
 
 	// The transformed regexp mustn't match barx
-	f(t, "(foo|bar$)x*", "", "(?:foo|bar(?-m:$))x*")
+	f("(foo|bar$)x*", "", "(?:foo|bar$)x*")
 }
 
 func TestTagFiltersString(t *testing.T) {
diff --git a/lib/storage/tag_filters_timing_test.go b/lib/storage/tag_filters_timing_test.go
index af119fbbe..3789560fe 100644
--- a/lib/storage/tag_filters_timing_test.go
+++ b/lib/storage/tag_filters_timing_test.go
@@ -32,6 +32,29 @@ func BenchmarkTagFilterMatchSuffix(b *testing.B) {
 			}
 		})
 	})
+	b.Run("regexp-any-suffix-match-anchored", func(b *testing.B) {
+		key := []byte("^foo.*$")
+		isNegative := false
+		isRegexp := true
+		suffix := marshalTagValue(nil, []byte("ojksdfds"))
+		b.ReportAllocs()
+		b.SetBytes(int64(1))
+		b.RunParallel(func(pb *testing.PB) {
+			var tf tagFilter
+			if err := tf.Init(nil, nil, key, isNegative, isRegexp); err != nil {
+				logger.Panicf("BUG: unexpected error: %s", err)
+			}
+			for pb.Next() {
+				ok, err := tf.matchSuffix(suffix)
+				if err != nil {
+					logger.Panicf("BUG: unexpected error: %s", err)
+				}
+				if !ok {
+					logger.Panicf("BUG: unexpected suffix mismatch")
+				}
+			}
+		})
+	})
 	b.Run("regexp-any-nonzero-suffix-match", func(b *testing.B) {
 		key := []byte("foo.+")
 		isNegative := false
@@ -55,6 +78,29 @@ func BenchmarkTagFilterMatchSuffix(b *testing.B) {
 			}
 		})
 	})
+	b.Run("regexp-any-nonzero-suffix-match-anchored", func(b *testing.B) {
+		key := []byte("^foo.+$")
+		isNegative := false
+		isRegexp := true
+		suffix := marshalTagValue(nil, []byte("ojksdfds"))
+		b.ReportAllocs()
+		b.SetBytes(int64(1))
+		b.RunParallel(func(pb *testing.PB) {
+			var tf tagFilter
+			if err := tf.Init(nil, nil, key, isNegative, isRegexp); err != nil {
+				logger.Panicf("BUG: unexpected error: %s", err)
+			}
+			for pb.Next() {
+				ok, err := tf.matchSuffix(suffix)
+				if err != nil {
+					logger.Panicf("BUG: unexpected error: %s", err)
+				}
+				if !ok {
+					logger.Panicf("BUG: unexpected suffix mismatch")
+				}
+			}
+		})
+	})
 	b.Run("regexp-any-nonzero-suffix-mismatch", func(b *testing.B) {
 		key := []byte("foo.+")
 		isNegative := false