parquet_argsort Module

private interface argsort_i32_i32()

Arguments

private interface argsort_i32_i64()

Arguments

private interface argsort_i64_i32()

Arguments

private interface argsort_i64_i64()

Arguments

private interface argsort_f32_i32()

Arguments

private interface argsort_f32_i64()

Arguments

private interface argsort_f64_i32()

Arguments

private interface argsort_f64_i64()

Arguments

private interface argsort_bool_i32()

Arguments

private interface argsort_bool_i64()

Arguments

private interface argsort_chr_i32()

Arguments

private interface argsort_chr_i64()

Arguments

public module function pf_sort_threads() result(n)

Resolves how many threads a sort should use. This is the only place the auto rule lives, and the only place in this module carrying OpenMP plumbing at all -- the same arrangement parquet_tables_parallel.f90 keeps for the table layer, and worth more here, since the alternative is that plumbing repeated in 65 generated bodies. How many threads an AUTOMATIC sort -- one where threads= is absent -- would use right now: omp_get_max_threads() when the caller is not inside an OpenMP parallel region, and 1 when they are, because a nested region is the caller's business.

Public because the read-time parquet_open_reader(..., sort_by=) has to ask the same question from a different module, and one implementation of this rule is worth more than a private copy in each -- two copies drifting would mean a raw-array sort and a read-time sort silently disagreeing about when to thread. Useful in its own right for reporting or logging what an automatic sort is about to do.

Arguments

Return Value integer

threads an automatic sort would use; 1 means serial.

public module function tail_team(nthreads, n) result(team)

Team size for a trivially parallel whole-column loop, given an already-resolved sort thread count.

Separate from resolve_thread_count because the question is different: that one answers "how many threads may this sort use", this one answers "is this particular O(n) loop big enough to be worth a team". Both are needed -- a 64-thread sort still should not open a team to copy 500 elements.

Arguments

Return Value integer

team size; 1 means run it serially.

public module subroutine extract_i32(values, buf, descending, nulls_first, proc, is_valid, threads)

Extracts a 32-bit integer key into the canonical form the engine takes.

Arguments

public module subroutine extract_i64(values, buf, descending, nulls_first, proc, is_valid, threads)

Extracts a 64-bit integer key into the canonical form the engine takes.

Arguments

public module subroutine extract_f32(values, buf, descending, nulls_first, proc, is_valid, threads)

Extracts a 32-bit real key into the canonical form the engine takes.

Arguments

public module subroutine extract_f64(values, buf, descending, nulls_first, proc, is_valid, threads)

Extracts a 64-bit real key into the canonical form the engine takes.

Arguments

public module subroutine extract_bool(values, buf, descending, nulls_first, proc, is_valid, threads)

Extracts a logical key into the canonical form the engine takes.

Arguments

public module subroutine extract_chr(values, buf, descending, nulls_first, proc, is_valid, threads)

Extracts a string key into the canonical form the engine takes.

Arguments

public module subroutine drive_engine(keys, nrows, proc, perm, threads)

Runs the C++ engine over keys, returning a 1-based permutation.

Arguments

public module subroutine drive_engine_grouped(keys, nrows, proc, perm, threads, group_offsets, group_ekeys)

drive_engine, plus the group boundaries when group_offsets is asked for.

Absent group_offsets is exactly drive_engine, one-shot fast path and all. Present, it routes through engine_build_runs instead, which always uses the builder -- so asking for boundaries costs one extra copy of a single key. That is the documented price of one entry point serving three operations rather than three of them.

Arguments

public module subroutine runs_to_offsets(tie, nrows, offsets)

Turns engine_build_runs' tie flags into the offsets group_offsets promises: length ngroups + 1, last entry nrows + 1, so group g is perm(o(g):o(g+1)-1) for every g with no last-iteration special case.

Arguments

public module subroutine resolve_thread_count(threads, nrows, count)

Arguments

public module subroutine fill_identity(perm, n, nthreads)

Fills perm(1:n) with 1..n, threaded when nthreads and n justify it.

Its own procedure rather than an inline loop because it is one of the three whole-column serial loops that bound a threaded sort's end-to-end speedup, and measuring it separately is how that was found. See bench/benchmark_sort_tail.f90.

Arguments

public module subroutine valid_from_mask(mask, n, proc, valid)

Builds the engine's int8 validity array from a logical mask, leaving valid UNALLOCATED when the mask marks nothing null (the engine's no-nulls fast path).

Arguments

public module subroutine engine_build_runs(keys, nrows, proc, perm, tie, threads, group_ekeys)

Sorts, and reports where the runs of EQUAL rows are: tie(k) is 1 when output position k holds a row comparing equal to the one before it. One call, because pf_unique/pf_rank need both and would otherwise build the permutation twice.

