Repository navigation
Description
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)
- Check out
v5.0.0-beta.1. - Append the code below to
packages/rs-drive/tests/compound_cursor_tests.rs. It reuses that file'ssetup_left_over_fixture,left_over_oracle_rows,left_over_expected_pageandleft_over_pagehelpers. - Run
cargo test -p drive --test compound_cursor_tests probe_ -- --nocapture --test-threads=1. probe_ordering_only_two_levelsfails with 8 of 24 mismatches.probe_in_and_range_two_levelsandprobe_control_range_with_left_over_propertypass.
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
- Any app that pages a feed ordered by two index properties (for example "by category, then by time") without a filter loses documents. Nothing reports an error, and the proof verifies.
- Why we stopped using document cursors: on protocol 13 (before fix(drive)!: cursor pagination over multi-branch query levels dropped sibling-branch documents #4396), paging a two-property index with
startAfterreturned 197 of 229 rows for us. Since then Forge never pages a multi-branch index with a document cursor; it uses keyset ranges (property > last) or single-branch reads (refs.ts L14-L19). The probe above is how we checked whether 5.0.0-beta.1 lets us go back to cursors for this shape. - Related but different: SDK: paging past the end of a mixed-direction query fails proof verification ('upright op in a right-to-left walk'); desc ignored without a range clause #5244 (mixed-direction paging past the end fails verification, and
descignored without a range clause), Proof verification fails for document query using startAt without where/orderBy #3078 (startAtwith no where or orderBy fails verification).
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