Skip to content

Bug: Partial string scans into StringChunkData can corrupt checkpointed relationship properties #658

Description

@jkumz

Ladybug version

0.17.1

What operating system are you using?

macOS 26.4 arm64

What happened?

Deleting a relationship row from a property-bearing relationship table can corrupt the projected string property value for surviving relationships after checkpoint/reload.

I've attached a repro that uses anonymous node/relationship tables and neutral string values. It was reduced from internal data then obfuscated.

The schema is:

CREATE NODE TABLE A (id INT64, key STRING, PRIMARY KEY(id));
CREATE NODE TABLE B (id INT64, key STRING, PRIMARY KEY(id));
CREATE REL TABLE A_TO_B (FROM A TO B, type STRING, MANY_MANY);

The relationship table has one string property, type. The fixture contains 953 relationship rows with this value distribution:

REL_A: 739 rows
REL_B: 202 rows
REL_C:  12 rows

Two rows matter for the minimal repro:

watched survivor: offset 0,   node_3379  -> node_3382,  type REL_A
trigger delete:   offset 952, node_10049 -> node_10050, type REL_A

The watched survivor is not deleted. The trigger row is deleted to dirty a relationship property segment; the reload step then exercises the persisted string-property state for surviving relationships.

The e2e flow is:

  1. COPY load A, B, and A_TO_B from Parquet.
  2. Confirm count(r) = 953.
  3. Confirm survivor node_3379 -> node_3382 at relationship offset 0 projects REL_A in both scan directions.
  4. Delete relationship offset(ID(r)) = 952.
  5. Confirm the survivor still projects REL_A before reload.
  6. Run -RELOADDB.
  7. Confirm count(r) = 952.
  8. Confirm the survivor still projects REL_A in both scan directions.

On lbug v0.17.1, the survivor's forward projection changes after reload:

count_before,953
forward_before,0,REL_A
backward_before,0,REL_A
forward_after_delete,0,REL_A
backward_after_delete,0,REL_A
count_after_reopen,952
forward_after_reopen,0,REL_B
backward_after_reopen,0,REL_A

Expected output:

count_before,953
forward_before,0,REL_A
backward_before,0,REL_A
forward_after_delete,0,REL_A
backward_after_delete,0,REL_A
count_after_reopen,952
forward_after_reopen,0,REL_A
backward_after_reopen,0,REL_A

The important details are:

  1. The delete succeeds. Relationship count drops from 953 to 952.
  2. The watched relationship is not the deleted row.
  3. The watched relationship still projects the correct value before reload.
  4. The incorrect value appears after persisted state is reloaded.
  5. The same relationship can disagree by scan direction after reload.

This points at persisted string property state for a relationship table and can silently change the meaning of relationship properties on surviving rows.

In the reduced fixture the values are neutral (REL_A, REL_B, REL_C), but the original failure was found because a relationship type property controlled graph semantics. After deleting an unrelated relationship and reopening the database, surviving relationship IDs with stable endpoints could project a different type value depending on access path. That made higher-level graph invariants false even though no new relationship IDs appeared and no survivor endpoints changed.

The failure mode is worse than a failed delete because it is silent data corruption at the query-visible property layer:

  • the target relationship is removed as expected;
  • surviving relationship IDs remain present;
  • endpoints remain stable;
  • only the string property projection changes after checkpoint/reload.

Minimal e2e repro test

A proposed native e2e test file:

test/test_files/dictionary_bug/orb383_relationship_projection_obfuscated.test

A proposed fixture directory:

test/test_files/dictionary_bug/orb383_relationship_projection_obfuscated_fixture/
  A.parquet
  B.parquet
  A_TO_B.parquet
  README.md

The exact PR fixture uses the native e2e runner format with -SKIP_IN_MEM, -CASE, -STATEMENT, and ${LBUG_ROOT_DIRECTORY} fixture paths. The abridged logical flow is:

-CLEAN_DATABASE
-DATASET PARQUET empty

