[prev] 3 [next]

Estimating Selection Result Size

Analysis relies on operation and data distribution:

E.g. select * from R where a = k;

Case 1:   uniq(R.a)   ⇒   0 or 1 result

Case 2:   rR  tuples && size(dom(R.a)) = n   ⇒   rR / n results

E.g. select * from R where a < k;

Case 1:   k ≤ min(R.a)   ⇒   0 results

Case 2:   k > max(R.a)   ⇒   ≅ rR results

Case 3:   size(dom(R.a)) = n   ⇒   ? min(R.a) ... k ... max(R.a) ?