API: Let tie breaker sort direction match global ordering
Most API endpoints add a "tie breaker" to the order. That is - unless we already order by id
- we add id DESC
to any global order to make sure we order by something unique too. This leads to consistent ordering results, whereas without the tie breaker, the order would only be partial for non-unique order_by
fields.
The tie breaker looks like so:
def order_options_with_tie_breaker
order_options = { params[:order_by] => params[:sort] }
order_options['id'] ||= 'desc'
order_options
end
Now coming from !22623 (merged), I suspect this pattern forces us to create two indexes if we optimally wanted to support the ordering. Let's look at an example:
Let's look at a query for the first page of GET /api/v4/projects?order_by=created_at&sort=desc
SELECT
"projects".*
FROM
"projects"
WHERE
"projects"."visibility_level" = 20
AND "projects"."pending_delete" = FALSE
ORDER BY
"projects"."created_at" DESC,
"projects"."id" DESC
LIMIT 20 OFFSET 0;
This nicely uses the existing index with a backward scan. Note we order by DESC, DESC
and the existing index is ordered by ASC, ASC
, so this is the exact opposite. This allows for the backwards scan: https://explain.depesz.com/s/760Tc
Let's try this for sort=asc
:
SELECT
"projects".*
FROM
"projects"
WHERE
"projects"."visibility_level" = 20
AND "projects"."pending_delete" = FALSE
ORDER BY
"projects"."created_at" ASC,
"projects"."id" DESC
LIMIT 20 OFFSET 0;
Note that now we order by ASC, DESC
now and that is incompatible with any (forward/backward) scan on the index with order asc, asc
. Hence this results in reading all the data from the index and sorting it on the fly: https://explain.depesz.com/s/H1rE
There are two ways to address this:
- Create two indexes per every sort direction, example: !22623 (merged)
- Let the tie breaker sort order match whatever the global sort order is.
Change-wise, this is as simple as:
def order_options_with_tie_breaker
order_options = { params[:order_by] => params[:sort] }
order_options['id'] ||= params[:sort] || 'desc'
order_options
end
This leads to always having either ASC, ASC
or DESC, DESC
directions for the ordering. This can be satisfied by one index only.
What I'm not sure about is whether or not the change in behavior is something we can just do in a minor release or something we may need to announce better. I don't see us documenting the behavior of the tie breaker anywhere though, so it might just be fine.