Ha sorry false friend during translation. Indexes.
The covering indexes we use to store our triples (think RDF) are a (novel) form of adaptive radix trie.
We handle hashes the same, recomputed for leaves, stored in inner nodes.
Have you looked at SIP or Highway hash? If you only use the hash as an implementation detail (as we do) without exposing it via an API you might not need the cryptographic strength of SHA. Both accept a key parameter which prevents attackers from crafting malicious datasets with bad worst-case performance characteristics or hash collisions, while having huge speedups over true cryptographic hash functions.
Funnily enough we do use bitsets heavily inside the trie to speed up set operations and joins between indexes.
The join algorithm is actually very similar to how ECS engines like Legion compute the components relevant to their entities.
There's a new variant called the HOT (height optimized trie) to improve over ART :) but really nice, didn't know of SIP or highway hash, but I wanted to prevent collisions as There's also a diff algorithm, which compares revisions (that said we now also store the type of change, plus the context nodes and the root of the change in a simple JSON file -- so changes are tracked, too).
The data in SirixDB is always indexed by a 64bit int whereas the upper 10 bits denote the position of the node in the page. I've also used different node sizes as in an ART and I'm using a bitset, too in a new node type.
Don't you have to join the data stored in the ART itself? Trying to understand why and how you join index pages :-)
Yeah we actually are much closer to the "old" ART than using the disciminating bit aproach of HOT.
Hot is a more complex data structure with a less deterministic structure which makes it less suited for set operations defined over it and makes it difficult to store the hashes of subtrees in the nodes, also it is not really suited for covering indices from what I can see.
The original ART is not a covering either because of their optimistic infix compression, but it's really easy to make it covering.
We also have the goal of being really "simple" in terms of moving parts, and "easy" in terms of implementation.
Our adaptiveness is not based on different node types but based on a single node type that comes in different sizes and uses perfect-consistent-locality-sensitive-cuckoo-hashing (yeah it's a mouthfull ^^'). We call the thing Persistent Adaptive Cuckoo Trie, or PACT (as in pact with the devil) for short.
The idea is that because of the 256-fanout, we can fine tune our hash functions, to be perfect and collision free, to preserve locality so that two adjacent byte keys will go into the same bucket, and to be consistent on resize, so that doubling the node size only requires a memcpy of the lower half of the new bucket array into the upper half (memory which needs to be initialised anyways, so we get the grow for free modulo reallocation overhead).
This not only saves us costly rehasing but also makes the implementation much simpler.
We figured if we want to build a competitor to RDF it better be implementable by anybody during a hackathon.
The binary triples (Tribles, get it?) that we store are 16byte unique entity id, 16byte unique attribute id, and 32byte value.
We don't do surrogate keys, to not only simplify the implementation and reduce latency, but to also be able to do range and limit queries from the primary indexes directly.
Because we store triples materializing all pssible indexes over our tables (3! + 3) is actually feasible.
This allows us to create a worst case optimal join algorithm that is completely skew resistant.
We're currently working on adding minhash heuristics into the PACT to always pic the optimal variable order for constraint propagation which should make things instance optimal (a first to our knowledge).
So yeah basically the idea is to have a immutable in-memory knowledge base that is amortized O(1) for everything. I.e. you pay per inserted element but not by how much was already inserted, you pay proportional to the size of the intersection of the operands for set ops and not propertional to sum of the operands, you pay proportional to your result size for a query and not propertional to the size of the data queried.
We also have a (still very stealthy) discord channel if you'd like to chat some more about this stuff at discord.gg/tribles :D
Have you looked at SIP or Highway hash? If you only use the hash as an implementation detail (as we do) without exposing it via an API you might not need the cryptographic strength of SHA. Both accept a key parameter which prevents attackers from crafting malicious datasets with bad worst-case performance characteristics or hash collisions, while having huge speedups over true cryptographic hash functions.
Funnily enough we do use bitsets heavily inside the trie to speed up set operations and joins between indexes.
The join algorithm is actually very similar to how ECS engines like Legion compute the components relevant to their entities.