CREATE NODE TABLE A (id INT64, key STRING, PRIMARY KEY(id));
CREATE NODE TABLE B (id INT64, key STRING, PRIMARY KEY(id));
CREATE REL TABLE A_TO_B (FROM A TO B, type STRING, MANY_MANY);

COPY A (id, key) FROM "test/test_files/dictionary_bug/orb383_relationship_projection_obfuscated_fixture/A.parquet";
COPY B (id, key) FROM "test/test_files/dictionary_bug/orb383_relationship_projection_obfuscated_fixture/B.parquet";
COPY A_TO_B (type) FROM "test/test_files/dictionary_bug/orb383_relationship_projection_obfuscated_fixture/A_TO_B.parquet";

MATCH ()-[r:A_TO_B]->() RETURN 'count_before', count(r);
----
count_before|953

MATCH (a:A {key: 'node_3379'})-[r:A_TO_B]->(b:B {key: 'node_3382'})
RETURN 'forward_before', offset(ID(r)), r.type;
----
forward_before|0|REL_A

MATCH (b:B {key: 'node_3382'})<-[r:A_TO_B]-(a:A {key: 'node_3379'})
RETURN 'backward_before', offset(ID(r)), r.type;
----
backward_before|0|REL_A

MATCH ()-[r:A_TO_B]->() WHERE offset(ID(r)) = 952 DELETE r;
----

MATCH (a:A {key: 'node_3379'})-[r:A_TO_B]->(b:B {key: 'node_3382'})
RETURN 'forward_after_delete', offset(ID(r)), r.type;
----
forward_after_delete|0|REL_A

MATCH (b:B {key: 'node_3382'})<-[r:A_TO_B]-(a:A {key: 'node_3379'})
RETURN 'backward_after_delete', offset(ID(r)), r.type;
----
backward_after_delete|0|REL_A

-RELOADDB

MATCH ()-[r:A_TO_B]->() RETURN 'count_after_reopen', count(r);
----
count_after_reopen|952

MATCH (a:A {key: 'node_3379'})-[r:A_TO_B]->(b:B {key: 'node_3382'})
RETURN 'forward_after_reopen', offset(ID(r)), r.type;
----
forward_after_reopen|0|REL_A

MATCH (b:B {key: 'node_3382'})<-[r:A_TO_B]-(a:A {key: 'node_3379'})
RETURN 'backward_after_reopen', offset(ID(r)), r.type;
----
backward_after_reopen|0|REL_A

On released lbug v0.17.1 and unpatched builds before the attached fix, the forward_after_reopen assertion fails because it returns:

forward_after_reopen|0|REL_B

Manual repro shape

The same repro can be run manually in two phases.

Run these commands from the repository root, or replace the fixture paths with absolute paths.

Setup/delete phase:

CREATE NODE TABLE A (id INT64, key STRING, PRIMARY KEY(id));
CREATE NODE TABLE B (id INT64, key STRING, PRIMARY KEY(id));
CREATE REL TABLE A_TO_B (FROM A TO B, type STRING, MANY_MANY);

COPY A (id, key) FROM "test/test_files/dictionary_bug/orb383_relationship_projection_obfuscated_fixture/A.parquet";
COPY B (id, key) FROM "test/test_files/dictionary_bug/orb383_relationship_projection_obfuscated_fixture/B.parquet";
COPY A_TO_B (type) FROM "test/test_files/dictionary_bug/orb383_relationship_projection_obfuscated_fixture/A_TO_B.parquet";

MATCH ()-[r:A_TO_B]->() RETURN 'count_before', count(r);
MATCH (a:A {key: 'node_3379'})-[r:A_TO_B]->(b:B {key: 'node_3382'})
RETURN 'forward_before', offset(ID(r)), r.type;
MATCH (b:B {key: 'node_3382'})<-[r:A_TO_B]-(a:A {key: 'node_3379'})
RETURN 'backward_before', offset(ID(r)), r.type;

MATCH ()-[r:A_TO_B]->() WHERE offset(ID(r)) = 952 DELETE r;

