{"action":"created","comment":{"url":"https://api.github.com/repos/pingcap/tidb/pulls/comments/70568741","id":70568741,"diff_hunk":"@@ -57,13 +68,101 @@ func (c *Column) String() string {\n \treturn strings.Join(strs, \"\\n\")\n }\n \n+// EqualRowCount estimates the row count where the column equals to value.\n+func (c *Column) EqualRowCount(value types.Datum) (int64, error) {\n+\tif len(c.Numbers) == 0 {\n+\t\treturn pseudoRowCount / pseudoEqualRate, nil\n+\t}\n+\tindex, match, err := c.search(value)\n+\tif err != nil {\n+\t\treturn 0, errors.Trace(err)\n+\t}\n+\tif index == len(c.Numbers) {\n+\t\treturn c.Numbers[index-1] + 1, nil\n+\t}\n+\tif match {\n+\t\treturn c.Repeats[index] + 1, nil\n+\t}\n+\ttotalCount := c.Numbers[len(c.Numbers)-1] + 1\n+\treturn totalCount / c.NDV, nil\n+}\n+\n+// LessRowCount estimates the row count where the column less than value.\n+func (c *Column) LessRowCount(value types.Datum) (int64, error) {\n+\tif len(c.Numbers) == 0 {\n+\t\treturn pseudoRowCount / pseudoLessRate, nil\n+\t}\n+\tindex, match, err := c.search(value)\n+\tif err != nil {\n+\t\treturn 0, errors.Trace(err)\n+\t}\n+\tif index == len(c.Numbers) {\n+\t\treturn c.totalRowCount(), nil\n+\t}\n+\tnumber := c.Numbers[index]\n+\tprevNumber := int64(0)\n+\tif index > 0 {\n+\t\tprevNumber = c.Numbers[index-1]\n+\t}\n+\tlessThanBucketValueCount := number - c.Repeats[index]\n+\tif match {\n+\t\treturn lessThanBucketValueCount, nil\n+\t}\n+\treturn (prevNumber + lessThanBucketValueCount) / 2, nil\n+}\n+\n+// BetweenRowCount estimate the row count where column greater or equal to a and less than b.\n+func (c *Column) BetweenRowCount(a, b types.Datum) (int64, error) {\n+\tif len(c.Numbers) == 0 {\n+\t\treturn pseudoRowCount / pseudoBetweenRate, nil\n+\t}\n+\tlessCountA, err := c.LessRowCount(a)\n+\tif err != nil {\n+\t\treturn 0, errors.Trace(err)\n+\t}\n+\tlessCountB, err := c.LessRowCount(b)\n+\tif err != nil {\n+\t\treturn 0, errors.Trace(err)\n+\t}\n+\tif lessCountA >= lessCountB {\n+\t\treturn c.inBucketBetweenCount(), nil\n+\t}\n+\treturn lessCountB - lessCountA, nil\n+}\n+\n+func (c *Column) totalRowCount() int64 {\n+\treturn c.Numbers[len(c.Numbers)-1] + 1\n+}\n+\n+func (c *Column) bucketRowCount() int64 {\n+\treturn c.totalRowCount() / int64(len(c.Numbers))\n+}\n+\n+func (c *Column) inBucketBetweenCount() int64 {\n+\treturn c.bucketRowCount()/3 + 1\n+}\n+\n+func (c *Column) search(target types.Datum) (index int, match bool, err error) {\n+\tindex = sort.Search(len(c.Values), func(i int) bool {\n+\t\tcmp, err1 := c.Values[i].CompareDatum(target)\n+\t\tif err1 != nil {\n+\t\t\terr = errors.Trace(err1)\n+\t\t\treturn false\n+\t\t}\n+\t\tif cmp == 0 {\n+\t\t\tmatch = true\n+\t\t}\n+\t\treturn cmp >= 0\n+\t})\n+\treturn\n+}\n+\n // Table represents statistics for a table.\n type Table struct {\n-\tinfo        *model.TableInfo\n-\tTS          int64 // build timestamp.\n-\tColumns     []*Column\n-\tCount       int64 // Total row count in a table.\n-\tBucketCount int64 // Number of histogram bucket.\n+\tinfo    *model.TableInfo\n+\tTS      int64 // build timestamp.","path":"plan/statistics/statistics.go","position":126,"original_position":126,"commit_id":"744003f1ee33659d72019dca415b2c53cbfb003f","original_commit_id":"744003f1ee33659d72019dca415b2c53cbfb003f","user":{"login":"shenli","id":1192573,"avatar_url":"https://avatars.githubusercontent.com/u/1192573?v=3","gravatar_id":"","url":"https://api.github.com/users/shenli","html_url":"https://github.com/shenli","followers_url":"https://api.github.com/users/shenli/followers","following_url":"https://api.github.com/users/shenli/following{/other_user}","gists_url":"https://api.github.com/users/shenli/gists{/gist_id}","starred_url":"https://api.github.com/users/shenli/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/shenli/subscriptions","organizations_url":"https://api.github.com/users/shenli/orgs","repos_url":"https://api.github.com/users/shenli/repos","events_url":"https://api.github.com/users/shenli/events{/privacy}","received_events_url":"https://api.github.com/users/shenli/received_events","type":"User","site_admin":false},"body":"Why make Ts/Columns/Count public?","created_at":"2016-07-13T06:11:38Z","updated_at":"2016-07-13T06:11:38Z","html_url":"https://github.com/pingcap/tidb/pull/1434#discussion_r70568741","pull_request_url":"https://api.github.com/repos/pingcap/tidb/pulls/1434","_links":{"self":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/comments/70568741"},"html":{"href":"https://github.com/pingcap/tidb/pull/1434#discussion_r70568741"},"pull_request":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/1434"}}},"pull_request":{"url":"https://api.github.com/repos/pingcap/tidb/pulls/1434","id":77112358,"html_url":"https://github.com/pingcap/tidb/pull/1434","diff_url":"https://github.com/pingcap/tidb/pull/1434.diff","patch_url":"https://github.com/pingcap/tidb/pull/1434.patch","issue_url":"https://api.github.com/repos/pingcap/tidb/issues/1434","number":1434,"state":"open","locked":false,"title":"plan/statistics: implement pseudo table and API to estimate row count.","user":{"login":"coocood","id":891222,"avatar_url":"https://avatars.githubusercontent.com/u/891222?v=3","gravatar_id":"","url":"https://api.github.com/users/coocood","html_url":"https://github.com/coocood","followers_url":"https://api.github.com/users/coocood/followers","following_url":"https://api.github.com/users/coocood/following{/other_user}","gists_url":"https://api.github.com/users/coocood/gists{/gist_id}","starred_url":"https://api.github.com/users/coocood/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/coocood/subscriptions","organizations_url":"https://api.github.com/users/coocood/orgs","repos_url":"https://api.github.com/users/coocood/repos","events_url":"https://api.github.com/users/coocood/events{/privacy}","received_events_url":"https://api.github.com/users/coocood/received_events","type":"User","site_admin":false},"body":"","created_at":"2016-07-12T12:38:37Z","updated_at":"2016-07-13T06:11:38Z","closed_at":null,"merged_at":null,"merge_commit_sha":"014b07980b40b041fb6cf12def0d24f70c849733","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/pingcap/tidb/pulls/1434/commits","review_comments_url":"https://api.github.com/repos/pingcap/tidb/pulls/1434/comments","review_comment_url":"https://api.github.com/repos/pingcap/tidb/pulls/comments{/number}","comments_url":"https://api.github.com/repos/pingcap/tidb/issues/1434/comments","statuses_url":"https://api.github.com/repos/pingcap/tidb/statuses/744003f1ee33659d72019dca415b2c53cbfb003f","head":{"label":"pingcap:coocood/statistics-api","ref":"coocood/statistics-api","sha":"744003f1ee33659d72019dca415b2c53cbfb003f","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-07-13T06:01:22Z","pushed_at":"2016-07-13T05:32:59Z","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":16791,"stargazers_count":4258,"watchers_count":4258,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":534,"mirror_url":null,"open_issues_count":94,"forks":534,"open_issues":94,"watchers":4258,"default_branch":"master"}},"base":{"label":"pingcap:master","ref":"master","sha":"13910f108c1d071c5a2d9fa92bb503c85775fc04","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-07-13T06:01:22Z","pushed_at":"2016-07-13T05:32:59Z","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":16791,"stargazers_count":4258,"watchers_count":4258,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":534,"mirror_url":null,"open_issues_count":94,"forks":534,"open_issues":94,"watchers":4258,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/1434"},"html":{"href":"https://github.com/pingcap/tidb/pull/1434"},"issue":{"href":"https://api.github.com/repos/pingcap/tidb/issues/1434"},"comments":{"href":"https://api.github.com/repos/pingcap/tidb/issues/1434/comments"},"review_comments":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/1434/comments"},"review_comment":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/pingcap/tidb/pulls/1434/commits"},"statuses":{"href":"https://api.github.com/repos/pingcap/tidb/statuses/744003f1ee33659d72019dca415b2c53cbfb003f"}}}}
{"actor":{"display_login":"shenli"}}