[HN Gopher] Efficient Pagination Using Deferred Joins
       ___________________________________________________________________
        
       Efficient Pagination Using Deferred Joins
        
       Author : aarondf
       Score  : 21 points
       Date   : 2022-01-17 17:37 UTC (1 days ago)
        
 (HTM) web link (aaronfrancis.com)
 (TXT) w3m dump (aaronfrancis.com)
        
       | grogers wrote:
       | Please don't do this.
       | 
       | 1. If you are scanning the (clustered) primary key, this is no
       | better than "normal" offset pagination. You need another index
       | with a smaller record size, without all the ancillary fields of
       | the PK, to make this have a benefit (since it'll read less data
       | than reading the primary key).
       | 
       | 2. It's still O(n^2) to page through n rows. Even if it's a
       | constant factor better, it still doesn't scale well. Offset
       | pagination works fine until it doesn't, and it'll fail
       | spectacularly when it does.
       | 
       | 3. You still get duplicated/missed elements in your response when
       | things are added/removed with smaller keys than your current
       | page.
        
         | deburo wrote:
         | What's the alternative?
         | 
         | I hate pagination, nothing feels efficient to me. Fortunately,
         | I've never worked on anything that required scale hehe..
        
           | taeric wrote:
           | I thought best practice was some form of key based
           | pagination. If you must keep things in numbered pages and
           | want to allow skipping to page x of y, then you are backed
           | into a realized view that includes the page numbers in the
           | data, at some level. You either build that on the fly every
           | time you do a query, or you prebuild it.
           | 
           | (Note, I'm not positive my thought here is accurate.)
        
         | taeric wrote:
         | I was curious how this method avoided the wall you will hit on
         | scanning. Answer appears to be that it doesn't?
        
           | nhoughto wrote:
           | Yeah it doesn't, the mistake is thinking the "select *" is
           | the expensive bit, for limit 15 it's cheap, it's the offset
           | 150000 that is expensive deferred or not.
        
         | srcreigh wrote:
         | How is it n^2?
         | 
         | I can see how the DB would need to scan the index from the left
         | side to arrive at the correct offset value O(n). But once it
         | gets there, it should be able to load 15 rows from primary
         | storage.
         | 
         | (FWIW in postgres the primary key index is a secondary index.)
         | 
         | I do agree that "deferred join" is no better than the first
         | option in theory.
         | 
         | How does your point #3 work? It seems to assume the DB tries to
         | guess how many rows are in a single page in order to implement
         | OFFSET. This seems like an obvious bug that would be long
         | fixed.
        
       ___________________________________________________________________
       (page generated 2022-01-18 23:01 UTC)