OWASP / OWASP/Nest

Refactor: eliminate O(n²) fuzzy matching in owasp-update-leaders

Open
#5,351 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
451
Forks
707
Avg merge
22h 59m
Merged PRs (30d)
91

Description

**Is this feature/refactor request related to a problem? Please describe.**
`backend/src/apps/owasp/management/commands/owasp_update_leaders.py` runs in O(U × M): for every unmatched leader, `find_best_user_match` (`:108-166`) scans the entire `User` table twice (an exact-match pass then a fuzzy pass), calling the expensive `fuzz.token_sort_ratio` 2-3× per user. Profiled with 2,000 users × 50 members: **200,000 `token_sort_ratio` calls = 5.84s cumulative of a 7.45s profile (4.41s wall)**. At realistic scale (~10k users × ~100-300 unmatched leaders × 3 entity passes) this is ~7-10M calls ≈ **4-6 minutes of single-core CPU per run**.

**Describe the solution you'd like**
Precompute three lowercase lookup dicts once per run (by `login`, `name`, `email`) and resolve exact matches in O(1); only fall back to fuzzy matching for leaders with no exact hit, and prefilter fuzzy candidates to those sharing a first-letter/token index so `token_sort_ratio` runs on ~U/26 candidates instead of all users. Expected: O(U + M×k×F), results unchanged for the common exact-match path.

**Describe alternatives you've considered**
- A pure two-pass refactor (dicts only, no fuzzy prefilter) — full speedup on exact matches, preserves results 100%; the prefilter is the optional second step.
- `rapidfuzz.process.extractOne` with a scorer/limit — cleanest API but swaps in a new dependency and changes tie-breaking behavior.

**Are you going to work on implementing this?**

- [x] Yes
- [ ] No

**Additional context**
Refactor only — no behavioral change intended on the exact-match path. The fuzzy prefilter (edge case: matches across different first letters) should be verified against the current `--threshold` behavior. Locale estimate: ~30-45 lines in `owasp_update_leaders.py`.

Contributor guide

Open the contributing guide

Research direction

Read backend/src/apps/owasp/management/commands/owasp_update_leaders.py, especially find_best_user_match at lines 108-166, and review the current --threshold behavior. Compare the exact-match lookup and fuzzy candidate filtering against the existing matching results; done means the exact path remains unchanged and the fuzzy prefilter is verified for cross-first-letter cases.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
backend, performance
Issue type
Refactor
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.