Estimate number of rows in query results Given the relation: 

donate(donor, type, amount, candidate, party, donate-date)



N(donate) 21,000 - total rows
V(party) = 30 - number of different parties
V(type) = 50 - number of different donation types
V(candidate) = 200 - number of different candidates


How to estimate how many rows would the following query yield?

SELECT candidate 
FROM donate
WHERE party="sky" AND type "shoe"


How can I use those details to infer the average number of results?

I can tell that the upper limit is 200 as that is the number of total candidates.
I can tell that there are on average 21000/200 = 105 donations to every candidate.
There are on average 21000/30 = 700 donations to every party.
Not really sure how to proceed.
The approach would be to separate the predicate (the WHERE clause) into its parts and work out the fractions.

The fraction of all rows returned for a given column value is called the selectivity of that column. Since each value of party will return, on average, 700 rows the selectivity of party is 700 / 21000. Similarly for type the selectivity is (number of rows per value)/(total number of rows) = 420 / 21000. If it helps you can think of selectivity as being the probability that a row taken randomly from the table will have the given value.

To combine the two parts of the predicate we multiply the selectivities. We multiply because of the AND clause. Again you can think of probability - if you roll a dice what's the chance you get two sixes in a row? It's (chance of a 6) AND (chance of a six) = 1/6 * 1/6 = 1/36. This is the "chance" per row so to get the number of rows returned we multiply by the table cardinality:

   700     420
  ----- * ----- * 2100
  21000   21000


Which works out at 14.

A similar, but different, calculation can be performed for an OR clause. Then we must account for double-counting of rows that match both conditions. The answer is 700 + 420 - 14 = 1106.

Now, there are several assumptions built into this calculation. First is that the data is evenly distributed over values i.e. that there are 420 values for "shoe" and 420 for "sock" and 420 for "shirt" etc. This is rarely so. More likely is that some values occur infrequently and others often e.g. 800 rows for "shoe" and 2 rows for "golf club". This problem is know as skew. A second assumption is that the two predicates are independent. This assumes if we change "sky" to "earth" there will still be 420 rows for "shoe". Again, this is unlikely to be wholly true. Perhaps sky people only ever donate wings and earth people only ever donate shoes? This problem is know as correlation.  If your data has skew or correlation the maths above is no longer correct.

Commercial DBMS collect statistics about the distribution of values within a column. This helps them with skew. Correlation is difficult and not well handled even in commercial products.

Here's a link which discusses selectivity and cardinality and here's one which discusses multi-column predicates. They're specifically for SQL Server but the maths applies elsewhere.


  I can tell that the upper limit is 200 as that is the number of total candidates.


This is not so. From what you've shown in the question (and I'm sure that's not your full database schema) there is nothing to prevent all rows in the table from having the same value of party, type and candidate. So for a 21,000 row table the maximum number of rows that can be returned is 21,000 or N(donate) in your nomenclature. If there are 200 separate values in the candidate column and you require that each value is returned at most once you need to specify that requirement in the query. In SQL this is achieved with the DISTINCT clause:

SELECT DISTINCT candidate 
FROM donate
WHERE party="sky" AND type "shoe"