cayleygraph / cayleygraph/cayley

postgres: poor performance on simple recursive queries

Open
#765 2 comments 0 reactions 0 assignees View on GitHub
performance
Dominant language
Go
Stars
15.1k
Forks
1.2k
PR merge metrics
No merged PRs in 30d

Description

Postgres driver performs badly on certain simple recursive queries. Herein are two Gizmo queries (a trivial select by-type and a recursive walk over the tree) over n=8258 nodes.

Toy dataset (n-quads, 2mb compress) used in this example: [knols.nq.zip](https://github.com/cayleygraph/cayley/files/2853640/knols.nq.zip)

```js
//// postgres: cayley -d postgres -a "..." http
//// bolt: cayley -d bolt -a knols.db http
//// memstore: cayley -d memstore http -i knols.nq
//
// postgres: 5ms
// bolt: 14ms
// memstore: 4ms
g.V()
.Has("", "")
.Count() // 8258

// postgres: 4.2s (849x) sic!
// bolt: 204ms (14x)
// memstore: 60ms (15x)
var child_critique = g.M()
.Out("")
.Out("")

g.V()
.Has("", "")
.FollowRecursive(child_critique)
.Count() // 8258
```

**Received results:**

```
I0212 00:43:39.167161 88149 shape.go:205] shape: (path.iteratorBuilder)(0x4484270)
I0212 00:43:39.167180 88149 shape.go:209] optimized: (path.iteratorBuilder)(0x4484270)
I0212 00:43:39.182679 88149 and_optimize.go:187] And: 5 Root: 10 Total Cost: 40 Best: 4611686018427387904
I0212 00:43:39.182699 88149 and_optimize.go:187] And: 5 Root: 12 Total Cost: 65568411 Best: 40
I0212 00:43:39.182705 88149 and_optimize.go:195] And: 5 Choosing: 10 Best: 40
I0212 00:43:39.182723 88149 and_optimize.go:92] 5 become 15
I0212 00:43:39.190905 88149 iterate.go:76] {
"UID": 7,
"Name": "Recursive",
"Type": "recursive",
"Iterators": [
{
"UID": 6,
"Name": "HasA(subject)",
"Type": "hasa",
"Size": 8,
"Iterators": [
{
"UID": 15,
"Name": "And",
"Type": "and",
"Size": 8,
"Exact": true,
"Iterators": [
{
"UID": 10,
"Name": "LinksTo(object)",
"Type": "linksto",
"Size": 8,
"Exact": true,
"Iterators": [
{
"UID": 9,
"Name": "Fixed([f4122d376d3bd58b458c0913ffc8beb22a4b0bc4])",
"Type": "fixed",
"Size": 1,
"Exact": true
}
]
},
{
"UID": 12,
"Name": "LinksTo(predicate)",
"Type": "linksto",
"Size": 17169,
"Exact": true,
"Iterators": [
{
"UID": 11,
"Name": "Fixed([1f822143c9f0cd043e31684ded5dd95982520224])",
"Type": "fixed",
"Size": 1,
"Exact": true
}
]
}
]
}
]
}
]
}
I0212 00:43:43.757395 88149 iterate.go:87] {
"UID": 7,
"Type": "recursive",
"ContainsCost": 240,
"NextCost": 17,
"Size": 0,
"ExactSize": false,
"Next": 0,
"Contains": 0,
"ContainsNext": 0,
"SubIts": [
{
"UID": 6,
"Type": "hasa",
"ContainsCost": 240,
"NextCost": 6,
"Size": 8,
"ExactSize": false,
"Next": 9,
"Contains": 0,
"ContainsNext": 0,
"SubIts": [
{
"UID": 15,
"Type": "and",
"ContainsCost": 4,
"NextCost": 5,
"Size": 8,
"ExactSize": true,
"Next": 9,
"Contains": 0,
"ContainsNext": 0,
"SubIts": [
{
"UID": 10,
"Type": "linksto",
"ContainsCost": 2,
"NextCost": 3,
"Size": 8,
"ExactSize": true,
"Next": 10,
"Contains": 0,
"ContainsNext": 8,
"SubIts": [
{
"UID": 9,
"Type": "fixed",
"ContainsCost": 1,
"NextCost": 1,
"Size": 1,
"ExactSize": true,
"Next": 0,
"Contains": 0,
"ContainsNext": 0,
"SubIts": null
}
]
},
{
"UID": 12,
"Type": "linksto",
"ContainsCost": 2,
"NextCost": 3,
"Size": 17169,
"ExactSize": true,
"Next": 0,
"Contains": 8,
"ContainsNext": 0,
"SubIts": [
{
"UID": 11,
"Type": "fixed",
"ContainsCost": 1,
"NextCost": 1,
"Size": 1,
"ExactSize": true,
"Next": 0,
"Contains": 0,
"ContainsNext": 0,
"SubIts": null
}
]
}
]
}
]
}
]
}
```

**Expected results:**

_dennwc [12:45 AM]_
Is it for Postgres? It looks weird.
`linksto -> fixed` should be optimized away
Those `linksto(fixed)` in the tree mean that it does the lookup+scan manually, instead of using `WHERE`.

**Output of `cayley version` or commit hash:** acf0ab2a9511

```
Cayley version: 0.7.5
```

**Environment details:**

Backend database: `postgres 10.5`

@dennwc

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the two Gizmo queries against PostgreSQL 10.5 with the linked knols dataset, then inspect the planner and iterator paths shown in shape.go, and_optimize.go, and iterate.go. Compare the recursive query's execution plan and timing with the reported results; done means the PostgreSQL path no longer performs the problematic recursive lookup/scan behavior while preserving the expected count.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, postgresql
Domain
databases, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.