List:General Discussion« Previous MessageNext Message »
From:Dan Nelson Date:June 19 2000 6:42pm
Subject:Re: Why, oh why...
View as plain text  
In the last episode (Jun 19), Carsten H. Pedersen said:
> The trouble, from my point of view, was stated in the first
> sentence:
> 
> > >> [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. 
[etc]
> 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
> result).

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
I/Os.

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)

-- 
	Dan Nelson
	dnelson@stripped
Thread
Why, oh why...Carsten H. Pedersen18 Jun
  • Re: Why, oh why...Jan Dvorak19 Jun
  • Re: Why, oh why...sasha19 Jun
    • Re: Why, oh why...Michael Widenius20 Jun
RE: Why, oh why...Carsten H. Pedersen19 Jun
  • Re: Why, oh why...Dan Nelson19 Jun
    • RE: Why, oh why...Carsten H. Pedersen20 Jun
      • RE: Why, oh why...Michael Widenius20 Jun
    • Re: Why, oh why...Michael Widenius20 Jun