Repository: duckdb/duckdb
File: src/storage/table/scan_state.cpp (C++)

Code before:

void RowGroupReorderer::SetRowGroupVectorWithLimit(
    const multimap<Value, pair<unique_ptr<BaseStatistics>, reference<RowGroup>>> &row_group_map) {
	D_ASSERT(row_limit.IsValid());

	const auto stat_type = order_type == RowGroupOrderType::ASC ? OrderByStatistics::MIN : OrderByStatistics::MAX;
	ordered_row_groups.reserve(row_group_map.size());

	Value previous_key;
	if (order_type == RowGroupOrderType::ASC) {
		auto it = row_group_map.begin();
		auto end = row_group_map.end();
		AddRowGroups(it, end, ordered_row_groups, row_limit.GetIndex(), column_type, stat_type);
	} else {
		auto it = row_group_map.rbegin();
		auto end = row_group_map.rend();
		AddRowGroups(it, end, ordered_row_groups, row_limit.GetIndex(), column_type, stat_type);
	}
}

bool RowGroupReorderer::AddRowGroupWithLimit(const Value &order_by_value, BaseStatistics &row_group_stats,
                                             reference<RowGroup> current_row_group, const Value &previous_order_by,
                                             reference<BaseStatistics> &last_row_group_stats, idx_t &qualifying_tuples,
                                             idx_t &seen_tuples, OrderByStatistics stat_type) {
	auto new_row_group_boundary = RetrieveStat(row_group_stats, stat_type, column_type);
	if ((stat_type == OrderByStatistics::MAX && new_row_group_boundary < order_by_value) ||
	    (stat_type == OrderByStatistics::MIN && new_row_group_boundary > order_by_value)) {
		// Row groups do not overlap: we can guarantee that the tuples up until now qualify
		last_row_group_stats = row_group_stats;
		qualifying_tuples = seen_tuples;
	} else {
		if (!previous_order_by.IsNull() && order_by_value != previous_order_by) {
			// Only if the opposite boundaries are inequal, we can guarantee to have >= 1 distinct qualifying rows.
			// We need distinctness as there may be secondary orders that qualify rows in later row groups.
			qualifying_tuples++;
		}
	}
	if (qualifying_tuples >= row_limit.GetIndex()) {
		return true;
	}

	seen_tuples += current_row_group.get().count;
	ordered_row_groups.emplace_back(current_row_group);
	return false;
}

optional_ptr<RowGroup> RowGroupReorderer::GetRootSegment(RowGroupSegmentTree &row_groups) {
	if (initialized) {
		return ordered_row_groups.empty() ? nullptr : ordered_row_groups[0];
	}


Review comment (suggestion):
We should also check null values here - if there are null values we only have at least 1 qualifying tuple (if `min = max`) or 2 qualifying tuples (if `min != max`).

Code after:
	column_has_filter[filter.scan_column_index] = false;
	always_true_filters++;
}

RowGroupReorderer::RowGroupReorderer(const RowGroupOrderOptions &options)
    : column_idx(options.column_idx), order_by(options.order_by), order_type(options.order_type),
      column_type(options.column_type), row_limit(options.row_limit), offset(0), initialized(false) {
}

optional_ptr<SegmentNode<RowGroup>> RowGroupReorderer::GetNextRowGroup(SegmentNode<RowGroup> &row_group) {
	D_ASSERT(RefersToSameObject(ordered_row_groups[offset].get(), row_group));
	if (offset >= ordered_row_groups.size() - 1) {
		return nullptr;
	}
	return ordered_row_groups[++offset].get();
}

Value RowGroupReorderer::RetrieveStat(const BaseStatistics &stats, OrderByStatistics order_by,
                                      OrderByColumnType column_type) {
	switch (order_by) {
	case OrderByStatistics::MIN:
		return column_type == OrderByColumnType::NUMERIC ? NumericStats::Min(stats) : StringStats::Min(stats);
	case OrderByStatistics::MAX:
		return column_type == OrderByColumnType::NUMERIC ? NumericStats::Max(stats) : StringStats::Max(stats);
	}
	return Value();
}

void SetRowGroupVectorWithLimit(const multimap<Value, RowGroupMapEntry> &row_group_map, const optional_idx row_limit,
                                const RowGroupOrderType order_type, const OrderByColumnType column_type,
                                vector<reference<SegmentNode<RowGroup>>> &ordered_row_groups) {
	D_ASSERT(row_limit.IsValid());

	const auto stat_type = order_type == RowGroupOrderType::ASC ? OrderByStatistics::MIN : OrderByStatistics::MAX;
	ordered_row_groups.reserve(row_group_map.size());

	Value previous_key;
	if (order_type == RowGroupOrderType::ASC) {
		auto it = row_group_map.begin();
		auto end = row_group_map.end();
		AddRowGroups(it, end, ordered_row_groups, row_limit.GetIndex(), column_type, stat_type);
	} else {
		auto it = row_group_map.rbegin();
		auto end = row_group_map.rend();
		AddRowGroups(it, end, ordered_row_groups, row_limit.GetIndex(), column_type, stat_type);
	}
}

optional_ptr<SegmentNode<RowGroup>> RowGroupReorderer::GetRootSegment(RowGroupSegmentTree &row_groups) {
	if (initialized) {
		if (ordered_row_groups.empty()) {