Hacktoberfest 2026: the issues maintainers tagged for October, open and beginner-friendly. Browse Hacktoberfest issues

BTreeIndex.Equal/In/GreaterThan/LessThan/Between/StartsWith miss duplicate keys and fail past the last key

Open
  • Is something wrong?
#255 1 comment 0 reactions 0 assignees View on GitHub

Maintainers usually reply within 2 days

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
55/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
csharp
Domain
database

Research direction

Read src/BLite.Core/Indexing/BTreeIndex.cs around the affected synchronous primitives and their async twins; compare their cursor and range behavior with Range. Run the B-tree model test at tests/BLite.Tests/Oracles/BTreeModelTests.cs and the reproductions in the issue. Done means all qualifying duplicate entries are returned, out-of-range bounds return empty results, and StartsWith uses ordinal prefix matching.

Written by the indexing model from the issue text.

Description

area/indexing bug package/core severity/low

Equal, In, InAsync, GreaterThan, LessThan, Between and StartsWith on BTreeIndex return one entry per duplicated key or skip only one copy of it, throw InvalidOperationException: Cursor is not valid. (or return nothing) when no key is at or after the bound, and StartsWith tests the prefix with the current culture. Range over the same bounds is correct.

Found by the B-tree model test (tests/BLite.Tests/Oracles/BTreeModelTests.cs, #259), which carries the affected rows as a known candidate until this is fixed.

Repro

using var storage = new StorageEngine(path, PageFileConfig.Default);
var index = new BTreeIndex(storage, IndexOptions.CreateBTree("k"));
var txn = storage.BeginTransaction().TransactionId;
index.GreaterThan(IndexKey.Create(28), false, txn).Count();   // empty index: throws InvalidOperationException "Cursor is not valid."
index.Insert(IndexKey.Create(28), new DocumentLocation(1, 1), txn);
index.Insert(IndexKey.Create(28), new DocumentLocation(1, 2), txn);
index.Insert(IndexKey.Create(30), new DocumentLocation(1, 3), txn);
var k = IndexKey.Create(28);

index.Range(k, k, IndexDirection.Forward, txn).Count();       // 2 (correct, the control)
index.Equal(k, txn).Count();                                  // expected 2,      actual 1
index.In([k], txn).Count();                                   // expected 2,      actual 1
index.GreaterThan(k, orEqual: false, txn);                    // expected [30],   actual [28, 30]
index.Between(k, IndexKey.Create(30), false, true, txn);      // expected [30],   actual [28, 30]
index.LessThan(k, orEqual: true, txn);                        // expected [28, 28], actual [28]
index.LessThan(IndexKey.Create(31), orEqual: false, txn);     // expected [30, 28, 28], actual []
index.GreaterThan(IndexKey.Create(31), false, txn);           // expected [], throws InvalidOperationException
index.Between(IndexKey.Create(31), IndexKey.Create(40), true, true, txn); // expected [], throws

var s = new BTreeIndex(storage, IndexOptions.CreateBTree("s"));
foreach (var (v, slot) in new[] { ("a\^Cb", 4), ("\0", 5), ("ab", 6) })
    s.Insert(IndexKey.Create(v), new DocumentLocation(1, (ushort)slot), txn);
s.StartsWith("\0", txn);                                      // expected ["\0"], actual ["\0", "a\^Cb", "ab"]
s.StartsWith("b", txn);                                       // expected [],     throws InvalidOperationException

Expected: every entry that satisfies the primitive, as Range over the same bounds returns them: all copies of a duplicated key, nothing (not an exception) when no key qualifies, and an ordinal prefix test for StartsWith, as BLQL's $startsWith documents ("Prefix match (ordinal)", README.md:1036).

Actual: see the comments above; three mechanisms, all in the primitives that sit on one IBTreeCursor.Seek (src/BLite.Core/Indexing/BTreeIndex.cs:567-677).

Mechanism (verified on 0450b97)

  • Duplicates. Equal (BTreeIndex.cs:567) and In (:665) yield cursor.Current once per key after Seek, which positions on the first copy (BTreeCursor.cs:115); the comment in Equal says as much ("Assuming unique for now"). GreaterThan with orEqual: false (:580) and Between with startInclusive: false (:623) step over one copy with a single MoveNext, so the other copies are returned. LessThan with orEqual: true (:597) starts at the first copy and walks backwards, so the later copies are never seen.
  • Past the last key. When Seek finds no key at or after the bound, the cursor is invalid (BTreeCursor.cs:151-152) and Current throws (BTreeCursor.cs:37). GreaterThan, Between and StartsWith read Current in a do ... while without checking, so they throw on an empty index and for any bound above the last key; LessThan calls MovePrev on the invalid cursor, which returns false, so it returns nothing although every key qualifies.
  • Culture. StartsWith stops at the first key for which val.StartsWith(prefix) is false (BTreeIndex.cs:658), a culture-sensitive comparison. With ICU (Linux, macOS, Windows on .NET 5+ with ICU), U+0000 to U+0003 are ignorable, so "a\^Cb".StartsWith("\0") is true and the walk runs on. Like uses the same test only to stop its walk (:715) and then filters with a regex, so Like is correct.

None of these is called from src/: the collections use Range, ScanRange/CountRange, TryFind, TryFindFirst and Relocate. They are public on BTreeIndex. Their *Async twins (BTreeIndex.cs:2134-2232) are written over RangeAsync with an ordinal prefix test and are correct, except InAsync (:2192), which calls TryFindAsync once per key and so returns one entry per duplicated key, like In.

Affected versions: the primitives are unchanged since the project was renamed (4236d9e, 2026-02-11, v1.0.0). Reproduced on v5.2.3 / 0450b97.

Fix considerations

  • Write the sync primitives the way their async twins already are: a Range over the bounds, which handles duplicates across leaves (#213), empty leaves and the end of the tree, with an exclusive bound skipping every entry equal to it (BetweenAsync, :2164).
  • In and InAsync become one Range(k, k) per key.
  • StartsWith(prefix) is the byte range from the prefix's key to the key after the prefix, the same boundary CollectionSecondaryIndex.CreateCompositeKeyBoundary builds for #206, which is ordinal by construction.
  • Alternatively, mark them [Obsolete] if nothing outside the engine is meant to use them.
Dominant language
C#
Stars
66
Forks
6
Avg merge
1d 2h
Merged PRs (30d)
58

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from EntglDb/BLite

All issues in EntglDb/BLite

Similar issues

More C# issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.