MATCH (a:A {key: 'node_3379'})-[r:A_TO_B]->(b:B {key: 'node_3382'})
RETURN 'forward_after_delete', offset(ID(r)), r.type;
MATCH (b:B {key: 'node_3382'})<-[r:A_TO_B]-(a:A {key: 'node_3379'})
RETURN 'backward_after_delete', offset(ID(r)), r.type;

Then close and reopen the database.

Reopen phase:

MATCH ()-[r:A_TO_B]->() RETURN 'count_after_reopen', count(r);
MATCH (a:A {key: 'node_3379'})-[r:A_TO_B]->(b:B {key: 'node_3382'})
RETURN 'forward_after_reopen', offset(ID(r)), r.type;
MATCH (b:B {key: 'node_3382'})<-[r:A_TO_B]-(a:A {key: 'node_3379'})
RETURN 'backward_after_reopen', offset(ID(r)), r.type;

Current result:

count_after_reopen,952
forward_after_reopen,0,REL_B
backward_after_reopen,0,REL_A

Expected result:

count_after_reopen,952
forward_after_reopen,0,REL_A
backward_after_reopen,0,REL_A

Diagnostic evidence from reduction

The repro was narrowed through relationship-ID diffs and direct DB open/reopen checks.

For the original internal dataset before obfuscation, a delete of one known trigger relationship showed this pattern:

same connection immediately after delete:
  target deleted:      yes
  new relationship IDs: 0
  survivor endpoint changes: 0
  survivor type changes: 0

second connection before close:
  target deleted:      yes
  new relationship IDs: 0
  survivor endpoint changes: 0
  survivor type changes: 0

after close/reopen:
  target deleted:      yes
  new relationship IDs: 0
  survivor endpoint changes: 0
  survivor type changes: > 0

The important conclusion was that the bad post-reload state was not relationship insertion and not endpoint corruption. The target relationship IDs were deleted. No new IDs appeared. Surviving endpoints remained stable. The drift was in projected string property values for surviving relationship IDs.

Manual CHECKPOINT was not a workaround. It could make the bad persisted state visible earlier to another connection, which further points at checkpoint/reload/persistence of relationship property chunks rather than the delete predicate itself.

Synthetic graphs created only through Cypher CREATE did not reproduce the issue, even at similar relationship counts. That is why the attached e2e uses Parquet and preserves row order and string value distribution.

Where the root cause appears to be

The root cause appears to be the partial string scan path into StringChunkData.

The current implementation mixes two coordinate systems:

  1. result row positions in the StringChunkData index chunk;
  2. dictionary slots in the destination StringChunkData dictionary.

This becomes visible when a dirty relationship property segment is checkpointed after a relationship delete. Checkpointing needs to copy surviving values from an existing string column chunk into a new StringChunkData chunk. For a partial segment, the implementation tries to materialize only the needed source dictionary entries.

Current code path that goes wrong

The snippets below are abridged to show the relevant contract mismatch.

1. Partial StringColumn chunk scan assigns provisional dictionary slots

In src/storage/table/string_column.cpp, the partial branch of StringColumn::scanSegment(const SegmentState&, ColumnChunkData*, offset_t, row_idx_t) scans the index child, deduplicates source dictionary indexes, writes provisional destination dictionary indexes into the result index chunk, and then asks DictionaryColumn to scan the selected dictionary values.

auto startOffsetInResult = resultChunk->getNumValues();
Column::scanSegment(state, resultChunk, startOffsetInSegment, numValuesToScan);

auto* stringResultChunk = dynamic_cast_checked<StringChunkData*>(resultChunk);
stringResultChunk->getIndexColumnChunk()->setNumValues(startOffsetInResult);

auto* indexChunk = stringResultChunk->getIndexColumnChunk();
indexColumn->scanSegment(getChildState(state, ChildStateIndex::INDEX), indexChunk,
    startOffsetInSegment, numValuesToScan);

const auto initialDictSize =
    stringResultChunk->getDictionaryChunk().getOffsetChunk()->getNumValues();

