Improving the performance of LIMIT,OFFSET in MySQL
Tags: mysql
Published: 2024-03-17 14:09:27

When using medium or large datasets, the use of LIMIT can be a performance bottle neck.

The reason it's a bottle neck is to do with how LIMIT works with OFFSET. 

LIMIT is not able to just retrieve the number of rows you ask for, it retrieves all rows up until it has enough data to return the rows being asked for, it then discards everything not needed. 

In the query below, 20 rows will be retrieved and 10 returned in the result set.

```SQL
SELECT *
FROM salaries
LIMIT 10
OFFSET 10
```

In the query below, 800010 rows are retrieved and 10 returned in the result set.

```SQL
SELECT *
FROM salaries
LIMIT 10
OFFSET 800000
```

If your website uses Previous/Next navigation to move through the pages of data, then one option is to return a cursor with your result set.

**What is a cursor?**

A cursor is an indicator to tell the query where in the result set the data needs to continue searching from.

It's important to remember that because data doesn't always return the same order each time, that the data needs to be ordered in a way that will make it consistent. 

A good way to do this is to include an ORDER BY in the query.

```SQL
SELECT *
FROM salaries
ORDER BY id
LIMIT 10
OFFSET 10
```

Once you receive the data from this query, the next query might be:

```SQL
SELECT *
FROM salaries
ORDER BY id
LIMIT 10
OFFSET 20
```
Where the offset is now 20 instead of 10 to retrieve the next set of 10 rows. 

Using a cursor here can help improve performance. To achieve this, your code would need to send the last read ID, so the new query can take that into account

```SQL
SELECT *
FROM salaries
WHERE id > 10
ORDER BY id
LIMIT 10
```

This will be especially beneficial when the page offset is large. Instead of retrieving 800000 rows and returning 10 rows, the query is only retrieves 10 rows. 

```SQL
SELECT *
FROM salaries
WHERE id > 800000
ORDER BY id
LIMIT 10
```

Cursors are not for every situation, sometimes you may need to navigate directly to page 10 of the result set, in a scenario like this, a cursor won't work, you won't know what the last ID read is. 

One way to improve a query like this is to use a _deferred join_.

**Deferred Joins**

Deferred joins are used to prefetch a dataset before retrieving all the data needed. 

To compare the query execution time with a standard LIMIT/OFFSET query, I am using the following base query.

```SQL
SELECT *
FROM salaries
ORDER BY salary, id
LIMIT 100
OFFSET 10
```

In the query above the average time to run on a table with about 1 million records was: **0.095** Seconds.

**Creating a deferred join.**

To create a deferred join, most of the work the query does is moved into a subquery that returns the PRIMARY KEY or UNIQUE indexed field, in this case the `id` field.  It just needs to be a field that can self join without generating multiple rows in the returned dataset.

This reduces the number of rows the outer query needs to retrieve before returning all the data required. 

It's no longer retrieving all the table columns and performing the LIMIT/OFFSET and discard on all the data, it's only doing that work on the `id` field data.

An added benefit to this is that the table index can be better utilized. 

Under some circumstances you may be able to use a covering query in the sub query, which can be more performant.

Below is the deferred query method, INNER JOINING the id field returned from the subquery with the main data, only those 10 rows of data will be retrieved and returned in the result set. 

```SQL
SELECT *
FROM salaries
  INNER JOIN (
    SELECT id
    FROM salaries
    ORDER BY salary, id
    LIMIT 100
    OFFSET 10
  ) s USING (id)
```

The average time for this query was: **0.0901** Seconds

While the deferred query was faster, it is not significantly  faster when the OFFSET is very small. 

Lets change the OFFSET to a much larger number

```SQL
SELECT *
FROM salaries
ORDER BY salary, id
LIMIT 100
OFFSET 800000
```

This time the average time for the query was: **0.3337** Seconds.

What about with a deferred join? 

```SQL
SELECT *
FROM salaries
  INNER JOIN (
    SELECT id
    FROM salaries
    ORDER BY salary, id
    LIMIT 100
    OFFSET 800000
  ) s USING (id)
```

For this query the time taken was: **0.1757** Seconds.

The deferred query method was about **2x faster** than the standard query.

---

Like anything in SQL, Deferred joins are not always going to be the best choice, but they can provide a lot of benefits to a LIMIT/OFFSET query.

The more rows your query needs to traverse to reach the data it needs to return, the larger the savings will be, but even with a small offset there was still benefit to using a deferred join.