Arguments

public module subroutine narrow_perm(perm64, proc, perm32, threads)

Narrows a 1-based int64 permutation to int32, aborting rather than truncating.

Arguments

public module subroutine narrow_offsets(offsets64, proc, offsets32)

Narrows a group-offsets array to int32, aborting rather than truncating.

NOT the same test as narrow_perm's, and the difference is exactly one row: a permutation's largest entry is n, but this array's is the sentinel n + 1. At n == huge(int32) the permutation narrows cleanly while the sentinel wraps negative, and a negative sentinel turns the last group's o(g+1) - 1 into a huge negative bound -- a silently empty or wildly wrong slice instead of an abort. So this checks the sentinel itself rather than the length.

Arguments

public module function sort_tier_of(key, i) result(tier)

RAW output tier of row i under one key: values(0), NaNs(1), nulls(2).

Absolute, and neither descending nor nulls_first reaches this. That a descending sort still puts nulls last is Arrow's own rule. nulls_first is left out for a different reason: it only ever REVERSES the tier order, so sort_compare_key applies it once by negating the tier comparison rather than having this relabel on every call — which is what keeps the whole comparator chain inside GCC's default inlining budget. Only a real-family key can be tier 1.

Arguments

Return Value integer

0, 1 or 2.

public module function sort_compare_key(key, a, b) result(c)

-1/0/+1 for rows a and b under ONE key, with its order and null placement applied.

Two rows in the same non-value tier (both null, or both NaN) compare EQUAL, so the caller's index tiebreaker keeps them in file order. descending negates the answer within the value tier only.

Arguments

Return Value integer

-1, 0 or +1.

public module function sort_row_less(keys, a, b) result(less)

THE sort comparator: every key in precedence order, then the row index as tiebreaker.

The index tiebreaker makes this a TOTAL ORDER in which no two distinct rows compare equal, which is what makes an unstable sort produce the stable answer, makes nth_element deterministic, and makes a parallel result bit-identical to a serial one by construction. Keep it beside sort_keys_compare -- feature_risks.md Risk-34.

Arguments

Return Value logical

.true. when a sorts before b.

public module function sort_keys_compare(keys, a, b, nkeys) result(c)

The same ordering as sort_row_less, three-way and WITHOUT the index tiebreaker.

Everything that must recognise "these two rows are equal" -- binary search, run detection for pf_unique/pf_rank, merging, is_sorted -- needs this one, since under the tiebreaker no two rows ever are equal. Sorting is the only caller that must NOT use it. nkeys is how many LEADING keys take part, clamped to size(keys): run detection passes a prefix because "sort by field then magnitude, but group by field alone" is one pass.

Arguments

Return Value integer

-1, 0 or +1.

public module function sort_counting_candidate(keys, n, lo, hi) result(ok)

Whether the single-key integer counting sort applies, and over what value range.

lo/hi are the key's range over its VALID rows only — a null row's value slot holds whatever the buffer contained, so including it could widen the range past the bucket limit and decline the fast path for no reason. An all-null key answers .true. with lo == hi == 0, which yields the identity permutation.

Arguments

Return Value logical

.true. when the counting path applies.

public module function sort_is_sorted(keys, n) result(answer)

Are rows 1..n already in order under every key?

Over sort_keys_compare, so adjacent EQUAL rows are in order — the tiebreaker would turn this into "is the row index ascending".

Arguments

Return Value logical

.true. when already ordered.

public module function sort_search_position(keys, n_search, upper) result(pos)

Binary search for the target row, which the caller APPENDED as row n_search + 1.

Preserve the appending. It is what removes any compare-a-row-against-a-value arm and so makes drift from the sort comparator structurally impossible — Risk-34.

Arguments

Return Value integer(kind=int64)

1-based insertion point in 1..n_search+1.

public module subroutine sort_comparison_permutation(keys, n, perm)

Fills perm with the 1-based permutation that puts rows 1..n in key order.

The serial half of the pure-Fortran engine (feature_sort.md Stage 2): an INTROSORT -- quicksort with median-of-three pivoting, a depth-limited heapsort fallback and a final insertion pass -- ordering by sort_row_less and nothing else.

It is unstable, and that is why it is correct. sort_row_less ends with a row index tiebreaker, so no two distinct rows compare equal and every correct sorting algorithm produces the SAME permutation -- the stable one. Switching this to a merge sort to "make it stable" would buy a temporary buffer and change no answer.

Arguments

public module subroutine sort_build_permutation(keys, n, perm)

THE engine entry point: the counting fast path where it applies, the introsort otherwise.

Mirrors the C++ sort_build_permutation exactly, including that the range scan's lo/hi are carried from the candidate test into the placement pass rather than rescanned. The two paths answer identically — the counting one is stable by construction, which is the same answer the comparator's index tiebreaker gives.

