非重复计数算法

Question

我想知道是否可以通过以下方式进行近似的非重复计数：

我有这样的聚合：

  +---------+----------------------+-------------------------------+
  | country | unique products sold | helper_data -- limit 1MB size |
  +---------+----------------------+-------------------------------+
  | US      | 100,000,005          | ??                            |
  | CA      | 192,394,293          | ??                            |
  +---------+----------------------+-------------------------------+

我想知道我是否可以获得以下信息：

  +---------+--------------------------------------+
  | country |         unique products sold         |
  +---------+--------------------------------------+
  | [ALL]   | 205,493,599 # possible to get this?? |
  | US      | 100,000,005                          |
  | CA      | 192,394,293                          |
  +---------+--------------------------------------+

换句话说，如果不传递所有的值（太多了，我没有足够的内存来处理它），是否可以为每个地区特定的行传递某种散列（或其他东西） -item，以估计在多个项目之间加在一起时近似的不同计数是多少？或者这是不可能的。

请注意，我不是在寻找 sql 方法，我只是想看看是否可以通过某种 object/hash/etc。返回每个订单项，然后跨多个订单项建立一个近似的唯一计数。

Answer 1

下面是 BigQuery Standard SQL 的简化示例，[我认为] 完全重现了您的用例

#standardSQL
WITH `project.dataset.table` AS (
  SELECT 'us' country, 1 product_id UNION ALL
  SELECT 'us', 2 UNION ALL
  SELECT 'us', 3 UNION ALL
  SELECT 'us', 4 UNION ALL
  SELECT 'us', 5 UNION ALL
  SELECT 'ca', 3 UNION ALL
  SELECT 'ca', 4 UNION ALL
  SELECT 'ca', 5 UNION ALL
  SELECT 'ca', 6 UNION ALL
  SELECT 'ca', 7 UNION ALL
  SELECT 'ca', 8 UNION ALL
  SELECT 'ca', 9
), aggregation AS (
  SELECT country, 
    COUNT(DISTINCT product_id) unique_products_sold,
    HLL_COUNT.INIT(product_id) AS helper_data
  FROM `project.dataset.table`
  GROUP BY country
)
SELECT country, unique_products_sold FROM aggregation UNION ALL
SELECT 'all', HLL_COUNT.MERGE(helper_data) FROM aggregation

结果

Row country unique_products_sold     
1   ca      7    
2   us      5    
3   all     9

如您所见，这是一个非常简单的查询，您可以在任何您喜欢的客户端中使用 - 例如 python

非重复计数算法

Distinct Count algorithm

python

algorithm

google-bigquery

hyperloglog