Building My Own Database in C++ — Part 2: Querying the Database
Table of Contents
Defining a schema
So far, our storage engine has treated tuples as raw bytes. While this is sufficient for storing records on disk, a database also needs to understand what those bytes represent. For example, a table might contain an id column containing integers and a name column containing strings.
To represent this information, we introduce three abstractions: Value, Column, and Schema. A Value represents an individual database value, a Column describes one field in a table, and a Schema describes the structure of an entire table.
We first define the types supported by our database using an enum class. For now, the database supports integers, booleans, larger integers, and variable-length strings.
1enum class TypeId
2 {
3 INTEGER,
4 BIGINT,
5 BOOLEAN,
6 VARCHAR
7 }; The VARCHAR type represents a variable-length string. Unlike an INTEGER, which always occupies a fixed number of bytes, a VARCHAR value can contain a different number of characters depending on the value. For example, "Alice" and "Christopher" have different lengths.
A Value represents one actual value stored in a tuple. The class keeps track of the value's type and stores the corresponding data. Factory methods are used to make constructing typed values explicit.
1namespace db
2 {
3 class Value
4 {
5 public:
6 static Value Integer(int32_t value) // factory methods to create a value
7 {
8 Value v;
9 v.type_ = TypeId::INTEGER;
10 v.int_value_ = value;
11 return v;
12 }
13
14 static Value BigInt(int64_t value)
15 {
16 Value v;
17 v.type_ = TypeId::BIGINT;
18 v.bigint_value_ = value;
19 return v;
20 }
21
22 static Value Boolean(bool value)
23 {
24 Value v;
25 v.type_ = TypeId::BOOLEAN;
26 v.bool_value_ = value;
27 return v;
28 }
29
30 static Value Varchar(const std::string &value)
31 {
32 Value v;
33 v.type_ = TypeId::VARCHAR;
34 v.string_value_ = value;
35 return v;
36 }
37
38 TypeId type() const
39 {
40 return type_;
41 }
42
43 int32_t as_int() const
44 {
45 return int_value_;
46 }
47
48 int64_t as_bigint() const
49 {
50 return bigint_value_;
51 }
52
53 bool as_bool() const
54 {
55 return bool_value_;
56 }
57
58 const std::string &as_string() const
59 {
60 return string_value_;
61 }
62
63 private:
64 TypeId type_;
65
66 int32_t int_value_ = 0;
67 int64_t bigint_value_ = 0;
68 bool bool_value_ = false;
69 std::string string_value_;
70 };
71
72 } For example, we can now create actual database values instead of manually constructing their serialized byte representation. The Integer() and Varchar() methods are static factory methods. Because they are static, they can be called directly using the class name without first creating a Value object. Each method constructs a Value, assigns its type, stores the corresponding data, and returns it.
Next, we need a way to describe what each field in a table represents. A Column stores the column's name and its type.
1namespace db
2 {
3 class Column
4 {
5 public:
6 Column(
7 std::string name,
8 TypeId type)
9 : name_(std::move(name)),
10 type_(type)
11 {
12 }
13
14 const std::string &name() const
15 {
16 return name_;
17 }
18
19 TypeId type() const
20 {
21 return type_;
22 }
23
24 private:
25 std::string name_;
26 TypeId type_;
27 };
28 }A column can now be defined using its name and type.
Finally, a Schema combines multiple columns to describe the structure of an entire table. The schema stores the columns in order, allowing each column to be identified by its index.
1namespace db
2 {
3
4 class Schema
5 {
6 public:
7 explicit Schema(std::vector<Column> columns)
8 : columns_(std::move(columns))
9 {
10 }
11
12 size_t column_count() const
13 {
14 return columns_.size();
15 }
16
17 const Column &column(size_t index) const
18 {
19 return columns_[index];
20 }
21
22 int column_index(const std::string &name) const
23 {
24 for (int i = 0; i < columns_.size(); i++)
25 {
26 if (columns_[i].name() == name)
27 {
28 return i;
29 }
30 }
31
32 return -1;
33 }
34
35 void add_column(const Column &column)
36 {
37 columns_.push_back(column);
38 }
39
40 private:
41 std::vector<Column> columns_;
42 };
43 } At this point, our database can represent both the structure of a table and the values stored within its rows. The Schema describes what columns exist and their types, while Value represents the actual data stored in those columns. The next step is to connect these logical representations to our Tuple class so that values can be serialized into the raw bytes stored by TablePage.
Building a predicate
Now that the database can represent typed values using Value and describe the structure of a table using Schema, the next step is to provide a way to filter tuples. A predicate represents a condition that a tuple must satisfy, such as checking whether a column is equal to a particular value or greater than a given value.
To represent these conditions, I first define the different types of comparisons that the database supports:
1#pragma once
2namespace db
3{
4 enum class ComparisonType
5 {
6 EQUAL,
7 NOT_EQUAL,
8 LESS_THAN,
9 LESS_THAN_OR_EQUAL,
10 GREATER_THAN,
11 GREATER_THAN_OR_EQUAL
12 };
13}The ComparisonType enum allows a predicate to describe the operation that should be performed. For example, a predicate could represent a condition such as age > 20 or name == "John".
The Predicate itself stores the column to inspect, the comparison to perform, and the value to compare against:
For example, a predicate could be constructed to represent age > 20. Thecolumn_name_ storesage, comparison_ stores GREATER_THAN, and value_ stores the value20.
As the query layer becomes more complex, a single predicate is no longer enough to represent every filtering condition. For example, a query might require both age > 20 and active == true to be satisfied. To support these combinations, I introduce an Expression interface that provides a common way to evaluate conditions against a tuple.
1#include "schema.h"
2#include "tuple.h"
3
4namespace db
5{
6 class Expression
7 {
8 public:
9 virtual ~Expression() = default;
10
11 virtual bool evaluate(
12 const Tuple &tuple,
13 const Schema &schema) const = 0;
14 };
15}The key part of this interface is the pure virtual evaluate() method. Any class that inherits from Expression must implement this method and return a boolean indicating whether the tuple satisfies its condition. The virtual destructor also ensures that derived objects can be safely destroyed through anExpression pointer.
With this interface in place, the existing Predicate class can inherit from Expression
1namespace db
2{
3 class Predicate : public Expression
4 {
5 public:
6 Predicate(
7 const std::string &column_name,
8 ComparisonType comparison,
9 const Value &value);
10
11 bool evaluate(
12 const Tuple &tuple,
13 const Schema &schema) const;
14
15 private:
16 std::string column_name_;
17 ComparisonType comparison_;
18 Value value_;
19 };
20}The actual comparison is handled by Value::compare(). Since a Value can contain different types, the comparison first checks that both values have the same type. It then performs the appropriate comparison based on the type of the value.
1 bool compare(
2 ComparisonType comparison,
3 const Value &other) const
4 {
5 if (type_ != other.type_)
6 {
7 throw std::invalid_argument(
8 "Cannot compare Values of different types");
9 }
10
11 switch (type_)
12 {
13 case TypeId::INTEGER:
14 {
15 int32_t left = as_int();
16 int32_t right = other.as_int();
17
18 switch (comparison)
19 {
20 case ComparisonType::EQUAL:
21 return left == right;
22
23 case ComparisonType::NOT_EQUAL:
24 return left != right;
25
26 case ComparisonType::LESS_THAN:
27 return left < right;
28
29 case ComparisonType::LESS_THAN_OR_EQUAL:
30 return left <= right;
31
32 case ComparisonType::GREATER_THAN:
33 return left > right;
34
35 case ComparisonType::GREATER_THAN_OR_EQUAL:
36 return left >= right;
37 }
38
39 break;
40 }
41
42 case TypeId::BIGINT:
43 {
44 int64_t left = as_bigint();
45 int64_t right = other.as_bigint();
46
47 switch (comparison)
48 {
49 case ComparisonType::EQUAL:
50 return left == right;
51
52 case ComparisonType::NOT_EQUAL:
53 return left != right;
54
55 case ComparisonType::LESS_THAN:
56 return left < right;
57
58 case ComparisonType::LESS_THAN_OR_EQUAL:
59 return left <= right;
60
61 case ComparisonType::GREATER_THAN:
62 return left > right;
63
64 case ComparisonType::GREATER_THAN_OR_EQUAL:
65 return left >= right;
66 }
67
68 break;
69 }
70
71 case TypeId::BOOLEAN:
72 {
73 bool left = as_bool();
74 bool right = other.as_bool();
75
76 switch (comparison)
77 {
78 case ComparisonType::EQUAL:
79 return left == right;
80
81 case ComparisonType::NOT_EQUAL:
82 return left != right;
83
84 case ComparisonType::LESS_THAN:
85 case ComparisonType::LESS_THAN_OR_EQUAL:
86 case ComparisonType::GREATER_THAN:
87 case ComparisonType::GREATER_THAN_OR_EQUAL:
88 throw std::invalid_argument(
89 "Ordering comparison is not supported for BOOLEAN");
90 }
91
92 break;
93 }
94
95 case TypeId::VARCHAR:
96 {
97 std::string left = as_string();
98 std::string right = other.as_string();
99
100 switch (comparison)
101 {
102 case ComparisonType::EQUAL:
103 return left == right;
104
105 case ComparisonType::NOT_EQUAL:
106 return left != right;
107
108 case ComparisonType::LESS_THAN:
109 return left < right;
110
111 case ComparisonType::LESS_THAN_OR_EQUAL:
112 return left <= right;
113
114 case ComparisonType::GREATER_THAN:
115 return left > right;
116
117 case ComparisonType::GREATER_THAN_OR_EQUAL:
118 return left >= right;
119 }
120
121 break;
122 }
123 }
124
125 throw std::invalid_argument("Invalid comparison");
126 }For integer and bigint values, all six comparison operators are supported. Strings can also use all six operators, using the normal lexicographical ordering of std::string. Boolean values only support equality and inequality because ordering comparisons such as less than or greater than do not have a meaningful interpretation here.
With the comparison logic in place, Predicate::evaluate() connects it to an actual tuple. The predicate first looks up the column's index in the schema, retrieves the corresponding value from the tuple, and then passes that value to Value::compare().
1
2Predicate::Predicate(
3 const std::string &column_name,
4 ComparisonType comparison,
5 const Value &value)
6 : column_name_(column_name),
7 comparison_(comparison),
8 value_(value)
9{
10}
11
12bool Predicate::evaluate(
13 const Tuple &tuple,
14 const Schema &schema) const
15{
16 int index = schema.column_index(column_name_);
17
18 if (index == -1)
19 {
20 return false;
21 }
22
23 Value tuple_value = tuple.get_value(schema, index);
24
25 return tuple_value.compare(
26 comparison_,
27 value_);
28}This gives the query layer a simple interface for filtering tuples. It does not need to know how a tuple is serialized or how values are stored inside a page. It only needs to provide a Tuple and Schema to the predicate, which then returns whether the tuple satisfies the condition. This will later allow an executor to scan through the table and return only the tuples that match a given predicate.
Building a compound predicate
With the Expression interface in place, we can now combine multiple conditions into a single expression. For example, a query might require both age > 20 and active == true to be satisfied. Alternatively, it might only require one of these conditions to hold. To support this, I introduce a CompoundPredicate that combines two expressions using a logical operator.
The LogicalOperator enum defines the two operators currently supported: AND and OR. Notice that both operands are references to Expression rather than Predicate. This allows a compound predicate to combine simple predicates or other compound predicates, making it possible to build nested conditions.
1#pragma once
2
3#include "expression.h"
4#include "predicate.h"
5
6namespace db
7{
8 enum class LogicalOperator
9 {
10 AND,
11 OR
12 };
13
14 class CompoundPredicate : public Expression
15 {
16 public:
17 CompoundPredicate(
18 const Expression &left,
19 LogicalOperator op,
20 const Expression &right);
21
22 bool evaluate(
23 const Tuple &tuple,
24 const Schema &schema) const override;
25
26 private:
27 const Expression &left_;
28 LogicalOperator op_;
29 const Expression &right_;
30 };
31}The class stores references to the left and right expressions, along with the logical operator connecting them. Its evaluate() method evaluates these expressions against the same tuple and schema, then combines their results according to the selected operator.
1using namespace db;
2
3CompoundPredicate::CompoundPredicate(
4 const Expression &left,
5 LogicalOperator op,
6 const Expression &right)
7 : left_(left),
8 op_(op),
9 right_(right)
10{
11}
12
13bool CompoundPredicate::evaluate(
14 const Tuple &tuple,
15 const Schema &schema) const
16{
17 bool left_result = left_.evaluate(tuple, schema);
18
19 if (op_ == LogicalOperator::AND)
20 {
21 if (!left_result)
22 {
23 return false;
24 }
25
26 return right_.evaluate(tuple, schema);
27 }
28
29 if (op_ == LogicalOperator::OR)
30 {
31 if (left_result)
32 {
33 return true;
34 }
35
36 return right_.evaluate(tuple, schema);
37 }
38
39 return false;
40}The implementation uses short-circuit evaluation to avoid unnecessary work. For AND, if the left expression evaluates to false, the entire condition must be false, so the right expression does not need to be evaluated. Similarly, for OR, if the left expression evaluates to true, the entire condition is already satisfied.
For example, we can combine age > 20 and active == true using AND. The resulting compound predicate returns true only when both conditions are satisfied. Since a CompoundPredicate also implements Expression, it can itself be combined with another expression to represent more complex conditions.
Defining an executor interface
So far, the query layer can evaluate predicates and scan through a table to retrieve matching tuples. However, each operation is implemented independently, and the caller is responsible for connecting the different steps together.
As the query layer grows, I want to combine different operations, such as sequential scans and projection, without tightly coupling them to one another. To achieve this, I introduce a common Executor interface that defines how query operators produce tuples.
1#pragma once
2
3#include "tuple.h"
4#include "rid.h"
5
6namespace db
7{
8 class Executor
9 {
10 public:
11 virtual ~Executor() = default;
12
13 virtual void init() = 0;
14 virtual bool next(Tuple &tuple, RID &rid) = 0;
15 };
16}The interface provides two methods. The init() method prepares the executor for execution, while next() attempts to produce the next tuple. It returns true when a tuple is available and false when there are no more results. The method also receives a RID output parameter, allowing an executor to return the identifier of the source tuple alongside its data.
Instead of returning every matching tuple in a std::vector, an executor can produce results incrementally. More importantly, every executor follows the same interface, allowing one executor to consume the output of another. This provides the foundation for a query execution pipeline, where each operator performs one operation and passes its results to the next operator.
Implementing a sequential scan executor
With the executor interface in place, I can update the SeqScanExecutor to implement it. A sequential scan visits every tuple in the table and evaluates it against a given expression, returning only the tuples that satisfy the condition.
The executor maintains references to the TableHeap, Schema, and Expression. It also keeps track of the tuple RIDs obtained from the table scan and the next RID to examine. When a matching tuple is found, it returns both the tuple and its RID.
1#pragma once
2
3#include <vector>
4#include "executor.h"
5#include "table_heap.h"
6#include "schema.h"
7#include "expression.h"
8
9namespace db
10{
11 class SeqScanExecutor : public Executor
12 {
13 public:
14 SeqScanExecutor(
15 TableHeap &table,
16 const Schema &schema,
17 const Expression &predicate);
18
19 void init() override;
20 bool next(Tuple &tuple, RID &rid) override;
21
22 private:
23 TableHeap &table_;
24 const Schema &schema_;
25 const Expression &predicate_;
26
27 std::vector<RID> rids_;
28 size_t next_rid_index_ = 0;
29 };
30}During initialization, the executor obtains the RIDs of the tuples in the table by calling scan() and resets its position to the beginning. The next() method then walks through these RIDs, retrieves each tuple, and evaluates it using the supplied expression.
1void SeqScanExecutor::init()
2{
3 rids_ = table_.scan();
4 next_rid_index_ = 0;
5}
6
7bool SeqScanExecutor::next(Tuple &tuple, RID &rid)
8{
9 while (next_rid_index_ < rids_.size())
10 {
11 RID current_rid = rids_[next_rid_index_++];
12 Tuple candidate;
13
14 if (!table_.get_tuple(current_rid, candidate))
15 {
16 continue;
17 }
18
19 if (predicate_.evaluate(candidate, schema_))
20 {
21 tuple = candidate;
22 rid = current_rid;
23 return true;
24 }
25 }
26
27 return false;
28}The next() method uses a loop because some tuples may not satisfy the predicate. It continues scanning until it finds a matching tuple or reaches the end of the RID list. When a match is found, the tuple and its RID are assigned to the output parameters and the method returns true.
If no more matching tuples are available, next() returns false. This lets the caller consume one result at a time without requiring the executor to build a vector containing every matching tuple. The table scan still collects RIDs in a vector, but tuple results are produced incrementally. Since the scan implements the common executor interface, its output can be consumed by another executor.
Implementing a projection executor
The sequential scan executor can now return matching tuples one at a time. However, it still returns every column in each tuple. A query may only need a subset of these columns. For example, SELECT name, age FROM users only requires the name and age columns.
I have already implemented a Projection class that selects values from a tuple and constructs a new tuple using an output schema. Rather than calling project() manually after executing a scan, I can wrap this functionality in a ProjectionExecutor. This executor consumes tuples from another executor and returns their projected versions.
Before integrating projection into the executor pipeline, I first define the Projectionclass in projection.h. It takes the input schema and the names of the columns to keep. It stores the input schema, builds an output schema containing only the selected columns, and remembers their positions in the input tuple.
1#pragma once
2
3#include <string>
4#include <vector>
5#include "schema.h"
6#include "tuple.h"
7
8namespace db
9{
10 class Projection
11 {
12 public:
13 Projection(
14 const Schema &input_schema,
15 const std::vector<std::string> &column_names);
16
17 Tuple project(const Tuple &tuple) const;
18
19 const Schema &output_schema() const;
20
21 private:
22 const Schema &input_schema_;
23 Schema output_schema_;
24 std::vector<int> column_indices_;
25 };
26}The input_schema_ describes the original tuple, while column_indices_ stores the positions of the requested columns in that schema. The output_schema_ describes the structure of the projected tuple. Since a Tuple stores serialized values, the schema is needed to interpret those values correctly when they are read back.
In projection.cpp, I use a helper function to build the output schema. It looks up each requested column in the input schema and copies its column definition into a new schema. If a requested column does not exist, the constructor throws an exception rather than creating an invalid projection. The constructor also stores each column's index for use when projecting tuples.
1#include "projection.h"
2
3#include <stdexcept>
4#include <utility>
5
6using namespace db;
7
8static Schema build_output_schema(
9 const Schema &input_schema,
10 const std::vector<std::string> &column_names)
11{
12 std::vector<Column> columns;
13
14 for (const std::string &name : column_names)
15 {
16 int index = input_schema.column_index(name);
17
18 if (index == -1)
19 {
20 throw std::invalid_argument(
21 "Column does not exist: " + name);
22 }
23
24 columns.push_back(input_schema.column(index));
25 }
26
27 return Schema(std::move(columns));
28}
29
30Projection::Projection(
31 const Schema &input_schema,
32 const std::vector<std::string> &column_names)
33 : input_schema_(input_schema),
34 output_schema_(build_output_schema(
35 input_schema,
36 column_names))
37{
38 for (const std::string &name : column_names)
39 {
40 column_indices_.push_back(
41 input_schema.column_index(name));
42 }
43}
44
45Tuple Projection::project(const Tuple &tuple) const
46{
47 std::vector<Value> values;
48
49 for (int index : column_indices_)
50 {
51 values.push_back(
52 tuple.get_value(input_schema_, index));
53 }
54
55 return Tuple(values, output_schema_);
56}
57
58const Schema &Projection::output_schema() const
59{
60 return output_schema_;
61}The build_output_schema() helper constructs a new schema containing only the requested columns, preserving their requested order. The constructor then saves each column's index so it does not need to look up the names again every time a tuple is projected.
The project() method uses those saved indices to retrieve the selected values from the input tuple. It places the values into a new tuple using the output schema. The output_schema() method exposes that schema so the caller can correctly interpret the projected tuple's values.
With the Projection class handling column selection, the executor itself can stay relatively simple. It only needs to request a tuple from its child executor, pass that tuple to project(), and return the projected result.
1#pragma once
2
3#include <string>
4#include <vector>
5#include "executor.h"
6#include "projection.h"
7
8namespace db
9{
10 class ProjectionExecutor : public Executor
11 {
12 public:
13 ProjectionExecutor(
14 Executor &child,
15 const Schema &input_schema,
16 const std::vector<std::string> &column_names);
17
18 void init() override;
19 bool next(Tuple &tuple, RID &rid) override;
20
21 const Schema &output_schema() const;
22
23 private:
24 Executor &child_;
25 Projection projection_;
26 };
27}The child_ reference represents the executor that supplies the input tuples. This could be a sequential scan executor or another executor that implements the same interface. The projection_ member handles the actual column selection using the existing Projection class.
1ProjectionExecutor::ProjectionExecutor(
2 Executor &child,
3 const Schema &input_schema,
4 const std::vector<std::string> &column_names)
5 : child_(child),
6 projection_(input_schema, column_names)
7{
8}
9
10void ProjectionExecutor::init()
11{
12 child_.init();
13}
14
15bool ProjectionExecutor::next(Tuple &tuple, RID &rid)
16{
17 Tuple input_tuple;
18
19 if (!child_.next(input_tuple, rid))
20 {
21 return false;
22 }
23
24 tuple = projection_.project(input_tuple);
25 return true;
26}
27
28const Schema &ProjectionExecutor::output_schema() const
29{
30 return projection_.output_schema();
31}When the projection executor is initialized, it initializes its child executor as well. Each call to next() requests the next tuple and RID from the child. If the child has no more tuples, the projection executor also returns false. Otherwise, it projects the input tuple and returns the resulting tuple while preserving the source RID.
The projected tuple has a different structure from the input tuple, so the projection executor also exposes its output schema. This schema describes the selected columns and allows callers to interpret the projected values correctly.
With this design, the two executors can be chained together. The sequential scan is responsible for retrieving and filtering tuples, while the projection executor is responsible for selecting columns. Each executor focuses on one operation and communicates with the next through the common interface.
The following example filters users whose age is greater than 25 and whose active flag is true, then returns only their names and ages:
1Predicate age_predicate(
2 "age",
3 ComparisonType::GREATER_THAN,
4 Value::Integer(25));
5
6Predicate active_predicate(
7 "active",
8 ComparisonType::EQUAL,
9 Value::Boolean(true));
10
11CompoundPredicate combined_predicate(
12 age_predicate,
13 LogicalOperator::AND,
14 active_predicate);
15
16SeqScanExecutor scan(table, schema, combined_predicate);
17
18ProjectionExecutor projection(
19 scan,
20 schema,
21 {"name", "age"});
22
23projection.init();
24
25Tuple tuple;
26RID rid;
27while (projection.next(tuple, rid))
28{
29 const Schema &output_schema = projection.output_schema();
30
31 std::string name =
32 tuple.get_value(output_schema, 0).as_string();
33 int age =
34 tuple.get_value(output_schema, 1).as_int();
35
36 std::cout << "name=" << name
37 << ", age=" << age << '
38';
39}This gives the database the beginnings of an execution pipeline. Instead of collecting all matching tuples and processing them in separate steps, the caller requests tuples from the outermost executor and lets each operator perform its part of the query. The same interface will make it easier to add further operators, such as sorting, limiting results, and joining tables. The current table scan still materializes the RID list, which can be optimized later.