Cardinality

Why interviewers love this word: it looks tiny, but it decides whether an index is a rocket or dead weight.

Question: What does cardinality mean in SQL, especially for indexes and performance?

Answer: Cardinality usually means how many distinct values a column has. A column like status has low cardinality because many rows share a few values, while email has high cardinality because most values are unique. This matters because indexes help most when they narrow a search to a small set of rows; if a filter matches too many rows, a table scan can be cheaper.

Interview-Ready Answer: In SQL, cardinality usually means the number of distinct values in a column. It matters for index choice because high-cardinality columns are usually more selective, so an index can jump straight to a small set of rows. Low-cardinality columns like flags or statuses often return a large fraction of the table, so a scan may beat using the index alone. One important detail is that COUNT(DISTINCT ...) ignores NULL in most databases, so you have to think about nulls when measuring it.

What cardinality really means

Detailed Explanation: In index interviews, cardinality usually means column cardinality: the number of distinct values in one column. Do not confuse this with table cardinality, which can mean the total number of rows. For example, a table with 10 million rows and a status column that contains only pending, paid, and shipped has low column cardinality but high table cardinality.

How the optimizer uses it under the hood

1. The database looks at statistics for the column, such as how many distinct values exist and how often each value appears.
2. It estimates selectivity, which means the fraction of rows that match a predicate. A highly selective filter keeps very few rows.
3. It compares the cost of using an index versus scanning the table. An index lookup is often around O(log N) to find the key, but the real cost also includes fetching matching rows.
4. If the filter matches a small slice of the table, the index wins. If the filter matches a large slice, the engine may choose a sequential scan because walking the index and then jumping around the table causes extra random I/O.
5. After big data changes, the engine needs fresh statistics. Stale stats make the optimizer guess badly and can produce a slow plan.

Low vs high cardinality

Rule of thumb: if a predicate returns only a tiny fraction of the table, an index is usually helpful. If it returns a big chunk, the engine may prefer a scan. There is no universal cutoff like 10% for every database; the decision depends on table size, row width, caching, clustering, and the cost of random reads.

Why low-cardinality indexes still sometimes help

• Composite indexes: A low-cardinality first column can become useful when paired with a more selective second column, such as (status, created_at).
• Covering queries: If the index contains all needed columns, the engine may avoid reading the table rows.
• Filtered use cases: In some databases, partial or filtered indexes make a low-cardinality predicate practical when only one value matters a lot.
• Warehouse engines: Some analytical systems use bitmap-style techniques where low-cardinality columns can still be valuable.

Edge cases interviewers love

• NULLs: COUNT(DISTINCT col) usually excludes NULL, so the measured cardinality may be lower than the real number of categories your business thinks it has.
• Skew: A column can have high cardinality but still be lopsided, such as one value holding 95% of rows. The rare values are selective; the common value is not.
• Stale stats: If a table changes a lot and stats are not refreshed, the optimizer may think a value is rare when it is actually common.
• Wide indexes: A high-cardinality text column may be unique but still expensive to index if the key is large and every write must maintain it.

Time and space notes: A B-tree index usually gives good lookup performance, but every extra index costs storage and write work. Inserts, updates, and deletes must maintain the index, so more indexes can slow writes even when they speed reads. That is why cardinality is not just about whether an index can work; it is also about whether the speedup is worth the maintenance cost.

Memory model: think of an index like a library catalog. If one label points to only a few books, the catalog helps a lot. If one label points to half the library, the catalog is less impressive.

Real-World Story: Imagine a checkout service for an e-commerce app with a 50-million-row orders table. The team adds an index on status because a dashboard needs WHERE status = 'shipped'. It looks smart, but 80% of orders are shipped, so the query still touches millions of rows. On the first busy Monday morning, the admin dashboard slows to a crawl, p95 latency jumps from 120 ms to 3 seconds, and EXPLAIN shows a sequential scan instead of the index.

The fix is to think in cardinality, not just in “has an index / has no index” terms. The team either uses a more selective composite index like (status, created_at) for the report, or switches the report to filter on a high-cardinality field such as order_id or customer_email when looking up a single order. The misunderstanding causes a classic symptom: lots of CPU, lots of I/O, and users seeing endless spinners even though an index exists. The lesson is simple: an index on a low-cardinality column can be real, but still not the right answer for the query pattern.

Follow-up & Tricky Questions:

• How does cardinality affect a composite index? The combined cardinality can be much higher than either column alone, so (status, created_at) can be much better than status by itself when the second column narrows the result set.
• What is the difference between cardinality and selectivity? Cardinality is the number of distinct values; selectivity is how small the matching result set is. They are related, but not identical: a column can have many distinct values and still be poorly selective if one value dominates the data.
• Why can an index on a low-cardinality column still help? It can help when combined with another filter, when the index covers the query, or when the engine can use a filtered/partial strategy. Alone, though, it often returns too many rows to beat a scan.
• How do databases know cardinality? They keep statistics such as row counts, distinct counts, and histograms, which are summaries of value distribution. The optimizer uses these to estimate cost before running the query.
• What happens when statistics are stale? The optimizer may think a predicate is selective when it is not, or the opposite, and choose a bad plan. That is how an index that used to be fast suddenly becomes “mysteriously” slow.
• Does COUNT(DISTINCT col) count NULL? Usually no. That is a common gotcha, so if NULL represents a real bucket in your data model, you must count it explicitly.
• Is high cardinality always better? No. A unique column is great for lookups, but if the query still needs a huge portion of the table, the index can be slower than a scan. More indexes also mean more storage and slower writes.
• Is cardinality the same as table size? No. Table size is total rows; cardinality is distinct values in a column. A giant table can still have very low cardinality in a status column.

• Gotcha: Is one-row-per-value always best? Not necessarily. Unique values are highly selective, but if the column is wide text or the query returns many columns anyway, the index may not be the cheapest path.
• Gotcha: Can a low-cardinality index be a waste? Yes, if it is used alone on a huge table and the result set is large. The engine may still scan because the index does not reduce work enough.
• Gotcha: Do planners use exact counts? Usually no; they use estimates from statistics. That is why skew and stale stats matter so much.

Common Mistakes:

• Mistake: Thinking cardinality means only “row count.” Correction: In index questions, it usually means the number of distinct values in a column.
• Mistake: Assuming every index is good. Correction: Low-cardinality indexes often do not help by themselves, especially on large tables.
• Mistake: Forgetting NULL. Correction: COUNT(DISTINCT ...) usually ignores NULL, so measure carefully.
• Mistake: Ignoring writes. Correction: Each extra index makes inserts, updates, and deletes more expensive.

Memory Hook: “A good index is a tiny key that opens few doors; a bad one is a key that opens almost every door.”

Cheat Sheet:

• Cardinality = number of distinct values in a column.
• High cardinality usually means higher selectivity.
• Low cardinality often means scans are competitive.
• Composite indexes can turn low-cardinality columns into useful ones.
• Statistics and histograms drive the optimizer’s estimate.
• NULL handling can change your count and your plan.

Practice Tasks:

• Run COUNT(DISTINCT ...) on several columns in one of your tables and rank them from lowest to highest cardinality.
• Add an index on a low-cardinality column and inspect the query plan for a filter on that column versus a filter on a unique column.
• Take a real query and try a composite index that combines a low-cardinality column with a more selective one.