How to implement random extraction in MySQL

1. Introduction

Now there is a requirement to randomly select three words at a time from a word list.

The table creation statement of this table is as follows:

mysql> Create table 'words'(
    'id' int(11) not null auto_increment;
    'word' varchar(64) default null;
    primary key ('id')
) ENGINE=InnoDB;

Then we insert 10,000 rows of data into it. Next let's see how to randomly select 3 words from it.

2. Memory temporary table

First of all, we usually think of using order by rand() to implement this logic:

mysql> select word from words order by rand() limit 3;

Although this sentence is very simple, but the execution The process is more complicated. We use explain to see the execution of the statement:

Using temporary in the Extra field indicates that a temporary table needs to be used, and Using filesort indicates that sorting is required. That is to say, sorting operation is required.

For InnoDB tables, performing full field sorting can reduce disk access, so it will be preferred.

#For memory tables, the table return process simply directly accesses the memory to obtain the data based on the location of the data rows, and does not result in multiple disk accesses at all. . So at this time MySQL will give priority to rowid sorting.

Let’s sort out the execution process of this statement:

• Create a temporary table, this table Using the memory engine, there are two fields in the table. The first field is of double type, marked as R, and the second field is of varchar(64) type, marked as W. And this table has no index.

• From the words table, take out all words in primary key order. For each word, call the rand() function to randomly generate a random decimal number greater than 0 and less than 1, and store the random decimal number and the word in the R and W fields of the temporary table respectively.

• The next step is to sort according to field R

• Initialize sort_buffer. sort_buffer includes a double type and an integer field.

• Take out the R value and position information row by row from the temporary memory table, and store them in the two fields of sort_buffer respectively.

• sort_buffer is sorted according to the R value

• After the sorting is completed, the location information of the first three results is taken out, and the corresponding information is taken out from the memory temporary table The word is returned to the client.

The process diagram is as follows:

The location information mentioned above is actually the location of the row, that is, This is the rowid we mentioned before.

For the InnoDB engine, there are two processing methods for tables with or without primary keys:

• For InnoDB tables with primary keysFor example, this rowid is the primary key id

• For InnoDB tables without primary keys, this rowid is generated by the system and is used to identify different rows .

Therefore, order by randn() uses a memory temporary table, and the sorting method of the memory temporary table uses the rowid sorting method.

3. Disk temporary table

Not all temporary tables are memory temporary tables. The tmp_table_size configuration limits the size of the memory temporary table. If this size is exceeded, the disk temporary table will be used. The InnoDB engine uses disk temporary tables by default.

4. Priority queue sorting algorithm

After MySQL5.6, the priority queue sorting algorithm was introduced. This algorithm does not require the use of temporary files. The original merge sort algorithm requires the use of temporary files.

Because when you use the merge algorithm, you actually only need to get the top 3, but if you run out of merge sort, the whole thing is already in order, causing a waste of resources.

The priority queue sorting algorithm can only take the top three. The execution process is as follows:

• For these 10,000 (R, rowid) to be sorted, the top three are taken first. Three rows are constructed into a heap, and the largest value is placed on the top of the heap;

• Take the next row (R’, rowid’) and compare it with the largest R in the current heap. If R’ is less than R, remove (R, rowid) from the heap and replace it with (R’, rowid’).

• Repeat the above process.

The process is shown in the figure below:

But when the limit number is relatively large, it is more difficult to maintain the heap, so it will Use the merge sort algorithm.

The above is the detailed content of How to implement random extraction in MySQL. For more information, please follow other related articles on the PHP Chinese website!