Shulou(Shulou.com)05/31 Report--

This article mainly shows you "MYSQL how to achieve ORDER BY and LIMIT", the content is easy to understand, clear, hope to help you solve your doubts, the following let the editor lead you to study and learn "MYSQL how to achieve ORDER BY and LIMIT" this article.

1. LIMIT in MYSQL and paging in ORACLE

Describe in the MYSQL official document that limit returns the data you need in the result set. It can return the required rows as soon as possible, regardless of the remaining lines.

There are also related grammars in ORACLE, such as rownun explain select * from testshared3 order by id limit 10 and 20 before 12C.

+-- +

| | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |

+-- +

| | 1 | SIMPLE | testshared3 | NULL | ALL | NULL | NULL | NULL | NULL | 1023820 | 100.00 | Using filesort |

+-- +

1 row in set, 1 warning (0.02 sec)

But according to the hint of the source code

DBUG_PRINT ("info", ("filesort PQ is applicable"))

DBUG_PRINT ("info", ("filesort PQ is not applicable"))

Note that PQ may be deprecated here. When to deprecate, look behind.

You can see whether PQ is enabled, that is, the abbreviation for priority queue.

You can find the instructions in trace:

[root@testmy tmp] # cat pq.trace | grep "filesort PQ is applicable"

Titled 2: | info: filesort PQ is applicable

Use the execution plan in ORACLE:

Plan hash value: 1473139430

| | Id | Operation | Name | Rows | Bytes | TempSpc | Cost (% CPU) | |

| | 0 | SELECT STATEMENT | | 100 | 77900 | | 85431 (1) |

| | * 1 | VIEW | | 100 | 77900 | | 85431 (1) |

| | * 2 | COUNT STOPKEY | | |

| | 3 | VIEW | | 718K | 524m | | 85431 (1) |

| | * 4 | SORT ORDER BY STOPKEY | | 718K | 325m | 431m | 85431 (1) |

| | 5 | TABLE ACCESS FULL | TEST10 | 718K | 325m | | 13078 (1) |

Here SORT ORDER BY STOPKEY stands for sorting to stop, but ORACLE has no source code and cannot be used for exact evidence.

Priority queue and heap sort, you can only guess that he used priority queue and heap sort

Heap sorting and priority queues

-- large top heap features (similar to small top heap, see code)

1. Complete binary tree must be satisfied.

About the complete binary tree reference

Http://blog.itpub.net/7728585/viewspace-2125889/

2. It is convenient to calculate the position of two leaf nodes according to the position of the parent node.

If the location of the parent node is iUniver 2

The left child node is I, and the right child node is iNode 1

This is the characteristic of the complete binary tree.

3. All child nodes can be regarded as a child heap, then all nodes have

Parent node > = left child node & & parent node > = right node

4. It is obvious that the largest element can be found, which is the root node of the whole heap

-- the heap needs to complete the operation

Heap sorting method is also the implementation of the optimal queue. Priority queue is obviously used in the MYSQL source code to optimize order by limit n, and this algorithm is also used to estimate max.

Of course, the premise is that the index is not used.

According to these characteristics, it is obviously another recursive heap operation.

Refer to Chapter 6 of the introduction to the algorithm, where the illustrations can be further understood. Here is a large top pile that has been constructed.

Build method: the bottom-up build heap from left to right is actually the process of constantly calling maintenance methods

Maintenance method: using the recursive step-by-step descent method for maintenance is the core content of the whole algorithm, and it is clear that any other operation of the maintenance method comes from it.

Sorting method: the largest element is put at the end, and then adjusted layer by layer.

Applications in the database:

Order by asc/desc limit n: simplified sorting, just sort the first n on it, not all sort complete, superior performance, database paging query a lot of use of this algorithm. Reference code

Max/min: a [1] is the maximum. It can only guarantee that a [1] > = a [2] & & a [1] > = a [3] can not guarantee a [3] > = a [4]. The Max value can be found after the heap is established, but MYSQL max does not use this algorithm.

