{"action":"created","issue":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/24582","repository_url":"https://api.github.com/repos/cockroachdb/cockroach","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/24582/labels{/name}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/24582/comments","events_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/24582/events","html_url":"https://github.com/cockroachdb/cockroach/issues/24582","id":312228204,"number":24582,"title":"distsqlrun: implement GRACE hash join (for equality joins only)","user":{"login":"jordanlewis","id":43821,"avatar_url":"https://avatars1.githubusercontent.com/u/43821?v=4","gravatar_id":"","url":"https://api.github.com/users/jordanlewis","html_url":"https://github.com/jordanlewis","followers_url":"https://api.github.com/users/jordanlewis/followers","following_url":"https://api.github.com/users/jordanlewis/following{/other_user}","gists_url":"https://api.github.com/users/jordanlewis/gists{/gist_id}","starred_url":"https://api.github.com/users/jordanlewis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jordanlewis/subscriptions","organizations_url":"https://api.github.com/users/jordanlewis/orgs","repos_url":"https://api.github.com/users/jordanlewis/repos","events_url":"https://api.github.com/users/jordanlewis/events{/privacy}","received_events_url":"https://api.github.com/users/jordanlewis/received_events","type":"User","site_admin":false},"labels":[{"id":78928347,"url":"https://api.github.com/repos/cockroachdb/cockroach/labels/enhancement","name":"enhancement","color":"84b6eb","default":true},{"id":406290612,"url":"https://api.github.com/repos/cockroachdb/cockroach/labels/performance","name":"performance","color":"fef2c0","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":{"url":"https://api.github.com/repos/cockroachdb/cockroach/milestones/13","html_url":"https://github.com/cockroachdb/cockroach/milestone/13","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/milestones/13/labels","id":2745639,"number":13,"title":"2.1","description":"","creator":{"login":"knz","id":642886,"avatar_url":"https://avatars3.githubusercontent.com/u/642886?v=4","gravatar_id":"","url":"https://api.github.com/users/knz","html_url":"https://github.com/knz","followers_url":"https://api.github.com/users/knz/followers","following_url":"https://api.github.com/users/knz/following{/other_user}","gists_url":"https://api.github.com/users/knz/gists{/gist_id}","starred_url":"https://api.github.com/users/knz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/knz/subscriptions","organizations_url":"https://api.github.com/users/knz/orgs","repos_url":"https://api.github.com/users/knz/repos","events_url":"https://api.github.com/users/knz/events{/privacy}","received_events_url":"https://api.github.com/users/knz/received_events","type":"User","site_admin":false},"open_issues":572,"closed_issues":59,"state":"open","created_at":"2017-09-05T15:30:49Z","updated_at":"2018-04-07T17:53:48Z","due_on":null,"closed_at":null},"comments":1,"created_at":"2018-04-07T17:53:47Z","updated_at":"2018-04-07T18:01:45Z","closed_at":null,"author_association":"OWNER","body":"See #24580 for a description of the current hash join algorithm. The tl;dr is that the current hash join algorithm performs `n` RocksDB disk seeks if the probing side of the hash join has `n` rows in it. This is expensive.\r\n\r\nGRACE hash join is a slightly more sophisticated hash join algorithm, usable for equality joins only, that will give us better runtime properties when hash join needs to spill to disk. It operates in two phases, once the join runs out of memory and must spill to disk. The high level view is that it partitions the left and right side into large buckets by a hash function `A`, writes those buckets to disk, then iterates through pairs of those buckets and does a normal hash join with a different hash function `B`.\r\n\r\n**Phase 1: partitioning**\r\nIn this phase, we iterate through both sides of the join, hashing every row using a hash function `A` that produces `n` partitions. This will produce `n` partitions for each side of the join, which will be persisted to disk separately. As memory fills up, each of these partitions is flushed to disk repeatedly until the inputs are exhausted.\r\n\r\n**Phase 2: join**\r\nNow, we retrieve pairs of partitions from disk and join each pair using the ordinary hash join algorithm (and a different hash function `B`). Since we're performing an equality join, we can guarantee that each row on the left side of the join, if it has a match, will be in the same partition on the right side of the join. So, it's safe to do the join in pieces, partition by partition.\r\n\r\nIf one of the partition hash joins itself runs out of memory, we can recursively apply this algorithm. The partition will be divided into sub-partitions by a new hash function, spilled to disk, and so on.\r\n\r\n----\r\n\r\nBecause of the danger of having to recursively spill to disk, it's important to pick a hash function that partitions the input streams into reasonable sizes. I think this is probably only possible given table statistics because you need to know the approximate size of the table to determine how many partitions you need of the table such that each partition fits into the available SQL memory.\r\n\r\ncc @rytaft - will table statistics include the approximate size of the entire table?"},"comment":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/comments/379487945","html_url":"https://github.com/cockroachdb/cockroach/issues/24582#issuecomment-379487945","issue_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/24582","id":379487945,"user":{"login":"jordanlewis","id":43821,"avatar_url":"https://avatars1.githubusercontent.com/u/43821?v=4","gravatar_id":"","url":"https://api.github.com/users/jordanlewis","html_url":"https://github.com/jordanlewis","followers_url":"https://api.github.com/users/jordanlewis/followers","following_url":"https://api.github.com/users/jordanlewis/following{/other_user}","gists_url":"https://api.github.com/users/jordanlewis/gists{/gist_id}","starred_url":"https://api.github.com/users/jordanlewis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jordanlewis/subscriptions","organizations_url":"https://api.github.com/users/jordanlewis/orgs","repos_url":"https://api.github.com/users/jordanlewis/repos","events_url":"https://api.github.com/users/jordanlewis/events{/privacy}","received_events_url":"https://api.github.com/users/jordanlewis/received_events","type":"User","site_admin":false},"created_at":"2018-04-07T18:01:45Z","updated_at":"2018-04-07T18:01:45Z","author_association":"OWNER","body":"Finally, there's an enhancement to GRACE hash join called hybrid hash join, which AFAICT is basically the same as GRACE hash join except it never flushes partition 0 on each side to disk - it just does the hash join for partition 0 during the partitioning phase. This saves a little bit of time.\r\n\r\nSee http://www.dcs.ed.ac.uk/home/tz/phd/thesis/node21.htm for more details on both these algorithms."}}
{"actor":{"display_login":"jordanlewis"}}