TPF indexing in Db

[joepio]

Although TPF queries are implemented, they are very slow and won't scale - a single TPF query iterates over all individual atoms in the store. To solve this, we need some type of index. Since we're using Sled, a key-value store, we can't use some SQL index, we need to build it ourselves.

One solution is to create two new Sled tree (a new k-v store). In the first one (for searching by Value) every k represents an Atomic Value, and v a vector of all subjects. In the second one for Properties, k = property, v = subject.

However, a very common TPF query will be like this: * isA SomeClass. If we only do above indexes, this will still be a costly query, because we'll still iterate over many resources - pretty much all resources will have the isA property.

We could improve performance if we'd also store the Property in the v fields mentioned above, instead of only storing the subjects. To prevent unnecessary data duplication / minimize storage impact, it might make sense to not store entire atoms, but to leave out the thing that's already known (the thing in the key).

A TPF query such as * isA SomeClass would probably start with using the ValueIndex, which return all SubjectProperty combinations. Then, the implementation will iterate over all SubjectProperties, filtering by property, returning all subjects.

I think Atomic Collections will rely on this query quite a bit: make a list of all Persons (or some class), sorted by some thing. This will do such a TPF query using the indexes, than returns all subjects.

Another possible optimization strategy is caching Collections (which internally use TPF queries). We could rebuild (or invalidate) them on Commits.

[joepio]

Resources have an explicit parent. Getting the parent is a cheap operation, but generating the children is expensive, as it currently requires a TPF query that iterates over all items. This specific operation should be very quick, but I'd like to make the optimizations generalizable.

One way to optimize this TPF query, is to keep track of incoming links. We could create a new inverted tree for this: ValueIndex<valueURL, MentionedIn<propery, Vec<subject>>>. In human language: you can get a MentionedIn for any value, which contains a list of properties. For any given property, you can find the subjects that have used that property to refer to the valueURL.

So when we have this ValueIndex, we need to add stuff into it. When do we build the index? I think we should update it whenever we add or remove a resource. We iterate over all the PropVals, check if they have an AtomicURL or ResourceArray, and add the items to the index. When a resource is deleted, it needs to be deleted from the index, too.

[joepio]

While I was working on the document editor, performance for Collections became pretty bad. This was due to the Documents creating a lot of Commits and Elements, and there was no indexing in the DB. When a Collection was to be fetched, a TPF query would be done, which in turn iterated over every resource... So I've started to build a value index. The Value index seems to be working properly, and it solves the performance issues I've had locally.

But a new issue is arising: it takes way to long to build the index. On my dev machine, where I have some 500MB of things in the store, it took about 30 minutes to build the index. It's insane. Every resource takes about 100+ ms. But why? I have no clue.

Maybe it's time to add some serious benchmarking.

[joepio]

Cause for slow indexing

• some Atoms have a lot of values (long resource arrays for write)
• some value are very common (such as the "" empty string, or the Commit class URL)

... which respectively result in extremely big HashMaps and HashSets.

For every atom, the DB needs to read out and write these very big objects. The PropSubjectMap approach might be fundamentally flawed, performance wise.

Some objects are over 1 MB. Which means reading and writing 1 MB for some atoms.

Length for map https://atomicdata.dev/agents/8S2U/viqkaAQVzUisaolrpX6hx/G/L3e2MTjWA83Rxk= is 1666566 bytes
Length for map https://atomicdata.dev/classes/Commit is 1666571

Value-property index

Instead of having a value index, we could have a value-property index. Each key would be a value-property combination. This would simply be a Set containing a bunch of subjects.

But... A ValueProperty index for https://atomicdata.dev/classes/Commit - https://atomicdata.dev/properties/isA would still be huge, so I don't think this would actually solve anything.

Store commits in a separate index

Since about 90% of the time on indexing on my local machine was for the commits, we might be able to skip these, or treat them differently. Would probably mean that some queries would no longer work for commits. Maybe the commit collection will need to change, in order to achieve this.

Post way less resources

This problem only arises if we have... lots of resources. Which we might not need. NestedResources for Documents might be the best place to start.

Use a different approach to (de-)serializing sled data.

If I understand correctly, rkyv allows for mutating resources without deserializing and reserializing the binary. I think this could be a significant part of the slowdown.

https://github.com/rkyv/rkyv

Make it a background process

If building an index is slow, that might not be a really big problem, as long as it happens in the background....

We could spin up an actix thread on server initialization, which iterates over all resources.

Or maybe introduce an indexQueue that contains a bunch of Atoms that have to be processed

[joepio]

I'm pretty content with the current implementation. Closing for now.