{"action":"closed","number":3148,"pull_request":{"url":"https://api.github.com/repos/druid-io/druid/pulls/3148","id":73824963,"html_url":"https://github.com/druid-io/druid/pull/3148","diff_url":"https://github.com/druid-io/druid/pull/3148.diff","patch_url":"https://github.com/druid-io/druid/pull/3148.patch","issue_url":"https://api.github.com/repos/druid-io/druid/issues/3148","number":3148,"state":"closed","locked":false,"title":"Adds long compression methods","user":{"login":"acslk","id":11131839,"avatar_url":"https://avatars.githubusercontent.com/u/11131839?v=3","gravatar_id":"","url":"https://api.github.com/users/acslk","html_url":"https://github.com/acslk","followers_url":"https://api.github.com/users/acslk/followers","following_url":"https://api.github.com/users/acslk/following{/other_user}","gists_url":"https://api.github.com/users/acslk/gists{/gist_id}","starred_url":"https://api.github.com/users/acslk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/acslk/subscriptions","organizations_url":"https://api.github.com/users/acslk/orgs","repos_url":"https://api.github.com/users/acslk/repos","events_url":"https://api.github.com/users/acslk/events{/privacy}","received_events_url":"https://api.github.com/users/acslk/received_events","type":"User","site_admin":false},"body":"This PR introduces a few new compression strategies for long values that are not block based (described in #3147).  The enum CompressionFormat is added to control the compression procedure, which could call GenericIndexed for block based compression.\r\n\r\nThe compression format added include delta compression, table compression, and a new uncompressed format. Delta compression finds the smallest value in the segment, and store all values as offsets. Table compression maps unique values and store their id. The offsets and ids are stored by using the smallest number of bits required for the maximum values. For example, if the maximum offset is 200, then all values are stored using 8 bits. The new uncompressed format is the uncompressed format without the header for position of each block and empty bytes at beginning of each block.\r\n\r\nUpdate\r\n\r\nAfter some discussion in #3147 , it's decided that compression strategy, which compress and decompress blocks of data without knowing the data format, and encoding format, which encode data using knowledge of its attributes such as size of each element, should be separated. Users would choose the combination of compression and encoding to use.\r\n\r\nThe existing compressions including LZF, LZ4, and Uncompressed all count as compression strategy. In addition, this PR included the compression NONE, which indicate no compression strategy should be used, and the values should be stored all together instead of in blocks, since this would allow faster random access. The LZF and Uncompressed strategy are still needed for backward compatibility, but they shouldn't be used for new data.\r\n\r\nThe encoding format introduced in this PR are Delta, Table, and Longs. Delta and table are described above, while Longs just indicated values are stored as 8 byte longs. Segments created prior to this PR are viewed as compression strategy used + Longs encoding. The strategy for choosing the encoding are auto and longs. Auto strategy scans through the data for its cardinality and maximum offset, and choose the most appropriate format. Longs strategy just always choose longs format.\r\n\r\nBelow is a benchmark of combinations of all compression strategies and encoding strategies using some generated data sets.\r\n\r\nData sets includes: \r\n- enumerated (value from only a few selections, with probability heavily skewed toward one) \r\n- zipfLow (zipf distribution between 0 to 1000 with low exponent)\r\n- zipfHigh (zipf distribution between 0 to 1000 with high exponent)\r\n- uniform (uniform distribution between 0 to 1000)\r\n- sequential (sequential values starting from a timestamp)\r\n\r\nGenerated files size in kb (5,000,000 values)\r\n```\r\nzipfLow-LZ4-DELTA: 6870\r\nzipfLow-LZ4-LONGS: 9495\r\nzipfLow-NONE-DELTA: 7324\r\nzipfLow-NONE-LONGS: 39062\r\nuniform-LZ4-DELTA: 7354\r\nuniform-LZ4-LONGS: 11184\r\nuniform-NONE-DELTA: 7324\r\nuniform-NONE-LONGS: 39062\r\nsequential-LZ4-DELTA: 14706\r\nsequential-LZ4-LONGS: 19542\r\nsequential-NONE-DELTA: 14648\r\nsequential-NONE-LONGS: 39062\r\nenumerate-LZ4-DELTA: 442\r\nenumerate-LZ4-LONGS: 711\r\nenumerate-NONE-DELTA: 2441\r\nenumerate-NONE-LONGS: 39062\r\nzipfHigh-LZ4-DELTA: 1201\r\nzipfHigh-LZ4-LONGS: 1784\r\nzipfHigh-NONE-DELTA: 4884\r\nzipfHigh-NONE-LONGS: 39062\r\n```\r\n\r\nBenchmarks:\r\nreadContinuous reads every value, while readSkipping skips randomly between 0 - 2000 values on each read\r\n```\r\nRead Continuous\r\n enumerate      auto   lz4  30.587 ± 0.493  ms/op\r\n enumerate      auto  none   7.093 ± 0.116  ms/op\r\n enumerate     longs   lz4  19.731 ± 0.849  ms/op\r\n enumerate     longs  none   3.107 ± 0.060  ms/op\r\n   zipfLow      auto   lz4  36.530 ± 0.695  ms/op\r\n   zipfLow      auto  none  11.070 ± 0.209  ms/op\r\n   zipfLow     longs   lz4  33.192 ± 0.652  ms/op\r\n   zipfLow     longs  none   3.127 ± 0.076  ms/op\r\n  zipfHigh      auto   lz4  28.517 ± 0.804  ms/op\r\n  zipfHigh      auto  none   2.808 ± 0.072  ms/op\r\n  zipfHigh     longs   lz4  21.903 ± 0.508  ms/op\r\n  zipfHigh     longs  none   3.033 ± 0.040  ms/op\r\nsequential      auto   lz4  29.984 ± 0.807  ms/op\r\nsequential      auto  none   6.771 ± 0.090  ms/op\r\nsequential     longs   lz4  54.404 ± 1.106  ms/op\r\nsequential     longs  none   3.172 ± 0.088  ms/op\r\n   uniform      auto   lz4  32.214 ± 0.803  ms/op\r\n   uniform      auto  none  10.702 ± 0.145  ms/op\r\n   uniform     longs   lz4  31.917 ± 0.663  ms/op\r\n   uniform     longs  none   3.055 ± 0.072  ms/op\r\n\r\nReadSkipping\r\n enumerate      auto   lz4   1.533 ± 0.075  ms/op\r\n enumerate      auto  none   0.083 ± 0.002  ms/op\r\n enumerate     longs   lz4   5.862 ± 0.471  ms/op\r\n enumerate     longs  none   0.285 ± 0.003  ms/op\r\n   zipfLow      auto   lz4   5.017 ± 0.121  ms/op\r\n   zipfLow      auto  none   0.172 ± 0.003  ms/op\r\n   zipfLow     longs   lz4  19.103 ± 1.118  ms/op\r\n   zipfLow     longs  none   0.283 ± 0.002  ms/op\r\n  zipfHigh      auto   lz4   3.060 ± 0.164  ms/op\r\n  zipfHigh      auto  none   0.109 ± 0.002  ms/op\r\n  zipfHigh     longs   lz4   8.791 ± 1.083  ms/op\r\n  zipfHigh     longs  none   0.280 ± 0.002  ms/op\r\nsequential      auto   lz4   1.379 ± 0.304  ms/op\r\nsequential      auto  none   0.253 ± 0.003  ms/op\r\nsequential     longs   lz4  40.777 ± 0.681  ms/op\r\nsequential     longs  none   0.281 ± 0.003  ms/op\r\n   uniform      auto   lz4   0.822 ± 0.289  ms/op\r\n   uniform      auto  none   0.171 ± 0.003  ms/op\r\n   uniform     longs   lz4  18.799 ± 1.704  ms/op\r\n   uniform     longs  none   0.286 ± 0.003  ms/op\r\n```\r\n\r\nBenchmark on master, lz4 correspond to longs + lz4. There is no major performance difference\r\n```\r\nReadContinous\r\n enumerate     lz4  19.714 ± 0.455  ms/op\r\n   zipfLow     lz4  33.191 ± 0.640  ms/op\r\n  zipfHigh     lz4  21.761 ± 0.488  ms/op\r\nsequential     lz4  54.163 ± 1.077  ms/op\r\n   uniform     lz4  31.790 ± 0.871  ms/op\r\n\r\nReadSkipping\r\n enumerate     lz4   5.741 ± 0.346  ms/op\r\n   zipfLow     lz4  18.736 ± 0.425  ms/op\r\n  zipfHigh     lz4   8.739 ± 0.753  ms/op\r\nsequential     lz4  41.081 ± 1.034  ms/op\r\n   uniform     lz4  18.322 ± 0.325  ms/op\r\n```","created_at":"2016-06-14T22:30:03Z","updated_at":"2016-08-30T23:17:46Z","closed_at":"2016-08-30T23:17:46Z","merged_at":"2016-08-30T23:17:46Z","merge_commit_sha":"c4e8440c229535d9f6b08128cae4102cbfd30ee9","assignee":null,"assignees":[],"milestone":{"url":"https://api.github.com/repos/druid-io/druid/milestones/20","html_url":"https://github.com/druid-io/druid/milestones/0.9.2","labels_url":"https://api.github.com/repos/druid-io/druid/milestones/20/labels","id":1571409,"number":20,"title":"0.9.2","description":"","creator":{"login":"fjy","id":428325,"avatar_url":"https://avatars.githubusercontent.com/u/428325?v=3","gravatar_id":"","url":"https://api.github.com/users/fjy","html_url":"https://github.com/fjy","followers_url":"https://api.github.com/users/fjy/followers","following_url":"https://api.github.com/users/fjy/following{/other_user}","gists_url":"https://api.github.com/users/fjy/gists{/gist_id}","starred_url":"https://api.github.com/users/fjy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/fjy/subscriptions","organizations_url":"https://api.github.com/users/fjy/orgs","repos_url":"https://api.github.com/users/fjy/repos","events_url":"https://api.github.com/users/fjy/events{/privacy}","received_events_url":"https://api.github.com/users/fjy/received_events","type":"User","site_admin":false},"open_issues":16,"closed_issues":135,"state":"open","created_at":"2016-02-08T22:01:21Z","updated_at":"2016-08-30T23:17:46Z","due_on":null,"closed_at":null},"commits_url":"https://api.github.com/repos/druid-io/druid/pulls/3148/commits","review_comments_url":"https://api.github.com/repos/druid-io/druid/pulls/3148/comments","review_comment_url":"https://api.github.com/repos/druid-io/druid/pulls/comments{/number}","comments_url":"https://api.github.com/repos/druid-io/druid/issues/3148/comments","statuses_url":"https://api.github.com/repos/druid-io/druid/statuses/95fb9943535453e4910c1d29de55dbd04f98d1b1","head":{"label":"acslk:feature-compress","ref":"feature-compress","sha":"95fb9943535453e4910c1d29de55dbd04f98d1b1","user":{"login":"acslk","id":11131839,"avatar_url":"https://avatars.githubusercontent.com/u/11131839?v=3","gravatar_id":"","url":"https://api.github.com/users/acslk","html_url":"https://github.com/acslk","followers_url":"https://api.github.com/users/acslk/followers","following_url":"https://api.github.com/users/acslk/following{/other_user}","gists_url":"https://api.github.com/users/acslk/gists{/gist_id}","starred_url":"https://api.github.com/users/acslk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/acslk/subscriptions","organizations_url":"https://api.github.com/users/acslk/orgs","repos_url":"https://api.github.com/users/acslk/repos","events_url":"https://api.github.com/users/acslk/events{/privacy}","received_events_url":"https://api.github.com/users/acslk/received_events","type":"User","site_admin":false},"repo":{"id":58234003,"name":"druid","full_name":"acslk/druid","owner":{"login":"acslk","id":11131839,"avatar_url":"https://avatars.githubusercontent.com/u/11131839?v=3","gravatar_id":"","url":"https://api.github.com/users/acslk","html_url":"https://github.com/acslk","followers_url":"https://api.github.com/users/acslk/followers","following_url":"https://api.github.com/users/acslk/following{/other_user}","gists_url":"https://api.github.com/users/acslk/gists{/gist_id}","starred_url":"https://api.github.com/users/acslk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/acslk/subscriptions","organizations_url":"https://api.github.com/users/acslk/orgs","repos_url":"https://api.github.com/users/acslk/repos","events_url":"https://api.github.com/users/acslk/events{/privacy}","received_events_url":"https://api.github.com/users/acslk/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/acslk/druid","description":"Column oriented distributed data store ideal for powering interactive applications","fork":true,"url":"https://api.github.com/repos/acslk/druid","forks_url":"https://api.github.com/repos/acslk/druid/forks","keys_url":"https://api.github.com/repos/acslk/druid/keys{/key_id}","collaborators_url":"https://api.github.com/repos/acslk/druid/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/acslk/druid/teams","hooks_url":"https://api.github.com/repos/acslk/druid/hooks","issue_events_url":"https://api.github.com/repos/acslk/druid/issues/events{/number}","events_url":"https://api.github.com/repos/acslk/druid/events","assignees_url":"https://api.github.com/repos/acslk/druid/assignees{/user}","branches_url":"https://api.github.com/repos/acslk/druid/branches{/branch}","tags_url":"https://api.github.com/repos/acslk/druid/tags","blobs_url":"https://api.github.com/repos/acslk/druid/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/acslk/druid/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/acslk/druid/git/refs{/sha}","trees_url":"https://api.github.com/repos/acslk/druid/git/trees{/sha}","statuses_url":"https://api.github.com/repos/acslk/druid/statuses/{sha}","languages_url":"https://api.github.com/repos/acslk/druid/languages","stargazers_url":"https://api.github.com/repos/acslk/druid/stargazers","contributors_url":"https://api.github.com/repos/acslk/druid/contributors","subscribers_url":"https://api.github.com/repos/acslk/druid/subscribers","subscription_url":"https://api.github.com/repos/acslk/druid/subscription","commits_url":"https://api.github.com/repos/acslk/druid/commits{/sha}","git_commits_url":"https://api.github.com/repos/acslk/druid/git/commits{/sha}","comments_url":"https://api.github.com/repos/acslk/druid/comments{/number}","issue_comment_url":"https://api.github.com/repos/acslk/druid/issues/comments{/number}","contents_url":"https://api.github.com/repos/acslk/druid/contents/{+path}","compare_url":"https://api.github.com/repos/acslk/druid/compare/{base}...{head}","merges_url":"https://api.github.com/repos/acslk/druid/merges","archive_url":"https://api.github.com/repos/acslk/druid/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/acslk/druid/downloads","issues_url":"https://api.github.com/repos/acslk/druid/issues{/number}","pulls_url":"https://api.github.com/repos/acslk/druid/pulls{/number}","milestones_url":"https://api.github.com/repos/acslk/druid/milestones{/number}","notifications_url":"https://api.github.com/repos/acslk/druid/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/acslk/druid/labels{/name}","releases_url":"https://api.github.com/repos/acslk/druid/releases{/id}","deployments_url":"https://api.github.com/repos/acslk/druid/deployments","created_at":"2016-05-06T20:47:11Z","updated_at":"2016-05-06T20:47:19Z","pushed_at":"2016-08-26T19:26:41Z","git_url":"git://github.com/acslk/druid.git","ssh_url":"git@github.com:acslk/druid.git","clone_url":"https://github.com/acslk/druid.git","svn_url":"https://github.com/acslk/druid","homepage":"http://druid.io","size":127920,"stargazers_count":0,"watchers_count":0,"language":"Java","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"druid-io:master","ref":"master","sha":"03cfcf002b681255a7c9e1db2aea1201ef155a67","user":{"login":"druid-io","id":4203474,"avatar_url":"https://avatars.githubusercontent.com/u/4203474?v=3","gravatar_id":"","url":"https://api.github.com/users/druid-io","html_url":"https://github.com/druid-io","followers_url":"https://api.github.com/users/druid-io/followers","following_url":"https://api.github.com/users/druid-io/following{/other_user}","gists_url":"https://api.github.com/users/druid-io/gists{/gist_id}","starred_url":"https://api.github.com/users/druid-io/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/druid-io/subscriptions","organizations_url":"https://api.github.com/users/druid-io/orgs","repos_url":"https://api.github.com/users/druid-io/repos","events_url":"https://api.github.com/users/druid-io/events{/privacy}","received_events_url":"https://api.github.com/users/druid-io/received_events","type":"Organization","site_admin":false},"repo":{"id":6358188,"name":"druid","full_name":"druid-io/druid","owner":{"login":"druid-io","id":4203474,"avatar_url":"https://avatars.githubusercontent.com/u/4203474?v=3","gravatar_id":"","url":"https://api.github.com/users/druid-io","html_url":"https://github.com/druid-io","followers_url":"https://api.github.com/users/druid-io/followers","following_url":"https://api.github.com/users/druid-io/following{/other_user}","gists_url":"https://api.github.com/users/druid-io/gists{/gist_id}","starred_url":"https://api.github.com/users/druid-io/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/druid-io/subscriptions","organizations_url":"https://api.github.com/users/druid-io/orgs","repos_url":"https://api.github.com/users/druid-io/repos","events_url":"https://api.github.com/users/druid-io/events{/privacy}","received_events_url":"https://api.github.com/users/druid-io/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/druid-io/druid","description":"Column oriented distributed data store ideal for powering interactive applications","fork":false,"url":"https://api.github.com/repos/druid-io/druid","forks_url":"https://api.github.com/repos/druid-io/druid/forks","keys_url":"https://api.github.com/repos/druid-io/druid/keys{/key_id}","collaborators_url":"https://api.github.com/repos/druid-io/druid/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/druid-io/druid/teams","hooks_url":"https://api.github.com/repos/druid-io/druid/hooks","issue_events_url":"https://api.github.com/repos/druid-io/druid/issues/events{/number}","events_url":"https://api.github.com/repos/druid-io/druid/events","assignees_url":"https://api.github.com/repos/druid-io/druid/assignees{/user}","branches_url":"https://api.github.com/repos/druid-io/druid/branches{/branch}","tags_url":"https://api.github.com/repos/druid-io/druid/tags","blobs_url":"https://api.github.com/repos/druid-io/druid/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/druid-io/druid/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/druid-io/druid/git/refs{/sha}","trees_url":"https://api.github.com/repos/druid-io/druid/git/trees{/sha}","statuses_url":"https://api.github.com/repos/druid-io/druid/statuses/{sha}","languages_url":"https://api.github.com/repos/druid-io/druid/languages","stargazers_url":"https://api.github.com/repos/druid-io/druid/stargazers","contributors_url":"https://api.github.com/repos/druid-io/druid/contributors","subscribers_url":"https://api.github.com/repos/druid-io/druid/subscribers","subscription_url":"https://api.github.com/repos/druid-io/druid/subscription","commits_url":"https://api.github.com/repos/druid-io/druid/commits{/sha}","git_commits_url":"https://api.github.com/repos/druid-io/druid/git/commits{/sha}","comments_url":"https://api.github.com/repos/druid-io/druid/comments{/number}","issue_comment_url":"https://api.github.com/repos/druid-io/druid/issues/comments{/number}","contents_url":"https://api.github.com/repos/druid-io/druid/contents/{+path}","compare_url":"https://api.github.com/repos/druid-io/druid/compare/{base}...{head}","merges_url":"https://api.github.com/repos/druid-io/druid/merges","archive_url":"https://api.github.com/repos/druid-io/druid/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/druid-io/druid/downloads","issues_url":"https://api.github.com/repos/druid-io/druid/issues{/number}","pulls_url":"https://api.github.com/repos/druid-io/druid/pulls{/number}","milestones_url":"https://api.github.com/repos/druid-io/druid/milestones{/number}","notifications_url":"https://api.github.com/repos/druid-io/druid/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/druid-io/druid/labels{/name}","releases_url":"https://api.github.com/repos/druid-io/druid/releases{/id}","deployments_url":"https://api.github.com/repos/druid-io/druid/deployments","created_at":"2012-10-23T19:08:07Z","updated_at":"2016-08-30T21:16:24Z","pushed_at":"2016-08-30T23:17:46Z","git_url":"git://github.com/druid-io/druid.git","ssh_url":"git@github.com:druid-io/druid.git","clone_url":"https://github.com/druid-io/druid.git","svn_url":"https://github.com/druid-io/druid","homepage":"http://druid.io","size":154252,"stargazers_count":3657,"watchers_count":3657,"language":"Java","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":847,"mirror_url":null,"open_issues_count":503,"forks":847,"open_issues":503,"watchers":3657,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/druid-io/druid/pulls/3148"},"html":{"href":"https://github.com/druid-io/druid/pull/3148"},"issue":{"href":"https://api.github.com/repos/druid-io/druid/issues/3148"},"comments":{"href":"https://api.github.com/repos/druid-io/druid/issues/3148/comments"},"review_comments":{"href":"https://api.github.com/repos/druid-io/druid/pulls/3148/comments"},"review_comment":{"href":"https://api.github.com/repos/druid-io/druid/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/druid-io/druid/pulls/3148/commits"},"statuses":{"href":"https://api.github.com/repos/druid-io/druid/statuses/95fb9943535453e4910c1d29de55dbd04f98d1b1"}},"merged":true,"mergeable":null,"mergeable_state":"unknown","merged_by":{"login":"gianm","id":1214075,"avatar_url":"https://avatars.githubusercontent.com/u/1214075?v=3","gravatar_id":"","url":"https://api.github.com/users/gianm","html_url":"https://github.com/gianm","followers_url":"https://api.github.com/users/gianm/followers","following_url":"https://api.github.com/users/gianm/following{/other_user}","gists_url":"https://api.github.com/users/gianm/gists{/gist_id}","starred_url":"https://api.github.com/users/gianm/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gianm/subscriptions","organizations_url":"https://api.github.com/users/gianm/orgs","repos_url":"https://api.github.com/users/gianm/repos","events_url":"https://api.github.com/users/gianm/events{/privacy}","received_events_url":"https://api.github.com/users/gianm/received_events","type":"User","site_admin":false},"comments":13,"review_comments":111,"commits":16,"additions":4662,"deletions":2493,"changed_files":69}}
{"actor":{"display_login":"gianm"}}