title: Optimizing queries for the next and previous element
body: <p>I am looking for the best way to retrieve the next and previous records of a record without running a full query. I have a fully implemented solution in place, and would like to know whether there are any better approaches to do this out there. </p>
  
  <p>Let's say we are building a web site for a fictitious greengrocer. In addition to his HTML pages, every week, he wants to publish a list of special offers on his site. He wants those offers to reside in an actual database table, and users have to be able to sort the offers in three ways.</p>
  
  <p>Every item also has to have a detail page with more, textual information on the offer and "previous" and "next" buttons. The "previous" and "next" buttons need to point to the neighboring entries <em>depending on the sorting the user had chosen for the list</em>.</p>
  
  <p><a href="https://i.stack.imgur.com/5LMXm.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/5LMXm.gif" alt="alt text"></a><br>
  <sub>(source: <a href="http://www.pekkagaiser.com/stuff/Sort.gif?" rel="nofollow noreferrer">pekkagaiser.com</a>)</sub>  </p>
  
  <p>Obviously, the "next" button for "Tomatoes, Class I" has to be "Apples, class 1" in the first example, "Pears, class I" in the second, and none in the third.</p>
  
  <p>The task in the detail view is <strong>to determine the next and previous items without running a query every time</strong>, with the sort order of the list as the only available information (Let's say we get that through a GET parameter <code>?sort=offeroftheweek_price</code>, and ignore the security implications).</p>
  
  <p>Obviously, simply passing the IDs of the next and previous elements as a parameter is the first solution that comes to mind. After all, we already know the ID's at this point. But, this is not an option here - it would work in this simplified example, but not in many of my real world use cases.</p>
  
  <p>My current approach in my CMS is using something I have named "sorting cache". When a list is loaded, I store the item positions in records in a table named <code>sortingcache</code>.</p>
  
  <pre><code>name (VARCHAR)             items (TEXT)
  
  offeroftheweek_unsorted    Lettuce; Tomatoes; Apples I; Apples II; Pears
  offeroftheweek_price       Tomatoes;Pears;Apples I; Apples II; Lettuce
  offeroftheweek_class_asc   Apples II;Lettuce;Apples;Pears;Tomatoes
  </code></pre>
  
  <p>obviously, the <code>items</code> column is really populated with numeric IDs. </p>
  
  <p>In the detail page, I now access the appropriate <code>sortingcache</code> record, fetch the <code>items</code> column, explode it, search for the current item ID, and return the previous and next neighbour.</p>
  
  <pre><code>array("current"   =&gt; "Tomatoes",
        "next"      =&gt; "Pears",
        "previous"  =&gt; null
        );
  </code></pre>
  
  <p>This is obviously expensive, works for a limited number of records only and creates redundant data, but let's assume that in the real world, the query to create the lists is very expensive (it is), running it in every detail view is out of the question, and <em>some</em> caching is needed. </p>
  
  <p><strong>My questions:</strong></p>
  
  <ul>
  <li><p>Do you think this is a good practice to find out the neighbouring records for varying query orders?</p></li>
  <li><p>Do you know better practices in terms of performance and simplicity? Do you know something that makes this completely obsolete? </p></li>
  <li><p>In programming theory, is there a name for this problem?</p></li>
  <li><p>Is the name "Sorting cache" is appropriate and understandable for this technique? </p></li>
  <li><p>Are there any recognized, common patterns to solve this problem? What are they called?</p></li>
  </ul>
  
  <blockquote>
    <p><strong>Note:</strong> My question is not about building the list, or how to display the detail view. Those are just examples. My question is the <strong>basic functionality</strong> of determining the neighbors of a record when a re-query is impossible, and the fastest and cheapest way to get there.</p>
  </blockquote>
  
  <p>If something is unclear, please leave a comment and I will clarify.</p>
  
  <blockquote>
    <p>Starting a bounty - maybe there is some more info on this out there. </p>
  </blockquote>