我有以下表格：
Order
----
ID (pk)
OrderItem
----
OrderID (fk -> Order.ID)
ItemID (fk -> Item.ID)
Quantity
Item
----
ID (pk)
如何编写一个可以选择所有Orders与特定的至少 85% 相似的查询Order？
我考虑使用Jaccard Index统计量来计算两个Orders. （通过取每组的交集OrderItems除以每组的并集OrderItems）
但是，如果不为两个Orders. 还有其他方法吗？
另外，有没有办法将Quantity每个匹配项的差异包括OrderItem在内？
附加信息：
总计Orders：~79k
总计OrderItems：~1.76m
Avg. OrderItems每人Order：21.5
总计Items：~13k
笔记
85% 的相似度数字只是对客户实际需求的最佳猜测，未来可能会发生变化。适用于任何相似性的解决方案将是可取的。
您指定
如何编写可以选择与特定订单至少 85% 相似的所有订单的查询？
与“至少 85% 相似的所有订单对”相比，这是一个重要的简化。
我们将使用一些 TDQD（测试驱动查询设计）和一些分析来帮助我们。
要远程相似，两个订单必须至少有一个共同点。此查询可用于确定哪些订单与指定订单至少有一个共同点：
SELECT DISTINCT I1.OrderID AS ID
FROM OrderItem AS I1
JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
WHERE I1.OrderID != <specified order ID>
这会大量删除要检查的其他订单列表，但如果指定的订单包含您最受欢迎的商品之一，则很可能很多其他订单也这样做了。
代替 DISTINCT，您可以使用：
SELECT I1.OrderID AS ID, COUNT(*) AS Num_Common
FROM OrderItem AS I1
JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
WHERE I1.OrderID != <specified order ID>
GROUP BY I1.OrderID
这为您提供了与指定订单相同的订单中的项目数。我们还需要每个订单中的商品数量：
SELECT OrderID AS ID, COUNT(*) AS Num_Total
FROM OrderItem
GROUP BY OrderID;
对于 100% 的相似性，两个订单的共同项目与每个订单的项目数量一样多。不过，这可能不会找到很多订单对。我们可以很容易地找到与指定订单具有完全相同项目的订单：
SELECT L1.ID
FROM (SELECT OrderID AS ID, COUNT(*) AS Num_Total
FROM OrderItem
GROUP BY OrderID
) AS L1
JOIN (SELECT I1.OrderID AS ID, COUNT(*) AS Num_Common
FROM OrderItem AS I1
JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
WHERE I1.OrderID != <specified order ID>
GROUP BY I1.OrderID
) AS L2 ON L1.ID = L2.ID AND L1.Num_Total = L2.Num_Common;
编辑：事实证明这不够严格；为了使订单相同，指定订单中的商品数量也必须与公共数量相同：
SELECT L1.ID, L1.Num_Total, L2.ID, L2.Num_Common, L3.ID, L3.Num_Total
FROM (SELECT OrderID AS ID, COUNT(*) AS Num_Total
FROM OrderItem
GROUP BY OrderID
) AS L1
JOIN (SELECT I1.OrderID AS ID, COUNT(*) AS Num_Common
FROM OrderItem AS I1
JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
WHERE I1.OrderID != <specified order ID>
GROUP BY I1.OrderID
) AS L2 ON L1.ID = L2.ID AND L1.Num_Total = L2.Num_Common
JOIN (SELECT OrderID AS ID, COUNT(*) AS Num_Total
FROM OrderItem
WHERE OrderID = <specified order ID>
GROUP BY OrderID
) AS L3 ON L2.Num_Common = L3.Num_Total;
将 Wikipedia 中定义的Jaccard 相似性应用于两个订单 A 和 B，其中 |A| 作为订单 A 中项目数的计数，Jaccard 相似度J(A,B) = |A∩B| ÷ |A∪B| , 其中 |A∩B| 是两个订单共有的项目数，|A∪B| 是订购的不同项目的总数。
为了满足 85% 的 Jaccard 相似性标准，如果任一订单中的项目数小于某个阈值，则订单必须相同。例如，如果订单 A 和 B 都有 5 件商品，但两者之间有一件商品不同，那么它会给您 4 件共同的商品（|A∩B|）和总共 6 件商品（|A∪B|） ，所以 Jaccard 相似度 J(A,B) 只有 66⅔%。
对于 85% 的相似性，当两个订单中的每个订单中有 N 个项目且 1 个项目不同时，(N-1) ÷ (N+1) ≥ 0.85，这意味着 N > 12（准确地说是 12⅓）。对于分数 F = J(A,B)，一项不同的意思是(N-1) ÷ (N+1) ≥ F可以解决 N 给出N ≥ (1 + F) ÷ (1 - F)。随着相似性要求的提高，对于越来越大的 N 值，阶数必须相同。
进一步概括，假设我们有 N 和 M 个项目的不同大小订单（不失一般性，N < M）。|A∩B|的最大值 现在是 N 和 |A∪B| 的最小值 是M（意思是小顺序的所有项目都以大的顺序出现）。让我们定义 M = N + Δ，并且有 ∂ 项以较小的顺序出现，而在较大的顺序中不存在。由此可见，有 ∆+∂ 项以较大的顺序出现，而没有以较小的顺序出现。
根据定义，|A∩B| = N-∂和|A∪B| = (N-∂) + ∂ + (N+Δ-(N-∂))，其中三个相加的项表示（1）两个订单共有的项目数，（2）仅在较小的顺序，以及 (3) 仅在较大顺序中的项目数。这简化为：|A∪B| = N+Δ+∂。
对于相似性分数 F，我们对 J(A,B) ≥ F 的顺序对感兴趣，因此：
(N-∂) ÷ (N+Δ+∂) ≥ F
F ≤ (N-∂) ÷ (N+Δ+∂)
我们可以使用电子表格来绘制这些之间的关系。对于给定数量的较小顺序（x 轴）的项目，并且对于给定的相似度，我们可以绘制 ∂ 的最大值，它给出了 F 的相似度。公式是：
∂ = (N(1-F) - FΔ) ÷ (1+F)
这是常数 F 的 N 和 Δ 的线性方程；对于不同的 F 值，它是非线性的。显然，∂ 必须是非负整数。
给定 F = 0.85，对于相同大小的订单 (Δ=0)，对于 1 ≤ N < 13，∂ = 0；对于 13 ≤ N < 25，∂ ≤ 1；对于 25 ≤ N < 37，∂ ≤ 2，对于 37 ≤ N < 50，∂ ≤ 3。
对于相差 1 (Δ=1) 的阶数，对于 1 ≤ N < 18，∂ = 0；对于 18 ≤ N < 31，∂ ≤ 1；对于 31 ≤ N < 43，∂ ≤ 2；等等。如果 ∆=6，您需要 N=47 才能使订单与 ∂=1 有 85% 的相似度。这意味着小订单有 47 件商品，其中 46 件与 53 件商品的大订单相同。
到目前为止，一切都很好。我们如何应用该理论来选择与指定订单相似的订单？
首先，我们观察到指定的订单可能与类似订单的大小相同，或者更大或更小。这使事情变得有点复杂。
上式的参数为：
使用顶部开发的查询的微小变化可用的值：
对应查询：
SELECT OrderID AS ID, COUNT(*) AS NA
FROM OrderItem
WHERE OrderID = <specified order ID>
GROUP BY OrderID;
SELECT OrderID AS ID, COUNT(*) AS NB
FROM OrderItem
WHERE OrderID != <specified order ID>
GROUP BY OrderID;
SELECT I1.OrderID AS ID, COUNT(*) AS NC
FROM OrderItem AS I1
JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
WHERE I1.OrderID != <specified order ID>
GROUP BY I1.OrderID
为方便起见，我们希望值 N 和 N+Δ（因此也有 Δ）可用，因此我们可以使用 UNION 来适当地安排事物，其中：
在 UNION 查询的第二个版本中，使用：
这两个查询都保留了两个订单 ID 号，以便您以后可以追踪到其余的订单信息。
SELECT v1.ID AS OrderID_1, v1.NA AS NS, v2.ID AS OrderID_2, v2.NB AS NL
FROM (SELECT OrderID AS ID, COUNT(*) AS NA
FROM OrderItem
WHERE OrderID = <specified order ID>
GROUP BY OrderID
) AS v1
JOIN (SELECT OrderID AS ID, COUNT(*) AS NB
FROM OrderItem
WHERE OrderID != <specified order ID>
GROUP BY OrderID
) AS v2
ON v1.NA <= v2.NB
UNION
SELECT v2.ID AS OrderID_1, v2.NB AS NS, v1.ID AS OrderID_2, v1.NA AS NL
FROM (SELECT OrderID AS ID, COUNT(*) AS NA
FROM OrderItem
WHERE OrderID = <specified order ID>
GROUP BY OrderID
) AS v1
JOIN (SELECT OrderID AS ID, COUNT(*) AS NB
FROM OrderItem
WHERE OrderID != <specified order ID>
GROUP BY OrderID
) AS v2
ON v1.NA > v2.NB
这为我们提供了一个包含 OrderID_1、NS、OrderID_2、NL 列的表表达式，其中 NS 是小订单中的项目数，NL 是大订单中的项目数。由于 v1 和 v2 表表达式生成的订单号没有重叠，因此无需担心 OrderID 值相同的“反身”条目。在 UNION 查询中添加 NC 也是最容易处理的：
SELECT v1.ID AS OrderID_1, v1.NA AS NS, v2.ID AS OrderID_2, v2.NB AS NL, v3.NC AS NC
FROM (SELECT OrderID AS ID, COUNT(*) AS NA
FROM OrderItem
WHERE OrderID = <specified order ID>
GROUP BY OrderID
) AS v1
JOIN (SELECT OrderID AS ID, COUNT(*) AS NB
FROM OrderItem
WHERE OrderID != <specified order ID>
GROUP BY OrderID
) AS v2
ON v1.NA <= v2.NB
JOIN (SELECT I1.OrderID AS ID, COUNT(*) AS NC
FROM OrderItem AS I1
JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
WHERE I1.OrderID != <specified order ID>
GROUP BY I1.OrderID
) AS v3
ON v3.ID = v2.ID
UNION
SELECT v2.ID AS OrderID_1, v2.NB AS NS, v1.ID AS OrderID_2, v1.NA AS NL, v3.NC AS NC
FROM (SELECT OrderID AS ID, COUNT(*) AS NA
FROM OrderItem
WHERE OrderID = <specified order ID>
GROUP BY OrderID
) AS v1
JOIN (SELECT OrderID AS ID, COUNT(*) AS NB
FROM OrderItem
WHERE OrderID != <specified order ID>
GROUP BY OrderID
) AS v2
ON v1.NA > v2.NB
JOIN (SELECT I1.OrderID AS ID, COUNT(*) AS NC
FROM OrderItem AS I1
JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
WHERE I1.OrderID != <specified order ID>
GROUP BY I1.OrderID
) AS v3
ON v3.ID = v1.ID
这为我们提供了一个包含 OrderID_1、NS、OrderID_2、NL、NC 列的表表达式，其中 NS 是小订单中的项目数，NL 是大订单中的项目数，NC 是小订单中的项目数常见的。
给定 NS、NL、NC，我们正在寻找满足：
(N-∂) ÷ (N+Δ+∂) ≥ F。
∂ — 较小顺序中未匹配较大顺序的项目数
NS = N - 较小顺序的项目数
因此，条件必须是：
NC / (NL + (NS - NC)) ≥ F
LHS 上的项必须作为浮点数计算，而不是整数表达式。将其应用于上面的 UNION 查询，产生：
SELECT OrderID_1, NS, OrderID_2, NL, NC,
CAST(NC AS NUMERIC) / CAST(NL + NS - NC AS NUMERIC) AS Similarity
FROM (SELECT v1.ID AS OrderID_1, v1.NA AS NS, v2.ID AS OrderID_2, v2.NB AS NL, v3.NC AS NC
FROM (SELECT OrderID AS ID, COUNT(*) AS NA
FROM OrderItem
WHERE OrderID = <specified order ID>
GROUP BY OrderID
) AS v1
JOIN (SELECT OrderID AS ID, COUNT(*) AS NB
FROM OrderItem
WHERE OrderID != <specified order ID>
GROUP BY OrderID
) AS v2
ON v1.NA <= v2.NB
JOIN (SELECT I1.OrderID AS ID, COUNT(*) AS NC
FROM OrderItem AS I1
JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
WHERE I1.OrderID != <specified order ID>
GROUP BY I1.OrderID
) AS v3
ON v3.ID = v2.ID
UNION
SELECT v2.ID AS OrderID_1, v2.NB AS NS, v1.ID AS OrderID_2, v1.NA AS NL, v3.NC AS NC
FROM (SELECT OrderID AS ID, COUNT(*) AS NA
FROM OrderItem
WHERE OrderID = <specified order ID>
GROUP BY OrderID
) AS v1
JOIN (SELECT OrderID AS ID, COUNT(*) AS NB
FROM OrderItem
WHERE OrderID != <specified order ID>
GROUP BY OrderID
) AS v2
ON v1.NA > v2.NB
JOIN (SELECT I1.OrderID AS ID, COUNT(*) AS NC
FROM OrderItem AS I1
JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
WHERE I1.OrderID != <specified order ID>
GROUP BY I1.OrderID
) AS v3
ON v3.ID = v1.ID
) AS u
WHERE CAST(NC AS NUMERIC) / CAST(NL + NS - NC AS NUMERIC) >= 0.85 -- F
您可能会观察到此查询仅使用 OrderItem 表；不需要 Order 和 Item 表。
警告：部分测试的 SQL（警告讲师）。上面的 SQL 现在似乎可以在微小的数据集上产生似是而非的答案。我调整了相似性要求（0.25，然后是 0.55）并得到了合理的值和适当的选择性。但是，我的测试数据最大的顺序只有 8 个项目，而且肯定没有涵盖所描述数据的全部范围。由于我最常使用的 DBMS 不支持 CTE，因此下面的 SQL 未经测试。但是，我有一定的信心，除非我犯了一个大错误，否则版本 1 中的 CTE 代码（指定订单 ID 有很多重复）应该是干净的。我认为第 2 版也可能没问题，但是……它未经测试。
可能有更紧凑的方式来表达查询，可能使用 OLAP 函数。
如果我要对此进行测试，我将创建一个包含几个具有代表性的订单项集的表，检查返回的相似性度量是否合理。我会或多或少地处理查询，逐渐建立复杂的查询。如果其中一个表达式被证明有缺陷，那么我会对该查询进行适当的调整，直到缺陷得到修复。
显然，性能将是一个问题。最里面的查询不是非常复杂，但也不是微不足道的。然而，测量将显示这是一个严重的问题还是只是一个麻烦。研究查询计划可能会有所帮助。OrderItem.OrderID 上应该有一个索引似乎很可能；如果没有这样的索引，查询不太可能执行良好。这不太可能成为问题，因为它是一个外键列。
您可能会从使用“WITH 子句”（公用表表达式）中获得一些好处。他们将明确表示 UNION 子查询的两半中隐含的重复。
当表达式相同时，使用公用表表达式可以向优化器澄清，并可能有助于它更好地执行。它们还帮助人们阅读您的查询。上面的查询确实要求使用 CTE。
版本一：重复指定订单号
WITH SO AS (SELECT OrderID AS ID, COUNT(*) AS NA -- Specified Order (SO)
FROM OrderItem
WHERE OrderID = <specified order ID>
GROUP BY OrderID
),
OO AS (SELECT OrderID AS ID, COUNT(*) AS NB -- Other orders (OO)
FROM OrderItem
WHERE OrderID != <specified order ID>
GROUP BY OrderID
),
CI AS (SELECT I1.OrderID AS ID, COUNT(*) AS NC -- Common Items (CI)
FROM OrderItem AS I1
JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID AND I2.OrderID = <specified order ID>
WHERE I1.OrderID != <specified order ID>
GROUP BY I1.OrderID
)
SELECT OrderID_1, NS, OrderID_2, NL, NC,
CAST(NC AS NUMERIC) / CAST(NL + NS - NC AS NUMERIC) AS Similarity
FROM (SELECT v1.ID AS OrderID_1, v1.NA AS NS, v2.ID AS OrderID_2, v2.NB AS NL, v3.NC AS NC
FROM SO AS v1
JOIN OO AS v2 ON v1.NA <= v2.NB
JOIN CI AS v3 ON v3.ID = v2.ID
UNION
SELECT v2.ID AS OrderID_1, v2.NB AS NS, v1.ID AS OrderID_2, v1.NA AS NL, v3.NC AS NC
FROM SO AS v1
JOIN OO AS v2 ON v1.NA > v2.NB
JOIN CI AS v3 ON v3.ID = v1.ID
) AS u
WHERE CAST(NC AS NUMERIC) / CAST(NL + NS - NC AS NUMERIC) >= 0.85 -- F
版本 2：避免重复指定的订单号
WITH SO AS (SELECT OrderID AS ID, COUNT(*) AS NA -- Specified Order (SO)
FROM OrderItem
WHERE OrderID = <specified order ID>
GROUP BY OrderID
),
OO AS (SELECT OI.OrderID AS ID, COUNT(*) AS NB -- Other orders (OO)
FROM OrderItem AS OI
JOIN SO ON OI.OrderID != SO.ID
GROUP BY OI.OrderID
),
CI AS (SELECT I1.OrderID AS ID, COUNT(*) AS NC -- Common Items (CI)
FROM OrderItem AS I1
JOIN SO AS S1 ON I1.OrderID != S1.ID
JOIN OrderItem AS I2 ON I2.ItemID = I1.ItemID
JOIN SO AS S2 ON I2.OrderID = S2.ID
GROUP BY I1.OrderID
)
SELECT OrderID_1, NS, OrderID_2, NL, NC,
CAST(NC AS NUMERIC) / CAST(NL + NS - NC AS NUMERIC) AS Similarity
FROM (SELECT v1.ID AS OrderID_1, v1.NA AS NS, v2.ID AS OrderID_2, v2.NB AS NL, v3.NC AS NC
FROM SO AS v1
JOIN OO AS v2 ON v1.NA <= v2.NB
JOIN CI AS v3 ON v3.ID = v2.ID
UNION
SELECT v2.ID AS OrderID_1, v2.NB AS NS, v1.ID AS OrderID_2, v1.NA AS NL, v3.NC AS NC
FROM SO AS v1
JOIN OO AS v2 ON v1.NA > v2.NB
JOIN CI AS v3 ON v3.ID = v1.ID
) AS u
WHERE CAST(NC AS NUMERIC) / CAST(NL + NS - NC AS NUMERIC) >= 0.85 -- F
这些都不是易读的。两者都比完整写出 CTE 的大 SELECT 更容易。
这不足以进行良好的测试。它提供了一点点信心（它确实显示了“相同顺序”查询的问题。
CREATE TABLE Order (ID SERIAL NOT NULL PRIMARY KEY);
CREATE TABLE Item (ID SERIAL NOT NULL PRIMARY KEY);
CREATE TABLE OrderItem
(
OrderID INTEGER NOT NULL REFERENCES Order,
ItemID INTEGER NOT NULL REFERENCES Item,
Quantity DECIMAL(8,2) NOT NULL
);
INSERT INTO Order VALUES(1);
INSERT INTO Order VALUES(2);
INSERT INTO Order VALUES(3);
INSERT INTO Order VALUES(4);
INSERT INTO Order VALUES(5);
INSERT INTO Order VALUES(6);
INSERT INTO Order VALUES(7);
INSERT INTO Item VALUES(111);
INSERT INTO Item VALUES(222);
INSERT INTO Item VALUES(333);
INSERT INTO Item VALUES(444);
INSERT INTO Item VALUES(555);
INSERT INTO Item VALUES(666);
INSERT INTO Item VALUES(777);
INSERT INTO Item VALUES(888);
INSERT INTO Item VALUES(999);
INSERT INTO OrderItem VALUES(1, 111, 1);
INSERT INTO OrderItem VALUES(1, 222, 1);
INSERT INTO OrderItem VALUES(1, 333, 1);
INSERT INTO OrderItem VALUES(1, 555, 1);
INSERT INTO OrderItem VALUES(2, 111, 1);
INSERT INTO OrderItem VALUES(2, 222, 1);
INSERT INTO OrderItem VALUES(2, 333, 1);
INSERT INTO OrderItem VALUES(2, 555, 1);
INSERT INTO OrderItem VALUES(3, 111, 1);
INSERT INTO OrderItem VALUES(3, 222, 1);
INSERT INTO OrderItem VALUES(3, 333, 1);
INSERT INTO OrderItem VALUES(3, 444, 1);
INSERT INTO OrderItem VALUES(3, 555, 1);
INSERT INTO OrderItem VALUES(3, 666, 1);
INSERT INTO OrderItem VALUES(4, 111, 1);
INSERT INTO OrderItem VALUES(4, 222, 1);
INSERT INTO OrderItem VALUES(4, 333, 1);
INSERT INTO OrderItem VALUES(4, 444, 1);
INSERT INTO OrderItem VALUES(4, 555, 1);
INSERT INTO OrderItem VALUES(4, 777, 1);
INSERT INTO OrderItem VALUES(5, 111, 1);
INSERT INTO OrderItem VALUES(5, 222, 1);
INSERT INTO OrderItem VALUES(5, 333, 1);
INSERT INTO OrderItem VALUES(5, 444, 1);
INSERT INTO OrderItem VALUES(5, 555, 1);
INSERT INTO OrderItem VALUES(5, 777, 1);
INSERT INTO OrderItem VALUES(5, 999, 1);
INSERT INTO OrderItem VALUES(6, 111, 1);
INSERT INTO OrderItem VALUES(6, 222, 1);
INSERT INTO OrderItem VALUES(6, 333, 1);
INSERT INTO OrderItem VALUES(6, 444, 1);
INSERT INTO OrderItem VALUES(6, 555, 1);
INSERT INTO OrderItem VALUES(6, 777, 1);
INSERT INTO OrderItem VALUES(6, 888, 1);
INSERT INTO OrderItem VALUES(6, 999, 1);
INSERT INTO OrderItem VALUES(7, 111, 1);
INSERT INTO OrderItem VALUES(7, 222, 1);
INSERT INTO OrderItem VALUES(7, 333, 1);
INSERT INTO OrderItem VALUES(7, 444, 1);
INSERT INTO OrderItem VALUES(7, 555, 1);
INSERT INTO OrderItem VALUES(7, 777, 1);
INSERT INTO OrderItem VALUES(7, 888, 1);
INSERT INTO OrderItem VALUES(7, 999, 1);
INSERT INTO OrderItem VALUES(7, 666, 1);
这种方法考虑了使用 Extended Jaccard Coefficient 或Tanimoto Similarity的 Quantity 。它通过使用数量级的常见 ItemID 向量计算所有订单的相似性。它确实需要进行表扫描，但不需要对所有可能的相似性进行 N^2 次计算。
SELECT
OrderID,
SUM(v1.Quantity * v2.Quantity) /
(SUM(v1.Quantity * v1.Quantity) +
SUM(v2.Quantity * v2.Quantity) -
SUM(v1.Quantity * v2.Quantity) ) AS coef
FROM
OrderItem v1 FULL OUTER JOIN OrderItem v2
ON v1.ItemID = v2.ItemID
AND v2.OrderID = ?
GROUP BY OrderID
HAVING coef > 0.85;
扩展 Jaccard 系数的公式：
这个问题真的没有简单的答案。您当然可以存储 Jaccard 索引（实际上我只是存储符合条件的索引，然后丢弃其余索引），但真正的问题是计算它（实际上每次新订单时都必须扫描所有现有订单已输入系统以计算新指数）。
这可能会非常昂贵，具体取决于您维护的订单量。也许您只将它与去年的订单进行比较，或者其他什么。
如果你在飞行中做它，它会变得更有趣，但仍然很昂贵。
您可以轻松获得具有相同产品项目的所有订单的列表。每个项目一个列表。事实上，这不一定是很多数据（如果您对单个热门商品有很多订单，那么它可能是一个很长的列表）。单个查询也不是特别疯狂（再次取决于您的数据）。如果您拥有大量数据，则可以轻松地映射/减少查询，甚至可以使用分片数据存储。位图索引（如果你的数据库支持的话）特别适合快速获取这样的列表。
然后，您可以简单地计算一个订单号在所有列表中出现的次数，然后将那些不符合阈值的丢弃。这是一个直接的合并操作。
但是每次需要信息时都必须进行此计算，因为您无法真正存储它。
因此，它确实归结为您需要信息的目的、您需要它的频率、您的项目 <-> 订单分配、您可以等待多长时间等。
附加物：
再想一想，这是一个简单的查询，但运行起来可能需要一些时间。现代硬件可能并不多，您实际上并没有那么多数据。对于查看订单的单个屏幕，您不会注意到它。如果您在所有订单上运行报告，那么您肯定会注意到它——并且需要一种不同的方法。
让我们考虑一个包含 20 个订单项的订单。
你想要一个 85% 的匹配。这意味着有 17 个或更多共同项目的订单。
这是一个查询，它将为您提供您感兴趣的订单：
SELECT orderId, count(*) FROM OrderItem
WHERE itemId in ('list', 'of', 'items', 'in', 'order', 123, 456, 789)
GROUP BY orderId
HAVING count(*) >= 17
因此，这为您提供了与您的订单具有相同项目的所有订单项的集合。然后，您只需将它们通过 orderId 进行汇总，那些等于或大于您的阈值（本例中为 17）的就是候选订单。
现在，您不会说目录中有多少商品。如果您有 1000 个完美分布的项目，则此查询将处理 1600 行数据——这没什么大不了的。有了适当的索引，这应该很快。但是，如果您拥有“非常受欢迎”的项目，那么您将需要仔细阅读更多行数据。
但是，同样，您没有那么多数据。大多数查询可以在适当数据库的索引中完成，甚至不会命中实际表。因此，正如我所说，您可能不会注意到此查询对交互式系统的影响。
所以，试一试，看看它对你有什么好处。
这与其说是一个扩展评论，不如说是一个真正的答案。如果认为没有意义，我会删除它。
如果您试图即时查找“相似”商品，那么问题在于您有很多（约 79k）订单要查看。因此，如果您尝试这样做，那么您需要在进行昂贵的集合比较之前减少您正在考虑的订单数量。
@Will 指出的一种方法是考虑订单中的项目数量。因此，如果您的目标订单有 20 个项目，那么您只需要考虑具有 17-23 个 OrderItems 的订单（或类似的东西，取决于“85% 相似性”的精确计算）。我假设这些数字可以通过触发器计算，无论何时创建或更改订单，并存储在订单表的列中。
但是，如果您可以存储集合的大小，那么您也可以存储其他数字。例如，您可以在每个 Order 中存储奇数个OrderItem 主键值。然后，您正在考虑的订单必须适当地接近具有该数量的奇数订单号（我可能会在某个时候进行数学运算以填写“适当地接近”）。
如果您认为通过“奇数”将值划分为大小为 1 的条带，您可以使用模数运算符轻松地通过不同大小的条带进行划分。例如。ItemID%4<2 将制作大小为 2 的条纹。然后，您可以为每个 Order 记录这些条带中 OrderItem 主键的数量。您的候选订单必须在每种划分值的方式上适当地接近您的目标订单。
因此，您最终会得到一个大子查询，它试图通过查看存储在该表上并编制索引的一大堆指标来限制 Orders 表中候选者的大小。
嗯，有趣的是，我目前正在做类似的事情。您为什么不将样本订单（即他们的商品）与所有其他订单（他们的商品）结合起来，并通过对每个订单的匹配数进行分组来列出所有匹配率至少为 85% 的订单？
-- let @SampleorderID be the ID of a sample
declare @totalOrders int, @ThresholdOrderCount int
select @totalOrders = count(*) from OrderItems where orderID=@SampleOrderID
set @ThresholdOrderCount = 85*@totalOrders/100 -- 85% of the item amount of the sample
-- Now match the contents of the sample order with the contents of all other orders
-- count the #matches and show only those orders with at least 85% identical items
Select AllOrder.OrderID, count(*)
from OrderItems sample
join OrderItems AllOrder
on sample.ItemID = AllOrder.ItemID
where sample.OrderID = @SampleOrderID
and sample.OrderID<>AllOrder.OrderID
group by AllOrder.OrderID
having count(*)>@ThresholdOrderCount
这应该有效。但是，它也会返回订单，其中包含比样本更多的项目。如果没问题，那么上面的查询也应该很快。
为了速度，我会尝试这样的事情，按与 Order @OrderId 的相似性列出订单。加入的 INTS 应该是交集，相似度值是我计算 Jaccard 指数的尝试。
我在这里根本没有使用数量字段，但我认为如果我们找到一种量化包括数量在内的相似性的方法，它也可以在不减慢查询速度的情况下完成。下面，我将两个订单中的任何相同项目计算为相似性。您也可以加入数量，或使用包含数量的匹配项加倍的度量。我不知道这是否合理。
SELECT
OI.OrderId,
1.0*COUNT(INTS.ItemId) /
(COUNT(*)
+ (SELECT COUNT(*) FROM OrderItem WHERE OrderID = @OrderId)
- COUNT(INTS.ItemId)) AS Similarity
FROM
OrderItem OI
JOIN
OrderItem INTS ON INTS.ItemID = OI.ItemID AND INTS.OrderId=@OrderId
GROUP BY
OI.OrderId
HAVING
1.0*COUNT(INTS.ItemId) /
(COUNT(*)
+ (SELECT COUNT(*) FROM OrderItem WHERE OrderID = @OrderId)
- COUNT(INTS.ItemId)) > 0.85
ORDER BY
Similarity DESC
它还假定 OrderId/ItemId 组合在 OrderItem 中是唯一的。我意识到情况可能并非如此，并且可以使用视图来解决。
我确信有更好的方法，但衡量差异的一种方法是用类似这样的东西（假设所有数量都是正数）替换提名者 COUNT(INTS.ItemId)不同。
1/(ABS(LOG(OI.quantity)-LOG(INTS.quantity))+1)
补充：这个更易读的解决方案使用 JRideout 建议的 Tanimoto Similarity
DECLARE
@ItemCount INT,
@OrderId int
SELECT
@OrderId = 1
SELECT
@ItemCount = COUNT(*)
FROM
OrderItem
WHERE
OrderID = @OrderId
SELECT
OI.OrderId,
SUM(1.0* OI.Quantity*INTS.Quantity/(OI.Quantity*OI.Quantity+INTS.Quantity*INTS.Quantity-OI.Quantity*INTS.Quantity )) /
(COUNT(*) + @ItemCount - COUNT(INTS.ItemId)) AS Similarity
FROM
OrderItem OI
LEFT JOIN
OrderItem INTS ON INTS.ItemID = OI.ItemID AND INTS.OrderId=@OrderId
GROUP BY
OI.OrderId
HAVING
SUM(1.0* OI.Quantity*INTS.Quantity/(OI.Quantity*OI.Quantity+INTS.Quantity*INTS.Quantity-OI.Quantity*INTS.Quantity )) /
(COUNT(*) + @ItemCount - COUNT(INTS.ItemId)) > 0.85
ORDER BY
Similarity DESC
我会采取的方法是首先找到与所选订单的订单项相似 85% 的所有订单项，然后计算每个订单的这些订单项的数量并检查项目数是否与 85% 相似选择的订单，使用以下查询：
DECLARE @OrderId int = 2
SET @OrderId = 6
/*
Retrieve orderitems that match 85% with required @orderId
*/
;WITH SelectedOrderItemCount
AS
(
SELECT COUNT(*) * 0.85 AS LowerBoundary, COUNT(*) * 1.15 AS UpperBoundary
FROM OrderItem
WHERE OrderId = @OrderId
)
SELECT OtherOrders.OrderId, COUNT(*) as NumberOfOrderItems
FROM OrderItem SpecificOrder
INNER JOIN OrderItem OtherOrders
ON OtherOrders.ItemId = SpecificOrder.ItemId
WHERE SpecificOrder.OrderId = @OrderId AND
OtherOrders.OrderId <> @OrderId AND
OtherOrders.Quantity BETWEEN SpecificOrder.Quantity * 0.85 AND SpecificOrder.Quantity * 1.15
GROUP BY OtherOrders.OrderId
HAVING COUNT(*) BETWEEN (SELECT LowerBoundary FROM SelectedOrderItemCount)
AND (SELECT UpperBoundary FROM SelectedOrderItemCount)
完整的 SQLFiddle 演示在这里
这是一种数据挖掘问题。因此，您可以使用 85% 支持的 Apriori 算法，而不是使用 sql。该算法的实现可在许多工具中免费获得。