Redis的多参数匹配查找器

Question

我需要为某些数据集创建一个匹配查找器系统,如下所示:

有一组对象,每个对象都由一个字符串标识ObjectID.

每个对象都具有N个属性P _i.每个属性值都是一个字符串.

N = 3的数据库示例(在现实生活中N = 8).

ObjectID: P1     P2    P3
--------------------------------
APPLE:    RED    ROUND FRUIT
ORANGE:   ORANGE ROUND FRUIT
CARROT:   RED    LONG  VEGETABLE

系统必须返回ObjectIDs的集合,匹配对象属性的给定查询.在查询中,用户必须指定所有属性值.或者,对于查询中的某些或所有属性,用户可以指定"通配符"  *,这意味着任何属性值都将匹配条件.

示例查询:

P1  P2    P3        => Result
------------------------------------
*   ROUND FRUIT     => APPLE, ORANGE
RED LONG  VEGETABLE => CARROT
RED *     *         => CARROT, APPLE

所有这些都是用SQL完成的.

问题是:有没有一种巧妙的方法可以用Redis做到这一点？

请注意,我对基于Redis的解决方案感兴趣,特别是出于自我教育的目的; 对于这个特定的问题,其他数据库是offtopic.

更新:具有ObjectID每个P _i和应用程序端过滤的显式列表的简单解决方案对我来说看起来不够整洁:-)

Answer 1

你在这里想做的是一个倒排索引.

对于每列,将其映射到"集合".然后,您可以将集合相交以获得结果.

因此,APPLE: RED ROUND FRUIT将映射到以下插入:

SADD p1:RED APPLE
SADD p2:ROUND APPLE
SADD p3:FRUIT APPLE

然后,假设我想查询* ROUND FRUIT,我会这样做:

SINTER p2:ROUND p3:FRUIT

此命令采用p2:ROUND集合和p3:FRUIT集合中的项目的交集.这将返回所有的项目,ROUND而FRUIT不是关心的是什么p1.

其他一些例子:

SMEMBERS p1:GREEN
SINTER p1:RED p2:ROUND p3:FRUIT
SUNION p1:RED p1:GREEN

我的上述答案将使用一些计算能力,因为交叉操作是O(N*M).这是一种更加占用内存的方法,但由于它有效地预先计算了索引,因此检索速度更快.

对于每个属性组合,创建一个存储集合的键:

因此,APPLE: RED ROUND FRUIT将映射到以下插入:

SADD RED:ROUND:FRUIT APPLE
SADD :ROUND:FRUIT APPLE
SADD RED::FRUIT APPLE
SADD RED:ROUND: APPLE
SADD RED:: APPLE
SADD :ROUND: APPLE
SADD ::FRUIT APPLE
SADD ::: APPLE

然后,要查询,只需访问相应的密钥即可.例如,* ROUND FRUIT就是这样

SMEMBERS :ROUND:FRUIT

显然,当你有很多维度时,这在内存方面根本不能很好地扩展,但是检索结果会非常快捷.