Bug #82338 Please support ASC/DESC index traversal on ASC/ASC indexing.

• Submitted: 25 Jul 2016 21:05
• Modified: 29 Dec 2021 17:53
• Reporter: Domas Mituzas
• Status: Verified
• Category: MySQL Server: Optimizer
• Severity: S3 (Non-critical)
• Version: any, 5.6.31, 5.7.13
• OS: Any
• CPU Architecture: Any

[25 Jul 2016 21:05] Domas Mituzas

Description:
currently if a table has a multicolumn index on e.g. (a,b), this will happen:

ORDER BY a, b <--- no filesort
ORDER BY a DESC, b DESC <--- no filesort
ORDER BY a, b DESC <-- OH NO FILESORT
ORDER BY a DESC, b <--- OH NO FILESORT AGAIN

Currently that happens because tree traversal is most naive one:

Seek to position X, Y; next; next; next

What we need for mixed order reads is:

Seek to position X+1; prev; prev until hit X; jump to another X value; prev; prev; ...

Existing data structures make it possible, so just proper composite index traversal method is needed that optimizer can use not to be dumb. 

How to repeat:
SELECT * FROM table ORDER BY a ASC, b DESC

Suggested fix:
Implement the flexible direction index traversal.

[25 Jul 2016 21:10] Domas Mituzas

the bad cases should need more punctuation like'OH NO!!!! FILESORT!!!"

[26 Jul 2016 5:46] MySQL Verification Team

Hello Domas,

Thank you for the report and feedback!

Thanks,
Umesh

[26 Mar 2019 17:54] Domas Mituzas

:(

[29 Dec 2021 17:53] Domas Mituzas

:'(