Cost-Based Throttling for Expensive PostGIS Queries

← Back to Rate Limiting Geofence & Tile Endpoints

Count tokens, not requests: price each spatial call by its bounding-box area or radius, deduct that from a per-client budget, and reject when the budget runs dry.

# Context & when to use

A flat request-per-second limit assumes every request costs the same. Spatial requests violate that assumption by orders of magnitude. On one geofence route, an ST_DWithin with a 10 m radius touches a handful of index entries and returns in a millisecond; the same route with a 300 km radius scans a huge candidate set and holds a pooled connection for seconds. A limit set for the cheap case waves the expensive case straight through to your database; a limit set for the expensive case needlessly throttles honest cheap traffic.

Cost-based throttling resolves the tension by charging a request in proportion to how much work it will demand. Each client gets a token budget that refills at a steady rate. A cheap point lookup withdraws one token; a large-radius or low-zoom-tile request withdraws many. A client can fire hundreds of cheap requests a second or a few heavy ones — either way it consumes its fair share of a finite database, and no single request class can monopolise the pool. Use this when your routes have a wide cost spread and a flat sliding-window limit either over-throttles or under-protects. For routes where every request is roughly equal, the simpler sliding window is enough; the two compose well, and the parent rate limiting geofence and tile endpoints guide covers when to reach for each.

The cost estimate must be cheap and derived from the request itself — the bounding box, the radius, the requested feature limit — computed before the query runs. Deriving the cost from a bbox is the same geometry you already parse for bounding-box spatial index queries, so it adds no meaningful overhead.

# Cost model and token flow

# Runnable implementation

Two pieces: a pure-Python cost estimator that turns request parameters into a token count, and an atomic Redis token bucket that refills and deducts in one Lua script.

# app/cost_throttle.py
import math
import time
from dataclasses import dataclass
from redis.asyncio import Redis

# ---- 1. Cost estimation -------------------------------------------------
# Turn request geometry into a token cost. Keep it cheap and monotonic:
# bigger area / radius / feature count => strictly more tokens.

BASE_COST = 1.0          # every request costs at least this
AREA_WEIGHT = 40.0       # tokens per square degree of bbox
RADIUS_WEIGHT = 0.05     # tokens per km of ST_DWithin radius
FEATURE_WEIGHT = 0.002   # tokens per requested feature
COST_MAX = 60.0          # hard ceiling: one request can never cost more than this


def estimate_bbox_cost(minx: float, miny: float, maxx: float, maxy: float) -> float:
    # Area in square degrees is a coarse but effective proxy for how many
    # candidate rows a GiST index scan must consider. See the bounding-box
    # queries guide for how this same envelope drives the actual query.
    area = abs((maxx - minx) * (maxy - miny))
    return min(COST_MAX, BASE_COST + area * AREA_WEIGHT)


def estimate_radius_cost(radius_m: float) -> float:
    # ST_DWithin cost grows with the searched area (~ radius squared), but a
    # linear-in-km charge is a defensible, cheap approximation that still
    # punishes large radii hard once clamped.
    radius_km = radius_m / 1000.0
    return min(COST_MAX, BASE_COST + radius_km * RADIUS_WEIGHT)


# ---- 2. Atomic token bucket --------------------------------------------
# KEYS[1] = bucket key
# ARGV: now_ms, refill_per_sec, capacity, cost
# Returns {allowed(1|0), tokens_left_or_retry_ms}
TOKEN_BUCKET_LUA = """
local key    = KEYS[1]
local now    = tonumber(ARGV[1])
local rate   = tonumber(ARGV[2])          -- tokens per second
local cap    = tonumber(ARGV[3])
local cost   = tonumber(ARGV[4])

local data = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(data[1])
local ts     = tonumber(data[2])
if tokens == nil then tokens = cap; ts = now end

-- Refill by elapsed time, capped at capacity.
local elapsed = math.max(0, now - ts) / 1000.0
tokens = math.min(cap, tokens + elapsed * rate)

if tokens >= cost then
    tokens = tokens - cost
    redis.call('HMSET', key, 'tokens', tokens, 'ts', now)
    redis.call('PEXPIRE', key, math.ceil(cap / rate * 1000))
    return {1, tokens}
end

-- Not enough: how long until the shortfall refills?
local deficit = cost - tokens
local retry_ms = math.ceil(deficit / rate * 1000)
redis.call('HMSET', key, 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', key, math.ceil(cap / rate * 1000))
return {0, retry_ms}
"""


@dataclass
class Verdict:
    allowed: bool
    tokens_left: float
    retry_after: int


class CostThrottle:
    def __init__(self, redis: Redis, refill_per_sec: float, capacity: float, prefix: str = "cb"):
        self.redis = redis
        self.rate = refill_per_sec
        self.capacity = capacity
        self.prefix = prefix
        self._sha: str | None = None

    async def _load(self) -> str:
        if self._sha is None:
            self._sha = await self.redis.script_load(TOKEN_BUCKET_LUA)
        return self._sha

    async def spend(self, identity: str, cost: float) -> Verdict:
        key = f"{self.prefix}:{identity}"
        now_ms = int(time.time() * 1000)
        sha = await self._load()
        allowed, meta = await self.redis.evalsha(
            sha, 1, key, now_ms, self.rate, self.capacity, cost,
        )
        if allowed == 1:
            return Verdict(True, float(meta), 0)
        return Verdict(False, 0.0, max(1, math.ceil(int(meta) / 1000)))

Enforce it in a FastAPI dependency that estimates cost from the actual query parameters before the database is touched:

# app/routes/geofence.py
from fastapi import APIRouter, Depends, Request, HTTPException, Query
from app.cost_throttle import CostThrottle, estimate_radius_cost

router = APIRouter()

def get_throttle(request: Request) -> CostThrottle:
    # 100-token bucket refilling at 20 tokens/s per client.
    return CostThrottle(request.app.state.redis, refill_per_sec=20, capacity=100)

@router.get("/within")
async def within(
    request: Request,
    lng: float, lat: float,
    radius: float = Query(..., gt=0, le=50000, description="metres, capped at 50 km"),
    throttle: CostThrottle = Depends(get_throttle),
):
    cost = estimate_radius_cost(radius)
    identity = request.headers.get("x-api-key") or request.client.host
    verdict = await throttle.spend(f"within:{identity}", cost)
    if not verdict.allowed:
        raise HTTPException(
            status_code=429,
            detail=f"Query too expensive for remaining budget (cost={cost:.1f}).",
            headers={"Retry-After": str(verdict.retry_after)},
        )
    # ... run the ST_DWithin query here, now safely bounded ...
    return {"tokens_left": round(verdict.tokens_left, 1)}

# Key parameters & options

# Gotchas & failure modes

• Underestimating cost lets the expensive case through. If RADIUS_WEIGHT is too low, a large-radius query costs almost the same as a small one and the throttle does nothing. Calibrate weights against real EXPLAIN ANALYZE timings — pull the actual plans with query plan analysis and index tuning and set weights so a query that runs 10× longer costs roughly 10× the tokens.

• Unbounded radius or bbox exhausts the budget in one call. Without COST_MAX and a route-level le= cap on radius, a single request for a 5,000 km radius withdraws thousands of tokens (or worse, more than capacity, which can never be satisfied). Clamp cost to COST_MAX < capacity and reject absurd inputs with a 422 at the parameter level, as the Query(..., le=50000) above does.

• The cost of the cost estimate itself. If estimating cost requires its own database round trip (for example querying how many features fall in the bbox), you have added a query to save a query. Keep the estimate a pure function of request parameters — area, radius, requested limit — never a database call.

• Refill clock skew. Elapsed time is computed from the caller-supplied now_ms. As with any distributed limiter, drift between API replicas smears the refill rate; keep NTP tight or read TIME from Redis inside the script.

• Silent negative balances. If you deduct before checking (tokens = tokens - cost unconditionally), a bucket can go negative and a later cheap request is wrongly rejected for a long time. Always check tokens >= cost before deducting, as the script does.

# Verification

Confirm that cost scales with radius — a cheap request passes many times, an expensive one drains the bucket fast:

# Cheap: 10 m radius, cost ~1 token — should pass repeatedly against a 100-token bucket
for i in $(seq 1 20); do
  curl -s -o /dev/null -w "%{http_code} " \
    -H "x-api-key: demo" "http://localhost:8000/within?lng=13.4&lat=52.5&radius=10"
done; echo   # expect all 200s (20 tokens spent of 100)

# Expensive: 50 km radius clamps near COST_MAX (~60) — the 2nd request should 429
curl -s -o /dev/null -w "%{http_code}\n" -H "x-api-key: heavy" \
  "http://localhost:8000/within?lng=13.4&lat=52.5&radius=50000"   # 200
curl -s -o /dev/null -w "%{http_code}\n" -H "x-api-key: heavy" \
  "http://localhost:8000/within?lng=13.4&lat=52.5&radius=50000"   # 429 (budget < cost)

Assert the estimator is monotonic — larger radius must never cost less:

from app.cost_throttle import estimate_radius_cost
costs = [estimate_radius_cost(r) for r in (100, 1000, 20000, 500000)]
assert costs == sorted(costs)          # strictly non-decreasing
assert costs[-1] <= 60.0               # clamped at COST_MAX

# Related

• Rate Limiting Geofence & Tile Endpoints — where cost-based throttling fits among fixed-window, sliding-window, and token-bucket approaches
• Redis Sliding-Window Rate Limits for Spatial Endpoints — the flat-count limiter to layer beneath cost throttling
• Bounding-Box Spatial Index Queries — the same envelope geometry that feeds the cost estimate
• Query Plan Analysis & Index Tuning — measure real query cost to calibrate the token weights

← Back to Rate Limiting Geofence & Tile Endpoints