[SERVER-14584] BtreeLogic::Builder generates an invalid Btree Created: 16/Jul/14  Updated: 03/Feb/15  Resolved: 28/Jul/14

Status: Closed
Project: Core Server
Component/s: Index Maintenance, Storage
Affects Version/s: 2.2.7
Fix Version/s: 2.7.5

Type: Bug Priority: Major - P3
Reporter: Mathias Stearn Assignee: Mathias Stearn
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
Duplicate
duplicates SERVER-2732 btreebuilder may create a bucket with... Closed
Related
related to SERVER-7326 "validate" command should perform ful... Closed
Tested
Backwards Compatibility: Fully Compatible
Operating System: ALL
Participants:
Linked BF Score: 0

 Description   

The btree it builds has a root node with no nextChild. This means it has N keys and N children rather than N+1.

This only effects foreground index builds with enough data to have a multi-layer btree.

I verified this has been the behavior since at least 2.2 which is the oldest branch I can build locally.



 Comments   
Comment by Githook User [ 28/Jul/14 ]

Author:

{u'username': u'RedBeard0531', u'name': u'Mathias Stearn', u'email': u'mathias@10gen.com'}

Message: SERVER-14584 Clean up BtreeLogic::pushBack/_pushBack naming

There are no functional changes, other than the file:line that would be
printed on invariant failures.
Branch: master
https://github.com/mongodb/mongo/commit/94880490ed1d138be2a6547726ef598511f8311a

Comment by Githook User [ 28/Jul/14 ]

Author:

{u'username': u'RedBeard0531', u'name': u'Mathias Stearn', u'email': u'mathias@10gen.com'}

Message: SERVER-14584 Use correct algorithm in BtreeLogic::Builder

Both algorithms cover phases 2 and 3 of forground index building. Importantly
they both take as input pre-sorted data that has already been extracted from
the raw documents (phase 1).

OLD ALGORITHM:
Phase 2:
Add all keys to buckets. When a bucket gets full, create a new bucket and
link it as the original bucket's parent pointer. At the end of the stage
we have a linked-list of leaf nodes starting as the left-most corner.

Phase 3:
Walk the linked produced by phase 2, and build the layer above the leaves.
With each bucket, except for the last (right-most), pop* its highest key
and add it to the bucket that will be it's parent. If the current parent
bucket is full a new one is added to higher-layer linked list as in
phase 1. Phase 3 is repeated on the new higher-layer linked list until you
get a layer with a single bucket which is marked as the root of the tree.

  • Importantly, popping a key is what sets the nextChild pointer on a
    bucket. It is set to what used to be the prevChildNode of the key that is
    popped. A major flaw of this algorithm is that because no key is ever
    popped from the root, its nextChild pointer is never filled in.

NEW ALGORITHM:
Phase 2:
Add all keys to buckets. When a bucket gets full, pop the highest key
(setting the nextChild pointer of the bucket to the prevChild of the
popped key), add the popped key to a parent bucket, and create a new right
sibling bucket to add the new key to. If the parent bucket is full, this
same operation is performed on the parent and all full ancestors. If we
get to the root and it is full, a new root is created above the current
root. When creating a new right sibling, it is set as its parent's
nextChild as all keys in the right sibling will be higher than all keys
currently in the parent.

Phase 3:
Does nothing. This may go away soon.

Non-exhaustive list of benefits to the new algorthm:

Comment by Mathias Stearn [ 25/Jul/14 ]

SERVER-2732 is the same issue.

Generated at Thu Feb 08 03:35:20 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.