dgraph broken recursive sorting example/bug

README.md

dgraph recursive sorting bug

This gist is an extracted test case to show how sorting by timestamps in a recursive query in dgraph does not return the expected results.

dgraph version

Dgraph version   : v0.7.7
Commit SHA-1     : e065d29
Commit timestamp : 2017-07-04 21:10:40 +1000
Branch           : HEAD

I’m running it in docker with the exact command described in the getting started guide.

Problem

Run the data.graphql mutation against an empty dgraph instance. It will create all the nodes as well as the schema with reverse edges for the parent edge.

Here is the query that works as expected without sorting:

{
  recurse(id: a) {
    message
    timestamp
    ~parent
  }
}

This starts at the "root node" and recursively follows the reverse parent edges all the way downm (or until a limit of 1000 I believe, but that shouldn’t apply here). The response JSON looks like this:

{
  "recurse": [
    {
      "message": "root",
      "timestamp": "2017-06-21T11:50:05Z",
      "~parent": [
        {
          "message": "third child",
          "timestamp": "2017-06-21T11:52:20Z",
          "~parent": [
            {
              "message": "and another message",
              "timestamp": "2017-06-21T11:57:00Z"
            },
            {
              "message": "another message",
              "timestamp": "2017-06-21T11:53:00Z"
            }
          ]
        },
        {
          "message": "first child",
          "timestamp": "2017-06-21T11:51:00Z",
          "~parent": [
            {
              "message": "baz",
              "timestamp": "2017-06-21T11:53:02Z"
            },
            {
              "message": "bar",
              "timestamp": "2017-06-21T11:52:00Z"
            },
            {
              "message": "lorem ipsum",
              "timestamp": "2017-06-21T11:55:18Z"
            }
          ]
        },
        {
          "message": "second child",
          "timestamp": "2017-06-21T11:52:00Z"
        }
      ]
    }
  ]
}

It returns all nodes (9) and messages for all of them. So far so good.

Now I want to sort the ~parents by their timestamp, which I indexed as a datetime. This sorting works perfectly in non-recurse queries btw.

Adjust the query to add sorting (at least this is what I believe the correct query for what I’m looking to do should be):

{
  recurse(id: a) {
    message
    timestamp
    ~parent(orderasc: timestamp)
  }
}

Now the following is returned:

{
  "recurse": [
    {
      "message": "root",
      "timestamp": "2017-06-21T11:50:05Z",
      "~parent": [
        {
          "message": "first child",
          "timestamp": "2017-06-21T11:51:00Z",
          "~parent": [
            {
              "message": "lorem ipsum",
              "timestamp": "2017-06-21T11:55:18Z"
            }
          ]
        },
        {
          "message": "second child",
          "timestamp": "2017-06-21T11:52:00Z"
        }
      ]
    }
  ]
}

It no longer returns all the nodes. In a different example with more nodes (around 50) it also (randomly) returned no message for some of them.

data.graphql

# i indented the actual nodes so that is easier to see where the parent relationships go

mutation {
  schema {
    message      : string        @index .
    parent       : uid           @reverse .
    timestamp    : datetime      @index(datetime) .
  }

  set {
    <a> <message> "root" .
    <a> <timestamp> "2017-06-21T11:50:05" .

        <b> <message> "first child" .
        <b> <timestamp> "2017-06-21T11:51:00" .
        <b> <parent> <a> .

            <c> <message> "bar" .
            <c> <timestamp> "2017-06-21T11:52:00" .
            <c> <parent> <b> .

            <d> <message> "baz" .
            <d> <timestamp> "2017-06-21T11:53:02" .
            <d> <parent> <b> .

            <e> <message> "lorem ipsum" .
            <e> <timestamp> "2017-06-21T11:55:18" .
            <e> <parent> <b> .

        <f> <message> "second child" .
        <f> <timestamp> "2017-06-21T11:52:00" .
        <f> <parent> <a> .

        <g> <message> "third child" .
        <g> <timestamp> "2017-06-21T11:52:20" .
        <g> <parent> <a> .

            <h> <message> "another message" .
            <h> <timestamp> "2017-06-21T11:53:00" .
            <h> <parent> <g> .

            <i> <message> "and another message" .
            <i> <timestamp> "2017-06-21T11:57:00" .
            <i> <parent> <g> .
  }
}