2

I went through Range Extraction Documentation for MySQL Indexes. They have explained for single column indices. What is the procedure to reduce complex multi column (at least two) criteria?

What I am essentially asking is, is there an algorithm or any literature(s) that explains how to simplify/reduce range intervals from complex predicates? Assuming B-TREE index or any index with sequential arrangement of key values.

For example:-

Single Column Examples

From

(duration > 5 and duration < 10) or (duration < 100)

To

NULL < duration < 100

From

(duration > 5 and duration < 10) or (duration < 100)

To

5 < duration < 10
100 < duration

Two Column Examples

From

(duration in (9,10) and service_id > 500)

To

9 <= duration <= 9 AND 500 < service_id
10 <= duration <= 10 AND 500 < service_id

From

(duration in (9,10) and service_id = 500) or (duration = 19 and service_id=570)

To

9 <= duration <= 9 AND 500 <= service_id <= 500
10 <= duration <= 10 AND 500 <= service_id <= 500
19 <= duration <= 19 AND 570 <= service_id <= 570
  • theory.stanford.edu/~sergei/papers/sigmod10-index.pdf If you have enough time, go through this. You might not get everything you need from this. But this will give you some insights. – Arun Rajagopal Sep 16 at 13:22
  • 1
    Since that Yahoo research paper does not mention MySQL, the contents may or may not be actually used in MySQL or MariaDB. – Rick James Sep 16 at 15:34
  • 1
    I thought the OP was curious to know any algorithm for doing what MySQL seems to do while optimising. I might have understood the question wrong too. – Arun Rajagopal Sep 16 at 17:02
2

Historically, MySQL has kept the relevant algorithms simple, even if less than optimal. In particular, OR has been poorly optimized. 5.7 and 8.0 have new code, but I don't know if your examples have improved any.

EXPLAIN FORMAT=JSON sometimes gives clues. Also, see the "Optimizer Trace".

If you have sample data, use the Handler counts to deduce whether they are well optimized: http://mysql.rjweb.org/doc.php/index_cookbook_mysql#handler_counts.

But, be aware that MySQL will often do a table scan instead of using an obvious index. This is legitimate because of the cost of bouncing between the BTree for the secondary index and the BTree that contains the data. Typically, if more than 20% of the index needs to be touched, it will prefer to do a table scan. (The "20%" is no a hard-coded number, but is a gross simplification of the "cost-based" model that is used.)

Search for mysql cost based optimization. There have been a few articles written on the topic.

  • can i get any name for algorithms used in Range Simplification in mysql , especially if want to implement the same for a use-case – Dinesh Kumar Sep 17 at 5:15
  • 1
    @DineshKumar this is a pretty informative (although unofficial) blog on some intricacies of MySQL optimizer --> unofficialmysqlguide.com – Madhur Bhaiya Sep 17 at 6:50
  • 1
    @MadhurBhaiya - Tocker is quite knowledgeable about MySQL, so it is probably quite good, in spite of being "unofficial". – Rick James Sep 17 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.