Mainly build the executor
The processing model of a DBMS defines how the system executes query plans. There are different trade-offs for different workloads.
Volcano model:
Here is a detailed description of the volcano model:
-
Operators and Operations: The Volcano model breaks down a query’s execution plan into a series of operators and operations. Each operator represents a specific operation such as selection, projection, join, sort, aggregation, etc. These operators are designed to process and transform data.
-
Pipeline: In the volcano model, operators are connected by pipelines. These pipes are used to pass data and intermediate results, similar to data flows. Data flows from one operator to the next, and each operator can process and transform the data.
-
Logical query plan: Before query execution, DBMS first parses the query statement into a logical query plan. This plan consists of a series of logical operators and describes the logical operations of the query. These logical operators are converted into physical operators for execution plan generation.
-
Physical query plan: After generating the logical query plan, the DBMS converts it into a physical query plan, which is an execution plan composed of physical operators. Physical operators are tied to hardware and storage structures to efficiently manipulate data.
-
Query optimization: The key goal of the volcano model is to optimize the query execution plan. Before generating a physical query plan, the DBMS will consider the possibility of multiple execution plans and generate the best execution plan through cost estimation and optimization strategy selection. This involves choosing the best access path, join order, index usage and other decisions.
-
Generation of execution plan: Once the best physical query plan is determined, the DBMS will generate the execution plan and execute the query. During execution, data is passed through the operator pipeline, with each operator performing an appropriate operation based on its definition.
-
Monitoring and adjustment of execution plans: During the query execution process, DBMS can monitor and adjust execution plans to cope with performance changes under different circumstances. This includes re-optimizing query plans to accommodate new data distribution or access patterns.
The advantage of the volcano model is that it provides a flexible approach to optimize query execution, allowing the DBMS to choose the best execution plan at runtime, thereby improving query performance. By using logical and physical operators and pipeline connections to organize query plans, DBMS is able to dynamically adapt to different query needs and data environments.
Each query plan operator implements a Next() function.
1. Each time it is called, the operator returns a single tuple (a subset of columns, or a record), or an empty token if there is no tuple.
2. The operator implements a loop. The operator refers to the parent operator. Next, the child operator is called to extract data from the bottom of the query plan until the top is the output returned to the customer.
Also called volcano model or pipe model.
Advantages: There is no need to write the results immediately on the disk. In the disk system, if the disk runs out, the disk can be scattered at each step. Every time I take a page, I get a tuple. I can do whatever I need to do. It is possible. Getting all output without writing it back to disk makes output control particularly easy.
Physical implementation of different operators
1. Every time a tuple of the sub-operator is obtained, it is output to the outside. How does the data come from: execute the child.next method, execute the child.next method of the sub-operator in a loop, and output a piece of data each time it is executed.
2. Call the left child’s next, the implementation of the left child’s next: use the appearance to build a hash table to traverse the left child, call it over and over again to fill the hash table (the main function of the hash table is to detect whether there is a match)
3. Then execute for t in Remit(t), traverse a tuple on R, and then emit the tuple (one tuple each time).
4. Once the hash table is built, where does he have to do the detection: next there will be the appropriate children, going down there will be a filter (filter operator), but just an iterator over each of the child children, and then there will be a scan , each time a tuple is returned, apply the filter or evaluator, and then return to the previous loop. If a match is found, it will be returned to the parent node.
In the execution flow, the NEXT() method of the root node is called first, and its control flow propagates downward to the leaf nodes.
In a relational database, SQL statements will be converted into logical query plans and converted into physical query plans after query optimization. The system completes the corresponding statement functions by executing the physical query plan.
In a relational database, the physical query plan is organized into a tree within the system and executed through a specific query processing model (iterator model, producer model). The model to be implemented in this experiment is the iterator model. Each query plan node of this model gets the next tuple it needs through the NEXT() method until the NEXT() method returns false. In the execution flow, the NEXT() method of the root node is called first, and its control flow propagates downward to the leaf nodes. Each executor’s Next function returns a record identifier (RID) in addition to a tuple. The record identifier serves as a unique identifier for the tuple.
The actual tuples in the table are stored in TableHeap, which contains all functional interfaces for inserting, searching, changing, and deleting tuples, and can be sequenced through the TableIterator iterator Iterate over the tuples within it.
, each query plan node AbstractPlanNode is included in the executor class AbstractExecutor, and the user calls Next() of the query plan through the executor class method and initialization Init() method, and the query plan node stores the unique information required for the operation. For example, sequential scanning needs to save the table identifier to be scanned in the node, and the connection needs to be saved in the node. Save its child nodes and connected predicates in it.
In Init(), perform the initialization operations required for the plan node, and reset the iterator of the table here so that the query plan can re-traverse the table:
void SeqScanExecutor::Init() {
iter_ = table_info_->table_->Begin(exec_ctx_->GetTransaction());
end_ = table_info_->table_->End();
}
In Next(), schedule nodes to traverse the table and return tuples via input parameters, returning false when the traversal is complete:
bool SeqScanExecutor::Next(Tuple *tuple, RID *rid) {
const Schema *out_schema = this->GetOutputSchema();
Schema table_schema = table_info_->schema_;
while (iter_ != end_) {
Tuple table_tuple = *iter_;
*rid = table_tuple.GetRid();
std::vector<Value> values;
for (const auto & amp;col : GetOutputSchema()->GetColumns()) {
values.emplace_back(col.GetExpr()->Evaluate( & amp;table_tuple, & amp;table_schema));
}
*tuple = Tuple(values, out_schema);
auto *predicate = plan_->GetPredicate();
if (predicate == nullptr || predicate->Evaluate(tuple, out_schema).GetAs<bool>()) {
+ + iter_;
return true;
}
+ + iter_;
}
return false;
}
Here, the tuple is accessed through the iterator iter_, and when the plan node predicate predicate is non-empty, through Evaluate of predicate The code> method evaluates whether the current tuple satisfies the predicate and returns if it does, otherwise it traverses the next tuple. It is worth noting that the tuples in the table should be reorganized in the out_schema mode. In bustub, the output tuples of all query plan nodes are passed through the ColumnValueExpression of each column Column in out_schema Various “Evaluate” method constructs, such as Evaluate, EvaluateJoin, EvaluateAggregate.
For a plan node with a specific out_schema, the way to construct the output tuple is to traverse the Column in out_schema and pass the Column method of ColumnValueExpression in /code> extracts the row corresponding to the table tuple:
36 auto Evaluate(const Tuple *tuple, const Schema *schema) const -> Value override {
37 return tuple->GetValue(schema, col_idx_);
38}
Column stores the column number of the column in the table schema, and Evaluate extracts the corresponding column from the table tuple based on the column number.
Predicate: Expression:
comparisons: < > = !=
conjunction:and or
arithmetic operators: + – * / %
constant values
A reference to a tuple attribute
The actual tuples in the table are stored in TableHeap, which contains all functional interfaces for inserting, searching, changing, and deleting tuples, and can be sequenced through the TableIterator iterator Iterate over the tuples within it.
GROUP BY
The ORDER BY statement is used to sort the result set based on a specified column.
JOIN:
There are two implementation methods for JOIN.
1.Nestedloopjoin
2.Hashjoin
1: NestedLoopJoinExecutor
(It will be used in mysql, the implementation is relatively simple, mainly two loops are nested, so the performance is relatively poor)
NestedLoopJoinExecutor joins all the tuples in the two child plan nodes. Each time the Next() method is called, it returns a connection tuple that conforms to the connection predicate to the parent node:
NestedLoopJoinExecutor::NestedLoopJoinExecutor(ExecutorContext *exec_ctx, const NestedLoopJoinPlanNode *plan,
std::unique_ptr<AbstractExecutor> & amp; & amp;left_executor,
std::unique_ptr<AbstractExecutor> & amp; & amp;right_executor)
: AbstractExecutor(exec_ctx),
plan_(plan),
left_executor_(left_executor.release()),
right_executor_(right_executor.release()) {}
void NestedLoopJoinExecutor::Init() {
left_executor_->Init();
right_executor_->Init();
buffer_.clear();
const Schema *left_schema = plan_->GetLeftPlan()->OutputSchema();
const Schema *right_schema = plan_->GetRightPlan()->OutputSchema();
const Schema *out_schema = this->GetOutputSchema();
Tuple left_tuple;
Tuple right_tuple;
RID rid;
while (left_executor_->Next( & amp;left_tuple, & amp;rid)) {
right_executor_->Init();
while (right_executor_->Next( & amp;right_tuple, & amp;rid)) {
auto *predicate = plan_->Predicate();
if (predicate == nullptr ||
predicate->EvaluateJoin( & amp;left_tuple, left_schema, & amp;right_tuple, right_schema).GetAs<bool>()) {
std::vector<Value> values;
for (const auto & amp;col : out_schema->GetColumns()) {
values.emplace_back(col.GetExpr()->EvaluateJoin( & amp;left_tuple, left_schema, & amp;right_tuple, right_schema));
}
buffer_.emplace_back(values, out_schema);
}
}
}
}
Here, the Init() function completes all connection operations and stores all the resulting connection tuples in the buffer buffer_. It obtains the tuple of the sub-plan node through the Next() method of the sub-plan node, traverses each pair of tuple combinations through a double-layer loop, and calls its when the inner plan node returns false. Init()Initialize it. After obtaining the subplan node tuple, if there is a predicate, call the predicate’s EvaluateJoin to verify whether it conforms to the predicate. If there is no predicate or it matches the predicate, the output tuple is obtained by calling EvaluateJoin of each Column of out_schema and placed into buffer_.
bool NestedLoopJoinExecutor::Next(Tuple *tuple, RID *rid) {
if (!buffer_.empty()) {
*tuple = buffer_.back();
buffer_.pop_back();
return true;
}
return false;
}
2.HashJoinExecutor:
HashJoinExecutor uses the basic Hash Join Algorithm to perform connection operations. Hash connections are mainly divided into two phases: build phase and probe phase.
Bulid Phase
Select a table (usually a smaller table to reduce the time and space of building a hash table), and use the hash function on the join attribute on each tuple to obtain the hash value, so that Build a hash table.
Probe Phase
For another table, scan each row of it and calculate the hash value of the connection attribute. Compare it with the hash table established in the bulk phase. If there are any that fall in the same bucket, if the connection predicate is satisfied, connect it to a new one. surface.
When the memory is large enough, the entire table is in the memory during the process of establishing the hash table, and is placed on the disk only after the connection operation is completed. But this process will also bring a lot of I/O operations.
1. In order for the tuple to be inserted into the hash table, you first need to set the corresponding hash function for the connection key of the tuple, and the comparison method of its connection key :
struct HashJoinKey {
Value value_;
bool operator==(const HashJoinKey & amp;other) const { return value_.CompareEquals(other.value_) == CmpBool::CmpTrue; }
};
} // namespace bustub
namespace std {
/** Implements std::hash on AggregateKey */
template <>
struct hash<bustub::HashJoinKey> {
std::size_t operator()(const bustub::HashJoinKey & amp;key) const { return bustub::HashUtil::HashValue( & amp;key.value_); }
};
The connection key of the connection operation only consists of one attribute column of the tuple, so only the specific value of a single attribute column Value needs to be stored in the connection key. The connection key passes Value CompareEqualsCompare.
In HashJoinExecutor, use unordered_multimap to directly store tuples of connection keys. In principle, it is equivalent to the process of using an ordinary hash table and traversing buckets. But using multimap will make the implementation code simpler.
HashJoinExecutor::HashJoinExecutor(ExecutorContext *exec_ctx, const HashJoinPlanNode *plan,
std::unique_ptr<AbstractExecutor> & amp; & amp;left_child,
std::unique_ptr<AbstractExecutor> & amp; & amp;right_child)
: AbstractExecutor(exec_ctx), plan_(plan), left_child_(left_child.release()), right_child_(right_child.release()) {}
void HashJoinExecutor::Init() {
left_child_->Init();
right_child_->Init();
hash_map_.clear();
output_buffer_.clear();
Tuple left_tuple;
const Schema *left_schema = left_child_->GetOutputSchema();
RID rid;
while (left_child_->Next( & amp;left_tuple, & amp;rid)) {
HashJoinKey left_key;
left_key.value_ = plan_->LeftJoinKeyExpression()->Evaluate( & amp;left_tuple, left_schema);
hash_map_.emplace(left_key, left_tuple);
}
}
In Init(), HashJoinExecutor traverses the tuple of the left subplan node to complete the hash table construction operation.
bool HashJoinExecutor::Next(Tuple *tuple, RID *rid) {
if (!output_buffer_.empty()) {
*tuple = output_buffer_.back();
output_buffer_.pop_back();
return true;
}
Tuple right_tuple;
const Schema *left_schema = left_child_->GetOutputSchema();
const Schema *right_schema = right_child_->GetOutputSchema();
const Schema *out_schema = GetOutputSchema();
while (right_child_->Next( & amp;right_tuple, rid)) {
HashJoinKey right_key;
right_key.value_ = plan_->RightJoinKeyExpression()->Evaluate( & amp;right_tuple, right_schema);
auto iter = hash_map_.find(right_key);
uint32_t num = hash_map_.count(right_key);
for (uint32_t i = 0; i < num; + + i, + + iter) {
std::vector<Value> values;
for (const auto & amp;col : out_schema->GetColumns()) {
values.emplace_back(col.GetExpr()->EvaluateJoin( & amp;iter->second, left_schema, & amp;right_tuple, right_schema));
}
output_buffer_.emplace_back(values, out_schema);
}
if (!output_buffer_.empty()) {
*tuple = output_buffer_.back();
output_buffer_.pop_back();
return true;
}
}
return false;
}
In Next(), use the tuple of the right child plan node as a “probe” to find the tuple of the left child plan node with the same connection key as its join key. It should be noted that a right node tuple may have multiple left node tuples corresponding to it, but a Next() operation only returns one result connection tuple. Therefore, in one Next(), all result tuples obtained by the connection should be stored in the output_buffer_ buffer, so that in the next Next() Only the result tuple is extracted from the buffer without calling the Next() method of the child node.
TOP-N:
Heap sort
- Time complexity, the time complexity of heap sort is less than n^2
- Space complexity. The memory used here can be specified by yourself. At the same time, even if it is small, it can have better performance.
- It does not occupy more cluster resources, does not require file bucketing and multi-cluster computing, and does not require too many computing resources after the heap is completed.
INDEX-SCAN:
(Most) dbms want to use index scans as much as possible.
Which index to use depends on:
What properties does the index contain?
What attribute does the query refer to?
attribute range
Predicate composition
Whether the index has unique or non-unique keys