I suggest to add a new type which is similar to the sorted set : Interval set. The idea is to replace the score by an interval of number (integer or decimal).

This data structure allows to search for an item based on the associated interval.

Commands

Add members with interval in interval set

IADD <key> <minBound> <maxBound> <member> [<minBound> <maxBound> <member>]...

Delete member within an interval set

IREM <key> <member> [<member>]...

Query the interval set with an interval :

IOVERLAPS <key> <minBound> <maxBound> [WITHINTERVALS] [COUNT <amount>]

Query the interval set with a value :

ICONTAINS <key> <value> [WITHINTERVALS] [COUNT <amount>]

Bound specification

minBound and maxBound can be -inf or +inf.

The bound exclusion can be specify with ( caractère before the bound value (like ZRANGEBYSCORE command)

Comment From: zuiderkwast

Interesting. It sounds like a lot of work though. Are you willing to implement it and maybe also help maintaining it in the future? It could also be implemented as a module...

Comment From: madolson

I also think this is kind of interesting, what sort of problems is this intended to solve?

Comment From: guillaume-soulard

@zuiderkwast

Unfortunately my C programming skills are not enough. And yes i know this feature can be implemented as a redis module but for the same reason I mentioned I didn't code such module.

@madolson

In my company we have use case thant can be solved by this kind of data struct. We need to store ip range for blacklist purpose for exemple 192.168.1.0/24 (from 192.168.1.1 to 192.168.1.254) With the actual redis a set must be fill with all ips in range and query with SISMEMBER command. This work but it's not memory efficient. With interval set we store ip (ip has to be converted to decimal) in an interval set : IADD ipsToBlacklist 3231711489 3231711742 "" All we need next is to query the interval set with ICONTAINS : ICONTAINS ipsToBlacklist 3231711491 to know if the ip is in the range of any interval in the set. This is more memory efficient.

An another use case can be indexing date range.

Comment From: madolson

This is an interesting case, but it does really sound like it should fall in the module use case though. So probably not likely to get implemented.

Comment From: zuiderkwast

I can imagine use cases for time intervals in planning/scheduling/booking apps.

Just an idea: Can sorted sets be used for interval search? For example, store the lower bound of an interval as the score of an element and use ZRANGE ... BYSCORE REV to find the nearest lower bound of an interval, i.e. the interval containing the searched element? Possibly encode stuff in the element names or use the element names to lookup the interval in a hash or similar?

Comment From: guillaume-soulard

@zuiderkwast

Using sorted sets can help. I found a solution using 2 sorted sets. With this technique we have to use one set to store the lower bound of the interval and a second to store the max bound of the interval.

I use 3 intervals for this example : [3;20], [15;30] and [11;28] :

ZADD minSet 3 "3;20" 15 "15;30" 11 "11;28"
ZADD maxSet 20 "3;20" 30 "15;30" 28 "11;28"

Quering involve multiple commands but you can find the interval using these commands (DEL is optional) :

ZRANGESTORE minSetTemp minSet -999999999999 25 BYSCORE
ZRANGESTORE maxSetTemp maxSet 25 999999999999 BYSCORE
ZINTER 2 minSetTemp maxSetTemp
DEL minSetTemp maxSetTemp

The result of ZINTERis :

1) "11;28"
2) "15;30"

I believe it's possible to check for overlapping interval with additionnal set intersections.

Comment From: zuiderkwast

That can be put in a Lua script (or a Redis module).

Comment From: guillaume-soulard

I wrote a module to use intervals : https://github.com/ogama/redis-interval-module

Comment From: madolson

@ogama You should open a PR adding you module to the official list: https://github.com/redis/redis-doc/blob/29f18a45df400c3df119f1868f66a56256494cd1/modules.json

I think we can close this issue.