In the last episode (Jun 19), Carsten H. Pedersen said:
> The trouble, from my point of view, was stated in the first
> > >> [why] does MySQL insist on doing a scan of all keys on a simple
> > >> range constraint?
> i.e. why does MySQL insist on hitting *every single key* when it
> already knows the approximate min/max location ("" and "b"
> respectively) of the boundaries of the range in the index?
> like 2*(ln 117.000) = 24 index hits.
> Now that I know the min/max pair of the index, I can quickly
> calculate that the number of records that fullfil the criteria
> is indexpos(max) - indexpos(min).
.. and this is the impossible part (i.e. there is no such thing as an
indexpos function). An index isn't a linear lookup table. It's a
B-tree, and given the logical locations of two records on the tree,
it's impossible to count how many keys are between the two locations
without scanning every one.
> Without knowing the internals of MySQL, I'll hazard a guess that this
> is almost exactly what takes place when MySQL first decides where to
> search (and why EXPLAIN shows a "row" value so close to the actual
What mysql does is find the first "a" (which takes about 3 I/O's), then
scans until it finds something "not a", taking about one I/O per 150
keys or so (assuming 6 bytes per index entry, 1024-byte index blocks,
and a 90% fillrate for the index blocks), for a total of around 670
A lot of your time is probably CPU, though. I've noticed that mysql
doesn't handle indexes with many duplicate values very well.
(insert plea for bitmap indexes here)