ZINTER for Sorted Sets

[Calum Moore]

Hi

I know this has been discussed before (http://code.google.com/p/redis/issues/detail?id=328), but I wanted to look at this from a different angle - performance.

ZINTERSTORE has a complexity of  O(N*K)+O(M*log(M))

I believe O(M*log(M)) part is the cost of inserting items into the new sorted set (which you have to provide for ZINTERSTORE). However, while I do want a sorted set (so I can paginate), mostly I need intersection without the sorting keys (cross checking separate sets for membership, etc). 

Therefore, if we didn't have to add the keys back into a sorted list, then we could have a complexity of O(N*K).

I've already forked a ZINTER for myself (which returns a list without any scores), but I was wandering if this should/could be included in Redis? Happy to provide the code I have written :-)

Cal

[Josiah Carlson]

Calum,

That bug was marked "wontfix" for a reason: the request was predicated on a misunderstanding about what ZINTER/ZUNION did before they were *renamed* to ZINTERSTORE/ZUNIONSTORE. No one bothered to reply to the follow-on request because they were posting in a bug that had already been closed, and because the new feature request was more or less completely unrelated to the original request.

As for your request (and the last poster in the bug), I don't believe that ZINTER or ZUNION would ever be added again, with or without semantics that you describe. Why? Simply because the API of using Z*STORE commands + ZRANGE can accomplish everything you want and more. ZINTER/ZUNION is strictly less powerful than ZINTERSTORE/ZUNIONSTORE, and the non-store variants are rarely what people actually need. Another drawback is that without the use of a full ZSET with scores to order the results (instead appending them to a list, as an example), the results of your ZINTER operation won't necessarily have consistent ordering (in fact, I can construct a series of operations that would guarantee inconsistent orderings across calls, even when identical data is present in the system), which basically destroys any reasonable expectation of being able to paginate over the results of your ZINTER.

My advice: if you want consistent ordering for pagination, use ZINTERSTORE/ZUNIONSTORE and learn to live with the O(M Log(M)) creation time.

 - Josiah

--
You received this message because you are subscribed to the Google Groups "Redis DB" group.
To unsubscribe from this group and stop receiving emails from it, send an email to redis-db+u...@googlegroups.com.
To post to this group, send email to redi...@googlegroups.com.
Visit this group at http://groups.google.com/group/redis-db.
For more options, visit https://groups.google.com/groups/opt_out.