Function findKeyPositions

src/DataTypes/DataTypeMapHelpers.cpp:95–149

/// For each row in [start, end), finds the flat index of the matching key.
template <typename Matcher>
void findKeyPositions(
    const ColumnArray::Offsets & offsets,
    const Matcher & matcher,
    size_t start,
    size_t end,
    PaddedPODArray<size_t> & matched_positions)
{
    size_t num_rows = end - start;
    matched_positions.resize(num_rows);

    /// Relative offset of the key within the map from the previous row.
    /// Used for position prediction.
    size_t predicted_relative_pos = 0;
    bool have_prediction = false;

    for (size_t i = start; i < end; ++i)
    {
        size_t positions_row_idx = i - start;
        size_t offset_start = offsets[ssize_t(i) - 1];
        size_t offset_end = offsets[i];

        /// Try the predicted position first.
        if (have_prediction)
        {
            size_t predicted_pos = offset_start + predicted_relative_pos;
            if (predicted_pos < offset_end && matcher.match(predicted_pos))
            {
                matched_positions[positions_row_idx] = predicted_pos;
                continue;
            }
        }

        /// Prediction missed or not available. Fall back to linear scan.
        bool found = false;
        for (size_t j = offset_start; j < offset_end; ++j)
        {
            if (matcher.match(j))
            {
                matched_positions[positions_row_idx] = j;
                predicted_relative_pos = j - offset_start;
                have_prediction = true;
                found = true;
                break;
            }
        }

        if (!found)
        {
            /// Keep the prediction unchanged: if only this row is missing the key,
            /// subsequent rows likely have the same key order, so the prediction
            /// may still be valid. A wrong prediction costs only one extra match call.
            matched_positions[positions_row_idx] = KEY_NOT_FOUND;
        }
    }
}

/// Dispatches to the appropriate specialized matcher based on the key column type,
/// then calls findKeyPositions with that matcher.