Struct PruningJoinHashMap 

pub struct PruningJoinHashMap {
    pub map: HashTable<(u64, u64)>,
    pub next: VecDeque<u64>,
}

The PruningJoinHashMap is similar to a regular JoinHashMap, but with the capability of pruning elements in an efficient manner. This structure is particularly useful for cases where it’s necessary to remove elements from the map based on their buffer order.

Example

Let's continue the example of `JoinHashMap` and then show how `PruningJoinHashMap` would
handle the pruning scenario.

Insert the pair (10,4) into the `PruningJoinHashMap`:
map:
----------
| 10 | 5 |
| 20 | 3 |
----------
list:
---------------------
| 0 | 0 | 0 | 2 | 4 | <--- hash value 10 maps to 5,4,2 (which means indices values 4,3,1)
---------------------

Now, let's prune 3 rows from `PruningJoinHashMap`:
map:
---------
| 1 | 5 |
---------
list:
---------
| 2 | 4 | <--- hash value 10 maps to 2 (5 - 3), 1 (4 - 3), NA (2 - 3) (which means indices values 1,0)
---------

After pruning, the | 2 | 3 | entry is deleted from `PruningJoinHashMap` since
there are no values left for this key.

Fields

map: HashTable<(u64, u64)>

Stores hash value to last row index

next: VecDeque<u64>

Stores indices in chained list data structure

Implementations

impl PruningJoinHashMap

pub(crate) fn with_capacity(capacity: usize) -> Self

Constructs a new PruningJoinHashMap with the given capacity. Both the map and the list are pre-allocated with the provided capacity.

Arguments

• capacity: The initial capacity of the hash map.

Returns

A new instance of PruningJoinHashMap.

pub(crate) fn shrink_if_necessary(&mut self, scale_factor: usize)

Shrinks the capacity of the hash map, if necessary, based on the provided scale factor.

Arguments

• scale_factor: The scale factor that determines how conservative the shrinking strategy is. The capacity will be reduced by 1/scale_factor when necessary.

Note

Increasing the scale factor results in less aggressive capacity shrinking, leading to potentially higher memory usage but fewer resizes. Conversely, decreasing the scale factor results in more aggressive capacity shrinking, potentially leading to lower memory usage but more frequent resizing.

pub(crate) fn size(&self) -> usize

Calculates the size of the PruningJoinHashMap in bytes.

Returns

The size of the hash map in bytes.

pub(crate) fn prune_hash_values( &mut self, prune_length: usize, deleting_offset: u64, shrink_factor: usize, )

Removes hash values from the map and the list based on the given pruning length and deleting offset.

Arguments

• prune_length: The number of elements to remove from the list.
• deleting_offset: The offset used to determine which hash values to remove from the map.

Returns

A Result indicating whether the operation was successful.

Trait Implementations

impl JoinHashMapType for PruningJoinHashMap

Implementation of JoinHashMapType for PruningJoinHashMap.

fn extend_zero(&mut self, len: usize)

fn update_from_iter<'a>( &mut self, iter: Box<dyn Iterator<Item = (usize, &'a u64)> + Send + 'a>, deleted_offset: usize, )

fn get_matched_indices<'a>( &self, iter: Box<dyn Iterator<Item = (usize, &'a u64)> + 'a>, deleted_offset: Option<usize>, ) -> (Vec<u32>, Vec<u64>)

fn get_matched_indices_with_limit_offset( &self, hash_values: &[u64], limit: usize, offset: (usize, Option<u64>), ) -> (Vec<u32>, Vec<u64>, Option<(usize, Option<u64>)>)

fn is_empty(&self) -> bool

Returns true if the join hash map contains no entries.