We're already in config namespace so things like config::IndexType or config::ValidateIndex are redundant, just IndexType/ValidateIndex is enough

what's the point of typename here? It's already a fully resolved type due to <config::IndexType>

same, typename not needed

same with redundant config:: and typename Option<..>

redundant typename and config

redundant config

IDK if I should comment on this code since you've just moved it to another place, but the else branch does not have the values.reserve

This loop constantly checking for i != 0.
Moreover, the first iteration of this loop will always look like

if (values[0].second <= values[0].second) //current_group_max_index is zero
    current_group_max_index = 0;

since i == 0 and !is_first_group is false.

So we can just start from i = 1 and remove that check

Lambdas looks identical, I would do

std::sort(values.begin(), values.end(),
          [](auto const& p1, auto const& p2) {
              return Ascending ? p1.first < p2.first : p1.first > p2.first;
          });

Though I'm not sure whether we can use constexpr values with ternary operator, but I think that with lambdas we can

IMHO it is better to define

constexpr bool is_ascending(od::Ordering order) {
    return order == od::Ordering::ascending;
}

and then use if constexpr (is_ascending(Ordering))
Or maybe even

template <od::Ordering Ordering>
concept Ascending = (Ordering == od::Ordering::ascending);
template <od::Ordering Ordering>
concept Descending = (Ordering == od::Ordering::descending);

and do

    if constexpr (Ascending<Ordering>) {
        cs_asc_[key].emplace(value);
    } else {
        cs_desc_[key].emplace(value);
    }

Use AscCanonicalOD and DescCanonicalOD here

I suggest

template <Ordering Ordering, std::totally_ordered T>
bool Comp(T const& lhs, T const& rhs) {
    if constexpr (Ordering ==  Ordering::ascending) {
        return std::less<>{}(lhs, rhs);
    } else {
        return std::greater<>{}(lhs, rhs);
    }
}

And then we won't need to define Comp each time (I saw that the same Comp gets defined second time in Implement aod verifier and cover it with tests)

        std::sort(values.begin(), values.end(), [](auto const& p1, auto const& p2) {
            return od::Comp<Ordering>(p1.left_value, p2.left_value);
        });

Maybe std::span<const model::ColumnIndex>?
We're only need a view of a sequence and this way we're explicitly saying that we want model::ColumnIndex objects there

Store DataFrame in ComplexStrippedPartition as raw pointer:

A commit description explaining why will come in handy

Again, some commit description will be nice

will allow more types

Also maybe just std::ostream instead of stringstream? It seems like we can safely accept any output stream here

since we're only performing output operations

use range-based for for example like so

Use Comp defined as a result of fixing previous issue

Where is this function gets used? It seems like we don't need it

we use value only as value.right_value, so let's just define it as int value_right = values[i].right_value;

I would extract values.size() to like and n variable since it gets used a lot

why is longest_subseq_elements is an unordered_set? Can't we just define like vector<bool> of boost::dynamic_bitset with values.size() = n size and do a faster lookup this way?
Well, maybe not if n is much more that the size of longest subseq elements..
Like

Overall, a lot of code duplication in these two methods. The lines:

    od::RemovalSetAsVec removal_set;

    for (size_t begin_pointer = 0; begin_pointer < sp_begins_->size() - 1; begin_pointer  ) {
        size_t const group_begin = (*sp_begins_)[begin_pointer];
        size_t const group_end = (*sp_begins_)[begin_pointer   1];

        od::RemovalSetAsVec cur_removal_set = SplitRemovalSet(values);
        removal_set.insert(removal_set.end(), cur_removal_set.begin(), cur_removal_set.end());

are virtually the same in both cases.

I think we can create a helper function like this:

void ProcessGroups(const std::vector<size_t>& begins, std::function</*type*/> collect_values, od::RemovalSetAsVec& removal_set)
{
    for (size_t begin_pointer = 0; begin_pointer < begins.size() - 1;   begin_pointer) {
        size_t const group_begin = begins[begin_pointer];
        size_t const group_end = begins[begin_pointer   1];

        std::vector<ValueAndIndex> values;
        collect_values(group_begin, group_end, values);

        od::RemovalSetAsVec cur_removal_set = SplitRemovalSet(values);
        removal_set.insert(
            removal_set.end(),
            std::make_move_iterator(cur_removal_set.begin()),
            std::make_move_iterator(cur_removal_set.end())
        );
    }
}

And use it like so:

od::RemovalSetAsVec ComplexStrippedPartition::CommonSplitRemovalSet(model::ColumnIndex right) const {
    od::RemovalSetAsVec removal_set;

    ProcessGroups( *sp_begins_,
        [this, right](size_t group_begin, size_t group_end, std::vector<ValueAndIndex>& values) {
            values.reserve(group_end - group_begin);
            for (size_t i = group_begin; i < group_end;   i) {
                model::TupleIndex const tuple_index = (*sp_indexes_)[i];
                values.emplace_back(data_->GetValue(tuple_index, right), tuple_index);
            }
        },
        removal_set
    );

    return removal_set;
}

we don't need cur_removal_set object anymore - might as well move elements to a removal_set:

removal_set.insert(
            removal_set.end(),
            std::make_move_iterator(cur_removal_set.begin()),
            std::make_move_iterator(cur_removal_set.end())
        );

Oh, nevermind, there are integers there

we know how much time we will call emplace_back, so we should reserve memory to avoid reallocations:
values.reserve(group_end - group_begin);

same thing here with make_move_iterator

Well, we can avoid reallocations here, but this might increase the constant factor in time complexity. I'm not sure if it's worth it, as it depends on how frequently this function is called and the number of reallocations. However, we can do something like this:

            size_t total_values = 0;
            for (size_t i = group_begin; i < group_end;   i) {
                DataFrame::Range const& range = (*rb_indexes_)[i];
                total_values  = range.second - range.first   1;
            }
            values.reserve(total_values);

add using namespace config::names; and do :%s/config::names:://g

Idk if this is possible, but can we add some descriptive names to individual tests in this test suite? Like make those comments {}: Col5 -> Col1 into names? If it's hard, then feel free to ignore

since we're specifying type in static_cast, we can just use auto expected_error

separate with empty line

separate with empty line