{"action":"created","issue":{"url":"https://api.github.com/repos/facebook/rocksdb/issues/1614","repository_url":"https://api.github.com/repos/facebook/rocksdb","labels_url":"https://api.github.com/repos/facebook/rocksdb/issues/1614/labels{/name}","comments_url":"https://api.github.com/repos/facebook/rocksdb/issues/1614/comments","events_url":"https://api.github.com/repos/facebook/rocksdb/issues/1614/events","html_url":"https://github.com/facebook/rocksdb/pull/1614","id":193248464,"number":1614,"title":"Collapse range deletions","user":{"login":"ajkr","id":4780362,"avatar_url":"https://avatars.githubusercontent.com/u/4780362?v=3","gravatar_id":"","url":"https://api.github.com/users/ajkr","html_url":"https://github.com/ajkr","followers_url":"https://api.github.com/users/ajkr/followers","following_url":"https://api.github.com/users/ajkr/following{/other_user}","gists_url":"https://api.github.com/users/ajkr/gists{/gist_id}","starred_url":"https://api.github.com/users/ajkr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ajkr/subscriptions","organizations_url":"https://api.github.com/users/ajkr/orgs","repos_url":"https://api.github.com/users/ajkr/repos","events_url":"https://api.github.com/users/ajkr/events{/privacy}","received_events_url":"https://api.github.com/users/ajkr/received_events","type":"User","site_admin":false},"labels":[{"id":196859108,"url":"https://api.github.com/repos/facebook/rocksdb/labels/CLA%20Signed","name":"CLA Signed","color":"009900","default":false}],"state":"open","locked":false,"assignee":{"login":"lightmark","id":1549573,"avatar_url":"https://avatars.githubusercontent.com/u/1549573?v=3","gravatar_id":"","url":"https://api.github.com/users/lightmark","html_url":"https://github.com/lightmark","followers_url":"https://api.github.com/users/lightmark/followers","following_url":"https://api.github.com/users/lightmark/following{/other_user}","gists_url":"https://api.github.com/users/lightmark/gists{/gist_id}","starred_url":"https://api.github.com/users/lightmark/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lightmark/subscriptions","organizations_url":"https://api.github.com/users/lightmark/orgs","repos_url":"https://api.github.com/users/lightmark/repos","events_url":"https://api.github.com/users/lightmark/events{/privacy}","received_events_url":"https://api.github.com/users/lightmark/received_events","type":"User","site_admin":false},"assignees":[{"login":"lightmark","id":1549573,"avatar_url":"https://avatars.githubusercontent.com/u/1549573?v=3","gravatar_id":"","url":"https://api.github.com/users/lightmark","html_url":"https://github.com/lightmark","followers_url":"https://api.github.com/users/lightmark/followers","following_url":"https://api.github.com/users/lightmark/following{/other_user}","gists_url":"https://api.github.com/users/lightmark/gists{/gist_id}","starred_url":"https://api.github.com/users/lightmark/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lightmark/subscriptions","organizations_url":"https://api.github.com/users/lightmark/orgs","repos_url":"https://api.github.com/users/lightmark/repos","events_url":"https://api.github.com/users/lightmark/events{/privacy}","received_events_url":"https://api.github.com/users/lightmark/received_events","type":"User","site_admin":false}],"milestone":null,"comments":6,"created_at":"2016-12-03T00:12:17Z","updated_at":"2016-12-05T19:13:48Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/facebook/rocksdb/pulls/1614","html_url":"https://github.com/facebook/rocksdb/pull/1614","diff_url":"https://github.com/facebook/rocksdb/pull/1614.diff","patch_url":"https://github.com/facebook/rocksdb/pull/1614.patch"},"body":"Added a tombstone-collapsing mode to RangeDelAggregator, which eliminates overlap in the TombstoneMap. In this mode, we can check whether a tombstone covers a user key using upper_bound() (i.e., binary search). However, the tradeoff is the overhead to add tombstones is now higher, so at first I've only enabled it for range scans (compaction/flush/user iterators), where we expect a high number of calls to ShouldDelete() for the same tombstones. Point queries like Get() will still use the linear scan approach.\r\n\r\nAlso in this diff I changed RangeDelAggregator's TombstoneMap to use multimap with user keys instead of map with internal keys. Callers sometimes provided ParsedInternalKey directly, from which it would've required string copying to derive an internal key Slice with which we could search the map.\r\n\r\nTest Plan: unit tests"},"comment":{"url":"https://api.github.com/repos/facebook/rocksdb/issues/comments/264947280","html_url":"https://github.com/facebook/rocksdb/pull/1614#issuecomment-264947280","issue_url":"https://api.github.com/repos/facebook/rocksdb/issues/1614","id":264947280,"user":{"login":"facebook-github-bot","id":6422482,"avatar_url":"https://avatars.githubusercontent.com/u/6422482?v=3","gravatar_id":"","url":"https://api.github.com/users/facebook-github-bot","html_url":"https://github.com/facebook-github-bot","followers_url":"https://api.github.com/users/facebook-github-bot/followers","following_url":"https://api.github.com/users/facebook-github-bot/following{/other_user}","gists_url":"https://api.github.com/users/facebook-github-bot/gists{/gist_id}","starred_url":"https://api.github.com/users/facebook-github-bot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/facebook-github-bot/subscriptions","organizations_url":"https://api.github.com/users/facebook-github-bot/orgs","repos_url":"https://api.github.com/users/facebook-github-bot/repos","events_url":"https://api.github.com/users/facebook-github-bot/events{/privacy}","received_events_url":"https://api.github.com/users/facebook-github-bot/received_events","type":"User","site_admin":false},"created_at":"2016-12-05T19:13:48Z","updated_at":"2016-12-05T19:13:48Z","body":"@ajkr updated the pull request - [view changes](https://github.com/facebook/rocksdb/pull/1614/files/18894eba26adde84c12079a73fa59e56e30eb359..7dae12d5ba06203c46852b15a00a2ba4cb1bd152) - [changes since last import](https://github.com/facebook/rocksdb/pull/1614/files/18894eba26adde84c12079a73fa59e56e30eb359..7dae12d5ba06203c46852b15a00a2ba4cb1bd152)"}}
{"actor":{"display_login":"facebook-github-bot"}}