Skip to content

Cursor paging with no where clause (orderBy only) still drops documents from sibling branches at protocol 14; the proof verifies the short page #5273

Open

Description

@PastaPastaPasta

At protocol 14 (5.0.0-beta.1), a document query with no where clause, ordered by a multi-property index and paged with startAt / startAfter, still drops documents from the branches after the cursor's: any document whose lower-level value sorts before the cursor's is skipped. The proved path returns and verifies the same short page. #4396 fixed this family of bugs for an in or range clause with left-over properties, and its description lists this shape as not covered ("the no-where-clause path (orderBy-only with a cursor and leftover properties)"). We could not find an issue tracking it.

We hit this building Dash Forge, a git forge that runs on Platform.

Expected Behavior

For an index [a, b] and orderBy [[a, asc], [b, asc]] with no where clause, startAfter a document (a=1, b=5) returns every document after it in index order: the rest of the a=1 branch, then all of a=2.

Current Behavior

The document (2, 3) is missing: in branches after the cursor's, the cursor's b acts as a lower bound. The page comes back short, which a pager reads as the end of the data. With the proof, the page verifies.

From an rs-drive test at tag v5.0.0-beta.1 (fixture: a in {1, 2}, b in {3, 5, 7}, one document each, non-unique index [a asc, b asc]):

PROBE ordering-only [a,b] orderBy a asc, b asc: prove=false startAfter cursor=[1, 5, 0]
  got  [[1, 7, 0], [2, 5, 0], [2, 7, 0]]
  want [[1, 7, 0], [2, 3, 0], [2, 5, 0], [2, 7, 0]]
  missing [[2, 3, 0]] extra []
PROBE ordering-only [a,b] orderBy a asc, b asc: prove=false startAfter cursor=[1, 7, 0]
  got  [[2, 7, 0]]
  want [[2, 3, 0], [2, 5, 0], [2, 7, 0]]
  missing [[2, 3, 0], [2, 5, 0]] extra []
PROBE ordering-only [a,b] orderBy a asc, b asc: prove=true startAfter cursor=[1, 5, 0]
  got  [[1, 7, 0], [2, 5, 0], [2, 7, 0]]
  want [[1, 7, 0], [2, 3, 0], [2, 5, 0], [2, 7, 0]]
  missing [[2, 3, 0]] extra []
PROBE ordering-only [a,b] orderBy a asc, b asc: 8 of 24 cursor cases mismatched

Each probe tries every document as a startAt and a startAfter cursor, with and without proof, against an independently sorted list:

