【转帖推荐】mysql怎样执行orderby

ubuntuhk

mysql怎样执行orderby  
                    Joomla! 开源天空           作者：管理员           2009-03-06 21:39            
             

• 摘要：这篇文章对于mysql order by的执行方式，涉及到的细节做出了深入的描述。非常好，有空一定要翻译一下。
• 
  

          
                              Inlast couple of weeks there has been a tide of ORDER/GROUP BY-relatedoptimization bugs, where I was the fixer or the reviewer. This wasn'tan easy job because there is no sane description of how GROUP BY/ORDERBY handling is supposed to work.
To figure it out, I had to write an explanation of how it works. Thefirst part is about ORDER BY. Hopefully there will be subsequent partsthat will show how GROUP BY is related to ORDER BY and how it works.
Available means to produce ordered sequencesMySQL has two methods to produce ordered streams.
The first is to use a "range", "ref" or "index"access method over an ordered index. For versions up to 5.1, thoseaccess methods naturally return records in the index order, so we getordering for free (the exception is NDB engine which needs to domerge-sort when it gets data from several storage nodes). In MySQL 5.2,MyISAM and InnoDB have MultiRangeRead optimizationwhich breaks the ordering. We have a draft of how to make it preservethe ordering, but at the moment MRR is simply disabled wheneverordering is required.
The second, catch-all method, is to use the filesortalgorithm. In a nutshell, filesort() does quicksort on chunks of datathat fit into its memory and then uses mergesort approach to merge thechunks. The amount of memory available to filesort() is controlled by @@sort_buffer_sizevariable. if the sorted data doesn't fit into memory (i.e. there ismore than one chunk), filesort uses a temporary file to store thechunks.
Source data for filesort() always comes from one table. If there isa need to sort data from several tables, MySQL will first collect thedata into a temporary table and then invoke filesort() for thattemporary table. I don't know the true reason for this. Codewise,filesort() wants to pull its source data using something likesource.get_next_record() function, while join and union runtime producetheir using result.put_next_record()-type calls, so maybe the temporarytable is there only to resolve this push/pull mismatch and will go awayonce we get decent cursors.
filesort() has two modes of operation:

• Mode 1: the sorted elements contain all required columns of thesource table. The result of the sorting is a linear sequence of outputtuples, there is no need to access the source table after the sort isdone.
• Mode 2: sort <sort_key, rowid> pairs and produce asequence of rowids which one can use to get source table's rows in therequired order (but this will be essentially hit the table in randomorder and is not very fast)

Mode 1 is used whenever possible. Mode is used when mode1 is notapplicable. This is the case when the sorted tuples have blobs orvariable-length columns (TODO: check w/ evgen). Unfortunately, theEXPLAIN output provides no clue about which mode is used, so you'llhave to manually check for blobs in the output columns list.
Executing join to produce ordered streamAt the moment MySQL has three ways to run a join and produce ordered output:

Method	EXPLAIN output
Use index-based access method that produces ordered output	no mention of filesort
Use filesort() on 1st non-constant table	"Using filesort" in the first row
Put join result into a temporary table and use filesort() on it	"Using temporary; Using filesort" in the first row

Now I'll cover those three methods in more detail. The first methodcan be used when the first non-const table in the join order has anindex that matches the ORDER BY list. In this case we can use theindex, and the ordering will "spread over" other tables onto theoutput. Here is a swimlane diagram of this process, where differentcolumns represent different values of the ORDER BY expression:

                               
登录/注册后可看大图

This method is preferred over the other two as it requires no additional sorting steps.
The second method can be used when all ORDER BY elements refer tothe first table in the join order. In this case, we can filesort() thefirst table and then proceed to execute the join:

                               
登录/注册后可看大图

Herefilesort() may operate either in Mode 1 or in Mode 2. One may wonderwhy this is limited to doing filesort() after the first table. Afterall, we could do it after the second table as well - produce (tbl1,tbl2) record combinations, put them into temporary table, sort, etc.The expectation is perfectly reasonable but alas, MySQL will not evenconsider such query plans.
The last, the catch-all method is to write the entire join output into the temporary table and then invoke filesort:

                               
登录/注册后可看大图

I have an easier time recalling those three strategies when thereare pictures, hopefully they'll help you too. That's all for today, innext posts I'll cover the topics of how ordering affects joinoptimization and interoperates with GROUP BY.
原文：http://s.petrunia.net/blog/?p=24

转自：http://www.maycode.com/index.php ... ews/1417-mysql.html