CODEWITHSUNDEEP
mysqlsqlindexing
Chip
Chip

Reputation: 81

How can I query between two columns while still taking advantage of indexes?

Imagine I have a table contains all the chapters of a book and the start/end page from each chapter.

chapter |   start_page     | end_page
--------------------------------------
   1    |        1         |    24
   2    |        25        |    67
   3    |        68        |    123
   4    |        124       |    244
   5    |        245       |    323

I'm attempting to find out what chapter a random page falls on, let's say page 215 for example.

My first idea was to use a query like this

SELECT `chapter`
FROM `book`
WHERE `start_page` <= 215
AND `end_page` >= 215

Unfortunately MySQL can not take advantage of indexes in the above query which is a large problem due to the large size of my table.

After doing some research I came up with this query which does take advantage of indexes.

SELECT `chapter`
FROM `book`
WHERE `start_page` <= 215
ORDER BY `start_page` DESC     
LIMIT 1

The issue now is I want the ability to query multiple random pages while still taking advantage of indexes. It doesn't seem likely that I can modify my last query since it's so heavily reliant on limiting results to one.

Any advice would be much appreciated!

UPDATE: Thanks to a comment from Ray Toal I have a query which gives me the results I need with amazing performance. 

SELECT chapter 
FROM book 
WHERE (start_page = (SELECT max(start_page) FROM book WHERE start_page <= 73) AND end_page >= 73) 
OR (start_page = (SELECT max(start_page) FROM book WHERE start_page <= 92) AND end_page >= 92) 
OR (start_page = (SELECT max(start_page) FROM book WHERE start_page <= 300) AND end_page >= 300)

Upvotes: 8

Views: 1431

Answers (3)

Bohemian
Bohemian

Reputation: 425063

Isn't it as simple as this?

select max(chapter)
from book
where start_page <= 215;

If end pages follow previous start pages, this will work.

Upvotes: 1

Richard Sim&#245;es
Richard Sim&#245;es

Reputation: 12801

Syntactically-valid equivalent of Bohemian's INTERSECT solution (requires a unique index of some kind and large join buffer):

SELECT
    chapter
FROM
    book AS book_l
    JOIN book AS book_r
    USING (id)
WHERE
     book_l.start_page <= 215
     AND book_r.end_page >= 215;

Or a temptable approach (requires a single index on each of start_page and end_page):

SELECT chapter FROM (
    SELECT * FROM book WHERE start_page <= 215
    UNION
    SELECT * FROM book WHERE end_page >= 215
) AS derived WHERE start_page <= 215 AND end_page >= 215

Upvotes: 0

Richard Sim&#245;es
Richard Sim&#245;es

Reputation: 12801

Add two composite indices:

ALTER TABLE book
    ADD INDEX `page_range_from_start` (start_page, end_page)
    ADD INDEX `page_range_from_end` (end_page, start_page)

And proceed with your original query:

SELECT `chapter`
FROM `book`
WHERE
    `start_page` <= 215
    AND `end_page` >= 215

MySQL will choose the index leading with the column that will give it the fewest remaining rows to scan, and then it will have a second part of the index to reduce to the single desired row (without a scan).

Upvotes: 0

Related Questions