On Wed, May 31, 2023, at 16:53, Tomas Vondra wrote:
> I think this needs a better explanation - what exactly is a hashset in
> this context? Something like an array with a hash for faster lookup of
> unique elements, or what?
In this context, by "hashset" I am indeed referring to a data structure similar
to an array, where each element would be unique, and lookups would be faster
than arrays for larger number of elements due to hash-based lookups.
This data structure would store identifiers (IDs) of the nodes, not the complete
nodes themselves.
> Presumably it'd store whole adjacent nodes, not just some sort of node
> ID. So what if a node is adjacent to many other nodes? What if a node is
> added/deleted/modified?
That would require updating the hashset, which should be close to O(1) in
practical applications.
> AFAICS the main problem is the lookups of adjacent nodes, generating
> lot of random I/O etc. Presumably it's not that hard to keep the
> "relational" schema with table for vertices/edges, and then an auxiliary
> table with adjacent nodes grouped by node, possibly maintained by a
> couple triggers. A bit like an "aggregated index" except the queries
> would have to use it explicitly.
Yes, auxiliary table would be good, since we don't want to duplicate all
node-related data, and only store the IDs in the adjacent nodes hashset.
/Joel