Redis BUG: compare typo? - Nineya|java/go/python

https://github.com/antirez/redis/blob/b2ab1e01577fe3b8a8fb6188253d3b22b840bda5/src/t_zset.c#L567

I think it should be xxx >= 1, not (>). Is it so?

Comment From: neomantra

You are pointing to an older version of Redis (2.8?), but the same issue is in the 5.0 codebase using sdscmplex. https://github.com/antirez/redis/blob/2f282aee0b8e500697b627254b170f21d93dd4a8/src/t_zset.c#L655.

This seems to be the issue described in pull request #2212. I think sdscmp(range->min, range->max) > 0 they used is clearer than >= 1.

I'm trying to come up with a test case for this, and if I do I'll make a PR... but either way it seems incorrect since the magnitude of the underlying memcmp's return value is implementation specific.

Comment From: neomantra

I printf-instrumented both sections of zslIsInLexRange and zzlIsInLexRange and ran these commands:

zadd foo 1 aab 2 aba 3 abc
zrangebylex foo [abb [aba

On my system (OSX) is sdscmplex("abb", "aba") is returning 1 and thus the search will be performed. I observed this behavior in both encodings (by mucking with zset-max-ziplist-entries).

I haven't contrived an example where incorrect results or even the serverAssert could happen. From some inspection, I think it just does the search and the search results are correct.

So I think this is just a performance issue: the search can be known to have 0 results a priori, which is what that check was intended for, but it has to does the O(log(N)) search through the data anyway.

Also, perhaps update the issue name to indicate it affects sorted sets or ZRANGEBYLEX or something?

Comment From: neomantra

So I just generated 10M random 10-character strings and ZADDed them with a random z-score.

#!/usr/bin/env lua
# zfill.lua

local NUM_ELEMS = arg[1] or 5
local KEY_NAME = 'zfoo'
local MEMBER_LENGTH = 10

local random = math.random
local format = string.format
local stdout = io.stdout

local charset = {}  do -- [a-zA-Z]
    local char = string.char
    for c = 65, 90  do charset[#charset + 1] = char(c) end
    for c = 97, 122 do charset[#charset + 1] = char(c) end
end

local function random_string(length)
    if not length or length <= 0 then return '' end
    local res = ''
    for i = 1, length do
        res = res .. charset[random(1, #charset)]
    end
    return res
end

for i = 0, NUM_ELEMS do
    local zscore = random(-1000, 1000)
    local member = random_string(MEMBER_LENGTH)
    print(format('ZADD %s %d %s', KEY_NAME, zscore, member))
end

Populated with: ./zfill.lua 10000000 | redis-cli > /dev/null 2>&1

I experimented with both versions (> 0 and original > 1) with the following command: time redis-cli -r 1000000 zrangebylex zfoo [ZZ [ZY > /dev/null

There is a slight performance improvement with the > 0 version, 35.7 to 38.8 seconds range versus 40.8 to 48.4 second range (dropping highest/lowest of each).

I also re-verified with printf statements that the > 1 versus fails to escape with that query. On my system (OSX) it requires that the min/max are one byte away. So [ZZ [ZX had the same performance (~37 seconds, consistent with escaping) but [ZZ [ZY didn't.

So as I said, I think there is not a critical issue because of the other parts of the algorithm, but it is a minor performance issue in a very specific input case. [It also shows how great these data structures are that it doesn't matter too much.] I'll make a new pull request as the 4-year-old #2212 has conflicts.