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

Improve search if an index hint is wrong

    Details

    • # Replies:
      13
    • 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'agorrod', u'name': u'Alex Gorrod', u'email': u'alexander.gorrod@mongodb.com'}

          Message: Import wiredtiger: 1b6c815a3fd34f14c20d5cd627155799d1de535c from branch mongodb-3.6

          ref: ca6eee06ff..1b6c815a3f
          for: 3.5.1

          WT-2336 Add a test validating schema operations via file system call monitoring
          WT-2670 Add option to configure read-ahead per table and change default behavior
          WT-2960 Inserting multi-megabyte values can cause pathological lookaside usage
          WT-2969 Fix a bug that could cause 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-3057 WiredTiger hazard pointers should use the WT_REF, not the WT_PAGE.
          WT-3064 minor tree cleanups: .gitignore, NEWS misspelling
          Branch: master
          https://github.com/mongodb/mongo/commit/21a6f07d859c132154166bd3d83bbed238d5d719

          Show
          xgen-internal-githook Githook User added a comment - Author: {u'username': u'agorrod', u'name': u'Alex Gorrod', u'email': u'alexander.gorrod@mongodb.com'} Message: Import wiredtiger: 1b6c815a3fd34f14c20d5cd627155799d1de535c from branch mongodb-3.6 ref: ca6eee06ff..1b6c815a3f for: 3.5.1 WT-2336 Add a test validating schema operations via file system call monitoring WT-2670 Add option to configure read-ahead per table and change default behavior WT-2960 Inserting multi-megabyte values can cause pathological lookaside usage WT-2969 Fix a bug that could cause 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-3057 WiredTiger hazard pointers should use the WT_REF, not the WT_PAGE. WT-3064 minor tree cleanups: .gitignore, NEWS misspelling Branch: master https://github.com/mongodb/mongo/commit/21a6f07d859c132154166bd3d83bbed238d5d719
          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

            People

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

              Dates

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