Handling ordered lists


#1

As we all know, Datomic’s cardinality/many relationships are sets. To enforce a sequential order on a many attribute, one must manually implement a linked list or a position attribute, or serialize the list and store that.

(Aside: First-class ordered lists are a feature request from 2012, per Stuart Halloway:

The top-level decision with lists is “Do you want to query inside them?” If the answer is yes, then you should model a linked list or a positional list in Datomic. If you do not need to query inside lists, then you should request that we add support for lists as a first-class type. :slight_smile: (We are already considering this.)

)

How are folks finding each of these options? Are there some that feel particularly elegant or clunky in your use case? I’ve been tracking position in other attributes and I feel rather ambivalent about manually tracking it.


#2

I would love to see more examples of people modeling lists in datomic. Seems there are many ways to do it with various subtle implications.


#3

Generally speaking I avoid storing ordered data and would rather query data by time or any other aspect, but sometimes it can not be avoided. What I’ve discovered is that, at least for the data I have worked with, an order is only really needed for smaller amounts of data. So in my case it might be that I need to render page elements on a website where the page elements are defined by the user. It’s often only up to 20 or so of each element type for each user’s page. Initially I was storing the position or “spot” as I call it within each ‘ref’ item. However even at 20 items it was, relatively speaking, cumbersome to manage the code for updating relative items and their spots. So I then went with storing the ordered ids in a string at a higher level. Certainly was a better option for me considering the small amounts. Note though that I don’t currently use datomic anymore, so these days I’m storing ordered items in redis as a front to my db. Now that I’m looking at datomic again I’m deciding between that string again or keeping redis in front. Still trying to put all the pieces together for a new architecture.

Stu is right tho, I don’t query inside the list. I just grab the order and render and sometimes update the order.

Note that, IMO, one problem databases get into is providing ordered list for cases like mine (which is useful) only to have people start throwing thousands if not many more items into these ordered list only to discover the performance degrades pretty quickly when you need to insert something in the middle.


#4

With the current implementation, it is not only cumbersome to maintain the order aside, but also limiting, since unlike sets lists can contain multiple times the same value.
Consider for example the list of numbers played by a player at roulette: it could be 3, 7, 9, 3, 12, 12, 3
Having to build and maintain a data structure for such trivial example is really frustrating…
I’m all for something simple though limited in performance, since for large lists you typically store structures rather than values anyway, so order can be managed without too much overhead.


#5

I’m not sure why it would be limiting. In your roulette example, I would use an index attribute for each game played because you will probably not have to remove or change the order of the game played.

{:game/result 3
 :game/n 1}
{:game/result 7
 :game/n 2}
...

If you need an identity for the numbers you can always have :game/result be a ref to a number entity.