New data type: Lists in the Keymap model

[ohsayan]

Background

With 0.7.0, we introduced the Keymap data model which in turn introduced two new data types:

• str: An Unicode string
• binstr: A binary string

As we hinted earlier in our Roadmap (#203), we will be working on new data models and types. The type that we will be implementing next is the list type, similar to what most programming languages call an "Array" or "List". However, the list size, for obvious reasons is not fixed and you can virtually add an unlimited number of items to this list (as long as your disk and memory can hold them). Finally, our storage engine was designed with future scalability in mind and hence can easily support more data types.

Discussion

The goal of this discussion is determine how exactly we want this type to behave and what new actions we will add so that users can effectively use this type. As of now, this is our proposed design:

1. To create tables with lists

   CREATE TABLE <entity> keymap(<type>,list<<type>>)

   For example, to create a table with an Unicode key and a list with binary strings, we can run:

   CREATE TABLE <entity> keymap(str,list<binstr>)

2. Lists are non-recursive. This means that one list cannot ever contain another list
3. The allowed types will include all simple types, similar to those defined by the protocol
4. List actions are unified into one action, with corresponding sub-actions, like:
   • LIST PUSH <list> <element>
   • LIST POP <list>
   • And so on (we will discuss what exactly we want here)

I look forward to your inputs

[martinmolin]

This looks great. I think there are a ton of useful actions that can make lists awesome!
Like you said I think it's nice to group LIST actions into sub-actions to make it clear which actions are meant for which types.

Useful sub-actions could be, but not limited to:

• push
• pop
• insert
• clear
• first
• last
• length/count
• index (get an element at index)
• index_of (get an index by providing an element, not sure how feasible that would be, needs a way of comparing elements)

as well as some way to check the type of a list? A lot of these sub-actions only makes sense if the list is ordered though (I assumed it is) 😄

[ohsayan]

There will be push and insert. More precisely, one will append to the end while the other one will insert into the provided index.

[ohsayan]

Merging of lists can be very expensive, especially when dealing with huge lists (because we're using a single allocation and not linked structures)

[heliumbrain]

Oh, my brain somehow ignored PUSH.

Good point, scratch the merge idea 😄

[ohsayan]

@martinmolin That's exactly my reason for keeping everything under a LIST action — to not make things messy. Else you can have say 50 actions with funky names all over the place with virtually zero readability.

[ohsayan]

Inspecting the type of the list seems like a crucial thing, but it will obviously be reflected when you INSPECT the table. For example, it may return:

Keymap { data:(str, list<str>), volatile: false }

[heliumbrain]

I agree, this looks really good. Without knowing exactly how this would map to the current structure and if it's sorted or not. It would be really nice to be able to do something like

LIST GET <list> <element> <limit> - returning the latest keys + elements in the list according to the limit. Maybe that's already the plan?

[ohsayan]

The list preserves insertion order, for now

[ohsayan]

And yes, limits will exist, similar to those of traditional SQL's LIMIT <n>

[ohsayan]

One of my other questions surrounding lists is: Do we allow deleting lists through the standard DEL action, or not?

[ohsayan]

As discussed, DEL will do it

[ohsayan]

As discussed on our chat channels, we'd want to see the proposals for the LIST syntax here. Please drop a comment by with your proposal!

[martinmolin]

After a lot of thinking I'm not convinced having a LIST action is the simplest approach, basically what we need to be able to do is to tell the server that we want to execute an action on the Value of a specific Key. The user already knows the action should target a LIST so why specify it in the query? The server will have to check if the action can be performed on the type of Vanyway as well so it should not make any difference on performance either not directly specifying the type as LIST.

So instead of doing:

• LIST k PUSH v
• LIST k INSERT 1 v
• SORTEDLIST k PUSH v
• OTHERTYPE k ACTION v

We could have a unified way of indicating for the server which Key we want to perform said action on, for example, the above queries would look like:

• SELECT k PUSH v
• SELECT k INSERT 1 v
• SELECT k PUSH v
• SELECT k ACTION v

As you can see this means that PUSH into separate types that support that action share the exact same syntax, we can also specify which actions are valid for which types in the documentation.

[ohsayan]

The runtime cost for type evaluation doesn't seem like anything we can avoid either way

It doesn't actually work that way. If we SELECT, the type at this point still remains anonymous, then you pass a key, still anonymous, now we check the key, finally we determine the type. Now we check the action if it is suitable for that type.

Versus

Run a LIST (or whatever we do end up calling it), now check if the table actually has lists. If not, do an early return. Else, run the action.

[martinmolin]

What if it would check if the ACTION is supported for the table's type before using the Key? That'd essentially be the same early return I guess?

[ohsayan]

What if it would check if the ACTION is supported for the table's type before using the Key? That'd essentially be the same early return I guess?

Then we'd have to skip the key, look at the action.

[martinmolin]

Yes, if it would be faster to check the action first (like LIST would do) then it makes sense to check the action first! I don't see how LISTor SELECT would differ in performance, both of them are essentially the same steps required server side unless I'm mistaken 😅

[ohsayan]

Yes, if it would be faster to check the action first (like LIST would do) then it makes sense to check the action first! I don't see how LISTor SELECT would differ in performance, both of them are essentially the same steps required server side unless I'm mistaken 😅

Checking the action first is much more performant from an implementation perspective.

[ohsayan]

I completely forgot about this. @martinmolin haha, you'll remember this one ;)