src/trace_processor/storage_table.cc

/*
 * Copyright (C) 2018 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/storage_table.h"

namespace perfetto {
namespace trace_processor {

StorageTable::StorageTable() = default;
StorageTable::~StorageTable() = default;

base::Optional<Table::Schema> StorageTable::Init(int, const char* const*) {
  schema_ = CreateStorageSchema();
  return schema_.ToTableSchema();
}

std::unique_ptr<Table::Cursor> StorageTable::CreateCursor() {
  return std::unique_ptr<Cursor>(new Cursor(this));
}

std::unique_ptr<RowIterator> StorageTable::CreateBestRowIterator(
    const QueryConstraints& qc,
    sqlite3_value** argv) {
  const auto& cs = qc.constraints();
  auto obs = RemoveRedundantOrderBy(cs, qc.order_by());

  // Figure out whether the data is already ordered and which order we should
  // traverse the data.
  bool is_ordered, is_desc = false;
  std::tie(is_ordered, is_desc) = IsOrdered(obs);

  // Create the range iterator and if we are sorted, just return it.
  auto index = CreateRangeIterator(cs, argv);
  if (!index.error().empty()) {
    SetErrorMessage(sqlite3_mprintf(index.error().c_str()));
    return nullptr;
  }

  if (is_ordered)
    return index.ToRowIterator(is_desc);

  // Otherwise, create the sorted vector of indices and create the vector
  // iterator.
  return std::unique_ptr<VectorRowIterator>(
      new VectorRowIterator(CreateSortedIndexVector(std::move(index), obs)));
}

FilteredRowIndex StorageTable::CreateRangeIterator(
    const std::vector<QueryConstraints::Constraint>& cs,
    sqlite3_value** argv) {
  // Try and bound the search space to the smallest possible index region and
  // store any leftover constraints to filter using bitvector.
  uint32_t min_idx = 0;
  uint32_t max_idx = RowCount();
  std::vector<size_t> bitvector_cs;
  for (size_t i = 0; i < cs.size(); i++) {
    const auto& c = cs[i];
    size_t column = static_cast<size_t>(c.iColumn);
    auto bounds = schema_.GetColumn(column).BoundFilter(c.op, argv[i]);

    min_idx = std::max(min_idx, bounds.min_idx);
    max_idx = std::min(max_idx, bounds.max_idx);

    // If the lower bound is higher than the upper bound, return a zero-sized
    // range iterator.
    if (min_idx >= max_idx)
      return FilteredRowIndex(min_idx, min_idx);

    if (!bounds.consumed)
      bitvector_cs.emplace_back(i);
  }

  // Create an filter index and allow each of the columns filter on it.
  FilteredRowIndex index(min_idx, max_idx);
  for (const auto& c_idx : bitvector_cs) {
    const auto& c = cs[c_idx];
    auto* value = argv[c_idx];

    const auto& schema_col = schema_.GetColumn(static_cast<size_t>(c.iColumn));
    schema_col.Filter(c.op, value, &index);

    if (!index.error().empty())
      break;
  }
  return index;
}

std::pair<bool, bool> StorageTable::IsOrdered(
    const std::vector<QueryConstraints::OrderBy>& obs) {
  if (obs.size() == 0)
    return std::make_pair(true, false);

  if (obs.size() != 1)
    return std::make_pair(false, false);

  const auto& ob = obs[0];
  auto col = static_cast<size_t>(ob.iColumn);
  return std::make_pair(schema_.GetColumn(col).HasOrdering(), ob.desc);
}

std::vector<QueryConstraints::OrderBy> StorageTable::RemoveRedundantOrderBy(
    const std::vector<QueryConstraints::Constraint>& cs,
    const std::vector<QueryConstraints::OrderBy>& obs) {
  std::vector<QueryConstraints::OrderBy> filtered;
  std::set<int> equality_cols;
  for (const auto& c : cs) {
    if (sqlite_utils::IsOpEq(c.op))
      equality_cols.emplace(c.iColumn);
  }
  for (const auto& o : obs) {
    if (equality_cols.count(o.iColumn) > 0)
      continue;
    filtered.emplace_back(o);
  }
  return filtered;
}

std::vector<uint32_t> StorageTable::CreateSortedIndexVector(
    FilteredRowIndex index,
    const std::vector<QueryConstraints::OrderBy>& obs) {
  PERFETTO_DCHECK(obs.size() > 0);

  // Retrieve the index created above from the index.
  std::vector<uint32_t> sorted_rows = index.ToRowVector();

  std::vector<StorageColumn::Comparator> comparators;
  for (const auto& ob : obs) {
    auto col = static_cast<size_t>(ob.iColumn);
    comparators.emplace_back(schema_.GetColumn(col).Sort(ob));
  }

  auto comparator = [&comparators](uint32_t f, uint32_t s) {
    for (const auto& comp : comparators) {
      int c = comp(f, s);
      if (c != 0)
        return c < 0;
    }
    return false;
  };
  std::sort(sorted_rows.begin(), sorted_rows.end(), comparator);

  return sorted_rows;
}

bool StorageTable::HasEqConstraint(const QueryConstraints& qc,
                                   const std::string& col_name) {
  size_t c_idx = schema().ColumnIndexFromName(col_name);
  auto fn = [c_idx](const QueryConstraints::Constraint& c) {
    return c.iColumn == static_cast<int>(c_idx) && sqlite_utils::IsOpEq(c.op);
  };
  const auto& cs = qc.constraints();
  return std::find_if(cs.begin(), cs.end(), fn) != cs.end();
}

StorageTable::Cursor::Cursor(StorageTable* table)
    : Table::Cursor(table), table_(table) {}

int StorageTable::Cursor::Filter(const QueryConstraints& qc,
                                 sqlite3_value** argv) {
  iterator_ = table_->CreateBestRowIterator(qc, argv);
  if (!iterator_)
    return SQLITE_ERROR;
  columns_ = table_->schema_.mutable_columns();
  return SQLITE_OK;
}

int StorageTable::Cursor::Next() {
  iterator_->NextRow();
  return SQLITE_OK;
}

int StorageTable::Cursor::Eof() {
  return iterator_->IsEnd();
}

int StorageTable::Cursor::Column(sqlite3_context* context, int raw_col) {
  size_t column = static_cast<size_t>(raw_col);
  (*columns_)[column]->ReportResult(context, iterator_->Row());
  return SQLITE_OK;
}

}  // namespace trace_processor
}  // namespace perfetto