if (numValuesToScan == state.metadata.numValues) {
    // full segment path omitted
} else {
    std::unordered_map<string_index_t, uint64_t> indexMap;
    std::vector<std::pair<string_index_t, uint64_t>> offsetsToScan;
    for (auto i = 0u; i < numValuesToScan; i++) {
        if (!resultChunk->isNull(startOffsetInResult + i)) {
            auto index = indexChunk->getValue<string_index_t>(startOffsetInResult + i);
            auto element = indexMap.find(index);
            if (element == indexMap.end()) {
                indexMap.insert(std::make_pair(index, initialDictSize + offsetsToScan.size()));
                indexChunk->setValue<string_index_t>(initialDictSize + offsetsToScan.size(),
                    startOffsetInResult + i);
                offsetsToScan.emplace_back(index, initialDictSize + offsetsToScan.size());
            } else {
                indexChunk->setValue<string_index_t>(element->second, startOffsetInResult + i);
            }
        }
    }

    if (offsetsToScan.size() == 0) {
        return;
    }
    dictionary.scan(getChildState(state, ChildStateIndex::OFFSET),
        getChildState(state, ChildStateIndex::DATA), offsetsToScan, stringResultChunk,
        getChildState(state, ChildStateIndex::INDEX).metadata);
}

For this caller, the second element of each pair is a destination dictionary slot:

offsetsToScan.emplace_back(index, initialDictSize + offsetsToScan.size());

It is not a result row position.

2. DictionaryColumn::scan uses the second pair value as an output position

In src/storage/table/dictionary_column.cpp, DictionaryColumn::scan(...) is shared by callers that scan selected dictionary entries into a result.

template<typename Result>
void DictionaryColumn::scan(const SegmentState& offsetState, const SegmentState& dataState,
    std::vector<std::pair<string_index_t, uint64_t>>& offsetsToScan, Result* result,
    const ColumnChunkMetadata& indexMeta) const {
    string_index_t firstOffsetToScan = 0, lastOffsetToScan = 0;
    auto comp = [](auto pair1, auto pair2) { return pair1.first < pair2.first; };
    auto duplicationFactor = (double)offsetState.metadata.numValues / indexMeta.numValues;
    if (duplicationFactor <= 0.5) {
        std::sort(offsetsToScan.begin(), offsetsToScan.end(), comp);
        firstOffsetToScan = offsetsToScan.front().first;
        lastOffsetToScan = offsetsToScan.back().first;
    } else {
        const auto& [min, max] =
            std::minmax_element(offsetsToScan.begin(), offsetsToScan.end(), comp);
        firstOffsetToScan = min->first;
        lastOffsetToScan = max->first;
    }

    auto numOffsetsToScan = lastOffsetToScan - firstOffsetToScan + 1;
    std::vector<string_offset_t> offsets(numOffsetsToScan + 1);
    scanOffsets(offsetState, offsets.data(), firstOffsetToScan, numOffsetsToScan,
        dataState.metadata.numValues);

    for (auto pos = 0u; pos < offsetsToScan.size(); pos++) {
        auto startOffset = offsets[offsetsToScan[pos].first - firstOffsetToScan];
        auto endOffset = offsets[offsetsToScan[pos].first - firstOffsetToScan + 1];
        auto lengthToScan = endOffset - startOffset;
        scanValue(dataState, startOffset, lengthToScan, result, offsetsToScan[pos].second);

        if constexpr (std::same_as<Result, ValueVector>) {
            auto& scannedString = result->template getValue<string_t>(offsetsToScan[pos].second);
            while (pos + 1 < offsetsToScan.size() &&
                   offsetsToScan[pos + 1].first == offsetsToScan[pos].first) {
                pos++;
                result->template setValue<string_t>(offsetsToScan[pos].second, scannedString);
            }
        } else {
            DASSERT(pos == offsetsToScan.size() - 1 ||
                    offsetsToScan[pos].first != offsetsToScan[pos + 1].first);
        }
    }
}

This contract is correct for ValueVector callers. For those callers, offsetsToScan.second is an output vector position. Sorting by source dictionary index is safe because the output vector position travels with the selected old dictionary index.

