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. 
> 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

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
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