cayleygraph / cayleygraph/cayley

Use HyperLogLog to Help the Optimizier

Open
#643 1 comment 1 reaction 0 assignees View on GitHub
enhancement
Dominant language
Go
Stars
15.1k
Forks
1.2k
PR merge metrics
No merged PRs in 30d

Description

HyperLogLog allows you to, in a fixed number of bits, keep track of the cardinality of a set. It works a little like a Bloom filter...
```
hll := NewHLL()
hll.Add("foo")
hll.Add("foo") // Duplicates ignored
hll.Add("bar")

x := hll.Size() // 2
```
The proposal is this:
As a new index -- but only for nodes which appear in the predicate field -- we keep some new data
```
bucket "hll":
...
"": { subject_hll: bytes, object_hll: bytes}
...
...
```
And when a new quad comes in:
```
<_:32423> .
```
We add the subject and object to the respective HLLs in the index.
```
pred.subject_hll.Add("")
pred.object_hll.Add("<_:32423>")
```

Now, currently, we assume a fanout of 20 * underlying when trying to estimate the Size of a LinksTo. Instead, we can do much better, if we know the predicate:
```
max(pred.subject_hll.Size() / pred.object_hll.Size(), 1)
```
Or the reciprocal, depending on the direction of the link.

This means predicates like "name" will have a fan-out of 1 -- people generally only have one name. However, a given name will have a slightly larger fan-in -- maybe 1.5 -- as some names have more than one person (the "John Smith" effect)

Contributor guide

Open the contributing guide

Research direction

Start by locating the optimizer's LinksTo size or fanout estimation and the index-update path for new quads. Review how predicate indexes are stored, then determine how HyperLogLog data would fit those paths. Done means predicate-specific cardinality estimates replace the current fixed fanout assumption and are covered by appropriate tests.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
databases, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.