{"action":"created","comment":{"url":"https://api.github.com/repos/pingcap/tidb/pulls/comments/107064384","pull_request_review_id":28013722,"id":107064384,"diff_hunk":"@@ -0,0 +1,467 @@\n+// Copyright 2017 PingCAP, Inc.\n+//\n+// Licensed under the Apache License, Version 2.0 (the \"License\");\n+// you may not use this file except in compliance with the License.\n+// You may obtain a copy of the License at\n+//\n+//     http://www.apache.org/licenses/LICENSE-2.0\n+//\n+// Unless required by applicable law or agreed to in writing, software\n+// distributed under the License is distributed on an \"AS IS\" BASIS,\n+// See the License for the specific language governing permissions and\n+// limitations under the License.\n+\n+package executor\n+\n+import (\n+\t\"github.com/juju/errors\"\n+\t\"github.com/pingcap/tidb/context\"\n+\t\"github.com/pingcap/tidb/expression\"\n+\t\"github.com/pingcap/tidb/plan\"\n+\t\"github.com/pingcap/tidb/sessionctx/variable\"\n+\t\"github.com/pingcap/tidb/util/types\"\n+)\n+\n+// MergeJoinExec implements the merge join algorithm.\n+// This operator assumes that two iterators of both sides\n+// will provide required order on join condition:\n+// 1. For equal-join, one of the join key from each side\n+// matches the order given.\n+// 2. For other cases its preferred not to use SMJ and operator\n+// will throw error.\n+type MergeJoinExec struct {\n+\t// Left is always the driver side\n+\tctx           context.Context\n+\tstmtCtx       *variable.StatementContext\n+\tleftJoinKeys  []*expression.Column\n+\trightJoinKeys []*expression.Column\n+\tprepared      bool\n+\tleftFilter    expression.Expression\n+\trightFilter   expression.Expression\n+\totherFilter   expression.Expression\n+\tschema        *expression.Schema\n+\tpreserveLeft  bool // To perserve left side of the relation as in left outer join\n+\tpreserveRight bool // To perserve left side of the relation as in right outer join\n+\tcursor        int\n+\tdefaultValues []types.Datum\n+\t// Default for both side in case full join\n+\tdefaultLeftRow  *Row\n+\tdefaultRightRow *Row\n+\toutputBuf       []*Row\n+\n+\tleftRowBlock  rowBlockIterator\n+\trightRowBlock rowBlockIterator\n+\tleftRows      []*Row\n+\trightRows     []*Row\n+\tdesc          bool\n+}\n+\n+const rowBufferSize = 4096\n+\n+type joinBuilder struct {\n+\tcontext       context.Context\n+\tleftChild     Executor\n+\trightChild    Executor\n+\teqConditions  []*expression.ScalarFunction\n+\tleftFilter    expression.Expression\n+\trightFilter   expression.Expression\n+\totherFilter   expression.Expression\n+\tschema        *expression.Schema\n+\tjoinType      plan.JoinType\n+\tdefaultValues []types.Datum\n+}\n+\n+func (b *joinBuilder) Context(context context.Context) *joinBuilder {\n+\tb.context = context\n+\treturn b\n+}\n+\n+func (b *joinBuilder) EqualConditions(conds []*expression.ScalarFunction) *joinBuilder {\n+\tb.eqConditions = conds\n+\treturn b\n+}\n+\n+func (b *joinBuilder) LeftChild(exec Executor) *joinBuilder {\n+\tb.leftChild = exec\n+\treturn b\n+}\n+\n+func (b *joinBuilder) RightChild(exec Executor) *joinBuilder {\n+\tb.rightChild = exec\n+\treturn b\n+}\n+\n+func (b *joinBuilder) LeftFilter(expr expression.Expression) *joinBuilder {\n+\tb.leftFilter = expr\n+\treturn b\n+}\n+\n+func (b *joinBuilder) RightFilter(expr expression.Expression) *joinBuilder {\n+\tb.rightFilter = expr\n+\treturn b\n+}\n+\n+func (b *joinBuilder) OtherFilter(expr expression.Expression) *joinBuilder {\n+\tb.otherFilter = expr\n+\treturn b\n+}\n+\n+func (b *joinBuilder) Schema(schema *expression.Schema) *joinBuilder {\n+\tb.schema = schema\n+\treturn b\n+}\n+\n+func (b *joinBuilder) JoinType(joinType plan.JoinType) *joinBuilder {\n+\tb.joinType = joinType\n+\treturn b\n+}\n+\n+func (b *joinBuilder) DefaultVals(defaultValues []types.Datum) *joinBuilder {\n+\tb.defaultValues = defaultValues\n+\treturn b\n+}\n+\n+func (b *joinBuilder) BuildMergeJoin(assumeSortedDesc bool) (*MergeJoinExec, error) {\n+\tvar leftJoinKeys, rightJoinKeys []*expression.Column\n+\tfor _, eqCond := range b.eqConditions {\n+\t\tlKey, _ := eqCond.GetArgs()[0].(*expression.Column)\n+\t\trKey, _ := eqCond.GetArgs()[1].(*expression.Column)\n+\t\tleftJoinKeys = append(leftJoinKeys, lKey)\n+\t\trightJoinKeys = append(rightJoinKeys, rKey)\n+\t}\n+\texec := new(MergeJoinExec)\n+\texec.ctx = b.context\n+\texec.leftJoinKeys = leftJoinKeys\n+\texec.rightJoinKeys = rightJoinKeys\n+\texec.otherFilter = b.otherFilter\n+\texec.schema = b.schema\n+\texec.desc = assumeSortedDesc\n+\n+\texec.leftRowBlock = rowBlockIterator{\n+\t\tctx:      b.context,\n+\t\treader:   b.leftChild,\n+\t\tfilter:   b.leftFilter,\n+\t\tjoinKeys: leftJoinKeys,\n+\t}\n+\n+\texec.rightRowBlock = rowBlockIterator{\n+\t\tctx:      b.context,\n+\t\treader:   b.rightChild,\n+\t\tfilter:   b.rightFilter,\n+\t\tjoinKeys: rightJoinKeys,\n+\t}\n+\n+\texec.preserveLeft = false","path":"executor/merge_join.go","position":154,"original_position":154,"commit_id":"5d4c4e9784d97ab5b77faf9d87be37574e06277e","original_commit_id":"5d4c4e9784d97ab5b77faf9d87be37574e06277e","user":{"login":"hanfei1991","id":20884546,"avatar_url":"https://avatars3.githubusercontent.com/u/20884546?v=3","gravatar_id":"","url":"https://api.github.com/users/hanfei1991","html_url":"https://github.com/hanfei1991","followers_url":"https://api.github.com/users/hanfei1991/followers","following_url":"https://api.github.com/users/hanfei1991/following{/other_user}","gists_url":"https://api.github.com/users/hanfei1991/gists{/gist_id}","starred_url":"https://api.github.com/users/hanfei1991/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hanfei1991/subscriptions","organizations_url":"https://api.github.com/users/hanfei1991/orgs","repos_url":"https://api.github.com/users/hanfei1991/repos","events_url":"https://api.github.com/users/hanfei1991/events{/privacy}","received_events_url":"https://api.github.com/users/hanfei1991/received_events","type":"User","site_admin":false},"body":"You can remove this two lines.","created_at":"2017-03-21T03:04:52Z","updated_at":"2017-03-21T03:17:41Z","html_url":"https://github.com/pingcap/tidb/pull/2850#discussion_r107064384","pull_request_url":"https://api.github.com/repos/pingcap/tidb/pulls/2850","_links":{"self":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/comments/107064384"},"html":{"href":"https://github.com/pingcap/tidb/pull/2850#discussion_r107064384"},"pull_request":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/2850"}}},"pull_request":{"url":"https://api.github.com/repos/pingcap/tidb/pulls/2850","id":111056299,"html_url":"https://github.com/pingcap/tidb/pull/2850","diff_url":"https://github.com/pingcap/tidb/pull/2850.diff","patch_url":"https://github.com/pingcap/tidb/pull/2850.patch","issue_url":"https://api.github.com/repos/pingcap/tidb/issues/2850","number":2850,"state":"open","locked":false,"title":"Sort Merge Join","user":{"login":"ilovesoup","id":3347719,"avatar_url":"https://avatars1.githubusercontent.com/u/3347719?v=3","gravatar_id":"","url":"https://api.github.com/users/ilovesoup","html_url":"https://github.com/ilovesoup","followers_url":"https://api.github.com/users/ilovesoup/followers","following_url":"https://api.github.com/users/ilovesoup/following{/other_user}","gists_url":"https://api.github.com/users/ilovesoup/gists{/gist_id}","starred_url":"https://api.github.com/users/ilovesoup/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ilovesoup/subscriptions","organizations_url":"https://api.github.com/users/ilovesoup/orgs","repos_url":"https://api.github.com/users/ilovesoup/repos","events_url":"https://api.github.com/users/ilovesoup/events{/privacy}","received_events_url":"https://api.github.com/users/ilovesoup/received_events","type":"User","site_admin":false},"body":"Still doing tests. PR for review.\r\n\r\nAdded syntax like select /*! TIDB_SMJ(t1, t2) */ ... which indicates within this select block, t1,t2 will be joining with merge join; if needed, a sort will be appended in case of no order provided by child operators. The hint matching only matches table name and alias like in MySQL.\r\n\r\nIt will try to generate different plans according to join keys. Say a = b and c = d it will try both merge on a/b (ASC or DESC), c/d (ASC or DESC) and pick a plan with lowest cost along side other operator cost evaluation.\r\nThe merge join operator itself do a streamline iteration caching same key rows for both sides for look-back cross product. If a single key count is larger than memory size, it then will OOM. \r\n\r\nOn presence of merge hint, join reorder will be turned off.","created_at":"2017-03-16T12:26:59Z","updated_at":"2017-03-21T03:17:41Z","closed_at":null,"merged_at":null,"merge_commit_sha":"c648deb6b37ebfed01c83f5620a7d44f29dec8bc","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/pingcap/tidb/pulls/2850/commits","review_comments_url":"https://api.github.com/repos/pingcap/tidb/pulls/2850/comments","review_comment_url":"https://api.github.com/repos/pingcap/tidb/pulls/comments{/number}","comments_url":"https://api.github.com/repos/pingcap/tidb/issues/2850/comments","statuses_url":"https://api.github.com/repos/pingcap/tidb/statuses/5d4c4e9784d97ab5b77faf9d87be37574e06277e","head":{"label":"pingcap:maxiaoyu/mergejoin","ref":"maxiaoyu/mergejoin","sha":"5d4c4e9784d97ab5b77faf9d87be37574e06277e","user":{"login":"pingcap","id":11855343,"avatar_url":"https://avatars0.githubusercontent.com/u/11855343?v=3","gravatar_id":"","url":"https://api.github.com/users/pingcap","html_url":"https://github.com/pingcap","followers_url":"https://api.github.com/users/pingcap/followers","following_url":"https://api.github.com/users/pingcap/following{/other_user}","gists_url":"https://api.github.com/users/pingcap/gists{/gist_id}","starred_url":"https://api.github.com/users/pingcap/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pingcap/subscriptions","organizations_url":"https://api.github.com/users/pingcap/orgs","repos_url":"https://api.github.com/users/pingcap/repos","events_url":"https://api.github.com/users/pingcap/events{/privacy}","received_events_url":"https://api.github.com/users/pingcap/received_events","type":"Organization","site_admin":false},"repo":{"id":41986369,"name":"tidb","full_name":"pingcap/tidb","owner":{"login":"pingcap","id":11855343,"avatar_url":"https://avatars0.githubusercontent.com/u/11855343?v=3","gravatar_id":"","url":"https://api.github.com/users/pingcap","html_url":"https://github.com/pingcap","followers_url":"https://api.github.com/users/pingcap/followers","following_url":"https://api.github.com/users/pingcap/following{/other_user}","gists_url":"https://api.github.com/users/pingcap/gists{/gist_id}","starred_url":"https://api.github.com/users/pingcap/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pingcap/subscriptions","organizations_url":"https://api.github.com/users/pingcap/orgs","repos_url":"https://api.github.com/users/pingcap/repos","events_url":"https://api.github.com/users/pingcap/events{/privacy}","received_events_url":"https://api.github.com/users/pingcap/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/pingcap/tidb","description":"TiDB is a distributed NewSQL database compatible with MySQL protocol ","fork":false,"url":"https://api.github.com/repos/pingcap/tidb","forks_url":"https://api.github.com/repos/pingcap/tidb/forks","keys_url":"https://api.github.com/repos/pingcap/tidb/keys{/key_id}","collaborators_url":"https://api.github.com/repos/pingcap/tidb/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/pingcap/tidb/teams","hooks_url":"https://api.github.com/repos/pingcap/tidb/hooks","issue_events_url":"https://api.github.com/repos/pingcap/tidb/issues/events{/number}","events_url":"https://api.github.com/repos/pingcap/tidb/events","assignees_url":"https://api.github.com/repos/pingcap/tidb/assignees{/user}","branches_url":"https://api.github.com/repos/pingcap/tidb/branches{/branch}","tags_url":"https://api.github.com/repos/pingcap/tidb/tags","blobs_url":"https://api.github.com/repos/pingcap/tidb/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/pingcap/tidb/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/pingcap/tidb/git/refs{/sha}","trees_url":"https://api.github.com/repos/pingcap/tidb/git/trees{/sha}","statuses_url":"https://api.github.com/repos/pingcap/tidb/statuses/{sha}","languages_url":"https://api.github.com/repos/pingcap/tidb/languages","stargazers_url":"https://api.github.com/repos/pingcap/tidb/stargazers","contributors_url":"https://api.github.com/repos/pingcap/tidb/contributors","subscribers_url":"https://api.github.com/repos/pingcap/tidb/subscribers","subscription_url":"https://api.github.com/repos/pingcap/tidb/subscription","commits_url":"https://api.github.com/repos/pingcap/tidb/commits{/sha}","git_commits_url":"https://api.github.com/repos/pingcap/tidb/git/commits{/sha}","comments_url":"https://api.github.com/repos/pingcap/tidb/comments{/number}","issue_comment_url":"https://api.github.com/repos/pingcap/tidb/issues/comments{/number}","contents_url":"https://api.github.com/repos/pingcap/tidb/contents/{+path}","compare_url":"https://api.github.com/repos/pingcap/tidb/compare/{base}...{head}","merges_url":"https://api.github.com/repos/pingcap/tidb/merges","archive_url":"https://api.github.com/repos/pingcap/tidb/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/pingcap/tidb/downloads","issues_url":"https://api.github.com/repos/pingcap/tidb/issues{/number}","pulls_url":"https://api.github.com/repos/pingcap/tidb/pulls{/number}","milestones_url":"https://api.github.com/repos/pingcap/tidb/milestones{/number}","notifications_url":"https://api.github.com/repos/pingcap/tidb/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/pingcap/tidb/labels{/name}","releases_url":"https://api.github.com/repos/pingcap/tidb/releases{/id}","deployments_url":"https://api.github.com/repos/pingcap/tidb/deployments","created_at":"2015-09-06T04:01:52Z","updated_at":"2017-03-20T14:25:42Z","pushed_at":"2017-03-21T02:09:15Z","git_url":"git://github.com/pingcap/tidb.git","ssh_url":"git@github.com:pingcap/tidb.git","clone_url":"https://github.com/pingcap/tidb.git","svn_url":"https://github.com/pingcap/tidb","homepage":"","size":22464,"stargazers_count":7363,"watchers_count":7363,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":true,"forks_count":963,"mirror_url":null,"open_issues_count":193,"forks":963,"open_issues":193,"watchers":7363,"default_branch":"master"}},"base":{"label":"pingcap:master","ref":"master","sha":"e55534f1e95202e13030903e5fbc22fddb7117ca","user":{"login":"pingcap","id":11855343,"avatar_url":"https://avatars0.githubusercontent.com/u/11855343?v=3","gravatar_id":"","url":"https://api.github.com/users/pingcap","html_url":"https://github.com/pingcap","followers_url":"https://api.github.com/users/pingcap/followers","following_url":"https://api.github.com/users/pingcap/following{/other_user}","gists_url":"https://api.github.com/users/pingcap/gists{/gist_id}","starred_url":"https://api.github.com/users/pingcap/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pingcap/subscriptions","organizations_url":"https://api.github.com/users/pingcap/orgs","repos_url":"https://api.github.com/users/pingcap/repos","events_url":"https://api.github.com/users/pingcap/events{/privacy}","received_events_url":"https://api.github.com/users/pingcap/received_events","type":"Organization","site_admin":false},"repo":{"id":41986369,"name":"tidb","full_name":"pingcap/tidb","owner":{"login":"pingcap","id":11855343,"avatar_url":"https://avatars0.githubusercontent.com/u/11855343?v=3","gravatar_id":"","url":"https://api.github.com/users/pingcap","html_url":"https://github.com/pingcap","followers_url":"https://api.github.com/users/pingcap/followers","following_url":"https://api.github.com/users/pingcap/following{/other_user}","gists_url":"https://api.github.com/users/pingcap/gists{/gist_id}","starred_url":"https://api.github.com/users/pingcap/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pingcap/subscriptions","organizations_url":"https://api.github.com/users/pingcap/orgs","repos_url":"https://api.github.com/users/pingcap/repos","events_url":"https://api.github.com/users/pingcap/events{/privacy}","received_events_url":"https://api.github.com/users/pingcap/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/pingcap/tidb","description":"TiDB is a distributed NewSQL database compatible with MySQL protocol ","fork":false,"url":"https://api.github.com/repos/pingcap/tidb","forks_url":"https://api.github.com/repos/pingcap/tidb/forks","keys_url":"https://api.github.com/repos/pingcap/tidb/keys{/key_id}","collaborators_url":"https://api.github.com/repos/pingcap/tidb/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/pingcap/tidb/teams","hooks_url":"https://api.github.com/repos/pingcap/tidb/hooks","issue_events_url":"https://api.github.com/repos/pingcap/tidb/issues/events{/number}","events_url":"https://api.github.com/repos/pingcap/tidb/events","assignees_url":"https://api.github.com/repos/pingcap/tidb/assignees{/user}","branches_url":"https://api.github.com/repos/pingcap/tidb/branches{/branch}","tags_url":"https://api.github.com/repos/pingcap/tidb/tags","blobs_url":"https://api.github.com/repos/pingcap/tidb/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/pingcap/tidb/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/pingcap/tidb/git/refs{/sha}","trees_url":"https://api.github.com/repos/pingcap/tidb/git/trees{/sha}","statuses_url":"https://api.github.com/repos/pingcap/tidb/statuses/{sha}","languages_url":"https://api.github.com/repos/pingcap/tidb/languages","stargazers_url":"https://api.github.com/repos/pingcap/tidb/stargazers","contributors_url":"https://api.github.com/repos/pingcap/tidb/contributors","subscribers_url":"https://api.github.com/repos/pingcap/tidb/subscribers","subscription_url":"https://api.github.com/repos/pingcap/tidb/subscription","commits_url":"https://api.github.com/repos/pingcap/tidb/commits{/sha}","git_commits_url":"https://api.github.com/repos/pingcap/tidb/git/commits{/sha}","comments_url":"https://api.github.com/repos/pingcap/tidb/comments{/number}","issue_comment_url":"https://api.github.com/repos/pingcap/tidb/issues/comments{/number}","contents_url":"https://api.github.com/repos/pingcap/tidb/contents/{+path}","compare_url":"https://api.github.com/repos/pingcap/tidb/compare/{base}...{head}","merges_url":"https://api.github.com/repos/pingcap/tidb/merges","archive_url":"https://api.github.com/repos/pingcap/tidb/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/pingcap/tidb/downloads","issues_url":"https://api.github.com/repos/pingcap/tidb/issues{/number}","pulls_url":"https://api.github.com/repos/pingcap/tidb/pulls{/number}","milestones_url":"https://api.github.com/repos/pingcap/tidb/milestones{/number}","notifications_url":"https://api.github.com/repos/pingcap/tidb/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/pingcap/tidb/labels{/name}","releases_url":"https://api.github.com/repos/pingcap/tidb/releases{/id}","deployments_url":"https://api.github.com/repos/pingcap/tidb/deployments","created_at":"2015-09-06T04:01:52Z","updated_at":"2017-03-20T14:25:42Z","pushed_at":"2017-03-21T02:09:15Z","git_url":"git://github.com/pingcap/tidb.git","ssh_url":"git@github.com:pingcap/tidb.git","clone_url":"https://github.com/pingcap/tidb.git","svn_url":"https://github.com/pingcap/tidb","homepage":"","size":22464,"stargazers_count":7363,"watchers_count":7363,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":true,"forks_count":963,"mirror_url":null,"open_issues_count":193,"forks":963,"open_issues":193,"watchers":7363,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/2850"},"html":{"href":"https://github.com/pingcap/tidb/pull/2850"},"issue":{"href":"https://api.github.com/repos/pingcap/tidb/issues/2850"},"comments":{"href":"https://api.github.com/repos/pingcap/tidb/issues/2850/comments"},"review_comments":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/2850/comments"},"review_comment":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/2850/commits"},"statuses":{"href":"https://api.github.com/repos/pingcap/tidb/statuses/5d4c4e9784d97ab5b77faf9d87be37574e06277e"}}}}
{"actor":{"display_login":"hanfei1991"}}