In a multi-tenant platform where every tenant's data shares the same physical tables and tenants differ in size by orders of magnitude, why do query plans that are optimal for one tenant become pathological for another - and what is the fix?

The mechanism

The query planner chooses a plan using table-level statistics — cardinality estimates, value distributions, index selectivity. In a shared multi-tenant table, those statistics describe the aggregate of all tenants, and no individual tenant resembles the aggregate.

Concretely: a filter on status = 'open' might match 2% of rows platform-wide, so the planner picks an index scan. For a tenant where 90% of their records are open, that index scan visits nearly every one of their rows through the index — far slower than a direct scan of their partition.

Worse, with plan caching the plan is chosen once, typically by whichever tenant happened to execute the query first, and then reused for everyone. A plan tuned for a tenant with a thousand records is applied to one with fifty million.

Why it presents as a mystery

• The same query is fast for most customers and catastrophic for one.
• It changes after a statistics refresh, apparently at random.
• It cannot be reproduced in a test environment, because the data distribution there is uniform.
• The slow tenant's query looks identical in the logs to everyone else's.

The fixes, in order of leverage

1. Make the tenant a leading index column. Every index begins with the tenant identifier, so selectivity is evaluated within a tenant rather than across the estate, and every scan is confined to one tenant's rows. This is the single most important schema decision in a shared-table architecture.

2. Partition physically by tenant. With table partitioning on the tenant key, the planner prunes to one partition and its statistics are per-partition. This eliminates the aggregate-statistics problem at its root.

3. Defeat harmful plan reuse. Either parameterise so plans are cached per tenant shape, or force recompilation for queries known to be distribution-sensitive. Blanket recompilation costs CPU, so this is targeted rather than global.

4. Metadata-driven query construction with guard rails. Where tenants define their own fields and filters, the query builder must impose limits — mandatory tenant predicate, maximum result set, maximum join count, statement timeout — because tenant-authored queries are effectively untrusted input.

5. Per-tenant resource governance. A statement timeout and a concurrency limit per tenant, so a pathological plan degrades that tenant rather than saturating shared capacity. Without this, one tenant's bad query is everyone's incident.

The architectural lesson

Shared-table multi-tenancy is efficient and operationally simple, and it makes the largest tenants pay a design cost imposed by the smallest. Beyond some size, the honest answer is a different tenancy tier — dedicated schema, database or cell — rather than continuing to tune shared statistics. The architecture should include an explicit promotion path, because the alternative is discovering the need during an incident.