Revenue Source

Welcome to the Revenue Source affiliate marketing forums.

You are viewing our internet marketing and SEO forums as a guest which gives you limited access to most of our discussions.  By joining our free community, you will have access to post affiliate marketing topics, communicate privately with other members (PM), exchange SEO strategies, and access many other special features.  Registration is fast, simple and absolutely free so please, join our community today!

If you have any problems, please don't hesitate to contact us.

Go Back   Revenue Source > Site Design & Development > Databases
Reload this Page Possible optimization for sort_merge and UNION ORDER BY LIMIT
Tags: , , , , ,

Reply
 
LinkBack Thread Tools Search this Thread
Old
  (#1 (permalink))
Affiliate Blogs is Offline
Revenue Source Veteran
Affiliate Blogs has a brilliant future here!
 
Affiliate Blogs's Avatar
 
Join Date: Oct 2005
Posts: 9,144
Jack of All Trades
CyberSpace United States
   
Possible optimization for sort_merge and UNION ORDER BY LIMIT - 09-18-2007
Every so often you need to perform sort results retrieved from MySQL when your WHERE clause goes beyound col=const values which would allow MySQL to still use second portion of the index for the order by. Ranges as well as IN lists make this optimization impossible, not even speaking about index merge optimization. Lets look at this example:
PLAIN TEXT
SQL:
  1. [FONT='Courier New', Courier, monospace]CREATE TABLE `utest` ([/font]
  2. [FONT='Courier New', Courier, monospace] `c1` int(10) UNSIGNED NOT NULL,[/font]
  3. [FONT='Courier New', Courier, monospace] `c2` int(10) UNSIGNED NOT NULL,[/font]
  4. [FONT='Courier New', Courier, monospace] `ord` int(10) UNSIGNED NOT NULL,[/font]
  5. [FONT='Courier New', Courier, monospace] KEY `c1` (`c1`,`ord`),[/font]
  6. [FONT='Courier New', Courier, monospace] KEY `c2` (`c2`,`ord`)[/font]
  7. [FONT='Courier New', Courier, monospace]) ENGINE=MyISAM DEFAULT CHARSET=latin1[/font]
  8. [FONT='Courier New', Courier, monospace] [/font]
  9. [FONT='Courier New', Courier, monospace]mysql> EXPLAIN SELECT * FROM utest WHERE c1=5 OR c2=5 ORDER BY ord DESC LIMIT 10 \G[/font]
  10. [FONT='Courier New', Courier, monospace]*************************** 1. row ***************************[/font]
  11. [FONT='Courier New', Courier, monospace] id: 1[/font]
  12. [FONT='Courier New', Courier, monospace] select_type: SIMPLE[/font]
  13. [FONT='Courier New', Courier, monospace] TABLE: utest[/font]
  14. [FONT='Courier New', Courier, monospace] type: index_merge[/font]
  15. [FONT='Courier New', Courier, monospace]possible_keys: c1,c2[/font]
  16. [FONT='Courier New', Courier, monospace] KEY: c1,c2[/font]
  17. [FONT='Courier New', Courier, monospace] key_len: 4,4[/font]
  18. [FONT='Courier New', Courier, monospace] ref: NULL[/font]
  19. [FONT='Courier New', Courier, monospace] rows: 162380[/font]
  20. [FONT='Courier New', Courier, monospace] Extra: USING sort_union(c1,c2); USING WHERE; USING filesort[/font]
  21. [FONT='Courier New', Courier, monospace]1 row IN SET (0.00 sec) [/font]



As you can see MySQL 5.1.21 uses sort_merge to access the rows but it can't use it together with order by efficiently.
I'd say this is limitation as for this case you well could be retrieving sorted streams by the indexes and doing merge sort to get resulted rows in sorted order. Once this is implemented similar approach could be used for optimizing ORDER BY with IN.
This original query (in memory data) takes 1sec. Let's see how classic pre MySQL 5.0 solution - using UNION instead of single query works in this case:
PLAIN TEXT
SQL:
  1. [FONT='Courier New', Courier, monospace]mysql> EXPLAIN (SELECT * FROM utest WHERE c1=5) union (SELECT * FROM utest WHERE c2=5) ORDER BY ord DESC LIMIT 10 \G[/font]
  2. [FONT='Courier New', Courier, monospace]*************************** 1. row ***************************[/font]
  3. [FONT='Courier New', Courier, monospace] id: 1[/font]
  4. [FONT='Courier New', Courier, monospace] select_type: PRIMARY[/font]
  5. [FONT='Courier New', Courier, monospace] TABLE: utest[/font]
  6. [FONT='Courier New', Courier, monospace] type: ref[/font]
  7. [FONT='Courier New', Courier, monospace]possible_keys: c1[/font]
  8. [FONT='Courier New', Courier, monospace] KEY: c1[/font]
  9. [FONT='Courier New', Courier, monospace] key_len: 4[/font]
  10. [FONT='Courier New', Courier, monospace] ref: const[/font]
  11. [FONT='Courier New', Courier, monospace] rows: 108112[/font]
  12. [FONT='Courier New', Courier, monospace] Extra: [/font]
  13. [FONT='Courier New', Courier, monospace]*************************** 2. row ***************************[/font]
  14. [FONT='Courier New', Courier, monospace] id: 2[/font]
  15. [FONT='Courier New', Courier, monospace] select_type: UNION[/font]
  16. [FONT='Courier New', Courier, monospace] TABLE: utest[/font]
  17. [FONT='Courier New', Courier, monospace] type: ref[/font]
  18. [FONT='Courier New', Courier, monospace]possible_keys: c2[/font]
  19. [FONT='Courier New', Courier, monospace] KEY: c2[/font]
  20. [FONT='Courier New', Courier, monospace] key_len: 4[/font]
  21. [FONT='Courier New', Courier, monospace] ref: const[/font]
  22. [FONT='Courier New', Courier, monospace] rows: 54268[/font]
  23. [FONT='Courier New', Courier, monospace] Extra: [/font]
  24. [FONT='Courier New', Courier, monospace]*************************** 3. row ***************************[/font]
  25. [FONT='Courier New', Courier, monospace] id: NULL[/font]
  26. [FONT='Courier New', Courier, monospace] select_type: UNION RESULT[/font]
  27. [FONT='Courier New', Courier, monospace] TABLE: [/font]
  28. [FONT='Courier New', Courier, monospace] type: ALL[/font]
  29. [FONT='Courier New', Courier, monospace]possible_keys: NULL[/font]
  30. [FONT='Courier New', Courier, monospace] KEY: NULL[/font]
  31. [FONT='Courier New', Courier, monospace] key_len: NULL[/font]
  32. [FONT='Courier New', Courier, monospace] ref: NULL[/font]
  33. [FONT='Courier New', Courier, monospace] rows: NULL[/font]
  34. [FONT='Courier New', Courier, monospace] Extra: USING filesort[/font]
  35. [FONT='Courier New', Courier, monospace]3 rows IN SET (0.00 sec) [/font]



The query looks scare but in fact in completes in 1.05 sec not significantly faster than sort index merge in this case.
As the query time implies MySQL is not smart enough in this case to "dive into" the union and add ORDER BY ORD LIMIT 10 to individual queries.
What if we do int manually ?
PLAIN TEXT
SQL:
  1. [FONT='Courier New', Courier, monospace]mysql> EXPLAIN (SELECT * FROM utest WHERE c1=5 ORDER BY ord DESC LIMIT 10) union (SELECT * FROM utest WHERE c2=5 ORDER BY ord DESC LIMIT 10) ORDER BY ord DESC LIMIT 10 \G[/font]
  2. [FONT='Courier New', Courier, monospace]*************************** 1. row ***************************[/font]
  3. [FONT='Courier New', Courier, monospace] id: 1[/font]
  4. [FONT='Courier New', Courier, monospace] select_type: PRIMARY[/font]
  5. [FONT='Courier New', Courier, monospace] TABLE: utest[/font]
  6. [FONT='Courier New', Courier, monospace] type: ref[/font]
  7. [FONT='Courier New', Courier, monospace]possible_keys: c1[/font]
  8. [FONT='Courier New', Courier, monospace] KEY: c1[/font]
  9. [FONT='Courier New', Courier, monospace] key_len: 4[/font]
  10. [FONT='Courier New', Courier, monospace] ref: const[/font]
  11. [FONT='Courier New', Courier, monospace] rows: 108112[/font]
  12. [FONT='Courier New', Courier, monospace] Extra: USING WHERE[/font]
  13. [FONT='Courier New', Courier, monospace]*************************** 2. row ***************************[/font]
  14. [FONT='Courier New', Courier, monospace] id: 2[/font]
  15. [FONT='Courier New', Courier, monospace] select_type: UNION[/font]
  16. [FONT='Courier New', Courier, monospace] TABLE: utest[/font]
  17. [FONT='Courier New', Courier, monospace] type: ref[/font]
  18. [FONT='Courier New', Courier, monospace]possible_keys: c2[/font]
  19. [FONT='Courier New', Courier, monospace] KEY: c2[/font]
  20. [FONT='Courier New', Courier, monospace] key_len: 4[/font]
  21. [FONT='Courier New', Courier, monospace] ref: const[/font]
  22. [FONT='Courier New', Courier, monospace] rows: 54268[/font]
  23. [FONT='Courier New', Courier, monospace] Extra: USING WHERE[/font]
  24. [FONT='Courier New', Courier, monospace]*************************** 3. row ***************************[/font]
  25. [FONT='Courier New', Courier, monospace] id: NULL[/font]
  26. [FONT='Courier New', Courier, monospace] select_type: UNION RESULT[/font]
  27. [FONT='Courier New', Courier, monospace] TABLE: [/font]
  28. [FONT='Courier New', Courier, monospace] type: ALL[/font]
  29. [FONT='Courier New', Courier, monospace]possible_keys: NULL[/font]
  30. [FONT='Courier New', Courier, monospace] KEY: NULL[/font]
  31. [FONT='Courier New', Courier, monospace] key_len: NULL[/font]
  32. [FONT='Courier New', Courier, monospace] ref: NULL[/font]
  33. [FONT='Courier New', Courier, monospace] rows: NULL[/font]
  34. [FONT='Courier New', Courier, monospace] Extra: USING filesort[/font]
  35. [FONT='Courier New', Courier, monospace]3 rows IN SET (0.00 sec) [/font]



As you can see explain does not really change (it does not show if index is used for finding rows or sorting as well) but query speed goes to less than
0.01 sec.
So it is great optimization which you need to do manuall for the time being.
What is also interesting is the fact MySQL is unable to handle even basic UNION with limit (without order by) optimally - in creates result set for the union fully and when only takes 10 rows from it:
PLAIN TEXT
SQL:
  1. [FONT='Courier New', Courier, monospace]mysql> EXPLAIN (SELECT * FROM utest WHERE c1=5 ) union (SELECT * FROM utest WHERE c2=5 ) LIMIT 10 \G[/font]
  2. [FONT='Courier New', Courier, monospace]*************************** 1. row ***************************[/font]
  3. [FONT='Courier New', Courier, monospace] id: 1[/font]
  4. [FONT='Courier New', Courier, monospace] select_type: PRIMARY[/font]
  5. [FONT='Courier New', Courier, monospace] TABLE: utest[/font]
  6. [FONT='Courier New', Courier, monospace] type: ref[/font]
  7. [FONT='Courier New', Courier, monospace]possible_keys: c1[/font]
  8. [FONT='Courier New', Courier, monospace] KEY: c1[/font]
  9. [FONT='Courier New', Courier, monospace] key_len: 4[/font]
  10. [FONT='Courier New', Courier, monospace] ref: const[/font]
  11. [FONT='Courier New', Courier, monospace] rows: 108112[/font]
  12. [FONT='Courier New', Courier, monospace] Extra: [/font]
  13. [FONT='Courier New', Courier, monospace]*************************** 2. row ***************************[/font]
  14. [FONT='Courier New', Courier, monospace] id: 2[/font]
  15. [FONT='Courier New', Courier, monospace] select_type: UNION[/font]
  16. [FONT='Courier New', Courier, monospace] TABLE: utest[/font]
  17. [FONT='Courier New', Courier, monospace] type: ref[/font]
  18. [FONT='Courier New', Courier, monospace]possible_keys: c2[/font]
  19. [FONT='Courier New', Courier, monospace] KEY: c2[/font]
  20. [FONT='Courier New', Courier, monospace] key_len: 4[/font]
  21. [FONT='Courier New', Courier, monospace] ref: const[/font]
  22. [FONT='Courier New', Courier, monospace] rows: 54268[/font]
  23. [FONT='Courier New', Courier, monospace] Extra: [/font]
  24. [FONT='Courier New', Courier, monospace]*************************** 3. row ***************************[/font]
  25. [FONT='Courier New', Courier, monospace] id: NULL[/font]
  26. [FONT='Courier New', Courier, monospace] select_type: UNION RESULT[/font]
  27. [FONT='Courier New', Courier, monospace] TABLE: [/font]
  28. [FONT='Courier New', Courier, monospace] type: ALL[/font]
  29. [FONT='Courier New', Courier, monospace]possible_keys: NULL[/font]
  30. [FONT='Courier New', Courier, monospace] KEY: NULL[/font]
  31. [FONT='Courier New', Courier, monospace] key_len: NULL[/font]
  32. [FONT='Courier New', Courier, monospace] ref: NULL[/font]
  33. [FONT='Courier New', Courier, monospace] rows: NULL[/font]
  34. [FONT='Courier New', Courier, monospace] Extra: [/font]
  35. [FONT='Courier New', Courier, monospace]3 rows IN SET (0.00 sec) [/font]



Such query takes about 0.9 sec on the test data. Another possible optimizer improvement to do.
P.S This post is inspired by Does MySQL Optimize UNION with LIMIT clause topic on our MySQL Forums.


Possible optimization for sort_merge and UNION ORDER BY LIMIT - Read More...
  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!
Reply With Quote
Reply

« Using GROUP BY WITH ROLLUP for Reporting Performance Optimization | MySQL Master Class after HighLoad.RU »

Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On

Similar Threads for: Possible optimization for sort_merge and UNION ORDER BY LIMIT
Thread Thread Starter Forum Replies Last Post
Merchant 8848 - YesAsia - Drunken Tiger - Sky Is The Limit $12.99 Affiliate Marketin Affiliate Marketing News Shareasale Affiliate Deals 0 09-13-2007 08:52 AM
Facebook A Union Issue? Affiliate Marketing News Internet Marketing Articles 0 08-30-2007 10:26 PM
Using delayed JOIN to optimize count(*) and LIMIT queries Affiliate Blogs Databases 0 04-06-2007 07:06 PM
Yahoo - 70 Character Limit on Titles and Descriptions Affiliate Blogs Affiliate Marketing 0 04-06-2007 07:06 PM
Don’t Limit Your Affiliate Revenue xboxundone Affiliate Marketing 0 12-06-2006 10:14 PM



© 2004-6 RevenueSource.com.  All rights reserved.  Do not duplicate or redistribute in any form.
This website and its logos/design are property of RevenueSource.com.  All rights reserved. vBSEO 3.2.0 RC7

Contact Us - Affiliate Marketing & SEO Forums - Archive - Top

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34