I have done this in the code, and there are more detailed comments in the code, which will not be explained in detail here.

I used two arrays as test data.

Int iremiere a [11] = {0recronomy 999pyrr3, pyrrhen9, 34reparte5, 102pr 90pr 22221}; / / Test data a [0] is not used

Int b [11] = {0 # * * $$} 999 # # 999 # 2 # # 9 # # 999 # 888888 # 102 # # 90# 2222111}; / / Test data b [0] is not used

The maximum and minimum first three digits of a prime group are calculated respectively, and the MAX/ min value of b array is calculated. The results are as follows:

Gaopeng@bogon:~/datas$. / a.out

Big top pile:

Order by desc an array limit 3 result:2222 999 102

Max values b array reulst:888888

Small top pile:

Order by asc an array limit 3 result:1 2 3

Min values b array reulst:2

You can see it. No problem.

Priority queue: priority queue is different from the first-in-first-out rule of ordinary queue, but it is defined as first-out according to certain rules, such as maximum first-out or minimum first-out. This is not difficult, just like the order of the database.

Is by limit the same thing? Of course, it is done with a big top pile or a small top pile.

III. Interface of priority queue in MYSQL

The priority queue class in MYSQL is in

Class Priority_queue: public Less in priority_queue.h

He implements a lot of functions, but other functions are very simple, mainly heap maintenance.

The following is the maintenance code for the heap in the MYSQL source code

Void heapify (size_type I, size_type last)

{

DBUG_ASSERT (I)

< size()); size_type largest = i; do { i = largest; size_type l = left(i); size_type r = right(i); if (l < last && Base::operator()(m_container[i], m_container[l])) { largest = l; } if (r < last && Base::operator()(m_container[largest], m_container[r])) { largest = r; } if (largest != i) { std::swap(m_container[i], m_container[largest]); } } while (largest != i); } 可以看见实际和我写的差不多。 四、MYSQL如何判断是否启用PQ 一般来说快速排序的效率高于堆排序，但是堆排序有着天生的特点可以实现优先队列，来实现 order by limit (关于快速排序参考：http://blog.itpub.net/7728585/viewspace-2130743/) 那么这里就涉及一个问题，那就是快速排序和最优的队列的临界切换，比如 表A 100W行记录 id列没有索引 select * from a order by id limit 10; 和 select * from a order by id limit 900000,10; 肯定前者应该使用最优队列，而后者实际上要排序好至少900010行数据才能返回。 那么这个时候应该使用快速排序,那么trace信息应该为 filesort PQ is not applicable [root@testmy tmp]# cat pqdis.trace |grep "filesort PQ " T@2: | | | | | | | | | | info: filesort PQ is not applicable 那么MYSQL值确定是否使用PQ，其判定接口为check_if_pq_applicable函数， 简单的说MYSQL认为堆排序比快速排序慢3倍如下： /* How much Priority Queue sort is slower than qsort. Measurements (see unit test) indicate that PQ is roughly 3 times slower. */ const double PQ_slowness= 3.0; 所以就要进行算法的切换，但是具体算法没有仔细研究可以自行参考check_if_pq_applicable函数 至少和下面有关 1、是否能够在内存中完成 2、排序行数 3、字段数 最后需要说明一点PQ排序关闭了一次访问排序的pack功能如下： /* For PQ queries (with limit) we know exactly how many pointers/records we have in the buffer, so to simplify things, we initialize all pointers here. (We cannot pack fields anyways, so there is no point in doing lazy initialization). */ 五、实现代码，维护方法列出了2种实现，方法2是算法导论上的更容易理解 点击(此处)折叠或打开 /************************************************************************* >

File Name: heapsort.c

> Author: gaopeng QQ:22389860 all right reserved

> Mail: gaopp_200217@163.com

> Created Time: Sun 08 Jan 2017 11:22:14 PM CST

* * /

# include

# include

# define LEFT (I) I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.