List:Internals« Previous MessageNext Message »
From:Antony T Curtis Date:February 21 2001 3:17pm
Subject:Re: Optimisation suggestion...
View as plain text  
Thimble Smith wrote:
> On Wed, Feb 21, 2001 at 12:59:43PM +0000, Antony T Curtis wrote:
> > In the case where there is a SELECT on a table where no index is
> > directly applicable, if there is a compound index where the second part
> > (or third, etc) of the index is used in the WHERE clause, it should be
> > possible to still use that index by being able to skip rows rather than
> > doing a brute-force search through all the records.
> >
> > Any hints where I should look to see if such an optimisation could be
> > implemented?
> It isn't clear to me how that would work.  Do you mean, to scan
> the whole index in order to find rows where the secondary index
> part matches, instead of scanning the data file?  Or do you have
> something else in mind?  I think this optimization wouldn't work,
> but I'm not sure I understand what you're suggesting.
> Tim

The kind of thing it'd do is something like this...

If the key-part to scan is the (n)th key part of the index,

1. Seek index to start
2. Read key from index
3. Check (n)th key part against end-range, if less or equal, goto 6
4. Increment (n-1)th key part and seek to greater/equal key
5. goto stage 2
6. Check (n)th key part against start-range, if greater/equal, goto xx
7. Set (n)th key part to start-range and seek to greather/equal key
8. goto 2
9. (the key should point to valid row in range)
10. Seek to next key
11. if not end of index, goto 6

As an aside, IBM DB2 does not allow two indexes to exist where the two
keys have the same components but are in different orders,

Something like the following will fail in DB2.
> CREATE TABLE db.test (
>   INDEX (COL1, COL2),
>   INDEX (COL2, COL1)
> );

I suggest that their product does something similar to the above.

ANTONY T CURTIS                     Tel: +44 (1635) 36222
Abacus Polar Holdings Ltd           Fax: +44 (1635) 38670
> How come only your friends step on your new white sneakers?
character set conf fileChi-Wai Lau21 Feb
  • character set conf fileMichael Widenius21 Feb
  • Optimisation suggestion...Antony T Curtis21 Feb
    • Re: Optimisation suggestion...Thimble Smith21 Feb
  • Re: Optimisation suggestion...Antony T Curtis21 Feb
    • Re: Optimisation suggestion...Michael Widenius5 Mar
  • Re: Optimisation suggestion...Antony T Curtis5 Mar
    • Re: Optimisation suggestion...Michael Widenius5 Mar
  • Re: Optimisation suggestion...Antony T Curtis6 Mar
RE: Optimisation suggestion...Enrique Villar6 Mar
  • Re: Optimisation suggestion...Antony T Curtis6 Mar