52

10K users have the ability to see the full history of reviews (e.g. suggested edits history - users with less than 10K will just see their own reviews), on all queues - from the very first review ever.

However, to get to that first review I had to wait no less than 10 full seconds (OK, 9.76 don't kill me) which is eternity in terms of Stack Overflow.

The first history page of all queues is super fast, less than a second on all queues. But with each page, you pay with milliseconds - no formula I could find, but for example page 10,000 loads for 2.66 seconds:

Page 25,000? Wait 6.32 seconds:

And of course, what started this all:

It's pretty consistent on all queues and not browser specific, the load time is server side.

Can this please be fixed or at least improved?

  • 11
    [status-reproduced], +1 – Doorknob Oct 17 '13 at 12:26
  • 3
    I always believed it is normal that less used data is not in any of caches down the line and ends up on some forgotten corner of the HDD. – Mołot Oct 17 '13 at 12:36
  • FWIW, at Programmers (where there are about 250x less suggested edits, browsing the history is fast up to the last page – gnat Oct 17 '13 at 12:37
  • 4
    Http-Server-side paging instead paging on the database? – Johannes Kuhn Oct 17 '13 at 12:37
  • 6
    My thought was a database that skips poorly; I can't imagine the SO devs are silly enough to actually fetch all of the results to do the paging. – Wooble Oct 17 '13 at 12:39
  • @gnat good to know, so it's specific to Stack Overflow? – Shadow The Curly Braced Wizard Oct 17 '13 at 12:41
  • 5
    @ShaWizDowArd At least you didn't need to queue your request so that a robot could fetch a tape from a storage room and insert it into streamer for you. (Not quite a joke, seen setup like that in modern environment - just much more data than here.) – Mołot Oct 17 '13 at 12:45
  • 1
    @ShaWizDowArd yes looks SO-specific – gnat Oct 17 '13 at 12:56
  • Ha, try loading the all-time moderator stats. Usually takes 2 or 3 page loads... – animuson Oct 17 '13 at 16:50
  • 5
    consider editing your post to replace or complement boring "10 full seconds" with much more colorful "about three nanocenturies" – gnat Oct 17 '13 at 21:09
  • 3
    The short answer is: the query takes that long to run - it's optimized for recent results, not ancient ones. Is this really worth optimizing for? – Shog9 Oct 31 '13 at 23:30
  • @Shog well, if it can be somehow cached then all is good. How exactly only the devs can tell. Ideal situation is a site where all its pages are loading fast... I don't expect all pages to take <1s to load but 10 seconds are just too much. – Shadow The Curly Braced Wizard Nov 1 '13 at 7:53
  • its policy we need to follow it. – sachin10 Jan 14 '14 at 11:17
  • @Shog9: One extra reason for optimizing / caching it is that, if you have a page that takes 10 seconds to generate, having a couple clients request it repeatedly would be a really easy way to DoS your servers. – Ilmari Karonen Feb 25 '14 at 19:40
8
+100

This is by design. The explanation lies in the definition and behaviour of a sorting and paging algorithm.

Let's say that I define the terms pagenumber and pagesize for the sake of this explanation. Let's also assume that there's a hypothetical list of 100,000 things and I want to both page through them and sort them in some way... So the paging is done on a sorted set.

In the case of review queues, we sort history by review date descending and then page it by (I believe) 50 at a time.

The general formula for paging (depending on if you like to start your index at 0 or 1) is:

first record of page = (pagenumber - 1) * pagesize + 1
last record of page = (pagenumber - 1) * pagesize + pagesize

On the first page of historical reviews, pagenumber = 1 and pagesize = 50. When we run this through the formula we're getting records 1 through 50. This means that in English we want to find the top 50 reviews sorted by review date descending. A highly optimized sorting algorithm will begin to search all 100,000 records in a logarithmic fashion and once it finds the top 50, it will immediately stop sorting. It only had to find and sort 50 records in order to display page 1. So cost = 50. This is fast.

Now we want page 2. pagenumber = 2 and pagesize = 50. When we run this through the formula we're getting records 51 through 100. This means that in English we want to find the top 51st through 100th reviews sorted by review date descending. A highly optimized sorting algorithm will begin to search all 100,000 records in a logarithmic fashion and once it finds the top 100, it will immediately stop sorting. It had to find and sort the first 50 to know where 51 through 100 lie in the list of paged results that are sorted. So the cost = 100 to display page 2. This is twice as much work (on average) as page 1.

Page 3... cost = 150, 3x as expensive (on average) as page 1.

Now, since we had 100,000 rows and a page size of 50, the last page is pagenumber = 2000. To display this page, we have to sort EVERYTHING before the last 50 results in order to display the last 50 results in the proper order. In other words, the entire result set must be sorted to display the last page. Here, cost = 100000 which is very expensive.

This is why the last pages of the historical review are slow.

There are optimizations that can be done with such sorting algorithms. One such optimization is to pre-sort and store the list in a sorted fashion, so that all records are direct lookups. This takes up a lot of memory. Another optimization which lets the data remain dynamically sorted is to guarantee a cost no greater than 1/2 the result set by sorting by the reverse for the last half of the records... In other words, the first 50 records are cheap for a review date descending query, so the first 50 records of review date ascending are also cheap, and these would coincide with the last 50 records of the review date descending sort. We could do this and limit the cost in our example to cost = 50000 (the most expensive sorts being the middle of the set), but it is easier said than done.

I hope that this explains why you're experiencing slow historical pagination.

  • Well, not the answer I was hoping for, but definitely gives a reasonable explanation so thanks! – Shadow The Curly Braced Wizard Jul 15 '14 at 22:44
  • No worries. Like many parts of our code, it could be improved. It's an ever-evolving thing. – Haney Jul 15 '14 at 22:45
  • Since it's not widely used guess it's not worth the effort. Better spend the time and efforts on bugs with bigger impact. :) – Shadow The Curly Braced Wizard Jul 15 '14 at 22:46
  • 3
    I see it more as "I could fix this thing that works but is slow, or I could fix these other things that are completely broken and come back to this later!" – Haney Jul 15 '14 at 22:47
  • This is a great explanation! I had always wondered about the behavior of that type of pagination but did not realize there was an early opt out in the algorithm once it had examined every element once. It makes sense why it would take so long to see the last page of the set. I would really be interested in any expansion you have on approaches to making the process faster - aside from the already good suggestion of splitting the ascending and descending sets. – Travis J Jul 15 '14 at 22:54
  • @Haney by the way, is this all custom coding, or out of the box behaviour of some component you're using? – Shadow The Curly Braced Wizard Jul 15 '14 at 23:00
  • 1
    @TravisJ there are many approaches. The most common of which is pre-caching. AKA create a list that is a copy of your data but in the sort order you anticipate using (such as revision date descending). Double data (original list + sorted list) but very, very fast lookups. All performance is a game of memory vs speed... Get one by giving up the other. – Haney Jul 16 '14 at 1:21
  • @ShadowWizard some custom, some out of the box. In the case of reviews mostly just SQL... But a TOP query has to do the same work. – Haney Jul 16 '14 at 1:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .