system.sorting module

External merge sort with run generation and multi-way stream merging.

class system.sorting.RunMetadata(queue: ReadWriteQueue, size: int)

Bases: object

RunMetadata is a helper class allowing us to keep track of queues in external memory algorithms.

class system.sorting.RunGenerationResult(runs_metadata: list[RunMetadata], elements_written: int)

Bases: object

RunGenerationResult is a helper class to store the result of the run generation phase.

runs_metadata: list[RunMetadata]

elements_written: int

class system.sorting.RunGenerator(input_data: Iterator, queue_factory: QueueFactory, number_of_tuples_in_main_memory: int = 1000)

Bases: Generic

Phase 0 of external merge sort: reads the input in memory-sized chunks, sorts each chunk, and writes it out as a sorted run via the queue factory.

create_runs() → RunGenerationResult

Creates runs from the input file and write them to the output directory.

Returns:

A tuple consisting of (a list of RunMetadata instances, elements_written while creating runs).

class system.sorting.SingleStreamMerge(run_infos: list[RunMetadata], queue_factory: QueueFactory, number_of_tuples_in_main_memory: int)

Bases: Iterator, Generic

Merges k sorted input streams into a single sorted output stream. This is a single merge, not a recursive merge. As this implementation is lazy/demand-driven it can also be used for the final merge of a recursive merge.

class HeapEntry(queue: ReadWriteQueue)

Bases: Generic

HeapEntry is a helper class to store the value of an element and the read queue it came from. It is used to store the smallest element (=highest priority) of each run in the heap.

class system.sorting.ExternalMergeSort(input_data: Iterator, queue_factory: QueueFactory, number_of_tuples_in_main_memory: int = 1000, fan_in: int = 10)

Bases: Iterator, Generic

ExternalMergeSort is a class to merge sorted runs recursively based on arbitrary queues (which may be list-based or external or whatever queues). ExternalMergeSort is an iterator that returns the next element in the sorted runs and thus can directly be used in for loops. The final merge is online (on demand).

create_runs() → None

phase 0: create runs for the input data.

merge() → None

Phase i>0: Merges the runs iteratively till only one final merge is left to be done online.