RMQ forward scan build

[Malkovsky]

Currently FNBP cartesian tree used in the RMQ is built using a backward scan, this might create problems in the future. We'd like to support a build from a forward scan.

Possible solutions

• Add a "reverse" parameter to the template, meaning that all the buildup is done in reverse, with the backward scan becomes forward scan
• Change FNBP convention from ( left subtree ) right subtree to left subtree (right subtree). This will also allow us to buildup with forward scan

Both approaches break the leftmost tie-breaking, note specific tie-breaking is required by FNBP. The first variant simply reverses from leftmost min tie-breaking to rightmost, for the second variant additional excess primitives are probably required. Whether leftmost tie-breaking can be preserved with forward scan is not clear.

[Malkovsky]

@codex please review and give your suggestions

[chatgpt-codex-connector]

To use Codex here, create an environment for this repo.

[Malkovsky]

@codex please review and give your suggestions

[chatgpt-codex-connector]

Review Summary

I reviewed the RMQ-related changes currently on the branch and did not make any code changes, so I did not commit or create a follow-up PR.

Main Suggestions

1. Clarify whether this PR actually implements “forward scan build”

The PR title/body says the goal is an “RMQ forward scan build,” but both Cartesian builders still construct BP bits with a right-to-left loop:

• CartesianHybridBTree::build_bp_bits() still uses for (std::size_t i = values_.size(); i-- > 0;).
• CartesianRmM::build_bp_bits() uses the same right-to-left scan pattern.

The refactor removes prepend_bp_bit() and inlines a prepend_open lambda, which is fine as a micro-cleanup, but it does not appear to change the build direction.

Suggestion: Either:

• rename / reword the PR to describe the actual change, or
• add the forward-scan implementation in this PR, with explicit tests showing the expected Cartesian BP shape and RMQ tie behavior.

---

2. Make tie-breaking semantics explicit before changing scan direction

The current implementation documents stable Cartesian-tree construction and first-minimum behavior. The local selector documentation says equal minima stay stable through the same right-to-left construction rule used by the value Cartesian tree.

The value-level CartesianHybridBTree documentation also says it preserves a stable Cartesian-tree shape.

That matters because a forward construction can easily flip equal-value handling from first-minimum to last-minimum unless the stack condition and BP convention are changed carefully.

Suggestion: Before landing a forward scan, add a small design note or comments documenting:

• the exact duplicate-value rule,
• whether public RMQ must return the leftmost minimum,
• how the chosen BP convention preserves that rule,
• whether CartesianRmM, CartesianHybridBTree, and the new CartesianBTree alias all agree.

---

3. Add targeted duplicate-value tests for the Cartesian-specific backends

The generic value RMQ typed tests now include CartesianBTreeCase, which is good.

However, for this particular PR topic, I would add Cartesian-focused tests with repeated values and ranges that expose leftmost-vs-rightmost tie bugs. Suggested cases:

{5, 5, 5, 5}
{3, 1, 2, 1, 4}
{2, 1, 1, 1, 2}
{1, 2, 1, 2, 1}

For each backend:

• CartesianRmM
• CartesianHybridBTree
• CartesianBTree

verify that arg_min(left, right) returns the first minimum for half-open ranges. The current tests include the new backend in the shared suite, but I would still add a dedicated regression test because this PR’s core risk is tie-breaking under construction-order changes.

---

4. The same-leaf fast path looks reasonable, but deserves cross-chunk edge tests

The new leaf_range_arg_min_relative() avoids an absolute rank query for same-leaf depth RMQ ranges. It starts scanning at left_offset / 128, subtracts the prefix at the local left boundary for the first chunk, and then accumulates whole-chunk excesses for later chunks.

The added DepthBackendDirectPaths ranges improve coverage for same-leaf and intra-leaf paths.

Suggestion: Add a few more depth-backend cases that intentionally start and end around 128-bit chunk boundaries, for example:

• [127, 129)
• [128, 256)
• [129, 257)
• [255, 385)

That would directly stress the first_chunk, left_prefix, and chunk_base_excess logic.

---

5. Consider documenting CartesianBTree in the public API docs

The new alias is useful: it keeps the Cartesian BP encoding and BP-depth B-tree backend but disables the value-level top sparse overlay.

The benchmark overview already explains that CartesianBTree means CartesianHybridBTree without the value-level top sparse overlay.

Suggestion: If this alias is intended as a public backend and not just a benchmark probe, mention it wherever users discover RMQ backend choices. If it is meant only as a benchmark/reference variant, say that explicitly in the Doxygen comment.

---

Testing / Checks

• ⚠️ cmake -B build/review -DPIXIE_BENCHMARKS=OFF -DCMAKE_BUILD_TYPE=Release && cmake --build build/review -j2 && ./build/review/rmq_tests — blocked by environment/network limitation while FetchContent tried to clone GoogleTest and received CONNECT tunnel failed, response 403.

Commands Used

• pwd && find .. -name AGENTS.md -print && git status --short && git branch --show-current
• cat AGENTS.md && git log --oneline -5 && git status --short
• git diff HEAD~1..HEAD -- include/pixie/rmq/cartesian_hybrid_btree.h include/pixie/rmq/cartesian_rmm.h src/tests/rmq_tests.cpp
• rg -n "FNBP|RMQ|Cartesian|cartesian|forward|backward|scan|tie|leftmost" include src CMakeLists.txt
• nl -ba include/pixie/rmq/cartesian_hybrid_btree.h
• nl -ba include/pixie/rmq/cartesian_rmm.h
• nl -ba src/tests/rmq_tests.cpp
• nl -ba include/pixie/rmq.h
• cmake -B build/review -DPIXIE_BENCHMARKS=OFF -DCMAKE_BUILD_TYPE=Release && cmake --build build/review -j2 && ./build/review/rmq_tests

View task →