Skip to content

An indexed range scan starts in the MIDDLE of the run of index entries that share the lower-bound key, so >= silently drops part of the rows equal to the bound #7611

Closed

Description

@tae898

Summary

LSMTreeIndexMutable.compareKey() resolves an ambiguous binary-search landing point to the first entry of a same-key run only when the search key is a PARTIAL key. For a full key the walk is skipped, so an ascending range scan starts wherever the binary search happened to converge inside that run and the entries before it are never visited.

A key owns more than one entry in a page whenever more than one transaction wrote it, which is the normal state of any non-unique index under batched loading. So WHERE d >= 'x' returns every row above x and only some of the rows equal to x.

The row-scan path is correct on the same data, so adding an index to make the query faster changes its answer. >, =, <=, IN, and a predicate no index can serve are all correct; >= and BETWEEN are not. A bound parameter does not help, and neither does compaction.

The shortfall is floor((k-1)/2) for a run of k entries in one page, which is exactly the distance from the middle of the run to its start.

Found on a TPC-H Q6 shape (l_shipdate >= '1994-01-01' AND l_shipdate < '1995-01-01' on an indexed string column): revenue 11,801,684.4174 where eight other engines on the same data return 11,803,420.2534. The predicate on its own returns 92,037 rows where the row scan returns 92,040 at scale factor 0.1, and 908,652 against 909,455 at scale factor 1. Every lost row had l_shipdate exactly equal to the lower bound.

Version: 26.9.1 (build 9cea8e848fa57d275b8d614328245508cd76614a, branch main), from the official arcadedata/arcadedb:26.9.1 image, JDK Temurin 21.0.12. Both code sites named below are unchanged on main as of 2c60c3f4a555b151fc1e15ab6874c4b9d1463268 (2026-09-07).

Reproduction

One self-contained class, no Maven, no test harness. It builds and runs inside the published image:

docker run --rm -v "$PWD":/work -w /work --entrypoint sh arcadedata/arcadedb:26.9.1 -c \
  'javac -cp "/home/arcadedb/lib/*" IndexedLowerBoundRangeRepro.java && \
   java -cp "/home/arcadedb/lib/*:." IndexedLowerBoundRangeRepro'

It exits 0 if every count is right and 1 otherwise, so it can go straight into CI. On 26.9.1 it exits 1 with 22 wrong counts. Full source is attached below.

Observed output

The shape it was found on

102,280 documents, ISO date strings on a STRING property, 40 rows per day across seven years, shuffled and loaded in five batches of 20,000. One type carries a NOTUNIQUE index on the date; its twin carries none and holds the identical rows.

  indexed   d >= '1994-01-01' AND d < '1995-01-01'              14593      14600   WRONG
  indexed   d >  '1993-12-31' AND d < '1995-01-01'              14600      14600   ok
  indexed   d BETWEEN '1994-01-01' AND '1994-12-31'             14593      14600   WRONG
  indexed   d >= :from AND d < :to  (parameters)                14593      14600   WRONG
  indexed   d.substring(0, 4) = '1994'  (no index can serve it) 14600      14600   ok
  indexed   d = '1994-01-01'                                       40         40   ok

  no index  d >= '1994-01-01' AND d < '1995-01-01'              14600      14600   ok
  no index  d >  '1993-12-31' AND d < '1995-01-01'              14600      14600   ok
  no index  d BETWEEN '1994-01-01' AND '1994-12-31'             14600      14600   ok

  the rows the indexed range returns, by date, first three days of 1994:
    indexed  1994-01-01=33  1994-01-02=40  1994-01-03=40
    no index 1994-01-01=40  1994-01-02=40  1994-01-03=40

The loss is entirely on the day equal to the lower bound. Every later day is complete, which is why a range wide enough to matter still looks plausible and a row count is the only thing that catches it.

The minimal shape

Five rows below the bound, k rows exactly at it, five above, each row in its own transaction.

  k = 1, s >= 'B'                                               6          6   ok
  k = 2, s >= 'B'                                               7          7   ok
  k = 3, s >= 'B'                                               7          8   WRONG
  k = 4, s >= 'B'                                               8          9   WRONG
  k = 5, s >= 'B'                                               8         10   WRONG
  k = 10, s >= 'B'                                             11         15   WRONG
  k = 20, s >= 'B'                                             16         25   WRONG
  k = 40, s >= 'B'                                             26         45   WRONG
  k = 100, s >= 'B'                                            56        105   WRONG

Three rows at the bound are enough. The shortfall is floor((k-1)/2) at every size.

It is the index, not the literal

  indexed   s >= 'B'                                           11         15   WRONG
  indexed   s >= :b (parameter)                                11         15   WRONG
  indexed   s BETWEEN 'B' AND 'C'                              11         15   WRONG
  indexed   s >= 'B' AND s <= 'C'                              11         15   WRONG
  indexed   s IN ['B', 'C']                                    15         15   ok

  no index  s >= 'B'                                           15         15   ok
  no index  s >= :b (parameter)                                15         15   ok
  no index  s BETWEEN 'B' AND 'C'                              15         15   ok

IN is correct because it seeks each value as an exact key rather than as a range start.

Every ordered key type

  STRING indexed   s >= :b                                     11         15   WRONG
  INTEGER indexed   s >= :b                                    11         15   WRONG
  LONG indexed   s >= :b                                       11         15   WRONG
  DOUBLE indexed   s >= :b                                     11         15   WRONG
  DATE indexed   s >= :b                                       11         15   WRONG
  DATETIME indexed   s >= :b                                   11         15   WRONG

Each of those has its unindexed twin at the correct 15 in the captured output. Nothing here is about strings.

What is correct on the same data

  all rows at the bound in ONE transaction, s >= 'B'           15         15   ok
  UNIQUE index, every key distinct, s >= 'B000'                10         10   ok
  composite (s, t), PARTIAL key bound, s >= 'B'                15         15   ok
  indexed upper bound, s <= 'B'                                15         15   ok
  indexed equality, s = 'B'                                    10         10   ok
  indexed strict lower bound, s > 'A'                          15         15   ok
  index built AFTER the rows were written, s >= 'B'            15         15   ok

Five of those seven are the shape of the defect read backwards.

One transaction writing all the rows at the bound produces one index entry holding all their RIDs, so there is no run to land in the middle of. A UNIQUE index cannot have a run at all. A bound on the first property of a composite index is a PARTIAL key, which is the one case the existing code already handles. An upper bound is enforced by comparing each entry rather than by seeking, so it never converges anywhere. An equality goes through purpose == 1, which already collects the whole run with findFirstEntryOfSameKey/findLastEntryOfSameKey.

An index built after the rows exist is correct because the bulk build writes each key once. That is the workaround, and it is not a durable one: the next batch of inserts re-creates the runs.

At a size that fills many index pages, and across a compaction

400,000 rows, 1,000 distinct keys, 400 rows per key, 800 transactions.

  before compaction, s >= 'k00500'                         199948     200000   WRONG
  before compaction, s >  'k00499'                         200000     200000   ok
  before compaction, s =  'k00500'                            400        400   ok
  compact() -> true
  after compaction, s >= 'k00500'                          199995     200000   WRONG
  after compaction, s >  'k00499'                          200000     200000   ok

Compaction reduces the loss without removing it: the compacted sub-index writes each key once, so the residue is whatever is still sitting in mutable pages.

Where it comes from

One site, on the ascending-seek path only.

LSMTreeIndexMutable.compareKey() walks to the first entry of the run only for a partial key:

// engine/src/main/java/com/arcadedb/index/lsm/LSMTreeIndexMutable.java:335
if (convertedKeys.length < binaryKeyTypes.length) {
  // PARTIAL MATCHING
  if (purpose == 2) {
    // ASCENDING ITERATOR: FIND THE MOST LEFT ITEM
    mid = findFirstEntryOfSameKey(currentPageBuffer, convertedKeys, startIndexArray, mid);
  } else if (purpose == 3) {
    // DESCENDING ITERATOR
    mid = findLastEntryOfSameKey(count, currentPageBuffer, convertedKeys, startIndexArray, mid);
  }
}

// TODO: SET CORRECT VALUE POSITION FOR PARTIAL KEYS
return new LookupResult(true, false, mid, new int[] { currentPageBuffer.position() });

The guard reads as though a run of equal entries can only exist under a partial key. It cannot: a full key owns one entry per transaction that wrote it, because each commit appends its own (key, rids) entry to the mutable page rather than merging into the previous one. The binary search in LSMTreeIndexAbstract.lookupInPage() returns as soon as compareKey reports a match, and that mid is wherever the halving converged, which for a run of k is its middle.

LSMTreeIndexCursor's constructor takes that keyIndex as the page cursor's starting position:

// engine/src/main/java/com/arcadedb/index/lsm/LSMTreeIndexCursor.java:182
final LSMTreeIndexMutable.LookupResult lookupResult = index.lookupInPage(currentPage.getPageId().getPageNumber(), count,
    currentPageBuffer, serializedFromKeys, ascendingOrder ? 2 : 3);

if (!lookupResult.outside) {
  pageCursors[cursorIdx] = index.newPageIterator(pageId, lookupResult.keyIndex, ascendingOrder);

and the entries before it in that page are simply never produced. FetchFromIndexStep reaches this through index.range(true, convertedFrom, fromKeyIncluded, convertedTo, toKeyIncluded) at FetchFromIndexStep.java:533, and BetweenCondition lowers to the same inclusive from-key, which is why BETWEEN is affected too.

The exclusion check for !beginKeysInclusive sits further down the same constructor and skips entries equal to the from-key, so a strict > is unaffected: the entries the seek lost were the ones it was going to discard anyway.

The identical guard exists in LSMTreeIndexCompacted.compareKey() at line 389, where it carries a comment explaining the partial-key case it was written for (#6592, #6694). It is not reachable with a full key for the same reason compaction lowers the count above: a compacted page holds one entry per key.

A verified candidate fix

Dropping the convertedKeys.length < binaryKeyTypes.length guard in LSMTreeIndexMutable.compareKey(), so the walk to the run boundary runs for a full key too, makes every row in the reproduction correct, including the post-compaction rows:

docker run --rm -v "$PWD":/work -w /work --entrypoint sh arcadedata/arcadedb:26.9.1 -c \
  'javac -cp "/home/arcadedb/lib/*" -d fixclasses fixsrc/com/arcadedb/index/lsm/LSMTreeIndexMutable.java && \
   javac -cp "/home/arcadedb/lib/*" IndexedLowerBoundRangeRepro.java && \
   java -cp "fixclasses:/home/arcadedb/lib/*:." IndexedLowerBoundRangeRepro'

where fixsrc/... is the 26.9.1 file with the guard removed (candidate-fix.diff, attached). Output: ALL ROWS CORRECT - the defect did not reproduce. (attached as repro3-output-with-candidate-fix.txt). Same jars, same class, same data, one guard.

I have not measured what the walk costs on a hot path. findFirstEntryOfSameKey is a linear step back over entries that compare equal, so the cost is bounded by the run length in one page and is paid once per page per scan, not per row. If that is still too much for the equality-heavy paths, the narrower change is to run the walk only for purpose == 2 and purpose == 3, which are the iterator purposes and already the only two the block touches.

Suggested fix

Remove the partial-key guard so a full key gets the same run-boundary walk, in LSMTreeIndexMutable.compareKey() and, for symmetry, in LSMTreeIndexCompacted.compareKey().

I would expect a regression test asserting that an indexed >= and an indexed BETWEEN return the same rows as the unindexed scan over the same data, for a key written by several transactions, at k = 3 (the smallest failing case) and at a size that spans several index pages, ascending and descending, and repeated after compact(). The existing NOTUNIQUE duplicate-key regression test from #5119 covers the equality path and passes today; the range path has no equivalent.

Impact

Any >= or BETWEEN on an indexed non-unique property silently under-reports, with no error, no warning, and a plausible-looking answer. It is worse than a wrong row count in two ways: the query is also faster for having read less, and dropping the index makes the answer correct, so the index reads as an optimisation that changes results.

It needs no unusual schema and no unusual SQL. A date column with an index and a batched loader is enough, which is the common shape of every time-bounded report.

Related

#5119 (NOTUNIQUE index misses entries for keys with many duplicates) is the equality path of the same underlying fact about runs, fixed by #4946 with a regression test that still passes; this is the range-seek path, which that fix did not touch. #6592, #6692, and #6694 are the partial-key and descending-scan corners of the same compareKey() boundary handling, all in the compacted index. #5120 (compaction loses entries) is a different mechanism: here compaction reduces the loss rather than causing it.

Full reproduction source

IndexedLowerBoundRangeRepro.java
/*
 * Reproduction: an inclusive lower bound (>=, or the lower half of BETWEEN) served by an
 * LSM index silently drops part of the rows whose key is EXACTLY the bound.
 *
 * The same predicate answered by a row scan, the same predicate written with a strict >
 * against the previous key, and an equality on the bound are all correct on the same data,
 * so an index that exists only to make the query faster changes the answer.
 *
 * Build and run (no Maven needed, jars from the official image):
 *   javac -cp '/home/arcadedb/lib/*' IndexedLowerBoundRangeRepro.java
 *   java  -cp '/home/arcadedb/lib/*:.' IndexedLowerBoundRangeRepro
 */

import com.arcadedb.Constants;
import com.arcadedb.database.Database;
import com.arcadedb.database.DatabaseFactory;
import com.arcadedb.index.Index;
import com.arcadedb.index.IndexInternal;
import com.arcadedb.query.sql.executor.ResultSet;

import java.io.File;
import java.nio.file.Files;
import java.nio.file.Path;
import java.time.LocalDate;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.stream.Stream;

public class IndexedLowerBoundRangeRepro {

  /** rows strictly below and strictly above the bound, in the minimal shape */
  private static final int NEIGHBOURS = 5;
  /** rows exactly equal to the bound, in the minimal shape */
  private static final int AT_BOUND   = 10;


  private static Database db;
  private static int      failures = 0;

  public static void main(final String[] args) throws Exception {
    final Path dir = Files.createTempDirectory("indexed-lower-bound-repro");
    final String path = dir.resolve("repro").toString();

    System.out.println("ArcadeDB " + Constants.getVersion()
        + "  (build " + Constants.getBuildNumber() + ", branch " + Constants.getBranch()
        + ", " + Constants.getTimestamp() + ")");
    System.out.println("JVM      " + System.getProperty("java.vm.name") + " " + System.getProperty("java.version"));

    try (final DatabaseFactory factory = new DatabaseFactory(path)) {
      db = factory.create();

      partA();
      partB();
      partC();
      partD();
      partE();
      partF();
      partG();

      System.out.println();
      System.out.println(failures == 0
          ? "ALL ROWS CORRECT - the defect did not reproduce."
          : failures + " row(s) above returned the wrong number of records.");
    } finally {
      if (db != null && db.isOpen())
        db.drop();
      delete(dir.toFile());
    }
    System.exit(failures == 0 ? 0 : 1);
  }

  // ---------------------------------------------------------------------------------------------
  // A. the shape a TPC-H Q6 on a string date column hits
  // ---------------------------------------------------------------------------------------------

  private static void partA() {
    header("A. ISO date strings, one property, 40 rows per day over 7 years, loaded in batches");

    db.command("sql", "CREATE DOCUMENT TYPE Ship");
    db.command("sql", "CREATE PROPERTY Ship.d STRING");
    db.command("sql", "CREATE INDEX ON Ship (d) NOTUNIQUE");
    db.command("sql", "CREATE DOCUMENT TYPE ShipNoIndex");
    db.command("sql", "CREATE PROPERTY ShipNoIndex.d STRING");

    final int perDay = 40;
    final List<String> vals = new ArrayList<>();
    for (LocalDate d = LocalDate.of(1992, 1, 1); d.isBefore(LocalDate.of(1999, 1, 1)); d = d.plusDays(1))
      for (int i = 0; i < perDay; i++)
        vals.add(d.toString());
    Collections.shuffle(vals, new Random(42));

    final int batch = 20_000;
    for (int off = 0; off < vals.size(); off += batch) {
      final int lo = off, hi = Math.min(off + batch, vals.size());
      db.transaction(() -> {
        for (int i = lo; i < hi; i++) {
          db.newDocument("Ship").set("d", vals.get(i)).save();
          db.newDocument("ShipNoIndex").set("d", vals.get(i)).save();
        }
      });
    }

    final int year = 365 * perDay;   // 1994 is not a leap year
    System.out.println("  " + vals.size() + " rows, 2557 distinct dates, " + perDay + " rows per date");
    System.out.println();
    row("indexed   d >= '1994-01-01' AND d < '1995-01-01'",
        count("SELECT count(*) AS c FROM Ship WHERE d >= '1994-01-01' AND d < '1995-01-01'"), year);
    row("indexed   d >  '1993-12-31' AND d < '1995-01-01'",
        count("SELECT count(*) AS c FROM Ship WHERE d > '1993-12-31' AND d < '1995-01-01'"), year);
    row("indexed   d BETWEEN '1994-01-01' AND '1994-12-31'",
        count("SELECT count(*) AS c FROM Ship WHERE d BETWEEN '1994-01-01' AND '1994-12-31'"), year);
    row("indexed   d >= :from AND d < :to  (parameters)",
        count("SELECT count(*) AS c FROM Ship WHERE d >= :from AND d < :to",
            Map.of("from", "1994-01-01", "to", "1995-01-01")), year);
    row("indexed   d.substring(0, 4) = '1994'  (no index can serve it)",
        count("SELECT count(*) AS c FROM Ship WHERE d.substring(0, 4) = '1994'"), year);
    row("indexed   d = '1994-01-01'",
        count("SELECT count(*) AS c FROM Ship WHERE d = '1994-01-01'"), perDay);
    System.out.println();
    row("no index  d >= '1994-01-01' AND d < '1995-01-01'",
        count("SELECT count(*) AS c FROM ShipNoIndex WHERE d >= '1994-01-01' AND d < '1995-01-01'"), year);
    row("no index  d >  '1993-12-31' AND d < '1995-01-01'",
        count("SELECT count(*) AS c FROM ShipNoIndex WHERE d > '1993-12-31' AND d < '1995-01-01'"), year);
    row("no index  d BETWEEN '1994-01-01' AND '1994-12-31'",
        count("SELECT count(*) AS c FROM ShipNoIndex WHERE d BETWEEN '1994-01-01' AND '1994-12-31'"), year);
    System.out.println();
    System.out.println("  the rows the indexed range returns, by date, first three days of 1994:");
    System.out.println("    indexed  " + histogram(
        "SELECT d, count(*) AS n FROM Ship WHERE d >= '1994-01-01' AND d < '1994-01-04' GROUP BY d ORDER BY d"));
    System.out.println("    no index " + histogram(
        "SELECT d, count(*) AS n FROM ShipNoIndex WHERE d >= '1994-01-01' AND d < '1994-01-04' GROUP BY d ORDER BY d"));
    System.out.println("  where the defect bites, only the day EQUAL to the lower bound is short: every later");
    System.out.println("  day is complete, so the loss is entirely at the bound.");
  }

  // ---------------------------------------------------------------------------------------------
  // B. the minimal shape
  // ---------------------------------------------------------------------------------------------

  private static void partB() {
    header("B. Minimal shape: 5 rows below the bound, k rows AT it, 5 above, each row its own transaction");
    for (final int k : new int[] { 1, 2, 3, 4, 5, 10, 20, 40, 100 }) {
      final String t = "Min" + k;
      db.command("sql", "CREATE DOCUMENT TYPE " + t);
      db.command("sql", "CREATE PROPERTY " + t + ".s STRING");
      db.command("sql", "CREATE INDEX ON " + t + " (s) NOTUNIQUE");
      fillOneTxPerRow(t, "A", NEIGHBOURS);
      fillOneTxPerRow(t, "B", k);
      fillOneTxPerRow(t, "C", NEIGHBOURS);
      row("k = " + k + ", s >= 'B'", count("SELECT count(*) AS c FROM " + t + " WHERE s >= 'B'"), k + NEIGHBOURS);
    }
    System.out.println("  the shortfall is floor((k-1)/2): the scan starts at the entry the binary search");
    System.out.println("  converged on, which is the middle of the run of entries that share the bound key,");
    System.out.println("  rather than at the first entry of that run.");
  }

  // ---------------------------------------------------------------------------------------------
  // C. it is the index, not the literal
  // ---------------------------------------------------------------------------------------------

  private static void partC() {
    header("C. The same bound written five ways, indexed type against its unindexed twin");
    db.command("sql", "CREATE DOCUMENT TYPE Ix");
    db.command("sql", "CREATE PROPERTY Ix.s STRING");
    db.command("sql", "CREATE INDEX ON Ix (s) NOTUNIQUE");
    db.command("sql", "CREATE DOCUMENT TYPE Nx");
    db.command("sql", "CREATE PROPERTY Nx.s STRING");
    fillPairOneTxPerRow("Ix", "Nx", "A", NEIGHBOURS);
    fillPairOneTxPerRow("Ix", "Nx", "B", AT_BOUND);
    fillPairOneTxPerRow("Ix", "Nx", "C", NEIGHBOURS);
    final int expected = AT_BOUND + NEIGHBOURS;

    row("indexed   s >= 'B'", count("SELECT count(*) AS c FROM Ix WHERE s >= 'B'"), expected);
    row("indexed   s >= :b (parameter)", count("SELECT count(*) AS c FROM Ix WHERE s >= :b", Map.of("b", "B")), expected);
    row("indexed   s BETWEEN 'B' AND 'C'", count("SELECT count(*) AS c FROM Ix WHERE s BETWEEN 'B' AND 'C'"), expected);
    row("indexed   s >= 'B' AND s <= 'C'", count("SELECT count(*) AS c FROM Ix WHERE s >= 'B' AND s <= 'C'"), expected);
    row("indexed   s IN ['B', 'C']", count("SELECT count(*) AS c FROM Ix WHERE s IN ['B', 'C']"), expected);
    System.out.println();
    row("no index  s >= 'B'", count("SELECT count(*) AS c FROM Nx WHERE s >= 'B'"), expected);
    row("no index  s >= :b (parameter)", count("SELECT count(*) AS c FROM Nx WHERE s >= :b", Map.of("b", "B")), expected);
    row("no index  s BETWEEN 'B' AND 'C'", count("SELECT count(*) AS c FROM Nx WHERE s BETWEEN 'B' AND 'C'"), expected);
    System.out.println();
    System.out.println("  a bound parameter and an explicit BETWEEN do not help, which is what separates this");
    System.out.println("  from the FLOAT-precision literal defect: the bound value that reaches the index is right.");
  }

  // ---------------------------------------------------------------------------------------------
  // D. every key type
  // ---------------------------------------------------------------------------------------------

  private static void partD() {
    header("D. Declared key type of the indexed property, same minimal shape, bound passed as a parameter");
    keyType("STRING", "B", "A", "C");
    keyType("INTEGER", 20, 10, 30);
    keyType("LONG", 20L, 10L, 30L);
    keyType("DOUBLE", 20.5d, 10.5d, 30.5d);
    keyType("DATE", date(1994, 1, 1), date(1993, 6, 1), date(1994, 6, 1));
    keyType("DATETIME", dateTime(1994, 1, 1), dateTime(1993, 6, 1), dateTime(1994, 6, 1));
    System.out.println("  nothing here is about strings: every ordered key type loses the same rows.");
  }

  // ---------------------------------------------------------------------------------------------
  // E. what is correct on the same data
  // ---------------------------------------------------------------------------------------------

  private static void partE() {
    header("E. What is correct on the same data");

    // one index entry per key: all the rows at the bound written by ONE transaction
    db.command("sql", "CREATE DOCUMENT TYPE OneTx");
    db.command("sql", "CREATE PROPERTY OneTx.s STRING");
    db.command("sql", "CREATE INDEX ON OneTx (s) NOTUNIQUE");
    db.transaction(() -> {
      for (int i = 0; i < NEIGHBOURS; i++)
        db.newDocument("OneTx").set("s", "A").save();
      for (int i = 0; i < AT_BOUND; i++)
        db.newDocument("OneTx").set("s", "B").save();
      for (int i = 0; i < NEIGHBOURS; i++)
        db.newDocument("OneTx").set("s", "C").save();
    });
    row("all rows at the bound in ONE transaction, s >= 'B'",
        count("SELECT count(*) AS c FROM OneTx WHERE s >= 'B'"), AT_BOUND + NEIGHBOURS);

    // UNIQUE index: a key can never repeat
    db.command("sql", "CREATE DOCUMENT TYPE Uni");
    db.command("sql", "CREATE PROPERTY Uni.s STRING");
    db.command("sql", "CREATE INDEX ON Uni (s) UNIQUE");
    for (int i = 0; i < AT_BOUND; i++) {
      final int ii = i;
      db.transaction(() -> db.newDocument("Uni").set("s", String.format("B%03d", ii)).save());
    }
    row("UNIQUE index, every key distinct, s >= 'B000'",
        count("SELECT count(*) AS c FROM Uni WHERE s >= 'B000'"), AT_BOUND);

    // composite index, bound on the first property only: a PARTIAL key
    db.command("sql", "CREATE DOCUMENT TYPE Cmp");
    db.command("sql", "CREATE PROPERTY Cmp.s STRING");
    db.command("sql", "CREATE PROPERTY Cmp.t INTEGER");
    db.command("sql", "CREATE INDEX ON Cmp (s, t) NOTUNIQUE");
    for (int i = 0; i < NEIGHBOURS; i++) {
      final int ii = i;
      db.transaction(() -> db.newDocument("Cmp").set("s", "A").set("t", ii).save());
    }
    for (int i = 0; i < AT_BOUND; i++) {
      final int ii = i;
      db.transaction(() -> db.newDocument("Cmp").set("s", "B").set("t", ii).save());
    }
    for (int i = 0; i < NEIGHBOURS; i++) {
      final int ii = i;
      db.transaction(() -> db.newDocument("Cmp").set("s", "C").set("t", ii).save());
    }
    row("composite (s, t), PARTIAL key bound, s >= 'B'",
        count("SELECT count(*) AS c FROM Cmp WHERE s >= 'B'"), AT_BOUND + NEIGHBOURS);

    // the upper bound, which is enforced by comparison rather than by a seek
    row("indexed upper bound, s <= 'B'", count("SELECT count(*) AS c FROM Ix WHERE s <= 'B'"), AT_BOUND + NEIGHBOURS);
    row("indexed equality, s = 'B'", count("SELECT count(*) AS c FROM Ix WHERE s = 'B'"), AT_BOUND);
    row("indexed strict lower bound, s > 'A'", count("SELECT count(*) AS c FROM Ix WHERE s > 'A'"),
        AT_BOUND + NEIGHBOURS);

    // an index built AFTER the rows exist
    db.command("sql", "CREATE DOCUMENT TYPE Post");
    db.command("sql", "CREATE PROPERTY Post.s STRING");
    fillOneTxPerRow("Post", "A", NEIGHBOURS);
    fillOneTxPerRow("Post", "B", AT_BOUND);
    fillOneTxPerRow("Post", "C", NEIGHBOURS);
    db.command("sql", "CREATE INDEX ON Post (s) NOTUNIQUE");
    row("index built AFTER the rows were written, s >= 'B'",
        count("SELECT count(*) AS c FROM Post WHERE s >= 'B'"), AT_BOUND + NEIGHBOURS);
  }

  // ---------------------------------------------------------------------------------------------
  // F. at a size that fills many index pages, and across a compaction
  // ---------------------------------------------------------------------------------------------

  private static void partF() {
    header("F. 400,000 rows, 1,000 distinct keys, 400 rows per key, 800 transactions");
    db.command("sql", "CREATE DOCUMENT TYPE Big");
    db.command("sql", "CREATE PROPERTY Big.s STRING");
    db.command("sql", "CREATE INDEX ON Big (s) NOTUNIQUE");

    final int rows = 400_000, batch = 500;
    for (int off = 0; off < rows; off += batch) {
      final int lo = off, hi = Math.min(off + batch, rows);
      db.transaction(() -> {
        for (int i = lo; i < hi; i++)
          db.newDocument("Big").set("s", String.format("k%05d", i % 1000)).save();
      });
    }
    final int expected = 200_000;   // keys k00500 .. k00999, 400 rows each
    row("before compaction, s >= 'k00500'", count("SELECT count(*) AS c FROM Big WHERE s >= 'k00500'"), expected);
    row("before compaction, s >  'k00499'", count("SELECT count(*) AS c FROM Big WHERE s > 'k00499'"), expected);
    row("before compaction, s =  'k00500'", count("SELECT count(*) AS c FROM Big WHERE s = 'k00500'"), 400);

    boolean compacted = false;
    try {
      String name = null;
      for (final Index ix : db.getSchema().getIndexes())
        if (ix.getName().startsWith("Big"))
          name = ix.getName();
      final IndexInternal ix = (IndexInternal) db.getSchema().getIndexByName(name);
      ix.scheduleCompaction();
      compacted = ix.compact();
    } catch (final Exception e) {
      System.out.println("  compaction failed: " + e);
    }
    System.out.println("  compact() -> " + compacted);
    row("after compaction, s >= 'k00500'", count("SELECT count(*) AS c FROM Big WHERE s >= 'k00500'"), expected);
    row("after compaction, s >  'k00499'", count("SELECT count(*) AS c FROM Big WHERE s > 'k00499'"), expected);
  }

  // ---------------------------------------------------------------------------------------------
  // G. the plans
  // ---------------------------------------------------------------------------------------------

  private static void partG() {
    header("G. Execution plans, so the two paths are visible");
    System.out.println("  indexed  s >= 'B' : " + explain("SELECT FROM Ix WHERE s >= 'B'"));
    System.out.println("  no index s >= 'B' : " + explain("SELECT FROM Nx WHERE s >= 'B'"));
    System.out.println("  indexed  d >= '1994-01-01' AND d < '1995-01-01' : "
        + explain("SELECT FROM Ship WHERE d >= '1994-01-01' AND d < '1995-01-01'"));
  }

  // ---------------------------------------------------------------------------------------------

  private static void keyType(final String type, final Object bound, final Object below, final Object above) {
    final String ti = "Kt" + type, tn = "Kn" + type;
    db.command("sql", "CREATE DOCUMENT TYPE " + ti);
    db.command("sql", "CREATE PROPERTY " + ti + ".s " + type);
    db.command("sql", "CREATE INDEX ON " + ti + " (s) NOTUNIQUE");
    db.command("sql", "CREATE DOCUMENT TYPE " + tn);
    db.command("sql", "CREATE PROPERTY " + tn + ".s " + type);
    for (final Object v : new Object[] { below, bound, above }) {
      final int n = v == bound ? AT_BOUND : NEIGHBOURS;
      for (int i = 0; i < n; i++)
        db.transaction(() -> {
          db.newDocument(ti).set("s", v).save();
          db.newDocument(tn).set("s", v).save();
        });
    }
    final long indexed = count("SELECT count(*) AS c FROM " + ti + " WHERE s >= :b", Map.of("b", bound));
    final long scanned = count("SELECT count(*) AS c FROM " + tn + " WHERE s >= :b", Map.of("b", bound));
    row(type + " indexed   s >= :b", indexed, AT_BOUND + NEIGHBOURS);
    row(type + " no index  s >= :b", scanned, AT_BOUND + NEIGHBOURS);
  }

  private static Date date(final int y, final int m, final int d) {
    final Calendar c = Calendar.getInstance();
    c.clear();
    c.set(y, m - 1, d);
    return c.getTime();
  }

  private static Date dateTime(final int y, final int m, final int d) {
    final Calendar c = Calendar.getInstance();
    c.clear();
    c.set(y, m - 1, d, 12, 30, 15);
    return c.getTime();
  }

  private static void fillOneTxPerRow(final String type, final Object value, final int howMany) {
    for (int i = 0; i < howMany; i++)
      db.transaction(() -> db.newDocument(type).set("s", value).save());
  }

  private static void fillPairOneTxPerRow(final String a, final String b, final Object value, final int howMany) {
    for (int i = 0; i < howMany; i++)
      db.transaction(() -> {
        db.newDocument(a).set("s", value).save();
        db.newDocument(b).set("s", value).save();
      });
  }

  private static long count(final String sql) {
    return count(sql, Map.of());
  }

  private static long count(final String sql, final Map<String, Object> params) {
    try (final ResultSet rs = params.isEmpty() ? db.query("sql", sql) : db.query("sql", sql, params)) {
      if (!rs.hasNext())
        return 0;
      final Object v = rs.next().getProperty("c");
      return v == null ? 0 : ((Number) v).longValue();
    }
  }

  private static String histogram(final String sql) {
    final StringBuilder sb = new StringBuilder();
    try (final ResultSet rs = db.query("sql", sql)) {
      while (rs.hasNext()) {
        final var r = rs.next();
        sb.append(String.valueOf((Object) r.getProperty("d"))).append("=")
            .append(String.valueOf((Object) r.getProperty("n"))).append("  ");
      }
    }
    return sb.toString().trim();
  }

  /** first FETCH/SCAN line of the execution plan, so the reader can see which path ran */
  private static String explain(final String sql) {
    try (final ResultSet rs = db.query("sql", "EXPLAIN " + sql)) {
      if (!rs.hasNext())
        return "?";
      final Object p = rs.next().getProperty("executionPlanAsString");
      if (p == null)
        return "?";
      for (final String line : p.toString().split("\n"))
        if (line.contains("FETCH") || line.contains("SCAN"))
          return line.trim();
      return p.toString().replace('\n', ' ');
    }
  }

  private static void header(final String s) {
    System.out.println();
    System.out.println(s);
    System.out.println("  " + "-".repeat(s.length()));
  }

  private static void row(final String label, final long actual, final long expected) {
    final boolean ok = actual == expected;
    if (!ok)
      failures++;
    System.out.printf("  %-58s %10d %10d   %s%n", label, actual, expected, ok ? "ok" : "WRONG");
  }

  private static void delete(final File f) {
    if (f.isDirectory())
      try (final Stream<Path> s = Files.list(f.toPath())) {
        s.sorted(Comparator.reverseOrder()).map(Path::toFile).forEach(IndexedLowerBoundRangeRepro::delete);
      } catch (final Exception ignore) {
        // best effort
      }
    f.delete();
  }
}

Activity

  1. added
    in progressThe team is actively working on this issue
    on Sep 15, 2026
  2. self-assigned this
    on Sep 15, 2026
  3. added this to the 26.10.1 milestone on Sep 15, 2026
  4. lvca commented on Sep 15, 2026

    @lvca
    Member

    Fixed in #7616, merged to main for 26.10.1.

    You were right about the cause, and thanks for the exceptionally precise report - the floor((k-1)/2) shortfall and the minimal repro are what made the fix and the tests exact rather than approximate.

    What was happening. An index page holds one entry per transaction that wrote a key, not one entry per key. So any non-unique index loaded in batches ends up with several entries sharing the same key, sitting next to each other. When a query with >= (or the lower half of BETWEEN) looked up the starting key, the binary search stopped on whichever of those entries it happened to land on, and the scan began there - so the entries before it were never read. Every row above the bound was returned; only some of the rows equal to the bound were.

    That is why >, =, <= and IN were unaffected, why dropping the index gave the right answer, and why rebuilding the index helped only until the next batch of inserts.

    The fix. The starting point is now always moved to the first entry of the group of equal keys, for every kind of key rather than only for composite-index prefixes as before. Finding that first entry is a search outward from the landing point rather than a step-by-step walk, so it costs a single comparison when there is no duplicate group at all and stays cheap when there is a large one - the correction adds no measurable overhead to normal queries.

    Nothing to do on your side beyond upgrading once 26.10.1 is out. No schema, query or index change is needed, and existing indexes are fine as they are - the defect was in how the index was read, never in what was stored, so nothing on disk was ever wrong.

    The regression suite added with the fix compares an indexed type against an unindexed copy of the same rows across the run lengths you identified, every spelling of the bound, both scan directions, deletes and re-inserts inside the group, and before and after a compaction.


    ❤️ Thanks for helping make ArcadeDB better! ArcadeDB is free and open source, sustained by its community. If it's useful to you or your company, please consider becoming a sponsor to keep development going.

  5. removed
    in progressThe team is actively working on this issue
    on Sep 15, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

bugstorageStorage/paging/WAL engine layer

Type

No type

Projects

No projects

    Milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions