{"action":"created","comment":{"url":"https://api.github.com/repos/pingcap/tidb/pulls/comments/77544823","id":77544823,"diff_hunk":"@@ -47,10 +48,224 @@ func columnSubstitute(expr expression.Expression, schema expression.Schema, newE\n \treturn expr\n }\n \n+// propagateConstant propagate constant values of equality predicates and inequality predicates in a condition.\n+func propagateConstant(conditions []expression.Expression) []expression.Expression {\n+\tif len(conditions) == 0 {\n+\t\treturn conditions\n+\t}\n+\t// Propagate constants in equality predicates.\n+\t// e.g. for condition: \"a = b and b = c and c = a and a = 1\";\n+\t// we propagate constant as the following step:\n+\t// first: \"1 = b and b = c and c = 1 and a = 1\";\n+\t// next:  \"1 = b and 1 = c and c = 1 and a = 1\";\n+\t// next:  \"1 = b and 1 = c and 1 = 1 and a = 1\";\n+\t// next:  \"1 = b and 1 = c and a = 1\";\n+\n+\t// e.g for condition: \"a = b and b = c and b = 2 and a = 1\";\n+\t// we propagate constant as the following step:\n+\t// first: \"a = 2 and 2 = c and b = 2 and a = 1\";\n+\t// next:  \"a = 2 and 2 = c and b = 2 and 2 = 1\";\n+\t// next:  \"0\"\n+\tisHandled := make([]bool, len(conditions))\n+\ttype transitiveEqualityPredicate map[string]*expression.Constant // transitive equality predicates between one column and one constant\n+\tfor true {\n+\t\tequalities := make(transitiveEqualityPredicate, 0)\n+\t\tfor i, getOneEquality := 0, false; i < len(conditions) && !getOneEquality; i++ {\n+\t\t\tif isHandled[i] {\n+\t\t\t\tcontinue\n+\t\t\t}\n+\t\t\texpr, ok := conditions[i].(*expression.ScalarFunction)\n+\t\t\tif !ok {\n+\t\t\t\tcontinue\n+\t\t\t}\n+\t\t\t// process the included OR conditions recursively to do the same for CNF item.\n+\t\t\tswitch expr.FuncName.L {\n+\t\t\tcase ast.OrOr:\n+\t\t\t\texpressions := expression.SplitDNFItems(conditions[i])\n+\t\t\t\tnewExpression := make([]expression.Expression, 0)\n+\t\t\t\tfor _, v := range expressions {\n+\t\t\t\t\tnewExpression = append(newExpression, propagateConstant([]expression.Expression{v})...)\n+\t\t\t\t}\n+\t\t\t\tconditions[i] = expression.ComposeDNFCondition(newExpression)\n+\t\t\t\tisHandled[i] = true\n+\t\t\tcase ast.AndAnd:\n+\t\t\t\tnewExpression := propagateConstant(expression.SplitCNFItems(conditions[i]))\n+\t\t\t\tconditions[i] = expression.ComposeCNFCondition(newExpression)\n+\t\t\t\tisHandled[i] = true\n+\t\t\tcase ast.EQ:\n+\t\t\t\tvar (\n+\t\t\t\t\tcol      *expression.Column\n+\t\t\t\t\tval      *expression.Constant\n+\t\t\t\t\tisColumn bool\n+\t\t\t\t)\n+\t\t\t\tleft, ok1 := expr.Args[0].(*expression.Constant)\n+\t\t\t\tright, ok2 := expr.Args[1].(*expression.Constant)\n+\t\t\t\tif col, isColumn = expr.Args[0].(*expression.Column); ok2 && isColumn {\n+\t\t\t\t\tval = right\n+\t\t\t\t} else if col, isColumn = expr.Args[1].(*expression.Column); ok1 && isColumn {\n+\t\t\t\t\tval = left\n+\t\t\t\t} else {\n+\t\t\t\t\tcontinue\n+\t\t\t\t}\n+\t\t\t\tequalities[string(col.HashCode())] = val\n+\t\t\t\tisHandled[i] = true\n+\t\t\t\tgetOneEquality = true\n+\t\t\t}\n+\t\t}\n+\t\tif len(equalities) == 0 {\n+\t\t\tbreak\n+\t\t}\n+\t\tfor i := 0; i < len(conditions); i++ {\n+\t\t\tif isHandled[i] {\n+\t\t\t\tcontinue\n+\t\t\t}\n+\t\t\tif len(equalities) != 0 {\n+\t\t\t\tconditions[i] = constantSubstitute(equalities, conditions[i])\n+\t\t\t}\n+\t\t}\n+\t}\n+\t// Propagate transitive inequality predicates.\n+\t// e.g for conditions \"a = b and c = d and a = c and g = h and b > 0 and e != 0 and g like 'abc'\",\n+\t//     we propagate constant as the following step:\n+\t// 1. build multiple equality predicates(mep):\n+\t//    =(a, b, c, d), =(g, h).\n+\t// 2. extract inequality predicates between one constant and one column,\n+\t//    and rewrite them using the root column of a multiple equality predicate:\n+\t//    b > 0, e != 0, g like 'abc' ==> a > 0, g like 'abc'.\n+\t//    ATTENTION: here column 'e' doesn't belong to any mep, so we skip \"e != 0\".\n+\t// 3. propagate constants in these inequality predicates, and we finally get:\n+\t//    \"a = b and c = d and a = c and e = f and g = h and e != 0 and a > 0 and b > 0 and c > 0 and d > 0 and g like 'abc' and h like 'abc' \".\n+\tmultipleEqualities := make(map[*expression.Column]*expression.Column, 0)\n+\tunion := func(leftExpr *expression.Column, rightExpr *expression.Column) {","path":"plan/predicate_push_down.go","position":100,"original_position":100,"commit_id":"0e7ad1d9a05dc3286b48b06b1f12d57b25ce1ef0","original_commit_id":"0e7ad1d9a05dc3286b48b06b1f12d57b25ce1ef0","user":{"login":"hanfei1991","id":20884546,"avatar_url":"https://avatars.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":"make it a public function.","created_at":"2016-09-05T16:59:00Z","updated_at":"2016-09-05T16:59:00Z","html_url":"https://github.com/pingcap/tidb/pull/1652#discussion_r77544823","pull_request_url":"https://api.github.com/repos/pingcap/tidb/pulls/1652","_links":{"self":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/comments/77544823"},"html":{"href":"https://github.com/pingcap/tidb/pull/1652#discussion_r77544823"},"pull_request":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/1652"}}},"pull_request":{"url":"https://api.github.com/repos/pingcap/tidb/pulls/1652","id":83064103,"html_url":"https://github.com/pingcap/tidb/pull/1652","diff_url":"https://github.com/pingcap/tidb/pull/1652.diff","patch_url":"https://github.com/pingcap/tidb/pull/1652.patch","issue_url":"https://api.github.com/repos/pingcap/tidb/issues/1652","number":1652,"state":"open","locked":false,"title":"support constant propagation","user":{"login":"XuHuaiyu","id":9039012,"avatar_url":"https://avatars.githubusercontent.com/u/9039012?v=3","gravatar_id":"","url":"https://api.github.com/users/XuHuaiyu","html_url":"https://github.com/XuHuaiyu","followers_url":"https://api.github.com/users/XuHuaiyu/followers","following_url":"https://api.github.com/users/XuHuaiyu/following{/other_user}","gists_url":"https://api.github.com/users/XuHuaiyu/gists{/gist_id}","starred_url":"https://api.github.com/users/XuHuaiyu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/XuHuaiyu/subscriptions","organizations_url":"https://api.github.com/users/XuHuaiyu/orgs","repos_url":"https://api.github.com/users/XuHuaiyu/repos","events_url":"https://api.github.com/users/XuHuaiyu/events{/privacy}","received_events_url":"https://api.github.com/users/XuHuaiyu/received_events","type":"User","site_admin":false},"body":"@shenli @hanfei1991 @zimulala @coocood @tiancaiamao \r\nPTAL\r\nA transformation takes place for expressions like this:\r\n\r\n> WHERE column1 = column2 AND column2 = 'x'\r\n\r\nthe transformed condition becomes:\r\n\r\n> WHERE column1 = 'x' AND column2 = 'x'\r\n\r\n\r\nWith constant propagation, we can improve predicate push down\r\nlike:\r\n> SELECT * FROM t1 join t2 on t1.a = t2.a where t1.a = 1;\r\n\r\nafter propagate constant, we get \r\n> SELECT * FROM t1 join t2 where t2.a = 1 and t1.a = 1;\r\n\r\nand we can push down all the conditions.","created_at":"2016-08-29T08:44:34Z","updated_at":"2016-09-05T16:59:00Z","closed_at":null,"merged_at":null,"merge_commit_sha":"0a6057499108dbefb3628d6af4db0ab2743e90b9","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/pingcap/tidb/pulls/1652/commits","review_comments_url":"https://api.github.com/repos/pingcap/tidb/pulls/1652/comments","review_comment_url":"https://api.github.com/repos/pingcap/tidb/pulls/comments{/number}","comments_url":"https://api.github.com/repos/pingcap/tidb/issues/1652/comments","statuses_url":"https://api.github.com/repos/pingcap/tidb/statuses/0e7ad1d9a05dc3286b48b06b1f12d57b25ce1ef0","head":{"label":"pingcap:xuhuaiyu/constant-propagation","ref":"xuhuaiyu/constant-propagation","sha":"0e7ad1d9a05dc3286b48b06b1f12d57b25ce1ef0","user":{"login":"pingcap","id":11855343,"avatar_url":"https://avatars.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://avatars.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":"2016-09-05T09:40:23Z","pushed_at":"2016-09-05T15:12:10Z","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":23559,"stargazers_count":4596,"watchers_count":4596,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":true,"forks_count":576,"mirror_url":null,"open_issues_count":111,"forks":576,"open_issues":111,"watchers":4596,"default_branch":"master"}},"base":{"label":"pingcap:master","ref":"master","sha":"ad0c7b4b4c790bccee1efc1f18cbd6b355300656","user":{"login":"pingcap","id":11855343,"avatar_url":"https://avatars.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://avatars.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":"2016-09-05T09:40:23Z","pushed_at":"2016-09-05T15:12:10Z","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":23559,"stargazers_count":4596,"watchers_count":4596,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":true,"forks_count":576,"mirror_url":null,"open_issues_count":111,"forks":576,"open_issues":111,"watchers":4596,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/1652"},"html":{"href":"https://github.com/pingcap/tidb/pull/1652"},"issue":{"href":"https://api.github.com/repos/pingcap/tidb/issues/1652"},"comments":{"href":"https://api.github.com/repos/pingcap/tidb/issues/1652/comments"},"review_comments":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/1652/comments"},"review_comment":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/1652/commits"},"statuses":{"href":"https://api.github.com/repos/pingcap/tidb/statuses/0e7ad1d9a05dc3286b48b06b1f12d57b25ce1ef0"}}}}
{"actor":{"display_login":"hanfei1991"}}