{"action":"created","comment":{"url":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls/comments/46812054","id":46812054,"diff_hunk":"@@ -842,49 +840,69 @@ __wt_btcur_next_random(WT_CURSOR_BTREE *cbt)\n \tWT_STAT_FAST_CONN_INCR(session, cursor_next);\n \tWT_STAT_FAST_DATA_INCR(session, cursor_next);\n \n-\tif (cbt->ref != NULL) {\n+\t/*\n+\t * If we do not yet reference a page, pick a roughly random leaf page in\n+\t * the tree  and choose a number of leaf pages to skip between samples.\n+\t */\n+\tif (cbt->ref == NULL) {\n \t\t/*\n-\t\t * Number of leaf pages to skip between samples.\n-\t\t * !!! Ideally, this would be prime to avoid restart issues.\n+\t\t * We're compensating for unbalanced trees: in a balanced tree,\n+\t\t * we'd simply descend the tree selecting random slots, but that\n+\t\t * requires a balanced tree with uniform internal and leaf page\n+\t\t * sizes. In some WiredTiger releases, it was possible to have\n+\t\t * unbalanced trees (sometimes, very, very unbalanced trees),\n+\t\t * and in all WiredTiger releases, internal and leaf page sizes\n+\t\t * aren't uniform. So, we skip past 1% of the leaf pages in the\n+\t\t * tree between each random key return to compensate.\n+\t\t *\n+\t\t * Deciding how many leaf pages is roughly 1% of the file is not\n+\t\t * simple. Use the underlying file size divided by its block\n+\t\t * allocation size as our guess of leaf pages in the file (this\n+\t\t * can be entirely wrong, as it depends on how many pages are in\n+\t\t * this particular checkpoint, how large the leaf and internal\n+\t\t * pages really are, and other factors). Then, divide that value\n+\t\t * by 100 to get 1%, and increment the final result to make sure\n+\t\t * tiny files don't leave us with a skip value of 0.\n+\t\t *\n+\t\t * !!!\n+\t\t * Ideally, the number would be prime to avoid restart issues.\n \t\t */\n-\t\tif (cbt->rand_leaf_skip == 0) {\n-\t\t\tcbt->rand_leaf_skip = (uint32_t)\n-\t\t\t    (btree->bm->block->fh->size / btree->allocsize);\n-\t\t\t/* Walk 1% of pages each time, adjust for tiny files. */\n-\t\t\tcbt->rand_leaf_skip /= 100;\n-\t\t\t++cbt->rand_leaf_skip;\n-\t\t\tprintf(\"Skipping %u leaf pages each random op\\n\",\n-\t\t\t    cbt->rand_leaf_skip);\n-\t\t}\n-\n-\t\t/* Walk through the current parent. */\n-\t\tleaf = 0;\n-\t\tparent_ref = cbt->ref->home->pg_intl_parent_ref;\n-\t\tWT_RET(__wt_page_swap(session, cbt->ref, parent_ref, 0));\n-\t\tcbt->ref = parent_ref;\n-\n-\t\twhile (leaf < cbt->rand_leaf_skip) {\n-\t\t\tparent = cbt->ref->page;\n-\t\t\tWT_INTL_FOREACH_BEGIN(session, parent, child) {\n-\t\t\t\tif (__wt_ref_is_leaf(session, child) &&\n-\t\t\t\t    ++leaf == cbt->rand_leaf_skip) {\n-\t\t\t\t\tWT_RET(__wt_page_swap(\n-\t\t\t\t\t    session, cbt->ref, child, 0));\n-\t\t\t\t\tcbt->ref = child;\n-\t\t\t\t\tgoto leaf;\n-\t\t\t\t}\n-\t\t\t} WT_INTL_FOREACH_END;\n-\t\t\tdo {\n-\t\t\t\tWT_RET(__wt_tree_walk(session,\n-\t\t\t\t    &cbt->ref, NULL, WT_READ_SKIP_LEAF));\n-\t\t\t} while (cbt->ref == NULL);\n-\t\t}\n+\t\tcbt->rand_leaf_skip = (uint32_t)\n+\t\t    ((btree->bm->block->fh->size / btree->allocsize) / 100) + 1;\n+#if 0\n+\t\tprintf(\"Skipping %u leaf pages each random op\\n\",\n+\t\t    cbt->rand_leaf_skip);\n+#endif\n+\t\t/*\n+\t\t * Choose a leaf page from the tree.\n+\t\t */\n+\t\tWT_ERR(__cursor_func_init(cbt, true));\n+\t\tWT_WITH_PAGE_INDEX(\n+\t\t    session, ret = __wt_row_random_descent(session, cbt));\n+\t\tWT_ERR(ret);\n+\t} else {\n+\t\t/*\n+\t\t * Read through the tree, skipping leaf pages. Be cautious about\n+\t\t * the skip count: if the last leaf page skipped was also the\n+\t\t * last leaf page in the tree, it may be set to zero on return\n+\t\t * with the end-of-walk condition.\n+\t\t *\n+\t\t * Pages read for data sampling aren't \"useful\"; don't update\n+\t\t * the read generation of pages already in memory, and if a page\n+\t\t * is read, set its generation to a low value so it is evicted\n+\t\t * quickly.\n+\t\t */\n+\t\tfor (skip = cbt->rand_leaf_skip; cbt->ref == NULL || skip > 0;)\n+\t\t\tWT_ERR(__wt_tree_walk(session, &cbt->ref, &skip,\n+\t\t\t    WT_READ_NO_GEN | WT_READ_SKIP_INTL |\n+\t\t\t    WT_READ_SKIP_LEAF | WT_READ_WONT_NEED));","path":"src/btree/bt_cursor.c","position":107,"original_position":107,"commit_id":"1bd4974d84c40a281ce90f2c8e5aca812ec3a334","original_commit_id":"1bd4974d84c40a281ce90f2c8e5aca812ec3a334","user":{"login":"keithbostic","id":1393186,"avatar_url":"https://avatars.githubusercontent.com/u/1393186?v=3","gravatar_id":"","url":"https://api.github.com/users/keithbostic","html_url":"https://github.com/keithbostic","followers_url":"https://api.github.com/users/keithbostic/followers","following_url":"https://api.github.com/users/keithbostic/following{/other_user}","gists_url":"https://api.github.com/users/keithbostic/gists{/gist_id}","starred_url":"https://api.github.com/users/keithbostic/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/keithbostic/subscriptions","organizations_url":"https://api.github.com/users/keithbostic/orgs","repos_url":"https://api.github.com/users/keithbostic/repos","events_url":"https://api.github.com/users/keithbostic/events{/privacy}","received_events_url":"https://api.github.com/users/keithbostic/received_events","type":"User","site_admin":false},"body":"@agorrod, `WT_READ_SKIP_LEAF` matches `WT_READ_SKIP_INTL`, though.\r\n\r\nWe could use `WT_READ_IGNORE_LEAF` and `WT_READ_IGNORE_INTL`?\r\n\r\nI honestly don't care a lot, I'm OK with whatever you and @michaelcahill prefer.","created_at":"2015-12-07T11:42:43Z","updated_at":"2015-12-07T11:42:43Z","html_url":"https://github.com/wiredtiger/wiredtiger/pull/2369#discussion_r46812054","pull_request_url":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls/2369","_links":{"self":{"href":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls/comments/46812054"},"html":{"href":"https://github.com/wiredtiger/wiredtiger/pull/2369#discussion_r46812054"},"pull_request":{"href":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls/2369"}}},"pull_request":{"url":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls/2369","id":52761611,"html_url":"https://github.com/wiredtiger/wiredtiger/pull/2369","diff_url":"https://github.com/wiredtiger/wiredtiger/pull/2369.diff","patch_url":"https://github.com/wiredtiger/wiredtiger/pull/2369.patch","issue_url":"https://api.github.com/repos/wiredtiger/wiredtiger/issues/2369","number":2369,"state":"open","locked":false,"title":"WT-2262: Have random sampling walk the tree so it isn't biased in skewed trees.","user":{"login":"keithbostic","id":1393186,"avatar_url":"https://avatars.githubusercontent.com/u/1393186?v=3","gravatar_id":"","url":"https://api.github.com/users/keithbostic","html_url":"https://github.com/keithbostic","followers_url":"https://api.github.com/users/keithbostic/followers","following_url":"https://api.github.com/users/keithbostic/following{/other_user}","gists_url":"https://api.github.com/users/keithbostic/gists{/gist_id}","starred_url":"https://api.github.com/users/keithbostic/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/keithbostic/subscriptions","organizations_url":"https://api.github.com/users/keithbostic/orgs","repos_url":"https://api.github.com/users/keithbostic/repos","events_url":"https://api.github.com/users/keithbostic/events{/privacy}","received_events_url":"https://api.github.com/users/keithbostic/received_events","type":"User","site_admin":false},"body":"@michaelcahill, some changes for your consideration.","created_at":"2015-12-05T18:54:43Z","updated_at":"2015-12-07T11:42:43Z","closed_at":null,"merged_at":null,"merge_commit_sha":"ed260482dd742e898140532dee690ed650fae942","assignee":{"login":"keithbostic","id":1393186,"avatar_url":"https://avatars.githubusercontent.com/u/1393186?v=3","gravatar_id":"","url":"https://api.github.com/users/keithbostic","html_url":"https://github.com/keithbostic","followers_url":"https://api.github.com/users/keithbostic/followers","following_url":"https://api.github.com/users/keithbostic/following{/other_user}","gists_url":"https://api.github.com/users/keithbostic/gists{/gist_id}","starred_url":"https://api.github.com/users/keithbostic/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/keithbostic/subscriptions","organizations_url":"https://api.github.com/users/keithbostic/orgs","repos_url":"https://api.github.com/users/keithbostic/repos","events_url":"https://api.github.com/users/keithbostic/events{/privacy}","received_events_url":"https://api.github.com/users/keithbostic/received_events","type":"User","site_admin":false},"milestone":null,"commits_url":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls/2369/commits","review_comments_url":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls/2369/comments","review_comment_url":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls/comments{/number}","comments_url":"https://api.github.com/repos/wiredtiger/wiredtiger/issues/2369/comments","statuses_url":"https://api.github.com/repos/wiredtiger/wiredtiger/statuses/1bd4974d84c40a281ce90f2c8e5aca812ec3a334","head":{"label":"wiredtiger:WT-2262-keith","ref":"WT-2262-keith","sha":"1bd4974d84c40a281ce90f2c8e5aca812ec3a334","user":{"login":"wiredtiger","id":1251095,"avatar_url":"https://avatars.githubusercontent.com/u/1251095?v=3","gravatar_id":"","url":"https://api.github.com/users/wiredtiger","html_url":"https://github.com/wiredtiger","followers_url":"https://api.github.com/users/wiredtiger/followers","following_url":"https://api.github.com/users/wiredtiger/following{/other_user}","gists_url":"https://api.github.com/users/wiredtiger/gists{/gist_id}","starred_url":"https://api.github.com/users/wiredtiger/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wiredtiger/subscriptions","organizations_url":"https://api.github.com/users/wiredtiger/orgs","repos_url":"https://api.github.com/users/wiredtiger/repos","events_url":"https://api.github.com/users/wiredtiger/events{/privacy}","received_events_url":"https://api.github.com/users/wiredtiger/received_events","type":"Organization","site_admin":false},"repo":{"id":2944302,"name":"wiredtiger","full_name":"wiredtiger/wiredtiger","owner":{"login":"wiredtiger","id":1251095,"avatar_url":"https://avatars.githubusercontent.com/u/1251095?v=3","gravatar_id":"","url":"https://api.github.com/users/wiredtiger","html_url":"https://github.com/wiredtiger","followers_url":"https://api.github.com/users/wiredtiger/followers","following_url":"https://api.github.com/users/wiredtiger/following{/other_user}","gists_url":"https://api.github.com/users/wiredtiger/gists{/gist_id}","starred_url":"https://api.github.com/users/wiredtiger/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wiredtiger/subscriptions","organizations_url":"https://api.github.com/users/wiredtiger/orgs","repos_url":"https://api.github.com/users/wiredtiger/repos","events_url":"https://api.github.com/users/wiredtiger/events{/privacy}","received_events_url":"https://api.github.com/users/wiredtiger/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/wiredtiger/wiredtiger","description":"WiredTiger's source tree","fork":false,"url":"https://api.github.com/repos/wiredtiger/wiredtiger","forks_url":"https://api.github.com/repos/wiredtiger/wiredtiger/forks","keys_url":"https://api.github.com/repos/wiredtiger/wiredtiger/keys{/key_id}","collaborators_url":"https://api.github.com/repos/wiredtiger/wiredtiger/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/wiredtiger/wiredtiger/teams","hooks_url":"https://api.github.com/repos/wiredtiger/wiredtiger/hooks","issue_events_url":"https://api.github.com/repos/wiredtiger/wiredtiger/issues/events{/number}","events_url":"https://api.github.com/repos/wiredtiger/wiredtiger/events","assignees_url":"https://api.github.com/repos/wiredtiger/wiredtiger/assignees{/user}","branches_url":"https://api.github.com/repos/wiredtiger/wiredtiger/branches{/branch}","tags_url":"https://api.github.com/repos/wiredtiger/wiredtiger/tags","blobs_url":"https://api.github.com/repos/wiredtiger/wiredtiger/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/wiredtiger/wiredtiger/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/wiredtiger/wiredtiger/git/refs{/sha}","trees_url":"https://api.github.com/repos/wiredtiger/wiredtiger/git/trees{/sha}","statuses_url":"https://api.github.com/repos/wiredtiger/wiredtiger/statuses/{sha}","languages_url":"https://api.github.com/repos/wiredtiger/wiredtiger/languages","stargazers_url":"https://api.github.com/repos/wiredtiger/wiredtiger/stargazers","contributors_url":"https://api.github.com/repos/wiredtiger/wiredtiger/contributors","subscribers_url":"https://api.github.com/repos/wiredtiger/wiredtiger/subscribers","subscription_url":"https://api.github.com/repos/wiredtiger/wiredtiger/subscription","commits_url":"https://api.github.com/repos/wiredtiger/wiredtiger/commits{/sha}","git_commits_url":"https://api.github.com/repos/wiredtiger/wiredtiger/git/commits{/sha}","comments_url":"https://api.github.com/repos/wiredtiger/wiredtiger/comments{/number}","issue_comment_url":"https://api.github.com/repos/wiredtiger/wiredtiger/issues/comments{/number}","contents_url":"https://api.github.com/repos/wiredtiger/wiredtiger/contents/{+path}","compare_url":"https://api.github.com/repos/wiredtiger/wiredtiger/compare/{base}...{head}","merges_url":"https://api.github.com/repos/wiredtiger/wiredtiger/merges","archive_url":"https://api.github.com/repos/wiredtiger/wiredtiger/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/wiredtiger/wiredtiger/downloads","issues_url":"https://api.github.com/repos/wiredtiger/wiredtiger/issues{/number}","pulls_url":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls{/number}","milestones_url":"https://api.github.com/repos/wiredtiger/wiredtiger/milestones{/number}","notifications_url":"https://api.github.com/repos/wiredtiger/wiredtiger/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/wiredtiger/wiredtiger/labels{/name}","releases_url":"https://api.github.com/repos/wiredtiger/wiredtiger/releases{/id}","created_at":"2011-12-09T00:43:19Z","updated_at":"2015-12-07T06:57:45Z","pushed_at":"2015-12-07T06:24:20Z","git_url":"git://github.com/wiredtiger/wiredtiger.git","ssh_url":"git@github.com:wiredtiger/wiredtiger.git","clone_url":"https://github.com/wiredtiger/wiredtiger.git","svn_url":"https://github.com/wiredtiger/wiredtiger","homepage":"http://source.wiredtiger.com/","size":74987,"stargazers_count":625,"watchers_count":625,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":110,"mirror_url":null,"open_issues_count":25,"forks":110,"open_issues":25,"watchers":625,"default_branch":"master"}},"base":{"label":"wiredtiger:WT-2262","ref":"WT-2262","sha":"001d39b123b412b1346144b61d153e23886901cf","user":{"login":"wiredtiger","id":1251095,"avatar_url":"https://avatars.githubusercontent.com/u/1251095?v=3","gravatar_id":"","url":"https://api.github.com/users/wiredtiger","html_url":"https://github.com/wiredtiger","followers_url":"https://api.github.com/users/wiredtiger/followers","following_url":"https://api.github.com/users/wiredtiger/following{/other_user}","gists_url":"https://api.github.com/users/wiredtiger/gists{/gist_id}","starred_url":"https://api.github.com/users/wiredtiger/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wiredtiger/subscriptions","organizations_url":"https://api.github.com/users/wiredtiger/orgs","repos_url":"https://api.github.com/users/wiredtiger/repos","events_url":"https://api.github.com/users/wiredtiger/events{/privacy}","received_events_url":"https://api.github.com/users/wiredtiger/received_events","type":"Organization","site_admin":false},"repo":{"id":2944302,"name":"wiredtiger","full_name":"wiredtiger/wiredtiger","owner":{"login":"wiredtiger","id":1251095,"avatar_url":"https://avatars.githubusercontent.com/u/1251095?v=3","gravatar_id":"","url":"https://api.github.com/users/wiredtiger","html_url":"https://github.com/wiredtiger","followers_url":"https://api.github.com/users/wiredtiger/followers","following_url":"https://api.github.com/users/wiredtiger/following{/other_user}","gists_url":"https://api.github.com/users/wiredtiger/gists{/gist_id}","starred_url":"https://api.github.com/users/wiredtiger/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wiredtiger/subscriptions","organizations_url":"https://api.github.com/users/wiredtiger/orgs","repos_url":"https://api.github.com/users/wiredtiger/repos","events_url":"https://api.github.com/users/wiredtiger/events{/privacy}","received_events_url":"https://api.github.com/users/wiredtiger/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/wiredtiger/wiredtiger","description":"WiredTiger's source tree","fork":false,"url":"https://api.github.com/repos/wiredtiger/wiredtiger","forks_url":"https://api.github.com/repos/wiredtiger/wiredtiger/forks","keys_url":"https://api.github.com/repos/wiredtiger/wiredtiger/keys{/key_id}","collaborators_url":"https://api.github.com/repos/wiredtiger/wiredtiger/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/wiredtiger/wiredtiger/teams","hooks_url":"https://api.github.com/repos/wiredtiger/wiredtiger/hooks","issue_events_url":"https://api.github.com/repos/wiredtiger/wiredtiger/issues/events{/number}","events_url":"https://api.github.com/repos/wiredtiger/wiredtiger/events","assignees_url":"https://api.github.com/repos/wiredtiger/wiredtiger/assignees{/user}","branches_url":"https://api.github.com/repos/wiredtiger/wiredtiger/branches{/branch}","tags_url":"https://api.github.com/repos/wiredtiger/wiredtiger/tags","blobs_url":"https://api.github.com/repos/wiredtiger/wiredtiger/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/wiredtiger/wiredtiger/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/wiredtiger/wiredtiger/git/refs{/sha}","trees_url":"https://api.github.com/repos/wiredtiger/wiredtiger/git/trees{/sha}","statuses_url":"https://api.github.com/repos/wiredtiger/wiredtiger/statuses/{sha}","languages_url":"https://api.github.com/repos/wiredtiger/wiredtiger/languages","stargazers_url":"https://api.github.com/repos/wiredtiger/wiredtiger/stargazers","contributors_url":"https://api.github.com/repos/wiredtiger/wiredtiger/contributors","subscribers_url":"https://api.github.com/repos/wiredtiger/wiredtiger/subscribers","subscription_url":"https://api.github.com/repos/wiredtiger/wiredtiger/subscription","commits_url":"https://api.github.com/repos/wiredtiger/wiredtiger/commits{/sha}","git_commits_url":"https://api.github.com/repos/wiredtiger/wiredtiger/git/commits{/sha}","comments_url":"https://api.github.com/repos/wiredtiger/wiredtiger/comments{/number}","issue_comment_url":"https://api.github.com/repos/wiredtiger/wiredtiger/issues/comments{/number}","contents_url":"https://api.github.com/repos/wiredtiger/wiredtiger/contents/{+path}","compare_url":"https://api.github.com/repos/wiredtiger/wiredtiger/compare/{base}...{head}","merges_url":"https://api.github.com/repos/wiredtiger/wiredtiger/merges","archive_url":"https://api.github.com/repos/wiredtiger/wiredtiger/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/wiredtiger/wiredtiger/downloads","issues_url":"https://api.github.com/repos/wiredtiger/wiredtiger/issues{/number}","pulls_url":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls{/number}","milestones_url":"https://api.github.com/repos/wiredtiger/wiredtiger/milestones{/number}","notifications_url":"https://api.github.com/repos/wiredtiger/wiredtiger/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/wiredtiger/wiredtiger/labels{/name}","releases_url":"https://api.github.com/repos/wiredtiger/wiredtiger/releases{/id}","created_at":"2011-12-09T00:43:19Z","updated_at":"2015-12-07T06:57:45Z","pushed_at":"2015-12-07T06:24:20Z","git_url":"git://github.com/wiredtiger/wiredtiger.git","ssh_url":"git@github.com:wiredtiger/wiredtiger.git","clone_url":"https://github.com/wiredtiger/wiredtiger.git","svn_url":"https://github.com/wiredtiger/wiredtiger","homepage":"http://source.wiredtiger.com/","size":74987,"stargazers_count":625,"watchers_count":625,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":110,"mirror_url":null,"open_issues_count":25,"forks":110,"open_issues":25,"watchers":625,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls/2369"},"html":{"href":"https://github.com/wiredtiger/wiredtiger/pull/2369"},"issue":{"href":"https://api.github.com/repos/wiredtiger/wiredtiger/issues/2369"},"comments":{"href":"https://api.github.com/repos/wiredtiger/wiredtiger/issues/2369/comments"},"review_comments":{"href":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls/2369/comments"},"review_comment":{"href":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/wiredtiger/wiredtiger/pulls/2369/commits"},"statuses":{"href":"https://api.github.com/repos/wiredtiger/wiredtiger/statuses/1bd4974d84c40a281ce90f2c8e5aca812ec3a334"}}}}