使用 Redis 的多参数匹配器 [英] Multi-parameter match-finder with Redis

问题描述

我需要为一些数据集创建一个匹配器系统，如下:

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

每个对象正好有 N 个属性 P_i.每个属性值都是一个字符串.

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

<前>对象 ID:P1 P2 P3--------------------------------苹果:红色圆形水果橙色:橙色圆形水果胡萝卜:红长菜

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

示例查询:

<前>P1 P2 P3 => 结果---------------------* 圆形水果 => 苹果、橙子红长菜 => 胡萝卜红色 * * => 胡萝卜、苹果

所有这些都可以通过 SQL 轻松完成.

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

请注意，我对基于Redis的解决方案特别感兴趣，用于自学目的；对于这个特定问题，其他数据库是无关紧要的.

更新:为每个 P_i 和应用程序端过滤提供显式 ObjectID 列表的简单解决方案在我看来不够整洁:-)

解决方案

您在这里尝试做的是倒排索引.

对于每一列，将它映射到一个集合".然后，您可以将这些集合相交以获得结果.

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

SADD p1:RED APPLESADD p2:圆苹果SADD p3:水果苹果

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

烧结 p2:ROUND p3:FRUIT

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

其他一些例子:

SMEMBERS p1:GREEN烧结 p1:红色 p2:圆形 p3:水果SUNION p1:红色 p1:绿色

<小时>

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

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

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

SADD RED:ROUND:FRUIT APPLE悲伤:圆形:水果苹果悲伤的红::水果苹果悲伤的红色:圆形:苹果悲伤的红::苹果悲伤:圆形:苹果悲伤::水果苹果悲伤 ::: 苹果

然后，要查询，您只需访问相应的密钥.例如，* ROUND FRUIT 就是

SMEMBERS :ROUND:FRUIT

显然，当你有很多维度时，这在内存方面根本无法很好地扩展，但检索结果会非常迅速.

I need to create an match-finder system for some data set, as follows:

There is a set of objects, each identified by a string ObjectID.

Each object has exactly N properties P_i. Each property value is a string.

Database example for N = 3 (in real life N = 8).

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

The system must return sets of ObjectIDs, matching given query on object properties. In query user must specify all property values. Alternatively, for some or all properties in query user may specify a "wildcard" *, meaning that any property value would match criteria.

Example queries:

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

All of this is trivially done with SQL.

The question is: is there a neat way to do that with Redis?

Note that I'm interested in Redis-based solutions specifically, for self-education purposes; other DBs are offtopic for this particular question.

Update: Trivial solution with explicit ObjectID lists for each P_i and application-side filtering does not look neat enough to me :-)

解决方案

What you are trying to do here is an inverted index.

For each column, have it map to a "set". Then, you can intersect the sets to get the result.

So, APPLE: RED ROUND FRUIT would map to the following inserts:

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

Then, let's say I want to query for * ROUND FRUIT, I would do:

SINTER p2:ROUND p3:FRUIT

This command is taking the intersection of the items in the p2:ROUND set and the p3:FRUIT set. This will return all the items that are ROUND and FRUIT, not caring what p1 is.

Some other examples:

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

---

My above answer is going to use some computation power because the intersection operation is O(N*M). Here is a way of doing it that is more memory intensive, but will have faster retrieval because it effectively precomputes the indexes.

For each combination of properties, make a key that stores a set:

So, APPLE: RED ROUND FRUIT would map to the following inserts:

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

Then, to query, you simply access the respective key. For example, * ROUND FRUIT would simply be

SMEMBERS :ROUND:FRUIT

Obviously, this doesn't scale well at all in terms of memory when you have many dimensions, but it will be extremely snappy to retrieve results.

这篇关于使用 Redis 的多参数匹配器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！