StackExchange / StackExchange/StackExchange.Redis

SortedSetRangeByValue ReverseLimits breaks autocomplete numeric 0 prefix

Open
#1,302 5 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C#
Stars
6.2k
Forks
1.6k
Avg merge
1d 15h
Merged PRs (30d)
43

Description

When using a redis sorted set as an autocomplete, we've encountered an issue with this redis library when searching by a numeric prefix with a leading 0, such as 01234 due to the RedisDatabase.SortedSetRangeByValueAsync issuing a the ZRANGEBYLEX in the reverse order. this is not an issue when the prefix has a character anywhere, or does not start with 0.

Reproducing the issue:

run redis-cli MONITOR | grep autocomplete.test and run this code:

private async Task<IEnumerable<string>> Autocomplete(string prefix) {
  string key = "autocomplete.test";
  return (await _db.SortedSetRangeByValueAsync(key, prefix, prefix + '\xff', take: 50))
         .Select(x => (string)x);
}
var working = await Autocomplete("ABC");
var notWorking = await Autocomplete("0123");

Redis receives these commands:

"ZRANGEBYLEX" "autocomplete.test" "[ABC" "[ABC\xc3\xbf" "LIMIT" "0" "50"
"ZRANGEBYLEX" "autocomplete.test" "[0123\xc3\xbf" "[0123" "LIMIT" "0" "50"

notice how in the 2nd command, the min/max order is reversed to an impossible query.

Cause

I tracked down the issue to ReverseLimits calling RedisValue.CompareTo, which calls RedisValue.Simplify on x(min) and y(max) before comparing. x is simplified as Int64 since it all its characters are numeric, however y remains a string (it has the \xff suffix). when the x/y types are not the same, we run the following on line 399:

// otherwise, compare as strings
return string.CompareOrdinal((string)x, (string)y);

The issue is that (string)x is now the simplified x with type int64, so casting back to string drops the leading 0, while y did not switch types and has the leading 0.

Potential fixes:
  • Leading 0 should not treating as int64 (very questionable, as this has a large impact)
  • Keep the original x/y in RedisValue.CompareTo, and call string.CompareOrdinal on the original x/y before simplification.
  • Add an overload to Db.SortedSetRangeByValueAsync to skip calling ReverseLimits

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start at RedisDatabase.SortedSetRangeByValueAsync and ReverseLimits, then inspect RedisValue.CompareTo around line 399. Reproduce with redis-cli MONITOR and the shown ABC and 0123 prefixes; done when the numeric-leading-zero query no longer emits reversed bounds and autocomplete returns the expected range.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp, redis
Domain
database
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.