3 ms·

Feels like something the query planner should do to me… I wonder if this works on PG too, recently had some performance issues exactly due to large offsets :)

oconnore 4y ago
It seems like the query planner could perform this optimization, but also it seems like the index could maintain cardinality data to avoid requiring a scan/offset of ids. If the index had cardinality metadata, it could jump directly to the leaf node containing the first row in the result set.
- Sesse__ 4y ago
  > If the index had cardinality metadata, it could jump directly to the leaf node containing the first row in the result set. It's difficult to maintain cardinality metadata in the face of MVCC, even for the table as a whole. Page-level or similar on an index would be even harder.
Sesse__ 4y ago
In general, you cannot push a LIMIT and OFFSET down through a join, since the result is not guaranteed to be the same. (I have no idea what this gem does about that, but maybe it has some sort of 1:1 guarantee through foreign key information, or maybe it just doesn't care about getting too few rows if there are no matching tables in a join.) The linked blog post seems to indicate that you can satisfy an OFFSET purely using an index, which generally isn't the case. If you have ORDER BY id LIMIT 10 OFFSET 100000, the planner has to fetch 100010 rows in most databases that I know of.
- thomasmg 4y ago
  Yes, using OFFSET for pagination is often problematic. The best alternative IMHO is "keyset pagination", but it requires a bit of work. See https://use-the-index-luke.com/no-offset https://use-the-index-luke.com/no-offset
- jsmith99 4y ago
  There's a bit more explanation here https://dba.stackexchange.com/a/59490/167040 https://dba.stackexchange.com/a/59490/167040 about why the trick works. MySQL can use an index for OFFSET but normally doesn't due to using early row lookups.
  - Sesse__ 4y ago
    To be clear: MySQL cannot use an index to directly seek past the first OFFSET rows; you still have O(n) behavior for OFFSET n. But you can use a covering index scan for the rows that you skip, which especially for InnoDB is somewhat cheaper than getting the full row. I guess this is what the technique is about. Edit: Indeed, this technique is seemingly for converting a regular query to a self-join, ie. a LIMIT m OFFSET n => (a LIMIT m OFFSET n) JOIN a, which is allowed as long as you have a unique constraint on the column you're joining on. I had assumed it actually wanted to convert something that was already a join.

oconnore 4y ago

It seems like the query planner could perform this optimization, but also it seems like the index could maintain cardinality data to avoid requiring a scan/offset of ids. If the index had cardinality metadata, it could jump directly to the leaf node containing the first row in the result set.

Sesse__ 4y ago
> If the index had cardinality metadata, it could jump directly to the leaf node containing the first row in the result set. It's difficult to maintain cardinality metadata in the face of MVCC, even for the table as a whole. Page-level or similar on an index would be even harder.

Sesse__ 4y ago

In general, you cannot push a LIMIT and OFFSET down through a join, since the result is not guaranteed to be the same. (I have no idea what this gem does about that, but maybe it has some sort of 1:1 guarantee through foreign key information, or maybe it just doesn't care about getting too few rows if there are no matching tables in a join.) The linked blog post seems to indicate that you can satisfy an OFFSET purely using an index, which generally isn't the case. If you have ORDER BY id LIMIT 10 OFFSET 100000, the planner has to fetch 100010 rows in most databases that I know of.

thomasmg 4y ago
Yes, using OFFSET for pagination is often problematic. The best alternative IMHO is "keyset pagination", but it requires a bit of work. See https://use-the-index-luke.com/no-offset https://use-the-index-luke.com/no-offset
jsmith99 4y ago
There's a bit more explanation here https://dba.stackexchange.com/a/59490/167040 https://dba.stackexchange.com/a/59490/167040 about why the trick works. MySQL can use an index for OFFSET but normally doesn't due to using early row lookups.
- Sesse__ 4y ago
  To be clear: MySQL cannot use an index to directly seek past the first OFFSET rows; you still have O(n) behavior for OFFSET n. But you can use a covering index scan for the rows that you skip, which especially for InnoDB is somewhat cheaper than getting the full row. I guess this is what the technique is about. Edit: Indeed, this technique is seemingly for converting a regular query to a self-join, ie. a LIMIT m OFFSET n => (a LIMIT m OFFSET n) JOIN a, which is allowed as long as you have a unique constraint on the column you're joining on. I had assumed it actually wanted to convert something that was already a join.