cayleygraph / cayleygraph/cayley
Use HyperLogLog to Help the Optimizier
- 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
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