Arguments

public module subroutine sort_build_permutation_threaded(keys, n, nthreads, perm)

THE engine entry point when a thread count is available -- Stage 4.

Answers bit-identically to sort_build_permutation at every thread count, and that is a property of the ordering rather than of the implementation: sort_row_less ends in a row-index tiebreaker, so no two distinct rows compare equal, exactly one permutation is correct, and every correct algorithm must produce it. A threading bug therefore shows up as a WRONG permutation, never as a differently-ordered valid one.

nthreads is a resolved count, never a sentinel -- resolve_thread_count has already applied the caller's threads=, the automatic policy and the in-parallel rule. This procedure applies only the two clauses that need the DATA to decide: the row floor (an internal team-scaled rule), below which a team costs more than it saves, and one thread meaning the plain serial path. Both are observable through parquet_debug_sort_threads_used, which is the only way a test can see either.

Arguments

public module subroutine sort_counting_permutation(key, n, lo, hi, perm)

Fills perm by counting sort over lo..hi, with the nulls placed as one block.

Two O(n) passes and no comparisons at all. Stable by construction: the placement pass walks the input in index order, so equal values are emitted in file order — the same answer sort_row_less's index tiebreaker produces.

Arguments

public module subroutine sort_partial_permutation(keys, n, count, perm)

The first count entries of the sorted permutation, by heap selection.

std::partial_sort's algorithm, not a full sort truncated -- a test counts comparisons to hold that apart. Everything past count in perm is untouched.

Arguments

public module subroutine sort_nth_index(keys, n, nth, idx)

The row a full sort would place at 1-based rank nth, by quickselect.

Deterministic because the comparator is a total order: there is exactly one row at that rank, so this and a full sort cannot disagree. idx is 0 for an out-of-range rank, which every caller has already rejected.

Arguments

public module subroutine sort_build_runs_permutation(keys, n, group_keys, perm, tie)

Sorts, then flags where the runs of EQUAL rows begin. tie(1) is always 0.

group_keys is how many LEADING keys decide a tie; the sort itself always uses every key. That asymmetry is what produces "grouped by field, ordered within group".

Arguments

public module subroutine sort_merge_permutation(keys, n, na, perm)

Merges the already-ordered ranges 1..na and na+1..n into one permutation.

Ties take from the FIRST range, which is std::merge's stability guarantee and what makes pf_merge agree with pf_sort of the concatenation element for element.

Arguments

public module function parquet_debug_using_fortran_sort_engine() result(on)

Test-only reader for which engine drive_engine would use right now.

Arguments

Return Value logical

.true. when the Fortran engine is selected.

public module function parquet_debug_sort_heapsort_calls() result(n)

Test-only count of heapsort fallbacks since parquet_debug_set_sort_depth_limit.

What makes the forced-fallback test non-vacuous: the quicksort and heapsort paths answer identically, so only this counter can say which one ran.

Arguments

Return Value integer(kind=int64)

heapsort fallbacks entered.

public module function parquet_debug_sort_max_insertion_shift() result(n)

Test-only reader for how far the insertion pass moved anything since it was armed.

Must not exceed SORT_INSERTION_CUTOFF after a correct sort — that is the whole invariant the quicksort exists to establish, and the only observable that a defect in the partition or the heapsort has not simply been repaired by the insertion pass.

Arguments

Return Value integer(kind=int64)

largest shift, in positions.

public module function parquet_debug_sort_refine_runs() result(n)

Test-only count of parallel refine dispatches in the last string sort; 0 = serial.

Arguments

Return Value integer(kind=int64)

runs refined by a team, or sub-bucket loops that opened one.

public module function parquet_debug_sort_radix_passes() result(n)

Test-only count of radix scatter passes executed since that reset.

What makes a test of any pass-count optimisation non-vacuous: the constant-digit skip and the narrow-integer bias both leave the permutation bit-identical, so this is the only thing that can say whether either fired. Zero means the radix path did not run at all, which is itself worth asserting -- a floor or a decline is easy to trip by accident and looks exactly like an optimisation working perfectly.

Arguments

Return Value integer(kind=int64)

passes executed.

public module function parquet_debug_sort_threads_used() result(n)

Test-only count of threads the engine's last permutation build opened; 1 = serial.

What makes any Stage 4 threading test non-vacuous. The permutation is bit-identical at every thread count -- the comparator is a total order, so there is exactly one correct answer -- which means no assertion on perm can distinguish a threaded run from a serial one. A policy that silently refuses to thread is therefore invisible to every other test in the suite, and is the easiest Stage 4 bug to write.

Reports the RESOLVED count, not the team the runtime actually granted. Has no effect on, and says nothing about, the C++ engine.

Arguments

