Boosting Performance of Order by Limit Queries
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Alternative Title |
| |
| Title of Series | ||
| Number of Parts | 490 | |
| Author | ||
| License | CC Attribution 2.0 Belgium: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/46953 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
FOSDEM 2020103 / 490
4
7
9
10
14
15
16
25
26
29
31
33
34
35
37
40
41
42
43
45
46
47
50
51
52
53
54
58
60
64
65
66
67
70
71
72
74
75
76
77
78
82
83
84
86
89
90
93
94
95
96
98
100
101
105
106
109
110
116
118
123
124
130
135
137
141
142
144
146
151
154
157
159
164
166
167
169
172
174
178
182
184
185
186
187
189
190
191
192
193
194
195
200
202
203
204
205
206
207
208
211
212
214
218
222
225
228
230
232
233
235
236
240
242
244
249
250
251
253
254
258
261
262
266
267
268
271
273
274
275
278
280
281
282
283
284
285
286
288
289
290
291
293
295
296
297
298
301
302
303
305
306
307
310
311
315
317
318
319
328
333
350
353
354
356
359
360
361
370
372
373
374
375
379
380
381
383
385
386
387
388
391
393
394
395
397
398
399
401
409
410
411
414
420
421
422
423
424
425
427
429
430
434
438
439
444
449
450
454
457
458
459
460
461
464
465
466
468
469
470
471
472
480
484
486
487
489
490
00:00
Mathematical optimizationSoftware developerLimit (category theory)Order (biology)Query languageDifferent (Kate Ryan album)Order (biology)Limit (category theory)UsabilitySoftware developerMathematical optimizationQuery languageComputer animation
00:35
Limit (category theory)Order (biology)Query languagePrice indexComputer fileRange (statistics)Subject indexingRow (database)Table (information)Subject indexingOrder (biology)CASE <Informatik>Rule of inferenceClosed setKey (cryptography)Game theoryPort scannerReading (process)Cartesian coordinate systemMereologyLimit (category theory)Range (statistics)QuicksortComputer file2 (number)Query languageComputer animation
01:38
Order (biology)Subject indexingMiniDiscLimit (category theory)Port scannerPrice indexStreaming mediaCondition numberFunction (mathematics)Order (biology)Subject indexingRow (database)Table (information)Limit (category theory)Computer fileCASE <Informatik>Function (mathematics)Keyboard shortcutLogical constantQuicksortMereology2 (number)NumberControl flowBuffer solutionLattice (order)Condition numberRule of inferenceClosed setTelebankingComputer animation
04:28
Function (mathematics)Limit (category theory)Order (biology)Mathematical optimizationLattice (order)ZugangsverfahrenQuicksortElement (mathematics)Lattice (order)Table (information)Order (biology)CASE <Informatik>Subject indexingLimit (category theory)PlanningStrategy gamePropagatorRow (database)Type theoryMathematical optimizationEqualiser (mathematics)Query languageKeyboard shortcutComputer fileComputer animation
05:56
Order (biology)Lattice (order)Limit (category theory)Information managementPlanningSubject indexingOrder (biology)Table (information)Computer fileKeyboard shortcutMathematical optimizationRow (database)QuicksortCASE <Informatik>Strategy game2 (number)Run time (program lifecycle phase)Function (mathematics)Limit (category theory)NeuroinformatikComputer clusterRight anglePoint (geometry)Graph coloringLevel (video gaming)Multiplication signComputer animation
07:32
Mathematical optimizationSign (mathematics)Limit (category theory)Mathematical optimizationComputer animation
07:47
Mathematical optimizationKeyboard shortcutPartial derivativeFraction (mathematics)Limit (category theory)Order (biology)Military operationEstimationLattice (order)Computer configurationExtension (kinesiology)Materialization (paranormal)Table (information)Loop (music)Function (mathematics)Level (video gaming)Limit (category theory)WhiteboardOrder (biology)Equaliser (mathematics)Closed setFunction (mathematics)PropagatorThomas BayesPropositional formulaPlanningInstance (computer science)Table (information)Operator (mathematics)Subject indexingLattice (order)Row (database)Fraction (mathematics)NumberRing (mathematics)Identity managementWechselseitige InformationCondition numberGodEstimatorOcean currentWell-formed formulaCodeQuicksortKeyboard shortcutComputer file
11:35
Condition numberTable (information)Limit (category theory)Order (biology)Limit (category theory)Function (mathematics)Table (information)QuicksortMereologyLattice (order)Buffer solutionResultantRow (database)Computer fileCondition numberStability theoryEvent horizonWebsiteSet (mathematics)Computer animation
12:44
Order (biology)Limit (category theory)Convex hullTable (information)Key (cryptography)Lattice (order)Prime idealDiscrete element methodCondition numberHistogramSelectivity (electronic)Predicate (grammar)Table (information)Computer filePlanningRow (database)Condition numberKey (cryptography)Selectivity (electronic)Subject indexingPredicate (grammar)HistogramMereologyMathematical optimizationRun time (program lifecycle phase)Limit (category theory)Order (biology)Field (computer science)EstimatorQuicksortResultantCASE <Informatik>Query languagePhysical lawHypermediaWorkstation <Musikinstrument>BitMixed realityFault-tolerant systemWebsiteIdentity managementComputer animation
16:22
Multiplication signSubject indexingOrder (biology)CASE <Informatik>Table (information)Computer animation
18:07
Prime idealOrder (biology)Limit (category theory)Lattice (order)SummierbarkeitLipschitz-StetigkeitRule of inference1 (number)CASE <Informatik>Mathematical optimizationEstimatorCondition numberDecision theoryHypermediaOrder (biology)Right angleSelectivity (electronic)Table (information)Row (database)Computer animation
18:56
Point cloudOpen source
Transcript: English(auto-generated)
00:05
Hello everyone, I will be talking about how to improve the performance of order by limit queries in MariaDB and what is what has been the history of order by limit queries in both MariaDB and MySQL. I work as a optimizer developer in MariaDB corporation,
00:28
I have been involved in the company for the last 3 years almost. So, let us start. So, now this part would be the history and then I will talk what is new in MariaDB 10.5. So,
00:44
to handle order by limit queries what are the ways which we can do it. One thing is that we use an ordered index. The ordered index can be used in 3 ways, you could have a ref axis where you could have some key part equal to constant and then with the remaining key parts the rows
01:03
would be ordered. Something similar would also happen with range scan and with index scan you cannot have with index and you cannot have an equality. So, it would just be a normal index scan on the index. Second case would be file sort, file sort would have 2 ways how we have
01:25
it either you sort the first table and then do the join with the remaining tables or you put the entire join inside a temporary table and then sort the temporary table. So, this is the case the first case that we will use with an ordered index. So,
01:47
the records from this table would be ordered by the order by clause if the index can resolve the order by clause and then you perform the join with the remaining tables. The important thing is while doing the join you cannot use join buffering an example would be because
02:05
join buffering breaks the ordering. So, you have to make sure that join buffering is disabled. Second would be if you have a descending clause in the order by clause then you have to make sure that descending is for all the key parts of the index that is mentioned.
02:25
Also with this approach you can shortcut the join execution you do not need to compute the entire join you can stop as soon as the you get the number of records mentioned in the limit.
02:42
Now, this would be the second case where you sort where you apply file sort on the first non constant table. So, here you read from the table T 1 and pass it to file sort and then you read the output of file sort and then perform the remaining join. So, it is almost
03:07
similar to how we have with an ordered index that you can again you cannot use join buffering. Another important thing would be any condition that is dependent on the first table would be computed before sending the output to file sort. To see if this approach is working in explain
03:29
for example, you will see using file sort in the first column of the first row in explain. And again this is also another way in which you will be able to shortcut the execution with
03:42
limit because the rows would be ordered already. Now, this comes the third part where we try to perform the entire join first and then put the records inside the temporary table and then
04:01
pass the temporary table to file sort and then we get the ordered output. To apply the limit you cannot shortcut the join execution you have to compute the entire join and then only when you do file sort then you can shortcut the execution of file sort that you just as
04:22
soon as you get the limit records you use tell the file sort to stop and you are done. With this case there is no issue with using join buffering or any type of join order is not allowed, but the main drawback with for order by limit queries is that limit cannot
04:44
be applied before and you have to compute the entire join and only then you can apply the limit. So, this will this could be very inefficient for smaller limits and in explain the first row again shows using temporary using file sort which means that you are
05:04
using temporary table and then doing file sort. Now, what all we do we currently not have in the order by limit optimizer we currently do not take the cost of sorting limit is not taken into account and the only way in which we are able to shortcut the join execution is after
05:27
a join order is picked we check if a use of an index can be done to shortcut the join execution or if there is something like equality propagation you could do. So, that you could just file sort by the first table that you pick by the join order
05:44
here, but the join planner does not take limit into a consideration these are all the things done after the join planner has picked the join plan. So, here is an example we have a order by a particular column on which we have an index the join optimizer
06:07
picks a strategy where we use to compute the entire join and then do file sort which has an executions time of 25.2 seconds. Now, if I try to force a particular join
06:23
order using straight join then you can see that here I T fact is using an index on column 1 to do the join execution and the execution time is like 30 milliseconds. So, if the join optimizer had any idea that with this index we could shortcut the join execution
06:45
we could have come up with a better execution plan. Now, here is another example where you have again order by T 0 dot d, but you do not have an index on this column the join
07:04
optimizer again picked an approach where it was using temporary table plus file sort. Now, if I try to force the join order now in this case it is using file sort on the first table and again it is because it is using file sort on the first table the output is
07:21
ordered it can just go ahead and shortcut the execution as soon as it gets the limit records no need to compute the entire join again. Now, what is new in MariaDB 10.5 is we are coming with a cost based optimization where the join planner would take into
07:42
consideration both the cost of sorting and the limit. So, motivation wise both pushing the limit and cost of sorting and again the main thing that I have been emphasizing we want to shortcut the join execution for limit. So, to consider the limit we try to push
08:08
the limit now how the limit is pushed is we try to find a join prefix that can resolve the order by clause that is the prime condition that you can sort the prefix with the order
08:24
by clause and then you can just push the limit. So, inside the join planner code we try we apply the sort operation here and then we push the limit. So, how is push
08:40
the limit calculated? So, what exactly is meant by push the limit is you find a prefix by which ordering can be resolved and then the records in the prefix when you push the limit you will only read a fraction of those records and this fraction
09:00
is how this fraction is how we consider by taking limit into account. So, this is the prefix which can resolve the order by clause this is the total join cardinality and then you have limit. So, this is the number of this formula would give us the number of records that we would read from the prefix that can resolve the order by clause.
09:24
And so, to push the limit first you need the estimate of join cardinality. So, we run the join planner once to get the estimate of join cardinality currently. Also you have access methods like indexes that I was talking about that already have the
09:46
ordering in that have already all the records ordered. So, these are also considered during the join planner stage. Now, this will be a bit technical. So, for each join prefix you have
10:04
two conditions if that prefix can resolve the order by clause you can either push the limit at that very instance or you can extend the prefix by another table and then push the limit. Why do we do this is we want to consider all possible plans where we can push the limit.
10:23
Also, equality propagation earlier equality propagation is always done after the join planner has picked the plan. Now, equalities are propagated before. So, if you have a join prefix like this T 2 comma T 3 and you have an order by clause by T 1 dot a
10:41
and there is an equality. So, we would consider pushing the limit both after this plan and after this plan. So, the equalities of the where clause are propagated and considered by the join planner. Now, how does the join execution work? So, as soon as we have a prefix that can
11:03
resolve the order by clause we try to materialize the prefix and put the records inside a temporary table then we sort the materialized table with the order by clause and then from the output of file start we start reading one by one and then we join with the remaining tables and again
11:25
the execution again stops as soon as the records are found. So, again in by this we are not computing the entire join. So, this is how the execution path exactly looks you have
11:41
tables in the prefix, you materialize the result and put them inside the short nest. Join buffering is allowed for all these parts because these are coming before we are performing the order by clause plus conditions the conditions that are dependent only on these
12:01
tables are checked beforehand rest are attached to the later tables. So, the shortness you have you push send the records to file sort and then you start reading file sorts output and join
12:20
with the remaining tables. Again now it is similar to the example where we had we had file sort on the first table and then we were doing the join. So, again no join buffering is allowed over here and the execution will stop as soon as the limit records are reached.
12:46
So, here is an example where we will be using a short nest. So, you have an order by clause on two tables. So, if you see in the explain it shows a short nest here which is materialized
13:01
result of nation and customer table and so, this is and then you can see that we are applying file sort on the short nest. Another interesting part is if you can if you look at this condition for orders tables it will not know anything about the customer key.
13:24
So, it needs to refer to the fields of the short nest and not of the base table itself because the base tables are now no now not at all over there they are all referring to the shortness table fields. So, this was one of the examples that I was demonstrating
13:47
earlier where I was showing the limitation. So, we have again the same case where we have a key on column 1 and this was earlier using temporary table plus file sort, but after this optimization it is able to use an index on column 1 to do the joint execution
14:09
and it provides a 1900 x speed up for this case. Also here is another query where with the dbt 3 data set which I have created here.
14:26
So, again the execution time which was picking temporary table plus file sort earlier is now picking an index to do the joint execution and short cutting the joint execution as
14:41
soon as the limit records are reached and again providing a significant speed up. So, the most important part for the optimizer to pick any plan is the selectivity of the conditions. This approach that MariaDB has taken for order by limit optimization
15:06
heavily heavily depends on the selectivity of the conditions. So, if someone wants to use it I would suggest at least use histograms to provide the selectivities to the optimizer because otherwise the estimates can vary a lot and when we push the limit then that can give
15:32
us plans that are not that good. Also another limitation is that we have few predicates for which selectivity is not known. So, what we try to do is we predict
15:46
the selectivity as 100 percent, but we have discussed this internally in the team to may be add some penalty for such cases because if this condition is highly selective then using a shortness or using this new optimization can be harmful for us.
16:04
And again this part that the estimate of joint cardinality are very pessimistic we over predict everything. So, again when we push the limit then our estimates can be very optimistic instead of being pessimistic yeah that is all. Thank you questions.
17:19
. No, I did not get the complete question
17:22
can you repeat the question. .
17:51
No but the where clause would be evaluated beforehand before you do the order by clause if it is if the tables are inside the shortness that is you have it may be the case that the
18:17
conditions you have in the shortness more rows and then when you are joining with the remaining
18:22
ones you are not finding enough rows to match that may be an overestimate yes, but if you give the optimizer the right selectivity estimates I think so it can make a smart decision and may include the order table inside the shortness yeah if for such cases then I do not think
18:42
so this optimization would work that well yeah.