如何通过SQL为指定产品集合选择供应商数量最少的Listing？

表结构 #

CREATE TABLE products (id INT AUTOINCREMENT);
CREATE TABLE listings (
  id INT AUTOINCREMENT,
  product INT REFERENCES products(id),
  vendor INT
)

需求 #

为指定的一组产品选择对应的Listing，使得所涉及的不同供应商（vendor）数量最少。

示例数据 #

当指定产品集合为(1,2,3)时，期望得到的Listing id为(1,4,5)——供应商1覆盖产品1和2，供应商4覆盖产品3，仅2个不同供应商，是最少的可能。

提问 #

能否仅通过SQL实现该需求？还是需要通过多查询组合结果？

这个需求可以通过单条SQL语句实现，它本质是简化版的最小集合覆盖问题，我们可以借助递归CTE（公共表表达式）来枚举并筛选出最优的供应商组合，最终匹配对应的Listing。

以PostgreSQL为例，具体实现如下：

WITH target_products AS (
    -- 指定需要覆盖的目标产品集合
    SELECT unnest(ARRAY[1,2,3]) AS product_id
),
vendor_coverage AS (
    -- 统计每个供应商能覆盖的目标产品
    SELECT 
        l.vendor,
        array_agg(DISTINCT l.product) AS covered_products
    FROM listings l
    JOIN target_products tp ON l.product = tp.product_id
    GROUP BY l.vendor
),
recursive_sets AS (
    -- 递归起始：单个供应商的覆盖情况
    SELECT 
        ARRAY[v.vendor] AS vendor_set,
        v.covered_products AS covered,
        1 AS vendor_count
    FROM vendor_coverage v

    UNION ALL

    -- 递归扩展：逐步添加新供应商，扩大覆盖范围
    SELECT 
        rs.vendor_set || v.vendor,
        array(SELECT DISTINCT unnest(rs.covered) UNION SELECT DISTINCT unnest(v.covered)),
        rs.vendor_count + 1
    FROM recursive_sets rs
    JOIN vendor_coverage v ON v.vendor <> ALL(rs.vendor_set)
    -- 只继续递归还没覆盖所有产品的组合
    WHERE NOT (SELECT array_agg(product_id) FROM target_products) <@ rs.covered
),
optimal_vendors AS (
    -- 筛选出覆盖所有产品且供应商数量最少的组合
    SELECT vendor_set
    FROM recursive_sets
    WHERE (SELECT array_agg(product_id) FROM target_products) <@ covered
    ORDER BY vendor_count ASC
    LIMIT 1
)
-- 匹配对应的Listing，确保每个产品只返回一条记录
SELECT l.id
FROM listings l
JOIN optimal_vendors ov ON l.vendor = ANY(ov.vendor_set)
JOIN target_products tp ON l.product = tp.product_id
GROUP BY l.product, l.id
HAVING l.vendor = (
    SELECT vendor FROM listings l2 
    WHERE l2.product = l.product 
    AND l2.vendor = ANY(ov.vendor_set)
    LIMIT 1
)
ORDER BY l.id;

补充说明 #

• 不同SQL方言的语法会有差异（比如MySQL 8.0+支持递归CTE，但数组操作需要改用JSON或临时表）；
• 如果目标产品数量较多，递归CTE的性能会有所下降，此时可以考虑分步查询优化，但单SQL依然能完成完整逻辑；
• 示例中通过GROUP BY和子查询确保每个产品仅返回一条Listing，和需求示例的输出一致。

如果是非常简单的场景，也可以通过分步查询先统计供应商覆盖度再选择，但单SQL完全可以实现需求。

内容的提问来源于stack exchange，提问作者Filip Ježek