Return Value integer(kind=int64)

threads resolved for the last build; 1 means serial.

public module function parquet_debug_sort_split_buckets() result(n)

Test-only count of buckets Design B's split produced; 0 means it did not run.

Design B and the serial LSD loop answer identically by construction, so this is the only way to tell which one ran -- and therefore the only way any test of the split, the bucket cap or the balance test can be non-vacuous. Zero is informative rather than missing: it is exactly what a declined split looks like, which is the normal outcome on a low-cardinality key.

Arguments

Return Value integer(kind=int64)

buckets in the last split; 0 if Design B declined.

public module function parquet_debug_sort_design() result(n)

Test-only report of which parallel radix design ran: 0 serial, 1 A, 2 B.

The three answer identically by construction, so this is the only way a test of the Design A fallback can be non-vacuous -- A is reached only when B declines, and an assertion on the permutation cannot distinguish A, B and the serial loop.

Arguments

Return Value integer(kind=int64)

0 serial, 1 Design A, 2 Design B.

public module subroutine parquet_debug_set_sort_depth_limit(n)

Test-only override for the introsort's depth limit; NEGATIVE restores the computed one.

Zero makes the very first oversized range fall back to heapsort, which is the only way to reach that arm from a test-sized fixture. Has no effect on the C++ engine. Also ZEROES the heapsort counter, so a test arms and reads in the obvious order.

Arguments

public module subroutine parquet_debug_set_sort_track_shift(on)

Test-only arming of the final insertion pass's largest-shift tracker, zeroing it too.

Off by default, because armed it writes process-global state from an ordinary sort.

Arguments

public module subroutine parquet_debug_set_sort_radix_min_rows(n)

Test-only override for the radix path's row floor; NEGATIVE restores the built-in.

Used in both directions. A huge value DECLINES the radix path, which is what keeps the introsort's and the counting path's own negative controls non-vacuous now that the floor sits below their fixture sizes. A small one drives ordinary fixtures through the radix path. Has no effect on the C++ engine.

Arguments

public module subroutine parquet_debug_set_sort_task_floor(n)

Test-only override for the balanced split's task floor; NEGATIVE restores the built-in SORT_TASK_FLOOR.

The floor binds only when nv / team falls below it -- small n with a large team -- which no fixture in the suite reaches, so without this the constant is unexercised rather than merely untuned. Also the sweep instrument: a crossover cannot be located by rebuilding, because it sits inside this project's cross-build noise floor. Has no effect on the C++ engine.

Arguments

public module subroutine parquet_debug_set_sort_tail_min_rows(n)

Test-only override for the TAIL passes' row floor; NEGATIVE restores the built-in.

Separate from the sort's own floor because the tail is memcpy-shaped and crosses over an order of magnitude lower; the two shared one setting until this existed, which meant one number governing two different questions. Has no effect on the C++ engine.

Arguments

public module subroutine parquet_debug_set_sort_engine_min_rows(n)

Test-only override for the Fortran ENGINE's threading floor; NEGATIVE restores it.

The engine's floor is internal and automatic, and there is no published setting for it -- sort_parallel_min_rows was retired once this rule replaced it.

Arguments

public module subroutine parquet_debug_set_sort_counting_max_threads(n)

Test-only override for the counting path's team ceiling; NEGATIVE restores it.

Setting it to 1 restores the pre-fix behaviour (counting serial-only), which is how the fix is A/B'd in one binary; setting it high forces counting onto teams that should decline it. Has no effect on the C++ engine, which has never gated the counting path on the team at all.

Arguments

public module subroutine parquet_debug_set_sort_split_min_card(n)

Test-only override for the split's minimum distinct-value count; NEGATIVE restores the built-in SORT_SPLIT_MIN_CARD.

Selects the design at a fixed cardinality: 0 forces refined Design B onto every key, a huge value forces Design A. Both directions are needed -- one keeps Design A's own coverage non-vacuous on keys that would otherwise take the split, the other reaches the split from low-cardinality fixtures. Has no effect on the C++ engine.

Arguments

public module subroutine parquet_debug_set_sort_radix_fail_alloc(which)

Test-only forcing of an allocation failure in the radix path, to reach its fallbacks.

Selects WHICH allocation fails, because they are in series and a single flag would make the first mask every later one: 0 none, 1 the main scratch, 2 the deep string refine's, 3 the threaded tier split's counters, 4 Design B's task arrays, and 5 to 8 the four grow_run_list makes in turn. Every fallback answers identically, so no assertion on a permutation can tell one apart from the ordinary path -- pair 1 and 2 with the insertion-shift tracker, which can.

Arguments

public module subroutine parquet_debug_reset_sort_radix_passes()

Test-only zeroing of the executed-radix-pass counter, before the sort under test.

Arguments