Need composite key support in stores

[erights]

Currently, all our stores carry the qualifier "scalar" because they only accept scalar key values --- primitive data or remotables --- as keys. The plan all along is for them to support any passable key as a key. With #2004 closed, we record here the comment at #2004 (comment)

Add support for composite keys (i.e., arrays, records, maps, and sets used as keys). This will most likely require migrating from the current string-keyed key-value database to a more structured database such as sqlite, along with a concomitant (and likely massive) code overhaul to replace the current cover-based query mechanism with something more sophisticated that makes direct use of the underlying database affordances. When we get to this point, this task will almost certainly unpack into a whole new project plan of its own, with its own issue or issues to track it, but I'm noting it here for completeness and continuity.

We do indeed need to support composite keys, but not this way. At https://github.com/Agoric/agoric-sdk/blob/master/packages/store/src/patterns/encodePassable.js we already implement and test (thanks @gibson042 ) an encoding of all passables whose JS string ordering preserves their rank ordering according to compareRank. IOW, for all passable x and y

compareRank(x, y) < 0 implies that encodePassable(x) < encodePassable(y), etc.

This was the hard lifting for composite keys, and it is already behind us. We should still wait till after MN1 because we can. But when we do need these, the remaining steps to get there should be small. (@FUDCo please let me know what I'm forgetting)

This sort-order preserving encoding for all passables pays no egregious cost compared to other popular binary encodings that we've considered, such as Syrup. Thus, when we do switch marshal from JSON to some more efficient binary encoding, we should consider this one. (We should also give it some catchy name that suggests its magical property.)

[FUDCo]

I would maintain that the original comment you quote there is correct and that the passable encoding scheme, though exceedingly cool, will be insufficient for handling composite keys in many of the ways that people are likely to want to use them in practice.

The problem I foresee is that the encoding scheme imposes a one-dimensional ordering, whereas composite keys are likely to be used in conjunction with composite queries, which in many cases will in turn require multi-dimensional indexing to be efficient enough for practical use. Moreover, even queries on a single dimension are in many cases going to be misaligned with the ordering that we actually store, such that those particular queries will be impractically slow.

Admittedly my intuitions about probable use cases are speculative, but they are informed by experience. (In any case we should do more investigation into likely use patterns before we plunge into actually implementing anything.)

[erights]

Hi @gibson042 I assigned the two of us. We should fix this only after endojs/endo#1349

[erights]

At #7035 we discovered that the internal implementation of big stores (virtual and durable stores) was already using encodeKey, which already does an equality and sort-order preserving encoding of keys, both scalar and composite, into strings. Thus, these internal implementations already seem to support composite keys.

That's FYI since #7035 still tests and exports only scalar support, postponing composite key testing and support to a later PR.

[erights]

See endojs/endo#1349 .
Once that's done, at least one way to do this one will be easy.

[mhofman]

As I alluded to in #8756 (comment), and a recent discussion brought up, composite keys can be particularly tricky when it comes to the order of entries for composites of the same shape. If we want to preserve insertion order, the "first remembered appearance of a remotable in the collection" may affect the sort order. Consider the following example

setStore.add(harden([r1, r2]));
setStore.add(r2);
setStore.add(r1);
console.log(...setStore.values());

The above should likely log [r1, r2] r2 r1, but some implementations, in particular a trivial liveslots one, would instead return [r1, r2] r1 r2.