List oprations


#1

Hi, A few question about ordered lists:

  1. how can I see in the DB, using aql, if the list is ordered or not?

  2. does ordered list means it’s sorted?

  3. I want to scan the db and change all lists (in a specific bin) to be ordered. I want to do is using set_type, but I can’t seem to make it work. Is that possible? how can I do it?

Thanks


#2

Please cross link if you’re posting on another site: https://stackoverflow.com/questions/51068552/how-to-sort-all-lists-in-a-specific-bin-in-aerospike-using-aql

AQL is an admin and data browsing tool, and not intended for you to write applications with. It’s built on top of the C client. I would actually do what you’re asking in any of the main language clients (Java, Python, C#, C, Go).

The list data type can have two different types - unordered or ordered. Similarly, the map data type can be unordered, k-ordered, or kv-ordered. The list API will allow you to call any of the operations, regardless of the type you set, but you will have a different cost, in big-O terms. The performance of operations depending on the type is detailed on the website.

If you want to optimize for writes, an unordered list takes less time to add a new element. If you want to optimize for reads, an ordered list does better. You get to control it by setting the type of the list.


#3

Hi Ronen, Thank you very much for your answer. In my use case, I read the whole list but have multiple wriets, most of them of values that is already in the list.

To save space, I want to maintain a unique values list ( a set). I’m doing so by calling to the add operation with add_unique flag. This have a better running time when the list is ordered.

I would like to make sure all the old lists will be ordered from now on. aql has all list operations built in, all but set_type. Scanning the DB with set_type would be the easiest way to sort all lists, but I guess I’ll use one of the other clients.

BTW, why does ordered list takes more space?


#4

You could scan the namespace with a ScanPolicy.includeBinData=false and for each record digest you get back use operate() to wrap the following operations into a single transaction:

You will only need to run this once to clean up your database.

The ordering type will stick for all future operations. You’d just continue to use the ListWriteFlags.ADD_UNIQUE list policy.

This is for the Java client, but all other clients have these operations and policies in them.


#5
  1. regarding similar issue (using list as set), what will be the behavior & complexity of "ListOperation.append( new ListPolicy(ListOrder.ORDERED,ListWriteFlags.ADD_UNIQUE), bin, value) into EXISTING list which is not ordered and not unique WITHOUT performing above scan ?
  2. according to aerospike’s doc, the complexity of adding element to “unorder set” (N) is batter than “order set WITHOUT indexing on list elements” (N + log N) - is it true ? if so, unless I am indexing the list elements i batter use unorder list ?

#6

Let’s start with the fact that regardless of the big-O complexity analysis, which is a nice indicator, you should be benchmarking these things for yourself. You can use asbenchmark or write your own script to do that.

In (1) you’re changing the list order policy from unordered to order. Append unique to the unordered list is O(N), then a sort on it is O(N log N).

Regarding (2), be aware that the third column “Ordered (2) With No Index” refers to an ordered list in a namespace that stores data on SSD, while “Ordered (3) With Offset Index” refers to an ordered list in a namespaces that stores data in memory with persistence. It’s not an index you can build, rather it happens automatically depending on the storage definition of the namespace.

In general, adding/appending/inserting at a specific index position to an unordered list is O(1). Unordered lists are a better choice if you mostly add data, but don’t get it as often. Ordered lists are useful when you want faster read operations on the data, and are okay with paying the penalty of slower writes.

Again, use this complexity information as a guide. Benchmark the impact for yourself, otherwise choose ordering based on what it does for you in terms of application functionality.