Dgraph: Offset-based pagination is slow

[romshark]

Since after-based pagination doesn't work (see #3472 and #2744 and the forum) I had to fall back to offset-based pagination instead, which I expected to be slow (since offsets usually never use the indexes), yet I'm not sure whether it's _generally expected to be that slow_.

• What version of Dgraph are you using?

  • v1.0.14

• Have you tried reproducing the issue with latest release?

  • I did.

• What is the hardware spec (RAM, OS)?

  • OS: Windows 10 (Linux in docker)
  • RAM: 64 GB

• Steps to reproduce the issue (command/config used to run Dgraph).

  • Setup testing environment with docker-compose using the latest Dgraph images
  • Setup the schema:

  Post.id: string @index(hash) .
  Post.creation: dateTime .
  Post.title: string .
  Post.contents: string .
  

  • Fill the database with lots of data using this template:

  {
  set {
    _:post1 <Post.id> "00000000000000000000000000000006" .
    _:post1 <Post.title> "post 1" .
    _:post1 <Post.contents> "post 1 contents" .
    _:post1 <Post.creation> "2019-05-28T10:00:00+00:00" .
  }
  }
  

  (I used a dataset of 83.719 nodes)

  • Read the last 10 items of, say, 100k:

  {
  all(
    func: has(Post.id),
    orderasc: Post.id,
    first: 10,
    offset: 99990
  ) {
    uid
    Post.id
    Post.title
    Post.contents
    Post.creation
  }
  }
  
  



• Expected behaviour and actual result.
  
  
  
  • expected: as I already said, I expected offset to be slow, but since I had no other option left for pagination I _could_ expect it to optimize this query using the hash index, otherwise pagination is pretty much impossible to get fast.
  
  
  • actual: it takes almost 2.5 - 5 seconds!
  
  

[danielmai]

I don't think offset per-se is what's slow here. Pagination (first, offset, after) is fairly cheap. According to the query trace for the query you shared with ~100k Posts from your example, most of the time is taken with sorting. Here's a trace from Jaeger, showing that sorting took 1.8 seconds.

Removing the sort criteria from the query (orderasc: Post.id) speeds up the query significantly, from >2s down to 300ms, which is mostly taken up by has() as it doesn't use an index and iterates over the database. There might be some optimizations we can do here with sorting and pagination combined.

[romshark]

@danielmai I understand, but how do we do pagination over a sorted dataset then? 😄

What if I wanted to serve a paginable list of 100k+ posts sorted by Post.creation and Post.id (since Post.creation isn't unique). AFAIK there's no way to make your own index using a sorted edge like postListByCreationTime: uid @index(hash) @sort(Post.creation, Post.id) which would allow for fast offset based pagination.

[dmitryyankowski]

Any updates on this @danielmai :) @campoy

[dmitryyankowski]

Bump :)

[igormiletic]

Any work planned on this soon? We are expressing this as well and we realized that as offset get bigger and bigger query become slower and slower.

We have about 30.000.000 nodes and we have case that we need to export some data to AWS S3 (to make it available for Athena queries). It is almost impossible to extract all nodes using pagination as query become slower and slower as offset increase.

[EnricoMi]

I have raised a similar feature request #5807 and bug report #5808 regarding offset scaling, but without sorting. Please see there for some numbers.

[minhaj-shakeel]

Github issues have been deprecated.
This issue has been moved to discuss. You can follow the conversation there and also subscribe to updates by changing your notification preferences.