insert_user_bin.cpp File Reference

Implements raptor::insert_user_bin. More...

#include <iterator>
#include <optional>
#include <hibf/contrib/robin_hood.hpp>
#include <raptor/argument_parsing/update_arguments.hpp>
#include <raptor/file_reader.hpp>
#include <raptor/index.hpp>
#include "insert/is_fpr_exceeded.hpp"
#include "insert/strong_types.hpp"
#include "subtree.hpp"

Include dependency graph for insert_user_bin.cpp:

Classes
struct	raptor::rebuild_decision
	What to rebuild after a user bin was inserted, and where. More...

Enumerations
enum class	raptor::rebuild_kind : uint8_t { none , partial , full }
	The rebuild the index needs after a user bin was inserted.
enum class	raptor::tmax_check : uint8_t { no_rebuild , full_rebuild , partial_rebuild }
	The rebuild an IBF needs because of its number of technical bins.

Functions
tmax_check	raptor::check_tmax_rebuild (raptor_index< index_structure::hibf > const &index, size_t const ibf_idx)
	Checks whether the IBF at ibf_idx has grown too large.
robin_hood::unordered_flat_set< uint64_t >	raptor::detail::compute_kmers (std::vector< std::string > const &user_bin, raptor_index< index_structure::hibf > const &index)
	Computes the set of k-mers of a user bin, using the shape and window size the index was built with.
rebuild_decision	raptor::determine_rebuild (raptor_index< index_structure::hibf > const &index, detail::insert_location const &insert_location, std::optional< detail::rebuild_location > const &rebuild_location)
	Decides whether the index needs to be rebuilt after a user bin has been inserted.
void	raptor::full_rebuild (update_arguments const &arguments, std::vector< std::vector< std::string > > bin_path, raptor_index< index_structure::hibf > &index)
	Rebuilds index from scratch from all user bins in bin_path that have not been deleted.
std::optional< insert_location >	raptor::detail::get_location (std::vector< ibf_max > const &max_ibf_sizes, size_t const kmer_count, raptor_index< index_structure::hibf > &index)
	Determines where to store a user bin with kmer_count k-mers, and reserves the technical bins for it.
void	raptor::get_ubs (robin_hood::unordered_flat_set< uint64_t > &ub_ids, raptor_index< index_structure::hibf > &index, size_t const ibf_idx)
	Collects the IDs of all user bins stored in the subtree rooted at ibf_idx into ub_ids.
template<std::output_iterator< uint64_t > it_t>
void	raptor::detail::hash_paths_into (std::vector< std::string > const &paths, it_t target, seqan3::shape const shape, uint32_t const window_size)
	Reads the hashes of all files of a user bin into target.
std::optional< rebuild_location >	raptor::detail::insert_tb_and_parents (robin_hood::unordered_flat_set< uint64_t > const &kmers, insert_location insert_location, raptor_index< index_structure::hibf > &index)
	Inserts kmers at insert_location and into every merged bin on the path to the top-level IBF.
void	raptor::insert_user_bin (update_arguments const &arguments, raptor_index< index_structure::hibf > &index)
	Inserts the user bins listed in arguments.user_bins_to_insert into index.
bool	raptor::detail::is_deleted (raptor_index< index_structure::hibf > const &index, size_t const ibf_idx)
	Whether the IBF at ibf_idx has been removed by a partial rebuild.
size_t	raptor::detail::max_elements (max_elements_parameters const &params)
	The maximum number of elements a technical bin can hold without exceeding params.fpr.
std::vector< ibf_max >	raptor::detail::max_ibf_sizes (raptor_index< index_structure::hibf > const &index)
	The capacity of a technical bin of each IBF, sorted ascendingly. IBFs deleted by a partial rebuild are omitted.
detail::rebuild_location	raptor::parent_location (raptor_index< index_structure::hibf > const &index, size_t const ibf_idx)
	The merged bin the IBF at ibf_idx hangs in, as a rebuild location.
void	raptor::partial_rebuild (update_arguments const &arguments, detail::rebuild_location const &rebuild_location, raptor_index< index_structure::hibf > &index)
	Recomputes the layout of the subtree hanging in the merged bin given by rebuild_location.

Detailed Description

Implements raptor::insert_user_bin.

Author

Enrico Seiler <enrico.seiler AT fu-berlin.de>

Function Documentation

check_tmax_rebuild()

tmax_check raptor::check_tmax_rebuild	(	raptor_index< index_structure::hibf > const &	index,
		size_t const	ibf_idx )

Checks whether the IBF at ibf_idx has grown too large.

The top-level IBF must not exceed tmax; growing it beyond that requires a full rebuild. A lower-level IBF may exceed tmax by raptor::detail::tmax_slack bins before it is rebuilt.

Here is the call graph for this function:

Here is the caller graph for this function:

determine_rebuild()

rebuild_decision raptor::determine_rebuild	(	raptor_index< index_structure::hibf > const &	index,
		detail::insert_location const &	insert_location,
		std::optional< detail::rebuild_location > const &	rebuild_location )

Decides whether the index needs to be rebuilt after a user bin has been inserted.

Parameters

[in]	index	The index.
[in]	insert_location	Where the user bin was inserted.
[in]	rebuild_location	Where the FPR was exceeded, if it was exceeded at all.

Here is the call graph for this function:

Here is the caller graph for this function:

full_rebuild()

void raptor::full_rebuild	(	update_arguments const &	arguments,
		std::vector< std::vector< std::string > >	bin_path,
		raptor_index< index_structure::hibf > &	index )

Rebuilds index from scratch from all user bins in bin_path that have not been deleted.

Parameters

[in]	arguments	The update arguments.
[in]	bin_path	The bin path of index, followed by the user bins that have not been inserted yet.
[in,out]	index	The index to rebuild.

Computes a fresh layout with automatic tmax, overriding the tmax the index was built with: it should always perform better, especially when many user bins were inserted since.

The rebuilt index is the same as one built from the remaining user bins: deleted user bins are dropped from the bin path, and the remaining user bins are renumbered in their order. Until then, a deleted user bin keeps its ID and its entry in the bin path, see raptor::delete_user_bins, but no technical bin refers to it anymore.

Here is the call graph for this function:

Here is the caller graph for this function:

get_location()

std::optional< insert_location > raptor::detail::get_location	(	std::vector< ibf_max > const &	max_ibf_sizes,
		size_t const	kmer_count,
		raptor_index< index_structure::hibf > &	index )

Determines where to store a user bin with kmer_count k-mers, and reserves the technical bins for it.

Parameters

[in]	max_ibf_sizes	The capacity of each IBF, see raptor::detail::max_ibf_sizes.
[in]	kmer_count	The number of k-mers of the user bin.
[in,out]	index	The index to insert into.

Returns

Where to store the user bin, or std::nullopt if a full rebuild is unavoidable, in which case index is left unchanged.

Here is the call graph for this function:

Here is the caller graph for this function:

hash_paths_into()

template<std::output_iterator< uint64_t > it_t>

void raptor::detail::hash_paths_into	(	std::vector< std::string > const &	paths,
		it_t	target,
		seqan3::shape const	shape,
		uint32_t const	window_size )

Reads the hashes of all files of a user bin into target.

The file type is deduced from the first path; raptor::bin_validator rejects mixing file types within a user bin. The type is deduced per user bin because the files an index was built from and the files being inserted may be of different types.

Here is the call graph for this function:

Here is the caller graph for this function:

insert_tb_and_parents()

std::optional< rebuild_location > raptor::detail::insert_tb_and_parents	(	robin_hood::unordered_flat_set< uint64_t > const &	kmers,
		insert_location	insert_location,
		raptor_index< index_structure::hibf > &	index )

Inserts kmers at insert_location and into every merged bin on the path to the top-level IBF.

Parameters

[in]	kmers	The k-mers to insert.
[in]	insert_location	Where the user bin is stored.
[in,out]	index	The index to insert into.

Returns

The bin closest to the top-level IBF whose target FPR is exceeded, or std::nullopt if none is.

A query only reaches a lower-level IBF through the merged bins above it, hence the k-mers have to be present in all of them. Walking upwards means a returned location is the highest one that exceeds its FPR, i.e. rebuilding there also covers every exceeded bin below it.

Here is the call graph for this function:

Here is the caller graph for this function:

insert_user_bin()

void raptor::insert_user_bin	(	update_arguments const &	arguments,
		raptor_index< index_structure::hibf > &	index )

Inserts the user bins listed in arguments.user_bins_to_insert into index.

Parameters

[in]	arguments	The update arguments.
[in,out]	index	The index to insert into.

Each user bin is inserted individually. For each one, a suitable IBF and a range of technical bins is determined (see raptor::detail::get_location), the k-mers are inserted there and into all merged bins on the path to the top-level IBF, and the index is rebuilt if that insertion degraded it too much:

• If an IBF holds more technical bins than tmax allows, it is rebuilt. For the top-level IBF this means a full rebuild, for any other IBF a partial rebuild of the subtree it roots.
• Otherwise, if inserting exceeded the target FPR of a bin, the subtree containing that bin is rebuilt partially, or fully if the bin lies in the top-level IBF.

A partial rebuild recomputes the layout of one subtree, a full rebuild recomputes the whole index from all user bins that have not been deleted, including the ones not inserted yet. Consequently, a full rebuild finishes the insertion of every remaining user bin, and this function returns right after it. Setting arguments.disable_partial_rebuild replaces every partial rebuild by a full one.

A full rebuild drops deleted user bins from the bin path and renumbers the remaining ones in their order, as if the deleted user bins never existed.

The rebuilds are counted in arguments.partial_rebuilds and arguments.full_rebuilds.

Here is the call graph for this function:

Here is the caller graph for this function:

max_elements()

size_t raptor::detail::max_elements

(

max_elements_parameters const &

params

)

The maximum number of elements a technical bin can hold without exceeding params.fpr.

Inverts the Bloom filter FPR formula: ceil(BITS / (-HASH / log(1 - exp(log(FPR) / HASH)))).

Here is the call graph for this function:

Here is the caller graph for this function:

max_ibf_sizes()

std::vector< ibf_max > raptor::detail::max_ibf_sizes

(

raptor_index< index_structure::hibf > const &

index

)

The capacity of a technical bin of each IBF, sorted ascendingly. IBFs deleted by a partial rebuild are omitted.

This is the capacity implied by the bin size, not the current occupancy: a user bin that does not fit into a single technical bin is split over several of them, so the capacity is what decides how many bins it needs.

Here is the call graph for this function:

Here is the caller graph for this function:

partial_rebuild()

void raptor::partial_rebuild	(	update_arguments const &	arguments,
		detail::rebuild_location const &	rebuild_location,
		raptor_index< index_structure::hibf > &	index )

Recomputes the layout of the subtree hanging in the merged bin given by rebuild_location.

Parameters

[in]	arguments	The update arguments.
[in]	rebuild_location	The merged bin whose subtree is rebuilt.
[in,out]	index	The index to rebuild in.

Builds a new HIBF from the user bins of that subtree and splices it into index in place of the old subtree. The first IBF of the new subtree reuses the slot of the old one, so the merged bin in the parent stays valid and the rest of the index is untouched. The remaining new IBFs are appended to ibf_vector; IBFs of the old subtree that are not reused are retired, see raptor::detail::retire_ibf. Nothing outside the old subtree points into it, so no next_ibf_id entry is left dangling.

Here is the call graph for this function:

Here is the caller graph for this function: