fix: keep the correct top-N under limit when scores tie by spokodev · Pull Request #835 · krisk/Fuse

spokodev · 2026-07-02T00:02:54Z

search(query, { limit: N }) can return a different, worse-ordered top-N than search(query).slice(0, N) when scores tie at the cutoff. The heap that selects the top-N orders and evicts by raw score only, so it ignores the tie-break and any custom sortFn.

The documented contract, and the repo's own limit results match top-N of unlimited results test, is that a limited search returns the same items in the same order as an unlimited search truncated to N. The default sortFn breaks a score tie by ascending refIndex, but the heap evicts whatever sits at its root, which on a tie can be the lowest-refIndex (best) item, so the correct item is dropped. A custom sortFn is never consulted during eviction at all.

Repro

const fuse = new Fuse(['matchX', 'matchY', 'matchZ', 'match'], { threshold: 0.6 })
fuse.search('match').map(r => r.refIndex)              // [3, 0, 1, 2]
fuse.search('match', { limit: 2 }).map(r => r.refIndex)
// before: [3, 1]   (refIndex 0 dropped)
// after:  [3, 0]   (equals search().slice(0, 2))

Fix

Give MaxHeap the sort comparator and order and evict by it, so the worst retained item is the one that sorts last. The retained top-N is then identical to a full sort followed by a slice, and a custom sortFn is honored. src/ is the source of truth; dist/ is rebuilt with npm run build.

Added a tie-break case to test/optimizations.test.js. It fails before the change; the full suite (372) stays green, and typecheck, lint and format:check pass.

search(query, { limit: N }) could return a different, worse-ordered top-N than search(query).slice(0, N) when scores tie at the cutoff. The heap that selects the top-N ordered and evicted by raw score only, ignoring the tie-break and any custom sortFn, so on a tie the heap could drop the item the sort order says to keep. Give MaxHeap the sort comparator and order and evict by it, so the retained top-N matches a full sort followed by a slice and a custom sortFn is honored. dist regenerated with npm run build.

search(query, { limit: N }) selected the top-N with a max-heap that ordered and evicted by raw score alone, ignoring the sortFn tie-break and any custom sortFn. On a score tie at the cutoff it could drop the item a full sort would keep, so the result differed from search(query).slice(0, N). Order the heap by the sort comparator and break comparator ties by item index, applying the same tie-break to the full-sort path. The retained top-N is now identical to a full sort followed by a slice for every index, including reordered parseIndex records, and a custom sortFn is honored. Gate the heap on shouldSort so shouldSort:false keeps collection order. Remove the now-redundant MaxHeap.shouldInsert (insert already guards) and consolidate the sortFn casts into one typed assertion. Reported in #835.

krisk · 2026-07-13T16:56:15Z

Your diagnosis was right: the heap ordered and evicted by raw score, so on a tie at the cutoff it ignored the tie-break and dropped the item a full sort would keep. The repro made it easy to confirm.

I've extended it a fair bit past your branch, so I'm landing it as a separate commit rather than merging directly. The same root cause turned up in a few more spots:

A custom sortFn never got consulted during eviction, only at the final sort, so the retained set could be wrong, not just the order.
limit ignored shouldSort, so search(q, { limit }) used the heap even under shouldSort: false and returned top-N by score when it should have kept collection order.
Records can arrive out of idx order via Fuse.parseIndex, so I made idx the canonical tie-break on both the heap and the full sort.

Also dropped MaxHeap.shouldInsert (insert already guards), collapsed the sortFn casts, and added a regression test per case.

Closing in favor of that commit.

This PR contains the following updates: | Package | Type | Update | Change | |---|---|---|---| | [fuse.js](http://fusejs.io) ([source](https://github.com/krisk/Fuse)) | imports | minor | [`7.4.2` -> `7.5.0`](https://renovatebot.com/diffs/npm/fuse.js/7.4.2/7.5.0) | --- ### Release Notes <details> <summary>krisk/Fuse (fuse.js)</summary> ### [`v7.5.0`](https://github.com/krisk/Fuse/blob/HEAD/CHANGELOG.md#750-2026-07-13) [Compare Source](krisk/Fuse@v7.4.2...v7.5.0) ##### ⚠️ Behavior changes Every change in this release is a bug fix, but each one corrects a **scoring or ranking** bug. Scores and result ordering will shift for some queries. That is why this ships as a minor rather than a patch: the public API is unchanged and upgrading is a drop-in, but the results you get back can differ, and that should not arrive silently in a patch bump. If you assert on exact `score` values or on a specific result order, expect those assertions to need updating. Re-baseline them against 7.5.0 rather than pinning to 7.4.x, since the 7.4.x behavior was wrong in the cases below. - **Field-length normalisation now counts words correctly.** Tabs and newlines were not treated as word separators, so a multi-line or tab-delimited field was scored as though it were one long word, making it look far shorter than it is. Fields containing `\t`, `\n`, or `\r` now score differently ([#830](krisk/Fuse#830)). - **Key weights are now normalised in object and keyless-logical search.** Weights that did not sum to `1` were applied unnormalised, skewing the relative influence of each key. If your `keys` weights do not already sum to `1`, your relative ranking changes ([#833](krisk/Fuse#833)). - **`limit` now returns the correct top-N when scores tie.** A tie at the cutoff boundary could evict a result that should have been kept, so `limit` could return the *wrong* items, not merely the right items in a different order ([#835](krisk/Fuse#835)). - **Bitap respects `minMatchCharLength` in the exact-match shortcut.** Matches shorter than `minMatchCharLength` were still reported via the exact-match fast path, so the `matches` array could contain entries it was configured to exclude ([#831](krisk/Fuse#831)). ##### Bug Fixes - **bitap:** respect minMatchCharLength in exact-match shortcut ([dbb98b6](krisk/Fuse@dbb98b6)), closes [#831](krisk/Fuse#831) - **fieldNorm:** count tabs and newlines as word separators ([6fe85b0](krisk/Fuse@6fe85b0)), closes [#830](krisk/Fuse#830) - **fieldNorm:** count word-starts instead of space transitions ([2946f97](krisk/Fuse@2946f97)) - **scoring:** normalise key weights in object and keyless-logical search ([e164b61](krisk/Fuse@e164b61)), closes [#833](krisk/Fuse#833) - **search:** keep the correct top-N under limit when scores tie ([437f8f3](krisk/Fuse@437f8f3)), closes [#835](krisk/Fuse#835), thanks [@spokodev](https://github.com/spokodev) for the report and the fix ##### [7.4.2](krisk/Fuse@v7.4.1...v7.4.2) (2026-06-05) ##### Bug Fixes - **types:** emit CommonJS declarations (.d.cts) for node16/nodenext ([#780](krisk/Fuse#780)) ([33f5d29](krisk/Fuse@33f5d29)) ##### [7.4.1](krisk/Fuse@v7.4.0...v7.4.1) (2026-06-02) ##### Bug Fixes - **types:** add TypeScript declarations for fuse.js/worker-script ([6ef6c33](krisk/Fuse@6ef6c33)), closes [#828](krisk/Fuse#828) - **types:** ship TypeScript declarations for fuse.js/worker ([572ad1e](krisk/Fuse@572ad1e)), closes [#828](krisk/Fuse#828) </details> --- ### Configuration 📅 **Schedule**: (UTC) - Branch creation - At any time (no schedule defined) - Automerge - At any time (no schedule defined) 🚦 **Automerge**: Disabled by config. Please merge this manually once you are satisfied. ♻ **Rebasing**: Whenever PR becomes conflicted, or you tick the rebase/retry checkbox. 🔕 **Ignore**: Close this PR and you won't be reminded about this update again. --- - [ ] If you want to rebase/retry this PR, check this box --- This PR has been generated by [Mend Renovate](https://github.com/renovatebot/renovate).  Reviewed-on: https://git.oirnoir.dev/OIRNOIR/YouTube-Helper-Server/pulls/27

spokodev force-pushed the fix/limit-topn-tie-ordering branch from 9d899fc to 572811d Compare July 3, 2026 19:05

spokodev force-pushed the fix/limit-topn-tie-ordering branch from 572811d to a3a2af7 Compare July 4, 2026 11:35

krisk closed this Jul 13, 2026

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

fix: keep the correct top-N under limit when scores tie#835

fix: keep the correct top-N under limit when scores tie#835
spokodev wants to merge 1 commit into
krisk:mainfrom
spokodev:fix/limit-topn-tie-ordering

spokodev commented Jul 2, 2026 •

edited

Loading

Uh oh!

krisk commented Jul 13, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Uh oh!

Conversation

spokodev commented Jul 2, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Repro

Fix

Uh oh!

krisk commented Jul 13, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

spokodev commented Jul 2, 2026 •

edited

Loading