{"action":"created","issue":{"url":"https://api.github.com/repos/prestodb/presto/issues/6036","repository_url":"https://api.github.com/repos/prestodb/presto","labels_url":"https://api.github.com/repos/prestodb/presto/issues/6036/labels{/name}","comments_url":"https://api.github.com/repos/prestodb/presto/issues/6036/comments","events_url":"https://api.github.com/repos/prestodb/presto/issues/6036/events","html_url":"https://github.com/prestodb/presto/pull/6036","id":174991022,"number":6036,"title":"Add approximate most frequent aggregation","user":{"login":"yingted","id":3887435,"avatar_url":"https://avatars.githubusercontent.com/u/3887435?v=3","gravatar_id":"","url":"https://api.github.com/users/yingted","html_url":"https://github.com/yingted","followers_url":"https://api.github.com/users/yingted/followers","following_url":"https://api.github.com/users/yingted/following{/other_user}","gists_url":"https://api.github.com/users/yingted/gists{/gist_id}","starred_url":"https://api.github.com/users/yingted/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yingted/subscriptions","organizations_url":"https://api.github.com/users/yingted/orgs","repos_url":"https://api.github.com/users/yingted/repos","events_url":"https://api.github.com/users/yingted/events{/privacy}","received_events_url":"https://api.github.com/users/yingted/received_events","type":"User","site_admin":false},"labels":[{"id":196992743,"url":"https://api.github.com/repos/prestodb/presto/labels/CLA%20Signed","name":"CLA Signed","color":"ededed","default":false}],"state":"open","locked":false,"assignee":{"login":"cberner","id":842688,"avatar_url":"https://avatars.githubusercontent.com/u/842688?v=3","gravatar_id":"","url":"https://api.github.com/users/cberner","html_url":"https://github.com/cberner","followers_url":"https://api.github.com/users/cberner/followers","following_url":"https://api.github.com/users/cberner/following{/other_user}","gists_url":"https://api.github.com/users/cberner/gists{/gist_id}","starred_url":"https://api.github.com/users/cberner/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cberner/subscriptions","organizations_url":"https://api.github.com/users/cberner/orgs","repos_url":"https://api.github.com/users/cberner/repos","events_url":"https://api.github.com/users/cberner/events{/privacy}","received_events_url":"https://api.github.com/users/cberner/received_events","type":"User","site_admin":false},"assignees":[{"login":"cberner","id":842688,"avatar_url":"https://avatars.githubusercontent.com/u/842688?v=3","gravatar_id":"","url":"https://api.github.com/users/cberner","html_url":"https://github.com/cberner","followers_url":"https://api.github.com/users/cberner/followers","following_url":"https://api.github.com/users/cberner/following{/other_user}","gists_url":"https://api.github.com/users/cberner/gists{/gist_id}","starred_url":"https://api.github.com/users/cberner/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cberner/subscriptions","organizations_url":"https://api.github.com/users/cberner/orgs","repos_url":"https://api.github.com/users/cberner/repos","events_url":"https://api.github.com/users/cberner/events{/privacy}","received_events_url":"https://api.github.com/users/cberner/received_events","type":"User","site_admin":false}],"milestone":null,"comments":1,"created_at":"2016-09-05T03:52:56Z","updated_at":"2016-11-07T19:10:32Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/prestodb/presto/pulls/6036","html_url":"https://github.com/prestodb/presto/pull/6036","diff_url":"https://github.com/prestodb/presto/pull/6036.diff","patch_url":"https://github.com/prestodb/presto/pull/6036.patch"},"body":"(Moved from https://github.com/prestodb/presto/pull/4120)\n\nThis PR adds a truncated histogram aggregation that computes an approximate histogram of values. It's a hybrid of `histogram` and `numeric_histogram`.\n\nThe truncated histogram aggregation can be used to get an upper and lower bound for how many times each value appears in a column, for up to `buckets` values:\n- For less than `buckets` distinct values, it'll return the same result as `histogram(value)`.\n- For skewed distributions, you can get tight bounds for most permutations of the distribution.\n- For unskewed distributions, the bounds will be very loose. (for example, `SELECT approx_most_frequent(251, user_id) FROM users`).\n- I think, if any value appears more than `1 / buckets` of the time, it will be reported.\n\nIn addition, just like `histogram`, if the memory usage exceeds 4 MB, the query will fail. However, this generally happens only when the bucket count is set too high. I've also decreased the hash table load factor from 90% to 75% because it gives me 1.8x throughput (rows/cpu sec) in my tests.\n\nOriginal issue: https://github.com/facebook/presto/issues/4094\nCopied from: https://github.com/facebook/presto/pull/4119/\n\nText from issue:\n\n> I'm looking for an efficient way to get an (approximate) histogram of the frequent values for each column of a table. These columns are generally high-cardinality, but often skewed. Currently, I'm running a sequence of queries like:\n> \n> ```\n> SELECT col_x, count(*) AS c\n>     FROM my_table\n>     GROUP BY col_x\n>     ORDER BY c DESC\n>     LIMIT 250;\n> ```\n> \n> This is pretty slow when there are a lot of columns. I've tried running the queries together (using UNION ALL) and such, but it doesn't seem to avoid scanning the table multiple times. I'm looking for a faster way to approximate this result. I've looked at `TABLESAMPLE SYSTEM`, but it seems to omit data in a predictable way because of how my tables are laid out.\n> \n> I've noticed there is the `histogram(value)` and `numeric_histogram(bucket_limit, value)` aggregations. Are there any plans for an approximate variant of my SQL query?\n> \n> If not, would a patch be welcome? I'm thinking the signature would be:\n> `approx_most_frequent(bucket_limit, value)`. The algorithm would be a variant of Space-Saving [1], which computes frequent elements in constant space and linear time in input size. It returns tight error bounds for skewed data. In the limit, as `bucket_limit => infinity`, it degrades to `histogram`.\n> The implementation would be similar to that of `numeric_histogram`: Periodically, the smallest counters are merged.\n> \n> [1] Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi,\n>         \"Efficient Computation of Frequent and Top-_k_ Elements in Data Streams\",\n>         https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf\n"},"comment":{"url":"https://api.github.com/repos/prestodb/presto/issues/comments/258931876","html_url":"https://github.com/prestodb/presto/pull/6036#issuecomment-258931876","issue_url":"https://api.github.com/repos/prestodb/presto/issues/6036","id":258931876,"user":{"login":"cberner","id":842688,"avatar_url":"https://avatars.githubusercontent.com/u/842688?v=3","gravatar_id":"","url":"https://api.github.com/users/cberner","html_url":"https://github.com/cberner","followers_url":"https://api.github.com/users/cberner/followers","following_url":"https://api.github.com/users/cberner/following{/other_user}","gists_url":"https://api.github.com/users/cberner/gists{/gist_id}","starred_url":"https://api.github.com/users/cberner/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cberner/subscriptions","organizations_url":"https://api.github.com/users/cberner/orgs","repos_url":"https://api.github.com/users/cberner/repos","events_url":"https://api.github.com/users/cberner/events{/privacy}","received_events_url":"https://api.github.com/users/cberner/received_events","type":"User","site_admin":false},"created_at":"2016-11-07T19:10:32Z","updated_at":"2016-11-07T19:10:32Z","body":"realistically, I'm never going to have time to review this, so putting it up for grabs in case someone else does"}}
{"actor":{"display_login":"cberner"}}