Redis Sorted Set Member Size and Performance

Question

Redis Sorted Sets primarily sort based on a Score; however, in cases where multiple members share the same Score lexicographical (Alpha) sorting is used. The Redis zadd documentation indicates that the function complexity is:

"O(log(N)) where N is the number of elements in the sorted set"

I have to assume this remains true regardless of the member size/length; however, I have a case where there are only 4 scores resulting in members being sorted lexicographically after Score.

I want to prepend a time bases key to each member to have the secondary sort be time based and also add some uniqueness to the members. Something like:

"time-based-key:member-string"

My member-string can be larger JavaScript object literals like so:

JSON.stringify( {/* object literal */} )

Will the sorted set zadd and other functionality's performance remain constant?

If not, by what magnitude will performance be affected?

Answer 1

The complexity comes from the number of elements that need to be tested (compared against the new element) to find the correct insertion point (presumably using a binary search algorithm).

It says nothing about how long it will take to perform each test, because that's considered a constant factor (in the sense that it doesn't vary when you add more items).

The amount of data which needs to be compared before determining that a new element should go before or after an existing one will affect the total clock time, but it will do so for each comparison equally.

So your overall clock time for an insert will be quickest when comparing scores only, and progressively slower the deeper into a pair of strings it has to look to determine their lexical order. This won't be any particular magnitude, though, just the concrete number of microseconds to be multiplied by the log(n) complexity factor.