Expensive Regex

A panel evaluates path=~"/api/.*". The metric has three million series. The index has to walk every label-value pair in the metric for every step of the query to test the regex. Three thousand series match. The other two million nine hundred and ninety-seven thousand are evaluated and discarded. The panel takes nine seconds.

The same panel with path=~"/api/v2/checkout" evaluates against the index, finds the literal prefix, and short-circuits to the suffix match. Two hundred series match. The evaluation takes ninety milliseconds.

The query was the same. The matcher was the same. The metric was the same. The regex was the difference.

This lesson is about the slow-query shape that lives in the index, where the matcher is a regex rather than an equality. The fix is to anchor the regex, to prefer equality where possible, and to move the matcher out of the query entirely when it does not change.

What an expensive regex is

A regex matcher is a label matcher that uses the =~ (regex match) or !~ (negative regex match) operator in PromQL. The equivalent in LogQL is the |~ filter for log lines and the label matcher for stream selectors. The engine evaluates the regex against every candidate label value in the index.

  cost  =  candidates_scanned  x  regex_complexity  x  steps_in_range

       =  candidate_set      x  backtrack_count   x  range_steps

The cost is paid in three places:

• Candidate set. The number of series whose label values must be tested. The engine cannot prune a regex match by hash; it must test every candidate.
• Regex complexity. The number of operations the regex engine performs per candidate. A regex that requires backtracking is more expensive than a literal scan.
• Steps in range. For a range query, the cost is paid per step.

The classic shape of an expensive regex is the unanchored match: path=~"/api/.*". The .* matches every suffix; the engine has no way to short-circuit. The same match with an anchor, path=~"^/api/.*$", costs the same at the candidate test but provides the engine with hint about where to start the scan.

Why a sysadmin cares

A regex matcher on a high-cardinality metric is the slow-query shape most likely to be introduced by a copy-paste of someone else’s dashboard. The expression looks reasonable. The metric looks reasonable. The matcher is the difference between a panel that loads in tens of milliseconds and a panel that times out.

The cost is paid by the index for every step of the query. The engine does not have an index on the contents of a label value; it has an inverted index of (label_name, label_value) -> posting_list. A regex match is a sequential scan of the posting list, evaluating the regex against each value.

How to detect a regex-heavy query

The same engine metrics apply, with a focus on the index phase.

# READ-ONLY. Top ten queries by evaluation cost over the last
# five minutes. Annotate each one with whether it contains a
# regex matcher.
promql='topk(10, sum by (query) (rate(prometheus_engine_query_duration_seconds_sum[5m])))'
curl -s --data-urlencode "query=${promql}" http://prometheus:9090/api/v1/query \
  | jq '.data.result[] | {query: .metric.query, has_regex: (.metric.query | test("=~"))}'

{
  "query": "sum by (status) (rate(http_requests_total{path=~\"/api/.*\"}[5m]))",
  "has_regex": true
}

A regex match is visible in the query text. The engine logs the query text alongside the evaluation duration. A query that contains =~ and ranks in the top five by evaluation cost is a regex-heavy candidate.

# READ-ONLY. Confirm the candidate set for the matcher.
# PromQL does not expose the index directly, but the series
# count for the metric is the upper bound on the cost.
curl -s --data-urlencode 'query=count(http_requests_total{path=~"/api/.*"})' \
  http://prometheus:9090/api/v1/query

