tp: add IndexScan, which looks rows up through a dataframe's index Equalities on columns with an index, like a `CREATE PERFETTO INDEX` on a track id, are answered by the dataframe interpreter by searching the index. On the executor they cost a full scan per run. Before the dataframe module's queries can move to the executor, it needs the same lookup, finding the same rows in the same order. IndexScan narrows the index's entries by each equality on its leading columns, through filter::SearchIndexEqual as the interpreter does, and reads the rows in the index's order. Nothing is sorted or copied: each batch is a window of the dataframe's storage selecting a run of increasing rows, so rows far apart take a batch each. Any other condition is left to a Filter after the scan. The differential test now builds indexes and runs index plans. No callers yet.
diff --git a/Android.bp b/Android.bp index fd85756..bdb6977 100644 --- a/Android.bp +++ b/Android.bp
@@ -17902,6 +17902,7 @@ "src/trace_processor/core/exec/group_table.cc", "src/trace_processor/core/exec/grouped_sort.cc", "src/trace_processor/core/exec/hash_aggregate.cc", + "src/trace_processor/core/exec/index_scan.cc", "src/trace_processor/core/exec/interval_fill_gaps.cc", "src/trace_processor/core/exec/interval_flatten.cc", "src/trace_processor/core/exec/interval_intersect.cc",
diff --git a/BUILD b/BUILD index 1ea6dba..322832f 100644 --- a/BUILD +++ b/BUILD
@@ -2633,6 +2633,8 @@ "src/trace_processor/core/exec/grouped_sort.h", "src/trace_processor/core/exec/hash_aggregate.cc", "src/trace_processor/core/exec/hash_aggregate.h", + "src/trace_processor/core/exec/index_scan.cc", + "src/trace_processor/core/exec/index_scan.h", "src/trace_processor/core/exec/interval_fill_gaps.cc", "src/trace_processor/core/exec/interval_fill_gaps.h", "src/trace_processor/core/exec/interval_flatten.cc",
diff --git a/src/trace_processor/core/exec/BUILD.gn b/src/trace_processor/core/exec/BUILD.gn index 064cd58..dd38586 100644 --- a/src/trace_processor/core/exec/BUILD.gn +++ b/src/trace_processor/core/exec/BUILD.gn
@@ -49,6 +49,8 @@ "grouped_sort.h", "hash_aggregate.cc", "hash_aggregate.h", + "index_scan.cc", + "index_scan.h", "interval_fill_gaps.cc", "interval_fill_gaps.h", "interval_flatten.cc",
diff --git a/src/trace_processor/core/exec/dataframe_windows.h b/src/trace_processor/core/exec/dataframe_windows.h index 22dfff9..d9b7e80 100644 --- a/src/trace_processor/core/exec/dataframe_windows.h +++ b/src/trace_processor/core/exec/dataframe_windows.h
@@ -18,17 +18,20 @@ #define SRC_TRACE_PROCESSOR_CORE_EXEC_DATAFRAME_WINDOWS_H_ #include <algorithm> +#include <array> #include <cstdint> #include <memory> #include <vector> #include "perfetto/base/compiler.h" +#include "perfetto/base/logging.h" #include "src/trace_processor/core/dataframe/types.h" #include "src/trace_processor/core/exec/column_view.h" #include "src/trace_processor/core/exec/context.h" #include "src/trace_processor/core/exec/row_batch.h" #include "src/trace_processor/core/exec/selection.h" #include "src/trace_processor/core/util/range.h" +#include "src/trace_processor/core/util/span.h" namespace perfetto::trace_processor::core::exec { @@ -110,6 +113,67 @@ uint32_t next_ = 0; }; +// Reads a list of a dataframe's rows a batch at a time, in the list's order, +// for the sources which find the rows they read as a list. Nothing is copied: +// each batch is a window over a run of the list's rows which increase and fit +// in one, and its selection keeps those rows. A batch ends where the list +// stops increasing, so a list in increasing order of rows close together is +// read in few batches; any other in more, smaller ones. +class RowListReader { + public: + void Init( + const std::vector<std::shared_ptr<const dataframe::Column>>& columns, + Context& context) { + windows_.Init(columns, context); + } + + // Reads `rows`, which must stay unchanged until read. + void Start(Span<const uint32_t> rows) { + windows_.Rewind(); + next_ = rows.b; + end_ = rows.e; + last_end_ = 0; + } + + // Points `out` at the next batch of the rows. False once all are read. + bool Read(RowBatch& out) { + if (next_ == end_) { + return false; + } + uint32_t first = *next_++; + // A window can only move forward: a row before it starts the next run + // of windows from the beginning. + if (first < last_end_) { + windows_.Rewind(); + } + offsets_[0] = 0; + uint32_t count = 1; + for (; next_ != end_; ++next_) { + uint32_t offset = *next_ - first; + if (*next_ < first || offset >= kMaxBatchRows || + offset <= offsets_[count - 1]) { + break; + } + offsets_[count++] = offset; + } + uint32_t window = offsets_[count - 1] + 1; + windows_.Fill(first, window, out); + out.mutable_selection().KeepRows( + Span<const uint32_t>(offsets_.data(), offsets_.data() + count)); + last_end_ = first + window; + return true; + } + + private: + DataframeWindows windows_; + const uint32_t* next_ = nullptr; + const uint32_t* end_ = nullptr; + // Where the last window ended. + uint32_t last_end_ = 0; + // The rows of the current batch, from the first. + std::array<uint32_t, kMaxBatchRows> offsets_; +}; + } // namespace perfetto::trace_processor::core::exec #endif // SRC_TRACE_PROCESSOR_CORE_EXEC_DATAFRAME_WINDOWS_H_
diff --git a/src/trace_processor/core/exec/index_scan.cc b/src/trace_processor/core/exec/index_scan.cc new file mode 100644 index 0000000..f5b6804 --- /dev/null +++ b/src/trace_processor/core/exec/index_scan.cc
@@ -0,0 +1,140 @@ +/* + * Copyright (C) 2026 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "src/trace_processor/core/exec/index_scan.h" + +#include <cstdint> +#include <memory> +#include <utility> +#include <variant> +#include <vector> + +#include "perfetto/base/compiler.h" +#include "perfetto/base/logging.h" +#include "perfetto/ext/base/variant.h" +#include "src/trace_processor/containers/string_pool.h" +#include "src/trace_processor/core/common/filter_kernels.h" +#include "src/trace_processor/core/common/filter_value_cast.h" +#include "src/trace_processor/core/common/null_types.h" +#include "src/trace_processor/core/common/storage_types.h" +#include "src/trace_processor/core/dataframe/types.h" +#include "src/trace_processor/core/exec/context.h" +#include "src/trace_processor/core/exec/filter_value.h" +#include "src/trace_processor/core/exec/operator.h" +#include "src/trace_processor/core/exec/row_batch.h" +#include "src/trace_processor/core/util/bit_vector.h" +#include "src/trace_processor/core/util/slab.h" +#include "src/trace_processor/core/util/span.h" + +namespace perfetto::trace_processor::core::exec { +namespace { + +using filter::CastFilterValueResult; + +bool StoresNoValueForNulls(const dataframe::Column& column) { + const auto& n = column.null_storage.nullability(); + return n.Is<SparseNull>() || n.Is<SparseNullWithPopcountAlways>() || + n.Is<SparseNullWithPopcountUntilFinalization>(); +} + +// Where a column's values are stored, whatever their type. +const void* StorageOf(const dataframe::Column& column) { + return std::visit([](auto* p) { return static_cast<const void*>(p); }, + column.storage.data()); +} + +} // namespace + +IndexScan::IndexScan( + std::vector<std::shared_ptr<const dataframe::Column>> columns, + const dataframe::Index& index, + std::vector<Equality> equalities, + const StringPool* pool) + : columns_(std::move(columns)), + permutation_(index.permutation_vector()), + equalities_(std::move(equalities)), + pool_(pool) { + PERFETTO_CHECK(equalities_.size() <= index.columns().size()); + for (const Equality& eq : equalities_) { + PERFETTO_CHECK(!eq.column->storage.type().Is<Id>()); + } +} + +IndexScan::~IndexScan() = default; +IndexScan::State::~State() = default; + +std::unique_ptr<OperatorState> IndexScan::MakeState(Context& context) const { + auto state = std::make_unique<State>(); + state->reader.Init(columns_, context); + state->context = &context; + state->popcounts.resize(equalities_.size()); + for (uint32_t i = 0; i < equalities_.size(); ++i) { + const dataframe::Column& column = *equalities_[i].column; + const BitVector* nulls = column.null_storage.MaybeGetNullBitVector(); + if (StoresNoValueForNulls(column)) { + state->popcounts[i] = nulls->PrefixPopcount(); + } + state->columns.push_back( + {column.storage.type(), column.null_storage.nullability(), + StorageOf(column), nulls, state->popcounts[i].data(), pool_}); + } + return state; +} + +void IndexScan::Rewind(OperatorState& state) const { + state.Cast<State>().searched = false; +} + +Span<const uint32_t> IndexScan::Find(const State& s) const { + // The searches only read the index. + auto* b = const_cast<uint32_t*>(permutation_->data()); + Span<uint32_t> entries(b, b + permutation_->size()); + const FilterValue* values = s.context->filter_values().b; + for (uint32_t i = 0; i < equalities_.size() && !entries.empty(); ++i) { + const Equality& eq = equalities_[i]; + PERFETTO_DCHECK(eq.value < s.context->filter_values().size()); + const FilterValue& cast = values[eq.value]; + if (cast.value.validity == CastFilterValueResult::kNoneMatch) { + entries.e = entries.b; + break; + } + if (cast.value.validity == CastFilterValueResult::kAllMatch) { + continue; + } + const filter::IndexColumn& column = s.columns[i]; + if (column.type.Is<String>()) { + // A string compared by = was resolved to its id as it was cast. + entries = filter::SearchIndexEqual( + column, + CastFilterValueResult::Value(pool_->Get(cast.string_id).c_str()), + entries); + } else { + entries = filter::SearchIndexEqual(column, cast.value.value, entries); + } + } + return Span<const uint32_t>(entries.b, entries.e); +} + +bool IndexScan::GetData(RowBatch& out, OperatorState& state) const { + State& s = state.Cast<State>(); + if (PERFETTO_UNLIKELY(!s.searched)) { + s.reader.Start(Find(s)); + s.searched = true; + } + return s.reader.Read(out); +} + +} // namespace perfetto::trace_processor::core::exec
diff --git a/src/trace_processor/core/exec/index_scan.h b/src/trace_processor/core/exec/index_scan.h new file mode 100644 index 0000000..c768591 --- /dev/null +++ b/src/trace_processor/core/exec/index_scan.h
@@ -0,0 +1,107 @@ +/* + * Copyright (C) 2026 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef SRC_TRACE_PROCESSOR_CORE_EXEC_INDEX_SCAN_H_ +#define SRC_TRACE_PROCESSOR_CORE_EXEC_INDEX_SCAN_H_ + +#include <cstdint> +#include <memory> +#include <vector> + +#include "src/trace_processor/containers/string_pool.h" +#include "src/trace_processor/core/common/filter_kernels.h" +#include "src/trace_processor/core/dataframe/types.h" +#include "src/trace_processor/core/exec/context.h" +#include "src/trace_processor/core/exec/dataframe_windows.h" +#include "src/trace_processor/core/exec/operator.h" +#include "src/trace_processor/core/exec/row_batch.h" +#include "src/trace_processor/core/util/slab.h" +#include "src/trace_processor/core/util/span.h" + +namespace perfetto::trace_processor::core::exec { + +// Reads the rows of a dataframe which an index finds for equalities on its +// leading columns. +// +// An index lists a dataframe's rows in the order of their values in its +// columns, so the rows equal to a value in its first column are together in +// the list, those also equal to a value in its second column together within +// them, and so on. Each equality narrows the part of the list searched, +// comparing with one of the run's filter values (see +// Context::SetFilterValues). Any other condition of the plan, including on a +// sorted column, is left to a Filter after the scan. +// +// The rows are read in the index's order, as the dataframe interpreter +// returns them, with nothing copied or sorted: each batch is a window of the +// dataframe's storage selecting a run of the rows found (see RowListReader). +// +// The searches run once per run, when the first batch is asked for, and find +// exactly the rows the dataframe interpreter's would. The columns must be +// finalized. +class IndexScan final : public Source { + public: + static constexpr char kType = 0; + const void* type() const override { return &kType; } + + // = on one of the index's columns. Columns are given in the index's order, + // from its first. + struct Equality { + std::shared_ptr<const dataframe::Column> column; + // The filter value compared with. + uint32_t value = 0; + }; + + // Reads `columns` of a dataframe, at the rows of `index` which every one of + // `equalities` keeps. `pool` holds the strings of the columns searched and + // must outlive the scan. + IndexScan(std::vector<std::shared_ptr<const dataframe::Column>> columns, + const dataframe::Index& index, + std::vector<Equality> equalities, + const StringPool* pool); + ~IndexScan() override; + + std::unique_ptr<OperatorState> MakeState(Context& context) const override; + bool GetData(RowBatch& out, OperatorState& state) const override; + void Rewind(OperatorState& state) const override; + + private: + friend class PipelineFormatter; + + struct State : OperatorState { + ~State() override; + RowListReader reader; + const Context* context = nullptr; + // By equality, for a column which does not store a value per row, the + // bits set before each word of its null bit vector. + std::vector<Slab<uint32_t>> popcounts; + // By equality, its column, as filter::SearchIndexEqual takes it. + std::vector<filter::IndexColumn> columns; + // Whether this run's searches have run. + bool searched = false; + }; + + // The entries of the index this run reads. + Span<const uint32_t> Find(const State& s) const; + + std::vector<std::shared_ptr<const dataframe::Column>> columns_; + std::shared_ptr<std::vector<uint32_t>> permutation_; + std::vector<Equality> equalities_; + const StringPool* pool_; +}; + +} // namespace perfetto::trace_processor::core::exec + +#endif // SRC_TRACE_PROCESSOR_CORE_EXEC_INDEX_SCAN_H_
diff --git a/src/trace_processor/core/exec/lookup_benchmark.cc b/src/trace_processor/core/exec/lookup_benchmark.cc index 7c9cb6b..a3feb33 100644 --- a/src/trace_processor/core/exec/lookup_benchmark.cc +++ b/src/trace_processor/core/exec/lookup_benchmark.cc
@@ -41,6 +41,7 @@ #include "src/trace_processor/core/exec/eq_scans.h" #include "src/trace_processor/core/exec/filter.h" #include "src/trace_processor/core/exec/filter_value.h" +#include "src/trace_processor/core/exec/index_scan.h" #include "src/trace_processor/core/exec/operator.h" #include "src/trace_processor/core/exec/pipeline.h" #include "src/trace_processor/core/exec/row_cursor.h" @@ -135,25 +136,34 @@ return *args; } -// Shaped like the slice table: an id, ts ascending and a dur. -enum SliceCol : uint32_t { kTs, kDur, kSliceId }; +// Shaped like the slice table: an id, ts ascending, a dur, and an indexed +// track with about eight slices each. +enum SliceCol : uint32_t { kTs, kDur, kTrack, kSliceId }; struct Slices { Slices() { std::minstd_rand rng(2); - dataframe::AdhocDataframeBuilder builder({"ts", "dur"}, &pool); + dataframe::AdhocDataframeBuilder builder({"ts", "dur", "track"}, &pool); int64_t ts = int64_t{1} << 40; for (uint32_t i = 0; i < kRows; ++i) { ts += 1 + rng() % 100; PERFETTO_CHECK(builder.PushNonNull(kTs, ts)); PERFETTO_CHECK(builder.PushNonNull( kDur, (int64_t{1} << 40) + int64_t(rng() % 1000))); + uint32_t track = static_cast<uint32_t>(rng() % (kRows / 8)); + PERFETTO_CHECK(builder.PushNonNull(kTrack, int64_t{track})); all_ts.push_back(ts); + all_tracks.push_back(track); } auto built = std::move(builder).Build(); PERFETTO_CHECK(built.ok()); - df = std::make_unique<dataframe::Dataframe>(std::move(*built)); + uint32_t track = kTrack; + auto index = built->BuildIndex(&track, &track + 1); + PERFETTO_CHECK(index.ok()); + df = std::make_unique<dataframe::Dataframe>( + built->AddIndex(std::move(*index))); PERFETTO_CHECK(df->column(kTs).sort_state.Is<Sorted>()); + PERFETTO_CHECK(df->column(kTrack).sort_state.Is<Unsorted>()); PERFETTO_CHECK(df->column(kSliceId).storage.type().Is<Id>()); for (uint32_t i = 0; i < kLookups; ++i) { rows.push_back(static_cast<uint32_t>(rng() % kRows)); @@ -163,6 +173,7 @@ StringPool pool; std::unique_ptr<dataframe::Dataframe> df; std::vector<int64_t> all_ts; + std::vector<uint32_t> all_tracks; std::vector<uint32_t> rows; }; @@ -463,6 +474,48 @@ BENCHMARK(BM_TsEq_SortedScan)->Arg(64)->Arg(kLookups); // ----------------------------------------------------------------------------- +// track = ?, through an index, reading every row found +// ----------------------------------------------------------------------------- + +void BM_IndexEq_Interpreter(benchmark::State& state) { + const Slices& s = GetSlices(); + dataframe::TypedCursor cursor(s.df.get(), {{kTrack, 0, Eq{}, std::nullopt}}, + {}); + uint32_t i = 0; + auto n = static_cast<uint32_t>(state.range(0)); + uint32_t rows = 0; + for (auto _ : state) { + cursor.SetFilterValueUnchecked(0, s.all_tracks[s.rows[i++ % n]]); + for (cursor.ExecuteUnchecked(); !cursor.Eof(); cursor.Next()) { + rows += cursor.RowIndex() != 0; + } + } + benchmark::DoNotOptimize(rows); +} +BENCHMARK(BM_IndexEq_Interpreter)->Arg(64)->Arg(kLookups); + +void BM_IndexEq_IndexScan(benchmark::State& state) { + const Slices& s = GetSlices(); + ExecLookup lookup( + std::make_unique<IndexScan>( + Columns(*s.df, {kSliceId}), s.df->indexes()[0], + std::vector<IndexScan::Equality>{{s.df->shared_column(kTrack), 0}}, + &s.pool), + {}, {{Uint32{}, Eq{}}}, &s.pool); + uint32_t i = 0; + auto n = static_cast<uint32_t>(state.range(0)); + uint32_t rows = 0; + for (auto _ : state) { + lookup.Set(0, int64_t{s.all_tracks[s.rows[i++ % n]]}); + for (bool ok = lookup.Open(); ok; ok = lookup.cursor().Next()) { + rows += lookup.cursor().Value<uint32_t>(0) != 0; + } + } + benchmark::DoNotOptimize(rows); +} +BENCHMARK(BM_IndexEq_IndexScan)->Arg(64)->Arg(kLookups); + +// ----------------------------------------------------------------------------- // ts >= ? AND ts < ?, reading dur for every row // -----------------------------------------------------------------------------
diff --git a/src/trace_processor/core/exec/pipeline_formatter.cc b/src/trace_processor/core/exec/pipeline_formatter.cc index 286024e..4bb0cd0 100644 --- a/src/trace_processor/core/exec/pipeline_formatter.cc +++ b/src/trace_processor/core/exec/pipeline_formatter.cc
@@ -33,6 +33,7 @@ #include "src/trace_processor/core/exec/filter.h" #include "src/trace_processor/core/exec/grouped_sort.h" #include "src/trace_processor/core/exec/hash_aggregate.h" +#include "src/trace_processor/core/exec/index_scan.h" #include "src/trace_processor/core/exec/interval_fill_gaps.h" #include "src/trace_processor/core/exec/interval_flatten.h" #include "src/trace_processor/core/exec/interval_intersect.h" @@ -191,6 +192,9 @@ if (source.Is<SmallValueEqScan>()) { return "SmallValueEqScan"; } + if (source.Is<IndexScan>()) { + return "IndexScan"; + } return "Source"; }
diff --git a/src/trace_processor/core/exec/search_scans_unittest.cc b/src/trace_processor/core/exec/search_scans_unittest.cc index 6d355cd..78d3b23 100644 --- a/src/trace_processor/core/exec/search_scans_unittest.cc +++ b/src/trace_processor/core/exec/search_scans_unittest.cc
@@ -40,6 +40,7 @@ #include "src/trace_processor/core/exec/eq_scans.h" #include "src/trace_processor/core/exec/filter.h" #include "src/trace_processor/core/exec/filter_value.h" +#include "src/trace_processor/core/exec/index_scan.h" #include "src/trace_processor/core/exec/operator.h" #include "src/trace_processor/core/exec/pipeline.h" #include "src/trace_processor/core/exec/row_batch.h" @@ -81,13 +82,25 @@ const std::vector<Value>* values = nullptr; }; -enum Col : uint32_t { kTs, kSet, kSmall, kNeg, kDbl, kName, kDur, kMaybe, kId }; +enum Col : uint32_t { + kTs, + kSet, + kSmall, + kNeg, + kDbl, + kName, + kDur, + kMaybe, + kTag, + kId +}; class SearchScansDiffTest : public ::testing::Test { protected: void Build(uint32_t rows) { dataframe::AdhocDataframeBuilder builder( - {"ts", "set", "small", "neg", "dbl", "name", "dur", "maybe"}, &pool_); + {"ts", "set", "small", "neg", "dbl", "name", "dur", "maybe", "tag"}, + &pool_); int64_t ts = int64_t{1} << 33; uint32_t set = 0; uint32_t small = 1; @@ -121,9 +134,22 @@ maybe_.emplace_back(kBig + int64_t(rng_() % 50)); PERFETTO_CHECK(builder.PushNonNull(kMaybe, *maybe_.back())); } + PERFETTO_CHECK(builder.PushNonNull( + kTag, + pool_.InternString( + base::StackString<16>("t%u", static_cast<uint32_t>(rng_() % 20)) + .string_view()))); } auto df = std::move(builder).Build(); PERFETTO_CHECK(df.ok()); + // Indexes on unsorted columns of each kind: an integer, a sparse nullable + // integer, and a string, the last two with a second column. + for (std::vector<uint32_t> cols : std::vector<std::vector<uint32_t>>{ + {kDur}, {kMaybe, kDur}, {kTag, kDur}}) { + auto index = df->BuildIndex(cols.data(), cols.data() + cols.size()); + PERFETTO_CHECK(index.ok()); + *df = df->AddIndex(std::move(*index)); + } df_ = std::make_unique<dataframe::Dataframe>(std::move(*df)); PERFETTO_CHECK(df_->column_names()[kId] == dataframe::kAutoIdColumnName); } @@ -192,8 +218,9 @@ } // An executor plan for a logical plan which only filters: a scan doing the - // searches, if any, then a Filter for the rest. One equality search which - // needs no dispatch gets its own scan; anything else gets a SortedScan. + // searches, if any, then a Filter for the rest. A plan using an index gets + // an IndexScan; one equality search which needs no dispatch gets its own + // scan; anything else gets a SortedScan. struct ExecPlan { std::unique_ptr<Source> scan; std::unique_ptr<Pipeline> pipeline; @@ -207,7 +234,10 @@ ExecPlan out; out.casters.resize(plan.filter_value_count); std::vector<SortedScan::Search> searches; + std::vector<Filter::Condition> searches_as_conditions; std::vector<Filter::Condition> conditions; + std::vector<IndexScan::Equality> equalities; + const dataframe::Index* index = nullptr; bool empty = false; for (const auto& op : plan.ops) { if (const auto* f = std::get_if<dataframe::logical::Filter>(&op)) { @@ -242,9 +272,21 @@ if (kind) { searches.push_back( {df_->shared_column(f->col), *kind, f->op, *f->value_index}); + searches_as_conditions.push_back({f->col, f->op, *f->value_index}); } else { conditions.push_back({f->col, f->op, f->value_index.value_or(0)}); } + } else if (const auto* idx = + std::get_if<dataframe::logical::IndexFilter>(&op)) { + for (const auto& p : idx->predicates) { + if (!p.op.Is<Eq>()) { + return std::nullopt; + } + out.casters[*p.value_index] = + GetFilterValueCaster<Values>(p.storage, p.op); + equalities.push_back({df_->shared_column(p.col), *p.value_index}); + } + index = &df_->indexes()[idx->index]; } else if (std::holds_alternative<dataframe::logical::Empty>(op)) { empty = true; } else if (!std::holds_alternative<dataframe::logical::Scan>(op) && @@ -260,6 +302,13 @@ if (empty) { // Provably empty, whatever else the plan does. out.scan = std::make_unique<DataframeScan>(std::move(columns), 0); + } else if (index) { + // Through an index, any search of a sorted column is left to the Filter. + conditions.insert(conditions.end(), searches_as_conditions.begin(), + searches_as_conditions.end()); + out.scan = std::make_unique<IndexScan>(std::move(columns), *index, + std::move(equalities), &pool_); + ++index_scans_; } else if (searches.empty()) { out.scan = std::make_unique<DataframeScan>(std::move(columns), rows); } else if (one && one->kind == K::kSetIdEq) { @@ -300,6 +349,7 @@ uint32_t set_id_eq_scans_ = 0; uint32_t small_value_eq_scans_ = 0; uint32_t sorted_scans_ = 0; + uint32_t index_scans_ = 0; }; TEST_F(SearchScansDiffTest, FindsWhatTheInterpreterFinds) { @@ -315,11 +365,23 @@ std::vector<std::pair<uint32_t, Op>> shape; uint32_t filters = 1 + rng_() % 3; for (uint32_t i = 0; i < filters; ++i) { - // Favour the sorted columns: they are what is searched. + // Favour the sorted and indexed columns: they are what is searched. static constexpr uint32_t kSorted[] = {kTs, kSet, kSmall, kNeg, kDbl, kName, kId}; - uint32_t col = rng_() % 4 ? kSorted[rng_() % 7] - : static_cast<uint32_t>(rng_() % 9); + static constexpr uint32_t kIndexed[] = {kDur, kMaybe, kTag}; + uint32_t col; + switch (rng_() % 4) { + case 0: + case 1: + col = kSorted[rng_() % 7]; + break; + case 2: + col = kIndexed[rng_() % 3]; + break; + default: + col = static_cast<uint32_t>(rng_() % 10); + break; + } Op op = kOps[rng_() % (rng_() % 4 ? 6 : kOps.size())]; specs.push_back({col, i, op, std::nullopt}); shape.emplace_back(col, op); @@ -387,6 +449,7 @@ EXPECT_GT(set_id_eq_scans_, 0u); EXPECT_GT(small_value_eq_scans_, 0u); EXPECT_GT(sorted_scans_, 0u); + EXPECT_GT(index_scans_, 0u); } } // namespace