According to the documentation https://redis.io/commands/bzpopmin both bzpopmin and pzpopmax are O(logn), but I wonder if this is really the case, and if so, why? Theoretically, since the ZSET is stored in order, at least the MAX or MIN elements should be possible to be popped with just O(1) complexity. This can be a huge deal for some applications (for example priority queues).
Comment From: sundb
Look at the code, the *zpopmin command get the min and max element is O(1), but when delete it search the zset again(seems to be optimizable), and sine the search operation is from min to max, it will be O(log(N)).
You could try create a pr to optimise it?
Comment From: manast
Thanks for the reply.
You could try create a pr to optimise it?
I could, I just wanted to understand if it was a documentation inconsistency and, if not, if it was possible to improve it.
Comment From: sundb
This is not a documentation error, the current code is indeed O(log(N)), but it could hopefully be O(1).
Comment From: manast
This is not a documentation error, the current code is indeed O(log(N)), but it could hopefully be O(1).
Sure. That is what I understood from your first comment. 👍