[MOD-9694] Trie prefixes iterator by LukeMathWalker · Pull Request #6119 · RediSearch/RediSearch

LukeMathWalker · 2025-05-12T09:31:17Z

Describe the changes in the pull request

Introduce a new iterator that returns all of the prefixes of a given term, PrefixesIter.
It's equivalent to FindPrefixes in deps/triemap.h.

The test module has been broken down into iterator-specific modules. New tests are under tests/trie/iter/prefixes.rs. All the other test files are just chunks of the old tests/trie/iter.rs file.

Mark if applicable

This PR introduces API changes
This PR introduces serialization changes

codecov · 2025-05-12T10:16:16Z

Codecov Report

Attention: Patch coverage is 86.20690% with 8 lines in your changes missing coverage. Please review.

Project coverage is 87.30%. Comparing base (7177e72) to head (cbcccba).
Report is 3 commits behind head on master.

Files with missing lines	Patch %	Lines
src/util/arr/arr.c	66.66%	5 Missing ⚠️
src/util/arr/arr.h	90.00%	2 Missing ⚠️
src/redisearch_rs/trie_rs/src/iter/prefixes.rs	94.73%	1 Missing ⚠️

Additional details and impacted files

@@            Coverage Diff             @@
##           master    #6119      +/-   ##
==========================================
- Coverage   87.33%   87.30%   -0.04%     
==========================================
  Files         217      218       +1     
  Lines       38197    38219      +22     
  Branches     2145     2167      +22     
==========================================
+ Hits        33361    33367       +6     
- Misses       4821     4837      +16     
  Partials       15       15

Flag	Coverage Δ
flow	`82.61% <80.00%> (-0.17%)`	⬇️
unit	`43.23% <86.20%> (+0.03%)`	⬆️

Flags with carried forward coverage won't be shown. Click here to find out more.

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

LukeMathWalker · 2025-05-12T11:52:45Z

src/redisearch_rs/trie_bencher/src/bencher.rs

+    let map = c_load_from_terms(terms);
+    c.bench_function("C", |b| {
+        // We are leaking memory here, since we don't free the pointer to the result array.
+        b.iter_with_large_drop(|| map.find_prefixes(view).unwrap())


This can be fixed by moving util/arr.* to a subfolder, adding a CMakeLists.txt file, build it as a standalone static library, binding it to Rust and then calling array_free here.

It feels like a lot of changes for benching code that will be deleted once we swap the impl, but open to making them if you think it's worthwhile. cc @raz-mon @JoanFM

I noticed that our CI has been a little flaky lately, I wonder if leaving this out would contribute to making this worse.

Done in 9517ea3

Found a simpler way in e5cfc7a to avoid touching as many C files.

LukeMathWalker · 2025-05-12T11:58:12Z

In benches, the Rust version seems to be ~2x slower than the C one:

Wiki-1K|Find prefixes/Rust
                        time:   [67.442 ns 67.909 ns 68.336 ns]
                        change: [+0.0972% +1.3121% +2.5008%] (p = 0.03 < 0.05)
                        Change within noise threshold.
Wiki-1K|Find prefixes/C time:   [30.078 ns 30.588 ns 31.237 ns]
                        change: [-0.7652% +2.4754% +5.8325%] (p = 0.15 > 0.05)
                        No change in performance detected.

Investigating 🧐

LukeMathWalker · 2025-05-12T12:30:05Z

The C version was only returning values, ignoring the keys.
I've modified the Rust version to match its behaviour and now benches are where we like them to be:

Wiki-1K|Find prefixes/Rust: [21.289 ns 21.407 ns 21.526 ns]
Wiki-1K|Find prefixes/C:    [32.131 ns 34.159 ns 37.129 ns]

JoanFM · 2025-05-12T12:43:19Z

src/redisearch_rs/trie_bencher/src/bencher.rs

+    let map = c_load_from_terms(terms);
+    c.bench_function("C", |b| {
+        // We are leaking memory here, since we don't free the pointer to the result array.
+        b.iter_with_large_drop(|| map.find_prefixes(view).unwrap())


I noticed that our CI has been a little flaky lately, I wonder if leaving this out would contribute to making this worse.

JoanFM · 2025-05-12T13:12:51Z

src/redisearch_rs/trie_rs/tests/integration/iter/prefixes.rs

+#[test]
+fn non_empty_prefixes() {
+    let mut trie = TrieMap::new();
+    trie.insert(b"apple", b"apple".to_vec());


for readability of the goal, I would maybe have a different value than the key? Something like "apple-value" or sthg like this?

It would make it more clear to see if keyor value is extracted?

There is no room (in general) for key/value confusion, thanks to the type definition used in prefixes_iter.
I used the same string for both key and value to improve the readability of assertions. Looking at

assert_eq!(prefixes(&trie, b"apples"), vec![b"apple"]);

you can immediately confirm that, yes, apple is a prefix of apples.
If we change to add a suffix

assert_eq!(prefixes(&trie, b"apples"), vec![b"apple-v"]);

it becomes a bit more confusing in my opinion.

Yes yes I know is clear, but IMO is more straightforward to clarify with the value. But I guess there is already a pattern on other tests so it's okey

github-actions · 2025-05-12T17:50:07Z