The following comment in <drat/func/btree.c> (line 318, bold emphasis mine) is false:
However, if this is the first entry in this node, we only
descend it if its key's stated OID matches the desired OID;
else it exceeds the desired OID, and thus no records with the
desired OID exist in the whole tree.
The implementation thus needs to be fixed (again...) For non-leaf nodes, consider scanning the nodes in reverse instead, from largest to smallest (OID, XID) pair, then descend the first entry we see whose (OID, XID) is less than the desired (OID, XID). Doing this should get us to the leaf node that contains the first record we're looking for.
Also consider using binary search on each node rather than linear search. Get it working with linear search first, though!
The following comment in
<drat/func/btree.c>(line 318, bold emphasis mine) is false:The implementation thus needs to be fixed (again...) For non-leaf nodes, consider scanning the nodes in reverse instead, from largest to smallest (OID, XID) pair, then descend the first entry we see whose (OID, XID) is less than the desired (OID, XID). Doing this should get us to the leaf node that contains the first record we're looking for.
Also consider using binary search on each node rather than linear search. Get it working with linear search first, though!