Uploaded image for project: 'WiredTiger'
  1. WiredTiger
  2. WT-3052

Improve search if an index hint is wrong

    Details

    • Type: Improvement
    • Status: Resolved
    • Priority: Major - P3
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 3.2.12, WT2.9.1, 3.5.1, 3.4.2
    • Labels:
      None
    • # Replies:
      14
    • Last comment by Customer:
      true

      Description

      While fixing WT-3030, we noticed that a lot of searches saw ref->pindex_hint not match in the parent index being searched. The existing loops (from the hint to the end of the index, then from the beginning of the index to the hint) is inefficient in cases were the hint was slightly too large.

      Also note that in workloads where an internal page is splitting frequently, there can be concurrent searches in different versions of the index. This contributes both to hints being incorrect and churn when readers overwrite the hint set during splits.

        Issue Links

          Activity

          Hide
          xgen-internal-githook Githook User added a comment -

          Author:

          {u'username': u'michaelcahill', u'name': u'Michael Cahill', u'email': u'michael.cahill@mongodb.com'}

          Message: WT-3052 Improve search if index hint is wrong (#3166)

          • After a split, child references in an internal page can end up in a different location in the index array. WiredTiger maintains a hint of the expected offset, and searches if the expected reference is not found at the location of the hint. We now search in both directions starting at the hint: the old hint can be wrong in either direction but usually not by much.
          Show
          xgen-internal-githook Githook User added a comment - Author: {u'username': u'michaelcahill', u'name': u'Michael Cahill', u'email': u'michael.cahill@mongodb.com'} Message: WT-3052 Improve search if index hint is wrong (#3166) After a split, child references in an internal page can end up in a different location in the index array. WiredTiger maintains a hint of the expected offset, and searches if the expected reference is not found at the location of the hint. We now search in both directions starting at the hint: the old hint can be wrong in either direction but usually not by much. Mark the index hint volatile: it would be incorrect if the compiler read it multiple times rather than using a single copy. Branch: mongodb-3.4 https://github.com/wiredtiger/wiredtiger/commit/e4ee4d91f29af4a65b5b183dc558056808ec01aa
          Hide
          xgen-internal-githook Githook User added a comment -

          Author:

          {u'username': u'michaelcahill', u'name': u'Michael Cahill', u'email': u'michael.cahill@mongodb.com'}

          Message: WT-3052 Improve search if index hint is wrong (#3166)

          • After a split, child references in an internal page can end up in a different location in the index array. WiredTiger maintains a hint of the expected offset, and searches if the expected reference is not found at the location of the hint. We now search in both directions starting at the hint: the old hint can be wrong in either direction but usually not by much.
          Show
          xgen-internal-githook Githook User added a comment - Author: {u'username': u'michaelcahill', u'name': u'Michael Cahill', u'email': u'michael.cahill@mongodb.com'} Message: WT-3052 Improve search if index hint is wrong (#3166) After a split, child references in an internal page can end up in a different location in the index array. WiredTiger maintains a hint of the expected offset, and searches if the expected reference is not found at the location of the hint. We now search in both directions starting at the hint: the old hint can be wrong in either direction but usually not by much. Mark the index hint volatile: it would be incorrect if the compiler read it multiple times rather than using a single copy. Branch: mongodb-3.2 https://github.com/wiredtiger/wiredtiger/commit/e4ee4d91f29af4a65b5b183dc558056808ec01aa
          Hide
          xgen-internal-githook Githook User added a comment -

          Author:

          {u'username': u'daveh86', u'name': u'David Hows', u'email': u'howsdav@gmail.com'}

          Message: Import wiredtiger: d48181f6f4db08761ed7b80b0332908b272ad0d0 from branch mongodb-3.2

          ref: 040e3d6f76..d48181f6f4
          for: 3.2.12

          SERVER-26545 Remove fixed-size limitation on WiredTiger hazard pointers
          WT-2336 Add a test validating schema operations via file system call monitoring
          WT-2402 Misaligned structure accesses lead to undefined behavior
          WT-2670 Inefficient I/O when read full DB (poor readahead)
          WT-283 Add a way to change persistent object settings
          WT-2960 Inserting multi-megabyte values can cause pathological lookaside usage
          WT-2969 Possible snapshot corruption during compaction
          WT-3014 Add GCC/clang support for ELF symbol visibility.
          WT-3021 Fixes needed for Java log cursor example, Java raw mode cursors, log cursors in raw mode
          WT-3025 fix error path in log_force_sync
          WT-3028 Workloads with all dirty pages could trigger diagnostic stuck check
          WT-3030 Test failure indicating invalid key order during traversal
          WT-3034 Add support for single-writer named snapshots.
          WT-3037 Fix some outdated comments in logging
          WT-3048 WiredTiger maximum size warning uses the wrong format.
          WT-3051 Remove external __wt_hex symbol.
          WT-3052 Improve search if an index hint is wrong
          WT-3053 Review Python and Java calls to internal WiredTiger functions
          WT-3054 Java PackTest, PackTest03 do not compile
          WT-3055 Java AsyncTest faults
          WT-3056 For cursors with projections, keys should be allowed
          WT-3057 WiredTiger hazard pointers should use the WT_REF, not the WT_PAGE.
          WT-3061 syscall test runs with checkpoint_sync=false and doesn't acknowledge pwrite64
          WT-3064 minor tree cleanups: .gitignore, NEWS misspelling
          WT-3066 lint
          WT-3068 Copy wtperf artifacts when running Jenkins tests
          WT-3069 Fix build failures in LevelDB APIs
          WT-3070 Fix search_near() for index cursor
          WT-3071 Java: fix build with -Werror=sign-conversion
          WT-3075 Document and enforce that WiredTiger now depends on Python 2.7
          WT-3078 Fix a hang in the reconfiguration test.
          WT-3084 Fix Coverity resource leak complaint.
          Branch: v3.2
          https://github.com/mongodb/mongo/commit/52b68fa86ea43e909ad42c901d0579bced6b205f

          Show
          xgen-internal-githook Githook User added a comment - Author: {u'username': u'daveh86', u'name': u'David Hows', u'email': u'howsdav@gmail.com'} Message: Import wiredtiger: d48181f6f4db08761ed7b80b0332908b272ad0d0 from branch mongodb-3.2 ref: 040e3d6f76..d48181f6f4 for: 3.2.12 SERVER-26545 Remove fixed-size limitation on WiredTiger hazard pointers WT-2336 Add a test validating schema operations via file system call monitoring WT-2402 Misaligned structure accesses lead to undefined behavior WT-2670 Inefficient I/O when read full DB (poor readahead) WT-283 Add a way to change persistent object settings WT-2960 Inserting multi-megabyte values can cause pathological lookaside usage WT-2969 Possible snapshot corruption during compaction WT-3014 Add GCC/clang support for ELF symbol visibility. WT-3021 Fixes needed for Java log cursor example, Java raw mode cursors, log cursors in raw mode WT-3025 fix error path in log_force_sync WT-3028 Workloads with all dirty pages could trigger diagnostic stuck check WT-3030 Test failure indicating invalid key order during traversal WT-3034 Add support for single-writer named snapshots. WT-3037 Fix some outdated comments in logging WT-3048 WiredTiger maximum size warning uses the wrong format. WT-3051 Remove external __wt_hex symbol. WT-3052 Improve search if an index hint is wrong WT-3053 Review Python and Java calls to internal WiredTiger functions WT-3054 Java PackTest, PackTest03 do not compile WT-3055 Java AsyncTest faults WT-3056 For cursors with projections, keys should be allowed WT-3057 WiredTiger hazard pointers should use the WT_REF, not the WT_PAGE. WT-3061 syscall test runs with checkpoint_sync=false and doesn't acknowledge pwrite64 WT-3064 minor tree cleanups: .gitignore, NEWS misspelling WT-3066 lint WT-3068 Copy wtperf artifacts when running Jenkins tests WT-3069 Fix build failures in LevelDB APIs WT-3070 Fix search_near() for index cursor WT-3071 Java: fix build with -Werror=sign-conversion WT-3075 Document and enforce that WiredTiger now depends on Python 2.7 WT-3078 Fix a hang in the reconfiguration test. WT-3084 Fix Coverity resource leak complaint. Branch: v3.2 https://github.com/mongodb/mongo/commit/52b68fa86ea43e909ad42c901d0579bced6b205f
          Hide
          xgen-internal-githook Githook User added a comment -

          Author:

          {u'username': u'daveh86', u'name': u'David Hows', u'email': u'howsdav@gmail.com'}

          Message: Import wiredtiger: 8d2324943364286056ae399043f70b8a937de312 from branch mongodb-3.4

          ref: ca6eee06ff..8d23249433
          for: 3.4.2

          SERVER-26545 Remove fixed-size limitation on WiredTiger hazard pointers
          WT-2336 Add a test validating schema operations via file system call monitoring
          WT-2402 Misaligned structure accesses lead to undefined behavior
          WT-2670 Inefficient I/O when read full DB (poor readahead)
          WT-283 Add a way to change persistent object settings
          WT-2960 Inserting multi-megabyte values can cause pathological lookaside usage
          WT-2969 Possible snapshot corruption during compaction
          WT-3014 Add GCC/clang support for ELF symbol visibility.
          WT-3021 Fixes needed for Java log cursor example, Java raw mode cursors, log cursors in raw mode
          WT-3025 fix error path in log_force_sync
          WT-3028 Workloads with all dirty pages could trigger diagnostic stuck check
          WT-3030 Test failure indicating invalid key order during traversal
          WT-3034 Add support for single-writer named snapshots.
          WT-3037 Fix some outdated comments in logging
          WT-3048 WiredTiger maximum size warning uses the wrong format.
          WT-3051 Remove external __wt_hex symbol.
          WT-3052 Improve search if an index hint is wrong
          WT-3053 Review Python and Java calls to internal WiredTiger functions
          WT-3054 Java PackTest, PackTest03 do not compile
          WT-3055 Java AsyncTest faults
          WT-3056 For cursors with projections, keys should be allowed
          WT-3057 WiredTiger hazard pointers should use the WT_REF, not the WT_PAGE.
          WT-3061 syscall test runs with checkpoint_sync=false and doesn't acknowledge pwrite64
          WT-3064 minor tree cleanups: .gitignore, NEWS misspelling
          WT-3066 lint
          WT-3068 Copy wtperf artifacts when running Jenkins tests
          WT-3069 Fix build failures in LevelDB APIs
          WT-3070 Fix search_near() for index cursor
          WT-3071 Java: fix build with -Werror=sign-conversion
          WT-3075 Document and enforce that WiredTiger now depends on Python 2.7
          WT-3078 Fix a hang in the reconfiguration test.
          WT-3084 Fix Coverity resource leak complaint.
          Branch: v3.4
          https://github.com/mongodb/mongo/commit/d2c64ac8c526b70eadeb859ec41370a5f03a64aa

          Show
          xgen-internal-githook Githook User added a comment - Author: {u'username': u'daveh86', u'name': u'David Hows', u'email': u'howsdav@gmail.com'} Message: Import wiredtiger: 8d2324943364286056ae399043f70b8a937de312 from branch mongodb-3.4 ref: ca6eee06ff..8d23249433 for: 3.4.2 SERVER-26545 Remove fixed-size limitation on WiredTiger hazard pointers WT-2336 Add a test validating schema operations via file system call monitoring WT-2402 Misaligned structure accesses lead to undefined behavior WT-2670 Inefficient I/O when read full DB (poor readahead) WT-283 Add a way to change persistent object settings WT-2960 Inserting multi-megabyte values can cause pathological lookaside usage WT-2969 Possible snapshot corruption during compaction WT-3014 Add GCC/clang support for ELF symbol visibility. WT-3021 Fixes needed for Java log cursor example, Java raw mode cursors, log cursors in raw mode WT-3025 fix error path in log_force_sync WT-3028 Workloads with all dirty pages could trigger diagnostic stuck check WT-3030 Test failure indicating invalid key order during traversal WT-3034 Add support for single-writer named snapshots. WT-3037 Fix some outdated comments in logging WT-3048 WiredTiger maximum size warning uses the wrong format. WT-3051 Remove external __wt_hex symbol. WT-3052 Improve search if an index hint is wrong WT-3053 Review Python and Java calls to internal WiredTiger functions WT-3054 Java PackTest, PackTest03 do not compile WT-3055 Java AsyncTest faults WT-3056 For cursors with projections, keys should be allowed WT-3057 WiredTiger hazard pointers should use the WT_REF, not the WT_PAGE. WT-3061 syscall test runs with checkpoint_sync=false and doesn't acknowledge pwrite64 WT-3064 minor tree cleanups: .gitignore, NEWS misspelling WT-3066 lint WT-3068 Copy wtperf artifacts when running Jenkins tests WT-3069 Fix build failures in LevelDB APIs WT-3070 Fix search_near() for index cursor WT-3071 Java: fix build with -Werror=sign-conversion WT-3075 Document and enforce that WiredTiger now depends on Python 2.7 WT-3078 Fix a hang in the reconfiguration test. WT-3084 Fix Coverity resource leak complaint. Branch: v3.4 https://github.com/mongodb/mongo/commit/d2c64ac8c526b70eadeb859ec41370a5f03a64aa
          Hide
          xgen-internal-githook Githook User added a comment -

          Author:

          {u'username': u'keithbostic', u'name': u'Keith Bostic', u'email': u'keith.bostic@mongodb.com'}

          Message: WT-3286 Improve search if an index hint is wrong (#3390)

          Backport of WT-3052 to the 3.0 branch, includes commits 3ac257d and
          8735222.

          The significant change is switching WT_REF.pindex_hint to volatile,
          so we only read it once, and removing the assignment of pindex_hint
          entirely.
          Branch: mongodb-3.0
          https://github.com/wiredtiger/wiredtiger/commit/efd9204c4584d2303a14f092facb9c28913aabc7

          Show
          xgen-internal-githook Githook User added a comment - Author: {u'username': u'keithbostic', u'name': u'Keith Bostic', u'email': u'keith.bostic@mongodb.com'} Message: WT-3286 Improve search if an index hint is wrong (#3390) Backport of WT-3052 to the 3.0 branch, includes commits 3ac257d and 8735222. The significant change is switching WT_REF.pindex_hint to volatile, so we only read it once, and removing the assignment of pindex_hint entirely. Branch: mongodb-3.0 https://github.com/wiredtiger/wiredtiger/commit/efd9204c4584d2303a14f092facb9c28913aabc7

            People

            • Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:
                Days since reply:
                9 weeks, 4 days ago
                Date of 1st Reply: