Suggestion crashes with OOM from around ~3k HA seqs (6MB)

[corneliusroemer]

While it's fine to run the suggestion algorithm on around a thousand sequences, it seems to become unusable for only around ~3000 short flu HA sequences.

Repro:

1. Download these sequences: https://api.loculus.genspectrum.org/influenza-a/sample/unalignedNucleotideSequences/seg1?downloadAsFile=true&downloadFileBasename=influenza-a_nuc-seg1_2025-06-07T1034&dataFormat=fasta&versionStatus=LATEST_VERSION&isRevocation=false&country=Australia&length_seg1From=2000
2. Drop them into Nextclade and run suggest (take the time it takes)
3. Drop the file a second time into Nextclade (to double the number of sequences). Click re-suggest.

For flu on my machine, 500 seqs take around 2 seconds to suggest (with all wasm/minimizer cached). 1000 seqs take 4 seconds. 2000 seqs around 8 seconds. But from around 3k I get OOM crashes (after around 40 seconds).

[ivan-aksamentov]

This new global optimization algo loops quite a bit, but I don't immediately see anything criminal. Maybe it's in JS. Would be nice to see how CLI behaves vs Web as number of sequences grows.

nextclade/packages/nextclade/src/sort/minimizer_search.rs

Lines 131 to 193 in 25f5172

	for i in 0..params.max_iter {
	let mut hit_by_dataset: IndexMap<&String, usize> = indexmap! {};
	let mut top_hit_by_dataset: IndexMap<&String, usize> = indexmap! {};
	for qry in &unmatched {
	let hits = &results[qry].datasets;
	for hit in hits {
	*hit_by_dataset.entry(&hit.name).or_insert(0) += 1;
	}
	if !hits.is_empty() {
	*top_hit_by_dataset.entry(&hits[0].name).or_insert(0) += 1;
	}
	}
	let hit_by_dataset = reorder_indexmap(hit_by_dataset, dataset_order);
	let top_hit_by_dataset = reorder_indexmap(top_hit_by_dataset, dataset_order);
	if let Some(best_dataset) = key_of_max_value(&hit_by_dataset) {
	let mut best_dataset = *best_dataset;
	if hit_by_dataset[&best_dataset] == 0 {
	debug!("partition_sequences: no more hits");
	break;
	}
	if let Some(&best_top_dataset) = key_of_max_value(&top_hit_by_dataset) {
	if hit_by_dataset[best_top_dataset] == hit_by_dataset[best_dataset] {
	best_dataset = best_top_dataset;
	};
	let matched: BTreeSet<_> = results
	.iter()
	.filter(|(_, res)| res.datasets.iter().any(|dataset| &dataset.name == best_dataset))
	.map(|(i, _)| i)
	.copied()
	.collect();
	unmatched = unmatched.difference(&matched).copied().collect();
	top_hit_matches += top_hit_by_dataset[best_top_dataset];
	total_matches += hit_by_dataset[best_dataset];
	debug!("Global search: iteration {}", i);
	debug!(
	"Global search: added dataset '{}' ({} hits, {} top hits)",
	best_dataset, hit_by_dataset[best_dataset], top_hit_by_dataset[best_top_dataset]
	);
	debug!("Global search: hit matches {}", total_matches);
	debug!("Global search: top hit matches {}", top_hit_matches);
	debug!("Global search: unmatched remaining {}", unmatched.len());
	suggestions.push(DatasetSuggestionStats {
	name: best_dataset.to_owned(),
	n_hits: hit_by_dataset[best_top_dataset],
	qry_indices: matched.iter().copied().collect(),
	});
	if unmatched.is_empty() {
	break;
	}
	}
	}
	}