Query (index [a, b] unless noted) Mismatched cursor cases
no where, orderBy a asc, b asc 8 of 24
no where, orderBy a desc, b desc 8 of 24 (mirror image: (1, 7) dropped after a cursor at (2, 5))
no where, orderBy a asc only 8 of 24
no where, index [a, b, c], orderBy a, b, c asc 28 of 64
a in [1, 2] AND b > 0, orderBy a asc, b asc 0 of 24
a > 0 (left-over b), orderBy a asc, b asc (the shape #4396 fixed) 0 of 24

The other follow-up #4396 listed, in plus a range with a cursor, passes on [a, b]; #4726 appears to have fixed it. (With a left-over third property, a in [..] AND b > 0 on [a, b, c] is refused as having no valid index, so we could not probe that variant.)

Where it comes from (our reading). In the protocol 14 lowering, the sibling-aware cursor construction #4396 added is used only when there is a last where clause (single_in_path_query/v0 L529-L535). With no where clause the query is built by recursive_create_query_ordered (L492-L514, L57-L113). Its first level starts at the cursor's a, and recursive_insert_on_query_ordered_with_cursor then builds the next level to start from the cursor's b and sets it as the default subquery (L177-L231). The default subquery applies to every a branch, not just the cursor's. That is the construction #4396 describes as the cause.

The v5.0-dev branch has no commits under packages/rs-drive/src/query since the tag.

Possible Solution

Apply #4396's construction to the no-where-clause path: start the first level at the cursor's branch, give the default subquery no cursor bound (insert_all, direction from orderBy), and refine only the cursor's own branch with a conditional subquery at its key. It may be simplest to treat the first index property as an unbounded range "last clause" so this shape goes through the existing sibling-aware path. A property test like the probe below, comparing every cursor against a full sorted read for each supported shape, would catch the next member of this family.

Steps to Reproduce (for bugs)

  1. Check out v5.0.0-beta.1.
  2. Append the code below to packages/rs-drive/tests/compound_cursor_tests.rs. It reuses that file's setup_left_over_fixture, left_over_oracle_rows, left_over_expected_page and left_over_page helpers.
  3. Run cargo test -p drive --test compound_cursor_tests probe_ -- --nocapture --test-threads=1.
  4. probe_ordering_only_two_levels fails with 8 of 24 mismatches. probe_in_and_range_two_levels and probe_control_range_with_left_over_property pass.
Probe code
fn probe_all_cursors(
    name: &str,
    fixture: &LeftOverFixture,
    where_clauses: serde_json::Value,
    order_by: serde_json::Value,
    filter: impl Fn(&[u8; 3]) -> bool,
    order: &[(usize, bool)],
) -> usize {
    let full = left_over_oracle_rows(fixture, |_| true, order);
    let matching = left_over_oracle(fixture, &filter, order);
    let value_of = |id: &Identifier| full.iter().find(|(_, i)| i == id).unwrap().0;
    let mut failures = 0;
    let mut cases = 0;
    for prove in [false, true] {
        for (position, (cursor_values, id)) in full.iter().enumerate() {
            for included in [true, false] {
                cases += 1;
                let expected = left_over_expected_page(&full, &matching, position, included);
                let got = left_over_page(
                    fixture,
                    where_clauses.clone(),
                    order_by.clone(),
                    100,
                    Some((*id, included)),
                    prove,
                );
                if got != expected {
                    failures += 1;
                    if failures <= 6 {
                        let got_v: Vec<[u8; 3]> = got.iter().map(value_of).collect();
                        let want_v: Vec<[u8; 3]> = expected.iter().map(value_of).collect();
                        let missing: Vec<[u8; 3]> = expected
                            .iter()
                            .filter(|i| !got.contains(i))
                            .map(value_of)
                            .collect();
                        let extra: Vec<[u8; 3]> = got
                            .iter()
                            .filter(|i| !expected.contains(i))
                            .map(value_of)
                            .collect();
                        eprintln!(
                            "PROBE {name}: prove={prove} {} cursor={cursor_values:?}\n  got  {got_v:?}\n  want {want_v:?}\n  missing {missing:?} extra {extra:?}",
                            if included { "startAt" } else { "startAfter" }
                        );
                    }
                }
            }
        }
    }
    eprintln!("PROBE {name}: {failures} of {cases} cursor cases mismatched");
    failures
}

fn two_level_rows() -> Vec<[u8; 3]> {
    [1u8, 2]
        .iter()
        .flat_map(|a| [3u8, 5, 7].iter().map(move |b| [*a, *b, 0]))
        .collect()
}

#[test]
fn probe_ordering_only_two_levels() {
    let fixture = setup_left_over_fixture(&[("a", "asc"), ("b", "asc")], false, &two_level_rows());
    let failures = probe_all_cursors(
        "ordering-only [a,b] orderBy a asc, b asc",
        &fixture,
        json!([]),
        json!([["a", "asc"], ["b", "asc"]]),
        |_| true,
        &[(0, true), (1, true)],
    );
    assert_eq!(failures, 0);
}

#[test]
fn probe_in_and_range_two_levels() {
    let fixture = setup_left_over_fixture(&[("a", "asc"), ("b", "asc")], false, &two_level_rows());
    let failures = probe_all_cursors(
        "a in [1,2] and b > 0 on [a,b], orderBy a asc, b asc",
        &fixture,
        json!([["a", "in", [1, 2]], ["b", ">", 0]]),
        json!([["a", "asc"], ["b", "asc"]]),
        |_| true,
        &[(0, true), (1, true)],
    );
    assert_eq!(failures, 0);
}

#[test]
fn probe_control_range_with_left_over_property() {
    // The shape #4396 fixed: a single range clause with a left-over property.
    let fixture = setup_left_over_fixture(&[("a", "asc"), ("b", "asc")], false, &two_level_rows());
    let failures = probe_all_cursors(
        "control: a > 0, left-over b, orderBy a asc, b asc",
        &fixture,
        json!([["a", ">", 0]]),
        json!([["a", "asc"], ["b", "asc"]]),
        |_| true,
        &[(0, true), (1, true)],
    );
    assert_eq!(failures, 0);
}

Context

Your Environment

  • Version used: Platform v5.0.0-beta.1 (protocol 14, PlatformVersion::latest()), rs-drive integration test.
  • Environment name and version: Rust 1.98.1.
  • Operating System and version: macOS.
  • Link to your project: https://github.com/PastaPastaPasta/dash-forge

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions