diff options
| author | Keith Bostic <keith.bostic@mongodb.com> | 2017-01-23 00:53:47 -0500 |
|---|---|---|
| committer | Michael Cahill <michael.cahill@mongodb.com> | 2017-01-23 16:53:47 +1100 |
| commit | 5e6ffcc7ef98a609e4bbc0ecfef58dade45de1d7 (patch) | |
| tree | df8d192a4139f7cee2bd59d6e1aa00459aaa8d62 | |
| parent | 52171b4c668528c80d1e2084183899f294d4c797 (diff) | |
WT-3144 Make it less likely for random lookups to return WT_NOTFOUND (#3259)
There may be empty pages in the tree, and they're useless to us when trying to find random samples. If we don't find a non-empty page in "entries" random guesses, take the first non-empty page in the tree. If the search page contains nothing other than empty pages, restart from the root some number of times before giving up.
| -rw-r--r-- | src/btree/row_srch.c | 30 |
1 files changed, 28 insertions, 2 deletions
diff --git a/src/btree/row_srch.c b/src/btree/row_srch.c index aa299a161da..5b3f1195784 100644 --- a/src/btree/row_srch.c +++ b/src/btree/row_srch.c @@ -792,9 +792,11 @@ __wt_row_random_descent(WT_SESSION_IMPL *session, WT_CURSOR_BTREE *cbt) WT_PAGE *page; WT_PAGE_INDEX *pindex; WT_REF *current, *descent; + uint32_t i, entries, retry; btree = S2BT(session); current = NULL; + retry = 100; if (0) { restart: /* @@ -812,8 +814,32 @@ restart: /* break; WT_INTL_INDEX_GET(session, page, pindex); - descent = pindex->index[ - __wt_random(&session->rnd) % pindex->entries]; + entries = pindex->entries; + + /* + * There may be empty pages in the tree, and they're useless to + * us. If we don't find a non-empty page in "entries" random + * guesses, take the first non-empty page in the tree. If the + * search page contains nothing other than empty pages, restart + * from the root some number of times before giving up. + */ + for (i = 0; i < entries; ++i) { + descent = + pindex->index[__wt_random(&session->rnd) % entries]; + if (descent->state != WT_REF_DELETED) + break; + } + if (i == entries) + for (i = 0; i < entries; ++i) { + descent = pindex->index[i]; + if (descent->state != WT_REF_DELETED) + break; + } + if (i == entries) { + if (--retry > 0) + goto restart; + return (WT_NOTFOUND); + } /* * Swap the current page for the child page. If the page splits |