{ "data": { "result": [{ "metric": {}, "value": [1735000000.000, "3120" }] } }

Three thousand one hundred and twenty series match. The upper bound on the cost is three thousand one hundred and twenty regex evaluations per step. For a range query with 1 000 steps, that is 3.1 million regex evaluations.

How to fix it

Four options, in increasing order of cost.

Option 1. Anchor the regex. The cheapest fix. The author intended path=~"/api/.*" to mean “starts with /api”. The anchored version is path=~"^/api.*".

# Before: the engine tests every label value.
sum by (status) (rate(http_requests_total{path=~"/api/.*"}[5m]))

# After: the engine can short-circuit on the literal "/api".
sum by (status) (rate(http_requests_total{path=~"^/api.*"}[5m]))

The anchored version is roughly twice as fast on a typical metric. The saving is from the literal fast-path.

Option 2. Use equality for known values. When the path is known to be one of a fixed set, prefer equality with OR.

# Before: regex against three values.
sum by (status) (rate(http_requests_total{path=~"/api/v2/checkout|/api/v2/cart|/api/v2/pay"}[5m]))

# After: equality on three values, served from the index.
sum by (status) (rate(http_requests_total{path=~"/api/v2/checkout"}))
+ sum by (status) (rate(http_requests_total{path=~"/api/v2/cart"}))
+ sum by (status) (rate(http_requests_total{path=~"/api/v2/pay"}))

Equality matchers are served from the index directly. The three matchers each hit the posting list for their label value. The total cost is three lookups. The regex version walks the full posting list for the metric and tests each candidate.

Option 3. Bound the cardinality at relabel-config. When the matcher is stable and the high-cardinality component can be stripped, drop the part that explodes cardinality before it lands in the TSDB.

# /etc/prometheus/prometheus.yml -- relevant fragment.
scrape_configs:
  - job_name: 'api'
    static_configs:
      - targets: ['api:8080']
    metric_relabel_configs:
      # Replace the high-cardinality path with a low-cardinality
      # prefix. The path that matters for dashboards is the
      # route prefix; the per-request path is for logs.
      - source_labels: [path]
        regex: '(/api/v[0-9]+/[^/]+)/.*'
        action: replace
        target_label: route
        replacement: '$1'

The route label has bounded cardinality (the number of routes the API exposes, typically under one hundred). The path label can stay or be dropped, depending on what the exporter consumer needs.

Option 4. Move the matcher to a recording rule. When the panel must cover a wide window and the matcher is stable, pre-aggregate the result into a rule. The rule evaluates the matcher once per interval; the panel reads the rule output.

# /etc/prometheus/rules/api.yml
groups:
  - name: api.routing
    interval: 30s
    rules:
      - record: api:http_requests:rate5m_by_route
        expr: |
          sum by (route, status) (
            rate(http_requests_total[5m])
          )

# Panel expression reads from the rule.
sum by (status) (rate(api:http_requests:rate5m_by_route[5m]))

The rule pre-aggregates by route, the bounded label. The panel reads from the rule. The matcher no longer runs in the panel at all.

How to validate it

Validation is two steps.

Step 1. Confirm the cost is reduced.

# READ-ONLY. Re-query the same topk metric after the change.
# The regex-heavy query should drop out of the top ten.
promql='topk(10, sum by (query) (rate(prometheus_engine_query_duration_seconds_sum[5m])))'
curl -s --data-urlencode "query=${promql}" http://prometheus:9090/api/v1/query \
  | jq '.data.result[] | .metric.query'

"sum by (status) (rate(http_requests_total{status=~\"5..\"}[5m]))"
"sum by (service) (rate(http_requests_total[5m]))"

The original regex-heavy query no longer appears. A second query that contains a regex on status (a low-cardinality label) remains. The fix has landed for the offender.

Step 2. Confirm the result is correct.

# READ-ONLY. Compare the result of the original expression
# to the result of the rewritten expression at the same
# instant.
expr_before='sum by (status) (rate(http_requests_total{path=~"^/api.*"}[5m]))'
expr_after='sum by (status) (rate(api:http_requests:rate5m_by_route{route=~"^/api"}[5m]))'

curl -s --data-urlencode "query=${expr_before}" http://prometheus:9090/api/v1/query \
  | jq '.data.result' > /tmp/before.json
curl -s --data-urlencode "query=${expr_after}" http://prometheus:9090/api/v1/query \
  | jq '.data.result' > /tmp/after.json

diff /tmp/before.json /tmp/after.json && echo "match" || echo "drift"

A drift indicates that the rewrite has changed the meaning of the query. The most common cause is a label that the original regex matched but the rewrite did not, or a label that the original regex excluded but the rewrite included. Investigate before declaring the fix correct.

How it can fail

Five failure shapes that account for most regex-heavy incidents in production.

1. Anchoring missing on a prefix match. The author wrote path=~"/api/.*" meaning “starts with /api”. The engine reads “matches anywhere”. The two are different queries.
2. Cardinality label hidden inside the regex. The author wrote path=~"/api/.*/.*" meaning “matches /api with two segments”. The .* consumes everything including the unbounded path tail. The candidate set explodes.
3. Regex on a label that is already equality-matchable. The label has eight values. The author wrote env=~".+". The matcher should have been env=~"prod" or a fixed set. The index has to test every label value to confirm what env=~".+" already implies.
4. Recording rule that does not aggregate the matcher. The rule does sum by (status)(...) and the panel does sum by (status)(rate(...{path=~"^/api.*"})). The panel re-runs the matcher.
5. LogQL line filter that is a regex when an equality filter would do. LogQL’s |~ for log lines is the equivalent of an unanchored regex. The literal substring filter | "ERROR" is served from the log stream index where possible.

How to troubleshoot it

The diagnostic order for a regex-heavy report is:

1. Find the offender. topk(5, sum by (query) (rate(prometheus_engine_query_duration_seconds_sum[5m]))). Note the queries that contain =~.
2. Count the candidates. For each offending query, run the count expression with the matcher applied. A matcher whose candidate count equals the metric cardinality is the worst case.
3. Apply the cheapest fix first. Anchor, then equality, then relabel, then rule. Each step should be validated before the next.
4. Audit other queries. If one query is regex-heavy on a metric, other queries against the same metric probably are. The fix should be uniform.

Security implications

A regex matcher does not, on its own, expose new attack surface. It exposes the cost of every other query that runs concurrently. The mitigation is the same as for any slow query: bind the query endpoint to the internal network, cap per-tenant concurrency, and alert on query rate by query text.

A regex that matches arbitrary user input is also a regex that may be slow on adversarial input. The Prometheus engine uses RE2, which is linear-time and resistant to catastrophic backtracking; LogQL’s regex engine uses RE2 as well. The risk is in candidate-set size, not in backtracking.

Performance implications

• CPU. Per-step regex evaluation across the full candidate set. For a range query, the cost is paid per step.
• Memory. No additional memory beyond the index.
• Disk. No additional disk.

Production guidance

• Prefer equality over regex for any matcher with a fixed set of values.
• Anchor every regex. ^ and $ cost nothing at runtime.
• Move stable matchers into relabel-config. The matcher becomes a property of the metric, not a per-query cost.
• Audit panels for =~ against metrics whose cardinality is above one million. The matcher is the candidate set.
• For Loki, use |= and != for substring filters and |~ only for patterns that cannot be expressed as substrings.

Verification

You should now be able to answer:

• Why does path=~"/api/.*" cost more than path=~"^/api.*"?
• When should a matcher be moved into relabel-config rather than the query?
• How do you validate that a regex rewrite has not changed the meaning of the query?
• What is the right LogQL filter for a literal substring?

Quiz