It is not correct for the partial StringChunkData caller above, where offsetsToScan.second is a provisional destination dictionary slot.

3. scanValue(StringChunkData*) writes to the index chunk at offsetInResult

In src/storage/table/dictionary_column.cpp, the StringChunkData overload appends one materialized string to the destination dictionary, then writes the destination row/index chunk at offsetInResult.

Abridged shape:

void DictionaryColumn::scanValue(const SegmentState& dataState, uint64_t startOffset,
    uint64_t length, StringChunkData* result, uint64_t offsetInResult) const {
    auto& stringDataChunk = *result->getDictionaryChunk().getStringDataChunk();
    auto& offsetChunk = *result->getDictionaryChunk().getOffsetChunk();
    auto& indexChunk = *result->getIndexColumnChunk();

    if (stringDataChunk.getCapacity() < stringDataChunk.getNumValues() + length) {
        stringDataChunk.resize(std::bit_ceil(stringDataChunk.getNumValues() + length));
    }
    if (offsetChunk.getNumValues() == offsetChunk.getCapacity()) {
        offsetChunk.resize(std::bit_ceil(offsetChunk.getNumValues() + 1));
    }
    if (offsetInResult >= indexChunk.getCapacity()) {
        indexChunk.resize(std::bit_ceil(offsetInResult + 1));
    }

    dataColumn->scanSegment(dataState, startOffset, length,
        stringDataChunk.getData<uint8_t>() + stringDataChunk.getNumValues());
    indexChunk.setValue<string_index_t>(offsetChunk.getNumValues(), offsetInResult);
    offsetChunk.setValue<string_offset_t>(stringDataChunk.getNumValues(),
        offsetChunk.getNumValues());
    stringDataChunk.setNumValues(stringDataChunk.getNumValues() + length);
}

The critical line is:

indexChunk.setValue<string_index_t>(offsetChunk.getNumValues(), offsetInResult);

That treats offsetInResult as a row/index-chunk position.

But the partial StringColumn caller passed a provisional dictionary slot.

So the current path has this mismatch:

StringColumn partial chunk scan: offsetsToScan.second = destination dictionary slot
DictionaryColumn StringChunkData scan: offsetsToScan.second = result row position

Failure sequence in simplified terms

Suppose the source dictionary is:

old index 0 -> REL_A
old index 1 -> REL_B

Suppose the partial scan needs these result rows:

row 0 reads old index 1  # REL_B
row 1 reads old index 1  # REL_B duplicate
row 2 reads old index 0  # REL_A

StringColumn first assigns provisional destination dictionary indexes:

row 0 -> provisional new index 0  # first old index 1
row 1 -> provisional new index 0  # duplicate old index 1
row 2 -> provisional new index 1  # first old index 0

offsetsToScan:
  (old index 1, provisional slot 0)
  (old index 0, provisional slot 1)

If DictionaryColumn::scan sorts by old dictionary index, it materializes in this order:

(old index 0, provisional slot 1)  # REL_A first
(old index 1, provisional slot 0)  # REL_B second

Then scanValue(StringChunkData*) treats the provisional slot as a row position:

append REL_A as actual new dictionary index 0
write indexChunk[1] = 0

append REL_B as actual new dictionary index 1
write indexChunk[0] = 1

The final destination dictionary is:

new index 0 -> REL_A
new index 1 -> REL_B

But the row index chunk can now be:

row 0 -> new index 1 -> REL_B  # correct
row 1 -> new index 0 -> REL_A  # wrong; row 1 should be REL_B
row 2 -> new index 1 -> REL_B  # wrong; row 2 should be REL_A

Sorting is not the only problem. Even if materialization happens in encounter order, duplicate rows can still be overwritten because scanValue(StringChunkData*) writes only one row position per unique dictionary entry while the caller has already assigned duplicate result rows.

Encounter-order example:

offsetsToScan:
  (old index 1, provisional slot 0)
  (old index 0, provisional slot 1)

scanValue(StringChunkData*) does:

