ExportXMLWordPrintableJSON

    • Type: Task
    • Resolution: Unresolved
    • Priority: Major - P3
    • None
    • Affects Version/s: None
    • Component/s: Btree
    • None
    • Storage Engines - Persistence
    • 361.361
    • StorEng - Defined Pipeline
    • None

      Implement an efficient algorithm for finding differences between two versions (checkpoints) of the same btree. The high-level approach should be:

      • If the address cookie of two subtrees are identical, skip them.
      • If the address cookies are different, descend into them.
      • At the leaf page level, compare each key/value pair individually.

      This approach efficiently skips large parts of the btrees that are identical. Note that this requires:

      • Precise checkpoints, as we'd like to avoid RTS and history store lookups.
      • No prepared keys, as we'd like to avoid WT_PREPARE_CONFLICT.
      • If necessary, also all pages being clean, so that the address cookie comparison works.

      The motivating example for this work is WT-16188, so that we can efficiently determine which metadata entries changed in a shared metadata table between two checkpoints.

            Assignee:
            Peter Macko
            Reporter:
            Peter Macko
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

              Created:
              Updated: