Given a record and order conditions, find record(s) after or before

Question

For example, you have a list of items, sorted by priority. You have 10,000 items! If you are showing the user a single item, how do you provide buttons for the user to see the previous item or the next item (what are these items)?

You could pass the item's position to the item page and use OFFSET in your SQL query. The downside of this, apart from having to pass a number that may change, is that the database cannot jump to the offset; it has to read every record until it reaches, say, the 9001st record. This is slow. Having searched for a solution, I could not find one, so I wrote order_query.

order_query uses the same ORDER BY query, but also includes a WHERE clause that excludes records before (for next) or after (for prev) the current one.

Here is an example of what the criteria could look like (using the gem above):

p = Issue.find(31).relative_order_by_query(Issue.visible, 
      [[:priority, %w(high medium low)],
       [:valid_votes_count, :desc, sql: '(votes - suspicious_votes)'],
       [:updated_at, :desc],
       [:id, :desc]])

p.before     #=> ActiveRecord::Relation<...>
p.previous   #=> Issue<...>
p.position   #=> 5
p.next       #=> Issue<...>
p.after      #=> ActiveRecord::Relation<...>

Have I just reinvented the wheel here? I am very interested in other approaches of doing this on the backend.

Internally this gem builds a query that depends on the current record's order values and looks like:

SELECT ... WHERE    
x0 OR
y0 AND (x1 OR
        y1 AND (x2 OR
                y2 AND ...))
ORDER BY ...
LIMIT 1

Where x correspond to > / < terms, and y to = terms (for resolving ties), per order criterion.

Example query from the test suite log:

-- Current record: priority='high' (votes - suspicious_votes)=4 updated_at='2014-03-19 10:23:18.671039' id=9
SELECT  "issues".* FROM "issues"  WHERE 
  ("issues"."priority" IN ('medium','low') OR 
   "issues"."priority" = 'high' AND (
       (votes - suspicious_votes) < 4 OR 
       (votes - suspicious_votes) = 4 AND (
           "issues"."updated_at" < '2014-03-19 10:23:18.671039' OR 
           "issues"."updated_at" = '2014-03-19 10:23:18.671039' AND 
           "issues"."id" < 9)))   
ORDER BY 
  "issues"."priority"='high' DESC, 
  "issues"."priority"='medium' DESC, 
  "issues"."priority"='low' DESC, 
  (votes - suspicious_votes) DESC, 
  "issues"."updated_at" DESC, 
  "issues"."id" DESC
LIMIT 1

Answer 1

I found an alternative approach, and it uses a construct from the SQL '92 standard (Predicates 209), the row values constructor comparison predicate:

Let Rx and Ry be the two row value constructors of the comparison predicate and let RXi and RYi be the i-th row value constructor elements of Rx and Ry, respectively. "Rx comp op Ry" is true, false, or unknown as follows:

• "x = Ry" is true if and only if RXi = RYi for all i.
• "x <> Ry" is true if and only if RXi <> RYi for some i.
• "x < Ry" is true if and only if RXi = RYi for all i < n and RXn < RYn for some n.
• "x > Ry" is true if and only if RXi = RYi for all i < n and RXn > RYn for some n.

I found an example in this article by Markus Winand. Row value constructor comparison predicate can be used like this:

SELECT *
  FROM sales
 WHERE (sale_date, sale_id) < (?, ?)
 ORDER BY sale_date DESC, sale_id DESC

This is roughly equivalent to this query:

SELECT *
  FROM sales
 WHERE sale_date < ? OR (sale_date = ? AND sale_id < ?)
 ORDER BY sale_date DESC, sale_id DESC

The first caveat is that to use this directly all the order components have to be in the same direction, otherwise more fiddling is required. The other being that, despite being standard, row values comparison predicates are not supported by most databases (does work on postgres).