append REL_B as actual new dictionary index 0
write indexChunk[0] = 0

append REL_A as actual new dictionary index 1
write indexChunk[1] = 1

That overwrites row 1, which was a duplicate of row 0:

row 0 -> REL_B  # correct
row 1 -> REL_A  # wrong; duplicate row should still be REL_B
row 2 -> REL_A  # correct

So the root bug is that dictionary materialization and row-index assignment are split across two components that disagree about what the coordinate means.

The ValueVector path uses the same high-level dictionary scan helper, but for ValueVector the second pair element is a true output vector position.

For example:

offsetsToScan.second = output vector position

If DictionaryColumn::scan sorts selected dictionary offsets, the output vector position remains attached to the old dictionary index. scanValue(..., ValueVector*, offsetInVector) writes the concrete string value directly into that vector position. Duplicate strings can then be copied to additional vector positions.

StringChunkData is different because it has two layers:

  1. an index chunk mapping rows to dictionary entries;
  2. a dictionary chunk storing offsets and bytes.

The current StringChunkData path lets both StringColumn and DictionaryColumn mutate the index chunk while disagreeing about whether a number means row position or dictionary slot.

Why full-segment scans are less exposed

The full-segment StringColumn chunk scan path does not build the same selected-dictionary list.

Instead, it shifts every source index by the existing destination dictionary size, then appends the full source dictionary:

for (row_idx_t i = 0; i < numValuesToScan; i++) {
    indexChunk->setValue<string_index_t>(
        indexChunk->getValue<string_index_t>(startOffsetInResult + i) + initialDictSize,
        startOffsetInResult + i);
}
dictionary.scan(state, stringResultChunk->getDictionaryChunk());

That preserves the source dictionary layout. It does not need to materialize a subset of dictionary entries and map old dictionary indexes to new dictionary indexes.

The problematic branch is the partial branch, which is exactly the kind of branch used when checkpointing a dirty segment after a relationship delete.

Focused storage-level repro

The e2e repro proves the end-user visible failure, but the storage-level bug can be tested directly with a generic string-column contract test.

The key invariant is:

StringColumn scan to ValueVector == StringColumn scan to StringChunkData by row value

Test file:

test/storage/string_chunk_scan_test.cpp

It should create dictionary-backed string chunks, scan ranges into both result types, decode the resulting StringChunkData, and compare row values.

Useful cases:

  • duplicate first occurrence before the partial range;
  • dictionary order differing from row encounter order;
  • unique values in partial ranges;
  • all values duplicate;
  • duplicate values separated by nulls;
  • all-null ranges;
  • empty strings with duplicates;
  • full-segment fast path;
  • appending into a non-empty StringChunkData result;
  • explicit index bounds and repeated-value index equality;
  • JSON logical type over the same string storage path;
  • preservation of ValueVector sorted-offset duplicate reuse behavior.

Currently, partial StringChunkData scans can disagree with ValueVector scans. After correcting the scan contract, the focused tests pass.

Are there known steps to reproduce?

The recommended repro is the native e2e fixture described above.

Proposed files:

test/test_files/dictionary_bug/orb383_relationship_projection_obfuscated.test
test/test_files/dictionary_bug/orb383_relationship_projection_obfuscated_fixture/A.parquet
test/test_files/dictionary_bug/orb383_relationship_projection_obfuscated_fixture/B.parquet
test/test_files/dictionary_bug/orb383_relationship_projection_obfuscated_fixture/A_TO_B.parquet

Run:

E2E_TEST_FILES_DIRECTORY=test/test_files \
  build/<build-dir>/test/runner/e2e_test \
  dictionary_bug/orb383_relationship_projection_obfuscated.test \
  --gtest_filter='dictionary_bug~orb383_relationship_projection_obfuscated.AnonymousParquetDeleteReload' \
  --gtest_color=no

Expected on current builds: the e2e fails because forward_after_reopen returns 0|REL_B instead of 0|REL_A.

Expected after the partial StringChunkData scan contract is corrected: the e2e passes.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions