Vectorized membership masks for sorted arrays

[aunjgr]

Vectorized membership masks for sorted arrays

Motivation

Given a sorted value array and a reusable sorted member array, produce the value-aligned membership
mask without hashing, scalar extraction, or one binary search per value.

A plain two-pointer merge is optimal for one pair of complete arrays, but array engines process
independently scheduled chunks. Restarting that merge from the beginning of a large member set for
every chunk repeats O(members) work. Building a temporary hash table discards the ordering proof
and adds retained state. The proposed operation narrows the relevant member interval from each
chunk's first and last values, then merges only that interval.

This is a reusable building block for:

• sorted IN / NOT IN evaluation and semi, anti, or mark joins;
• exact dynamic/runtime filters over ordered inputs;
• applying sorted delete-key sets or deletion vectors;
• existence checks while merging or compacting sorted runs;
• INTERSECT / EXCEPT execution;
• filtering sorted dictionary domains against literal sets; and
• intersecting sorted sparse, patch, or index domains.

Proposed API

Add these public APIs under vortex_array::search_sorted:

SortedArray::try_new(array, SortedOrder { direction, nulls }, ctx)

sorted_membership_mask(values, &members, NullEquality, ctx) -> VortexResult<Mask>

The initial implementation supports canonical Bool, Primitive, Decimal, Binary, and UTF-8 arrays.
It has the following properties:

• the member set is canonicalized and order-validated once;
• each probe batch is canonicalized and validated independently;
• ascending/descending and nulls-first/nulls-last are explicit;
• null-equal and null-unequal set semantics are explicit;
• duplicates are permitted on either side;
• two binary searches narrow members to the probe batch's first/last values;
• one linear merge visits only that overlapping member slice;
• typed buffers and BinaryViews are read directly without Scalar or row-function callbacks;
• decimals with different physical widths compare through their common i256 value;
• primitive floats follow Vortex's existing total order and bitwise equality.

Initial implementation

An implementation is available in #9552 at signed commit 1868a4b.
Tests cover native and variable-width types, mixed-width decimals, both directions, null policies,
duplicates, empty inputs, mismatch/unsupported rejection, and unsorted input. A focused test uses one
million members and verifies a ten-value probe window performs fewer than 100 member comparisons.

On the development machine, the existing 65,536-value / 4,096-member Divan fixtures report medians
of approximately 272 us for i64 and 1.10 ms for external 16-byte BinaryView values.

Comparative benchmark

The Divan comparison uses one 8,192-row engine chunk. Member values become sparser as the member
set grows; construction and probe costs are measured separately.

members / hit density	narrowed merge	full merge	per-row binary search	hash probe	sorted validation	hash build
16K / 100%	54.1 us	15.6 us	100.1 us	22.3 us	6.3 us	58.1 us
65K / 25%	38.0 us	22.0 us	87.8 us	17.0 us	24.7 us	240.8 us
1M / 6.25%	35.3 us	105.1 us	115.9 us	18.2 us	381.4 us	5.77 ms

The result is deliberately not presented as a universal hash replacement. A prebuilt hash set wins
the probe-only comparison. Sorted membership avoids that hash construction, stays useful when the
sorted representation already exists, and prevents full-member rescans for independent ordered
chunks. Engine integrations should cost both alternatives.

Feedback is requested on the API/type names and placement under search_sorted.