c# - "pre-computed"map-reduce 索引(RavenDB/CouchDB)可以用于这种算法吗？

Question

我正在尝试查看是否可以将特定算法转换为 RavenDB/CouchDB 使用的那种 map-reduce 索引，即“预计算”map-reduce(这意味着索引在插入和更新时刷新，而不是在执行实际查询时)。

假设我们有一个典型的在线商店，有 50,000 种产品，按类别分组。每个产品都有一个“属性值”集合，例如“[红色、圆形、金属]”。

由于我们的网站上有如此多的产品，并且每个类别中可能有很多项目，我们希望为用户提供另一种方式来“过滤”他当前看到的产品。

例如，如果一个类别是“低于 20 美元”，则该类别中有一大堆产品。但是我们的用户只需要查看低于 $20 和红色的产品。遗憾的是，“低于 20 美元”类别中没有子类别“红色”。

我们的算法将获取当前的产品列表，并生成“有趣”的属性和属性值列表，即给定产品列表，它会输出如下内容:

Color
   Red (40)
   Blue (32)
   Yellow (17)
Material
   Metal (37)
   Plastic (36)
   Wood (23)
Shape
   Square (56)
   Round (17)
   Cylinder (12)

这种算法能否以某种方式预先计算 à la RavenDB/CouchDB map-reduce 索引？如果不是，为什么(这样我以后就可以识别那种算法)如果是，怎么做？

A C# 4.0 Visual Studio Test Solution可用于演示潜在的数据结构和示例数据，以及 map-reduce 实现的尝试(这似乎不可预先计算)。

Answer 1

一般情况:总是可能使用 CouchDB 样式的 map-reduce View ，但不一定实用。

最后，这主要是一个基于计数的论点:如果您需要针对 500,000 种产品的任何子集提出问题，那么您的数据库必须能够为 2^{500,000 种产品中的每一种提供不同的答案} 不同的可能问题，如果您必须为每个问题发出一个 B 树叶子(并且您需要发出数据，除非大多数这些查询的答案为零、假、一个空集或类似的空值)。

CouchDB 通过范围查询的存在提供了第一个小的优化(这意味着在理想情况下，它可以使用尽可能少的 N B 树叶子来回答 N² 个问题)。但是，在您的示例中，这只会将叶数减少到 2^250,000(这是理论上的下限)。

CouchDB 通过键前缀查询提供了第二个小优化，这意味着您可以将 [A]、[A,B] 和 [A,B,C] 查询压缩到单个 [A,B,C] 键中。因此，您的 2^250,000 可能性不复存在，您只剩下“仅仅”2^249,999 ...

因此，虽然您可以想出一种排放策略来回答任何子集的问题，但它需要的存储空间比我们星球上实际可用的存储空间要多。在一般情况下，要回答 N 个不同的问题，您需要至少发出 sqrt(N/2) B 树叶子，因此计算您的问题并确定叶子数量的下限是否为可以接受。

仅针对类别和子类别:如果您放弃任意的产品列表，只问“请提供按属性 B 和 C 筛选的类别 A 中的重要属性”形式的问题，那么你的发射数量下降到:

 AvgCategories * AvgAttr * 2 ^ (AvgAttr - 1) * 500,000

您基本上为每个产品发出键 [Category,Attr,Attr,...] 用于产品的所有类别和产品属性的所有组合，这让您可以查询按类别+属性。如果您平均每个产品有 1 个类别和 3 个属性，则可以计算出大约 600 万个条目，这是完全可以接受的。