[BUG] Index was outside the bounds of the array. / The method or operation is not implemented.

[alexSatov]

Version 5.0.11 / win10 / net6.0

Describe the bug Method ILiteCollection<T>.FindOne(Expression<Func<T, bool>> predicate) throws exceptions with a large number of parallel calls

Code to Reproduce

class PortedNumber
{
	[BsonId]
	public int Number { get; set; }
}

static ILiteCollection<PortedNumber> PortedNumbers;

[TestCase(1000000)]
void FindNumbers_Parallel(int n)
{
  var numbers = Enumerable.Range(0, n).Select(_ => Random.Next(0, 1000000000)).ToList();
  var results = new TimeSpan[n];
  var tasks = new Task[n];
  
  for (var i = 0; i < n; i++)
  {
	  var j = i;
	  var number = numbers[i];
  
	  tasks[i] = Task.Run(async () =>
	  {
		  var watch = Stopwatch.StartNew();
  
		  try
		  {
			  PortedNumbers.FindOne(pn => pn.Number == number);
		  }
		  catch (Exception e)
		  {
			  Console.WriteLine($"ERROR ({j}): {e.Message}");
		  }
		  finally
		  {
			  watch.Stop();
		  }
  
		  results[j] = watch.Elapsed;
	  });
  }
  
  Task.WaitAll(tasks);
  
  var sum = results.Aggregate((current, next) => current.Add(next));
  
  Console.WriteLine($"Max: {results.Max()}");
  Console.WriteLine($"Min: {results.Min()}");
  Console.WriteLine($"Avg: {sum / n}");
  Console.WriteLine($"Sum: {sum}");
  Console.WriteLine($"First 10:\r\n{string.Join("\r\n", results.Take(10))}");
}

Expected behavior No exceptions

Screenshots/Stacktrace

System.IndexOutOfRangeException: Index was outside the bounds of the array.
   at LiteDB.Engine.IndexNode.GetNextPrev(Byte level, Int32 order)
   at LiteDB.Engine.IndexService.Find(CollectionIndex index, BsonValue value, Boolean sibling, Int32 order)
   at LiteDB.Engine.IndexEquals.Execute(IndexService indexer, CollectionIndex index)+MoveNext()
   at LiteDB.LinqExtensions.<>c__DisplayClass2_0`2.<<DistinctBy>g___|0>d.MoveNext()
   at LiteDB.Engine.BasePipe.LoadDocument(IEnumerable`1 nodes)+MoveNext()
   at LiteDB.Engine.QueryPipe.Select(IEnumerable`1 source, BsonExpression select)+MoveNext()
   at LiteDB.Engine.QueryExecutor.<>c__DisplayClass10_0.<<ExecuteQuery>g__RunQuery|0>d.MoveNext()
   at LiteDB.BsonDataReader..ctor(IEnumerable`1 values, String collection)
   at LiteDB.Engine.QueryExecutor.ExecuteQuery(Boolean executionPlan)
   at LiteDB.Engine.QueryExecutor.ExecuteQuery()
   at LiteDB.Engine.LiteEngine.Query(String collection, Query query)
   at LiteDB.LiteQueryable`1.ExecuteReader()
   at LiteDB.LiteQueryable`1.ToDocuments()+MoveNext()
   at System.Linq.Enumerable.SelectEnumerableIterator`2.MoveNext()
   at System.Linq.Enumerable.TryGetFirst[TSource](IEnumerable`1 source, Boolean& found)
   at System.Linq.Enumerable.FirstOrDefault[TSource](IEnumerable`1 source)
   at LiteDB.LiteCollection`1.FindOne(BsonExpression predicate)
   at LiteDB.LiteCollection`1.FindOne(Expression`1 predicate)

System.NotImplementedException: The method or operation is not implemented.
   at LiteDB.BufferSliceExtensions.ReadIndexKey(BufferSlice buffer, Int32 offset)
   at LiteDB.Engine.IndexNode..ctor(IndexPage page, Byte index, BufferSlice segment)
   at LiteDB.Engine.IndexPage.GetIndexNode(Byte index)
   at LiteDB.Engine.IndexService.GetNode(PageAddress address)
   at LiteDB.Engine.IndexService.Find(CollectionIndex index, BsonValue value, Boolean sibling, Int32 order)
   at LiteDB.Engine.IndexEquals.Execute(IndexService indexer, CollectionIndex index)+MoveNext()
   at LiteDB.LinqExtensions.<>c__DisplayClass2_0`2.<<DistinctBy>g___|0>d.MoveNext()
   at LiteDB.Engine.BasePipe.LoadDocument(IEnumerable`1 nodes)+MoveNext()
   at LiteDB.Engine.QueryPipe.Select(IEnumerable`1 source, BsonExpression select)+MoveNext()
   at LiteDB.Engine.QueryExecutor.<>c__DisplayClass10_0.<<ExecuteQuery>g__RunQuery|0>d.MoveNext()
   at LiteDB.BsonDataReader..ctor(IEnumerable`1 values, String collection)
   at LiteDB.Engine.QueryExecutor.ExecuteQuery(Boolean executionPlan)
   at LiteDB.Engine.QueryExecutor.ExecuteQuery()
   at LiteDB.Engine.LiteEngine.Query(String collection, Query query)
   at LiteDB.LiteQueryable`1.ExecuteReader()
   at LiteDB.LiteQueryable`1.ToDocuments()+MoveNext()
   at System.Linq.Enumerable.SelectEnumerableIterator`2.MoveNext()
   at System.Linq.Enumerable.TryGetFirst[TSource](IEnumerable`1 source, Boolean& found)
   at System.Linq.Enumerable.FirstOrDefault[TSource](IEnumerable`1 source)
   at LiteDB.LiteCollection`1.FindOne(BsonExpression predicate)
   at LiteDB.LiteCollection`1.FindOne(Expression`1 predicate)

[alexSatov]

Also, actual DB file contains large table of PortedNumber entities (about 18m rows, 5GB)

[navferty]

@alexSatov could you please try with this version against your db, i've just added check to avoid index-out-of-range when searching by index: https://ci.appveyor.com/project/mbdavid/litedb/builds/48766520/job/3gp8t4vdtq5g67vc/artifacts

For some reason, in one of our DB this current IndexNode contained reference to Next/Prev pages as array with length less than expected for current index level.