为什么啤酒和纸尿裤最搭 - 用HybridDB/PostgreSQL查询商品营销最佳组合
背景
购买早餐时，包子和豆浆、茶叶蛋是最佳搭档吗？
为什么纸尿裤和啤酒是最佳搭档？
这些问题在积累了一定的订单数据后，是可以挖掘出来的。这个问题实际上是4.8号PostgreSQL社区杭州区活动上，一位社区的朋友提出来的，如何使用PostgreSQL找出最佳搭配的商品。
实际上有一个专业的推荐数据库，支持多种推荐算法，也可以很好的解决这个问题。
但是本文不打算使用RecDB这个产品来解决这样的问题。而是使用统计的方法能得出结论。
本文统计方法限制
本文涉及的统计方法只能用于计算直接关联的商品（表现为在同一个订单中的数据）的最佳组合。
如果你要计算间接关联的商品组合，例如A用户买了1,2，B用户买了2,3，实际上1,3是存在间接关联关系的。那么你需要用到recDB中提到的推荐算法，或者使用类似图式搜索。
参考
《金融风控、公安刑侦、社会关系、人脉分析等需求分析与数据库实现 - PostgreSQL图数据库场景应用》
场景虚构
假设有10万商品ID，虚构一批用户的购买或购物车记录，每一条订单或购物车记录中包含5到15个商品。一共构建约1100万条这样的记录。
建表
postgres=# create unlogged table buy (pay_id int8, item_id int[]);
CREATE TABLE
造数据
创建一个函数，用于插入buy表，（5到15个商品的数组）
create or replace function f() returns void as $$
declare
begin
for i in 5..15 loop
insert into buy (item_id) select array_agg((100000*random())::int8) from generate_series(1,i);
end loop;
end;
$$ language plpgsql strict;
使用pgbench，生成1100万记录
vi test.sql
select f();
pgbench -M prepared -n -r -P 1 -f ./test.sql -c 100 -j 100 -t 10000
transaction type: ./test.sql
scaling factor: 1
query mode: prepared
number of clients: 100
number of threads: 100
number of transactions per client: 10000
number of transactions actually processed: 1000000/1000000
latency average = 1.155 ms
latency stddev = 1.814 ms
tps = 85204.625725 (including connections establishing)
tps = 85411.351807 (excluding connections establishing)
script statistics:
- statement latencies in milliseconds:
1.158 select f();
确认数据已写入
postgres=# select count(*) from buy;
count
----------
11000000
(1 row)
postgres=# select * from buy limit 10;
pay_id | item_id
--------+--------------------------------------------------------------
| {6537,76804,33612,75580,8021}
| {72437,66015,2939,56128,7056}
| {40983,79581,15954,21039,6702,90279}
| {93626,8337,13416,69371,4366,75868}
| {84611,56893,25201,74038,59337,62045,59178}
| {97422,48801,69714,77056,17059,79714,21598}
| {42997,50834,57214,52866,83656,76342,5639,93416}
| {53543,24369,31552,28654,38516,63657,86564,11483}
| {58873,23162,23369,55091,32046,29907,31895,65658,5487}
| {39916,6641,85068,55870,27679,91770,46150,12290,48662,71350}
(10 rows)
GIN索引
postgres=# create index idx_buy_item on buy using gin(item_id);
分裂函数
分裂的目的是将一笔订单中的数组，分裂成若干个组合。例如5个商品的订单，拆分成4+3+2+1=10个2个商品的组合。
{6537,76804,33612,75580,8021}
拆分为如下组合
{6537,76804}
{6537,33612}
{6537,75580}
{6537,8021}
{76804,33612}
{76804,75580}
{76804,8021}
{33612,75580}
{33612,8021}
{75580,8021}
创建一个函数来完成这样的拆分工作
使用递归查询可以满足重新组合的目的
例子
WITH RECURSIVE
t(i) AS (
SELECT * FROM unnest('{A,B,C}'::char[])
),
cte AS (
SELECT i AS combo, i, 1 AS ct
FROM t
UNION ALL
SELECT cte.combo || t.i, t.i, ct + 1
FROM cte, t
WHERE ct <= 3 -- 组合3+1=4次
AND position(t.i in cte.combo) = 0 -- 新加入的字符不在已有字符中
)
SELECT ARRAY(SELECT combo FROM cte ORDER BY ct, combo) AS result;
result
---------------------------------------------------
{A,B,C,AB,AC,BA,BC,CA,CB,ABC,ACB,BAC,BCA,CAB,CBA}
(1 row)
函数1，返回指定个数的组合
假设数组中没有重复元素
create or replace function array_regroup(
i_arr int[], -- 输入数组
i_elems int -- 打散成固定长度的组合
) returns setof int[] as $$
declare
v_arr_len int := array_length(i_arr, 1); -- 输入的数组长度
begin
-- 保护
if i_elems > v_arr_len then
raise notice 'you cann''t return group len % more then %', i_elems, v_arr_len;
return;
elsif i_elems = v_arr_len then
return next i_arr;
return;
elsif i_elems = 1 then
return query select array(select i) from unnest(i_arr) t(i);
return;
end if;
return query
WITH RECURSIVE
t(i) AS (
select array(select i) from unnest(i_arr) t(i)
),
cte AS (
SELECT i AS combo, i, 1 AS ct
FROM t
UNION ALL
SELECT array(select i from (select unnest(array_cat(cte.combo, t.i)) order by 1) t(i)), t.i, ct + 1
FROM cte, t
WHERE cte.ct <= i_elems-1 -- 组合若干次
AND (not cte.combo @> t.i) -- 新加入的值不在已组合的值中
)
SELECT combo FROM cte where array_length(combo,1)=i_elems group by combo;
return;
end;
$$ language plpgsql strict;
postgres=# select array_regroup(array[1,2,3],2);
array_regroup
---------------
{2,3}
{1,2}
{1,3}
(3 rows)
函数2，返回所有个数的组合
create or replace function array_regroup(
i_arr int[] -- 输入数组
) returns setof int[] as $$
declare
v_arr_len int := array_length(i_arr, 1); -- 输入的数组长度
begin
return query
WITH RECURSIVE
t(i) AS (
select array(select i) from unnest(i_arr) t(i)
),
cte AS (
SELECT i AS combo, i, 1 AS ct
FROM t
UNION ALL
SELECT array(select i from (select unnest(array_cat(cte.combo, t.i)) order by 1) t(i)), t.i, ct + 1
FROM cte, t
WHERE cte.ct <= v_arr_len-1 -- 组合若干次
AND (not cte.combo @> t.i) -- 新加入的值不在已组合的值中
)
SELECT combo FROM cte group by combo;
return;
end;
$$ language plpgsql strict;
postgres=# select array_regroup(array[1,2,3]);
array_regroup
---------------
{2}
{2,3}
{1,2}
{1}
{1,2,3}
{3}
{1,3}
(7 rows)
函数3，返回指定个数的组合，仅输出包含了某些元素的组合（例如包含了面包ID的数组）
create or replace function array_regroup(
i_arr int[], -- 输入数组
i_elems int, -- 打散成固定长度的组合
i_arr_contain int[] -- 包含了这些商品ID的数组
) returns setof int[] as $$
declare
v_arr_len int := array_length(i_arr, 1); -- 输入的数组长度
begin
-- 保护
if i_elems > v_arr_len then
raise notice 'you cann''t return group len % more then %', i_elems, v_arr_len;
return;
elsif i_elems = v_arr_len then
return next i_arr;
return;
elsif i_elems = 1 then
return query select array(select i) from unnest(i_arr) t(i);
return;
end if;
return query
WITH RECURSIVE
t(i) AS (
select array(select i) from unnest(i_arr) t(i)
),
cte AS (
SELECT i AS combo, i, 1 AS ct
FROM t
UNION ALL
SELECT array(select i from (select unnest(array_cat(cte.combo, t.i)) order by 1) t(i)), t.i, ct + 1
FROM cte, t
WHERE cte.ct <= i_elems-1 -- 组合若干次
AND (not cte.combo @> t.i) -- 新加入的值不在已组合的值中
AND (cte.combo @> i_arr_contain)
)
SELECT combo FROM cte where array_length(combo,1)=i_elems group by combo;
return;
end;
$$ language plpgsql strict;
postgres=# select array_regroup(array[1,2,3,4,5],2,array[1]);
array_regroup
---------------
{1,2}
{1,3}
{1,4}
{1,5}
(4 rows)
Time: 1.150 ms
求单品的最佳一级组合
例如，找出面包的1个最佳搭档。
假设面包的商品ID=6537
postgres=# select item_id from buy where item_id @> array[6537];
......
{60573,17248,6537,77857,43349,66208,13656}
{97564,50031,79924,24255,6537,21174,39117}
{24026,78667,99115,87856,64782,8344,73169,41478,63091,29609,6537,71982,75382}
{53094,97465,26156,54181,6537}
(1101 rows)
Time: 5.791 ms
postgres=# explain select item_id from buy where item_id @> array[6537];
QUERY PLAN
---------------------------------------------------------------------------------
Bitmap Heap Scan on buy (cost=457.45..51909.51 rows=55000 width=60)
Recheck Cond: (item_id @> '{6537}'::integer[])
-> Bitmap Index Scan on idx_buy_item (cost=0.00..443.70 rows=55000 width=0)
Index Cond: (item_id @> '{6537}'::integer[])
(4 rows)
组合，寻找出现次数最多的组合。
postgres=# select count(*), array_regroup(item_id,2,array[6537]) from buy where item_id @> array[6537] group by 2 order by 1 desc;
count | array_regroup
-------+---------------
3 | {6537,55286}
3 | {6537,48661}
3 | {6537,78337}
3 | {6537,72623}
3 | {6537,81442}
3 | {6537,66414}
3 | {6537,35346}
3 | {6537,79565}
3 | {3949,6537}
......
Time: 286.859 ms
求单品的最佳二级组合
例如，找出面包的两个最佳搭档。
postgres=# select count(*), array_regroup(item_id,3,array[6537]) from buy where item_id @> array[6537] group by 2 order by 1 desc;
count | array_regroup
-------+--------------------
1 | {32,999,6537}
1 | {6537,49957,91533}
1 | {6537,49957,88377}
1 | {6537,49957,57887}
1 | {6537,49957,55192}
1 | {6537,49952,95266}
1 | {6537,49952,56916}
1 | {6537,49945,60492}
1 | {6537,49940,92888}
......
Time: 1055.414 ms
统计全网数据的最佳一级组合
可能需要很久
select count(*), array_regroup(item_id,2) from buy group by 2 order by 1 desc limit 10;
统计全网数据的最佳N级组合
可能需要很久
select count(*), array_regroup(item_id, n) from buy group by 2 order by 1 desc limit 10;
小结
1. 这个案例并没有什么高超的技术含量，仅仅是将数组按推荐级数进行分裂，统计出现的次数。
用到的数据库特性包括：
1.1. 数组类型的支持
1.2. plpgsql服务端编程
1.3. 数组元素的索引检索(包含某个元素)
1.4. MPP, 分布式数据库架构，提升运算速度。可以参考阿里云的HybridDB for PostgreSQL产品。
2. 注意, 本文统计方法限制
本文涉及的统计方法只能用于计算直接关联的商品（表现为在同一个订单中的数据）的最佳组合。
如果你要计算间接关联的商品组合，例如A用户买了1,2，B用户买了2,3，实际上1,3是存在间接关联关系的。那么你需要用到recDB中提到的推荐算法，或者使用类似图式搜索。
参考
《金融风控、公安刑侦、社会关系、人脉分析等需求分析与数据库实现 - PostgreSQL图数据库场景应用》
3. 阿里云HybridDB for PostgreSQL提供了MPP的能力，可以水平扩展，非常适合OLAP场景。例如本案涉及的大量group by的操作，可以得到很好的性能提升。
4. PostgreSQL 9.6开始加入了基于CPU的多核并行计算功能，对于OLAP场景也有非常大的性能提升，例如本案涉及的大量group by的操作，可以得到很好的性能提升。
参考
https://github.com/DataSystemsLab/recdb-postgresql
https://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy1/index.html
《分析加速引擎黑科技 - LLVM、列存、多核并行、算子复用 大联姻 - 一起来开启PostgreSQL的百宝箱》
《PostgreSQL 向量化执行插件(瓦片式实现) 10x提速OLAP》
《ApsaraDB的左右互搏(PgSQL+HybridDB+OSS) - 解决OLTP+OLAP混合需求》
《金融风控、公安刑侦、社会关系、人脉分析等需求分析与数据库实现 - PostgreSQL图数据库场景应用》