{"action":"created","issue":{"url":"https://api.github.com/repos/pg-strom/devel/issues/211","labels_url":"https://api.github.com/repos/pg-strom/devel/issues/211/labels{/name}","comments_url":"https://api.github.com/repos/pg-strom/devel/issues/211/comments","events_url":"https://api.github.com/repos/pg-strom/devel/issues/211/events","html_url":"https://github.com/pg-strom/devel/issues/211","id":111108961,"number":211,"title":"(JP) キー値の分布に偏りがあるGpuHashJoinでリトライ多発","user":{"login":"kaigai","id":216210,"avatar_url":"https://avatars.githubusercontent.com/u/216210?v=3","gravatar_id":"","url":"https://api.github.com/users/kaigai","html_url":"https://github.com/kaigai","followers_url":"https://api.github.com/users/kaigai/followers","following_url":"https://api.github.com/users/kaigai/following{/other_user}","gists_url":"https://api.github.com/users/kaigai/gists{/gist_id}","starred_url":"https://api.github.com/users/kaigai/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kaigai/subscriptions","organizations_url":"https://api.github.com/users/kaigai/orgs","repos_url":"https://api.github.com/users/kaigai/repos","events_url":"https://api.github.com/users/kaigai/events{/privacy}","received_events_url":"https://api.github.com/users/kaigai/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-10-13T05:38:24Z","updated_at":"2015-10-16T07:50:28Z","closed_at":null,"body":"tbl_A JOIN tbl_B ON key_A = key_B\r\nであるケースで、一方のキー値の分布に偏りが大きい場合にリトライが多発。\r\n酷い性能劣化を引き起こす。\r\n\r\n例えば、key_Aの分布が以下のような場合\r\n```\r\nkey_A | count(*)\r\n------+------------\r\n  100 |  1000\r\n  200 |   200\r\n  300 |     1\r\n  301 |     1\r\n```\r\nkey_Bが100のとき、Join結果は1000倍に膨れ上がるが、平均すると数倍にしか\r\nならないので、リトライ→バッファ不足を何度も繰り返し、なかなか収束しない。\r\n\r\n集約演算と同様に、Hash値にsaltを混ぜて特定のキー値を分散させる必要がある。\r\n\r\n特定のキー値でHash Chainが非常に長くなるというのはinner_preloadの時点で\r\n検出できるので、閾値なりを設けて平滑化を試みる。\r\ninner_preloadが1より大きなkey_dist_saltをセットした場合、これはinner sizeが\r\n大きくなったのと同様に取り扱うことができるので、既存のNoDataStore => Retry\r\nと同じ枠組みで処理する事ができる。"},"comment":{"url":"https://api.github.com/repos/pg-strom/devel/issues/comments/148641779","html_url":"https://github.com/pg-strom/devel/issues/211#issuecomment-148641779","issue_url":"https://api.github.com/repos/pg-strom/devel/issues/211","id":148641779,"user":{"login":"kaigai","id":216210,"avatar_url":"https://avatars.githubusercontent.com/u/216210?v=3","gravatar_id":"","url":"https://api.github.com/users/kaigai","html_url":"https://github.com/kaigai","followers_url":"https://api.github.com/users/kaigai/followers","following_url":"https://api.github.com/users/kaigai/following{/other_user}","gists_url":"https://api.github.com/users/kaigai/gists{/gist_id}","starred_url":"https://api.github.com/users/kaigai/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kaigai/subscriptions","organizations_url":"https://api.github.com/users/kaigai/orgs","repos_url":"https://api.github.com/users/kaigai/repos","events_url":"https://api.github.com/users/kaigai/events{/privacy}","received_events_url":"https://api.github.com/users/kaigai/received_events","type":"User","site_admin":false},"created_at":"2015-10-16T07:50:28Z","updated_at":"2015-10-16T07:50:28Z","body":"> 集約演算と同様に、Hash値にsaltを混ぜて特定のキー値を分散させる必要がある。\r\n\r\nが、Saltが大きくなるにしたがって、実行時に空回りするGPU Threadが多くなるので\r\n一筋縄ではいかない。\r\nキー重複の多いInner側の要素と結合する場合だけ、GPU Threadが増えるような\r\n実装ができれば良い。\r\nNVRTCにDynamic Parallelismが実装されれば可能か？"}}