Scalable Uniques in Postgres with HLL

Transcript

1. Scalable Uniques in Postgres - Craig Kerstiens Heroku Postgres
2. Postgresql-HLL
3. Truviso • Extended Postgres to do streaming • Various markets • Ad space • Wanted unique impressions • Sort of wanted unique impressions
4. SELECT count(*)
5. Approx Top K
6. Compressed Bitmap
7. HyperLogLog
8. HyperLogLog • KMV - K minimum value
9. HyperLogLog • KMV - K minimum value • Bit observable patterns
10. HyperLogLog • KMV - K minimum value • Bit observable patterns • Stochastic averaging
11. HyperLogLog • KMV - K minimum value • Bit observable patterns • Stochastic averaging • Harmonic averaging
12. HyperLogLog • KMV - K minimum value • Bit observable patterns • Stochastic averaging • Harmonic averaging
13. HyperLogLog • KMV - K minimum value • Bit observable patterns • Stochastic averaging • Harmonic averaging • Implemented by Aggregate Knowledge
15. HyperLogLog Probabilistic uniques with small footprint
16. HyperLogLog Probabilistic uniques with small footprint Close enough distinct with small footprint
17. Use cases
18. Use cases • Semi distinct count • Think pg_stat_statements • Ad networks • Web traffic
19. Use cases • Semi distinct count • Think pg_stat_statements • Ad networks • Web traffic • With rollups/groupings
20. Digging in CREATE  EXTENSION  hll;    CREATE  TABLE  helloworld  (            id        integer,            set      hll    );
21. Digging in CREATE  EXTENSION  hll;    CREATE  TABLE  helloworld  (            id        integer,            set      hll    );
22. Inserting data UPDATE  helloworld   SET  set  =  hll_add(set,  hll_hash_integer(12345))   WHERE  id  =  1; UPDATE  helloworld   SET  set  =  hll_add(set,  hll_hash_text('hello  world'))   WHERE  id  =  1;
23. Real world CREATE  TABLE  daily_uniques  (        date                        date  UNIQUE,        users                      hll );
24. Real world INSERT  INTO  daily_uniques(date,  users)    SELECT  date,  hll_add_agg(hll_hash_integer(user_id))    FROM  users    GROUP  BY  1;
25. Real world SELECT                EXTRACT(MONTH  FROM  date)  AS  month,                hll_cardinality(hll_union_agg(users)) FROM  daily_uniques WHERE  date  >=  '2012-­‐01-­‐01'  AND            date  <    '2013-­‐01-­‐01' GROUP  BY  1;
26. Real world SELECT                EXTRACT(MONTH  FROM  date)  AS  month,                hll_cardinality(hll_union_agg(users)) FROM  daily_uniques WHERE  date  >=  '2012-­‐01-­‐01'  AND            date  <    '2013-­‐01-­‐01' GROUP  BY  1;
27. Good practices
28. Good practices
29. Good practices • It uses update
30. Good practices • It uses update • Do as a batch in most cases
31. Good practices • It uses update • Do as a batch in most cases • Tweak the config
32. Tuning Parameters
33. Tuning Parameters • log2m - log base 2 of registers • Between 4 and 17 • Each 1 increase doubles storage
34. Tuning Parameters • log2m - log base 2 of registers • Between 4 and 17 • Each 1 increase doubles storage • regwidth - bits per register
35. Tuning Parameters • log2m - log base 2 of registers • Between 4 and 17 • Each 1 increase doubles storage • regwidth - bits per register • expthresh - threshold for explicit vs sparse
36. Tuning Parameters • log2m - log base 2 of registers • Between 4 and 17 • Each 1 increase doubles storage • regwidth - bits per register • expthresh - threshold for explicit vs sparse • spareson - on/off for sparse
37. Is it better?
38. 1280 bytes Estimate count of 10s of billions Few percent error
39. Resources • https://github.com/aggregateknowledge/ postgresql-hll • http://blog.aggregateknowledge.com/ 2013/02/04/open-source-release- postgresql-hll/ • http://tapoueh.org/blog/2013/02/25- postgresql-hyperloglog
40. Questions