In Blog 5, we built a SQL parser. It can take this:
INSERT INTO payments VALUES (500, payment_1, pending, 1)
and turn it into a struct:
InsertIntoTable{
TableName: "payments",
ColumnValues: []string{"500", "payment_1", "pending", "1"},
}
But this is still not enough for the storage engine.
Our storage engine only knows how to store key-value pairs. It does not know what a table is. It does not know what a column is. It does not know that 500 is an integer, pending is a string, and 1 is a boolean.
So, in this post we solve the missing bridge of persisting these in our key-value store.
CREATE and INSERT are PUT operations
This is the first major realisation. A key-value store is extensible to store literally anything. This is what we have been saying from the first post itself. But now we will be taking actual examples to prove that.
CREATE TABLE Example
Let's start with the create table example and see what should be the key and the value.
Serialisation
The key should be something that uniquely identifies the table, which is straightforward enough in this case as the table name. The value becomes everything else except the key, which is the schema of the table.
So, in order to store the table name, we can append a reserved keyword as prefix like schema as a unique identifier. The structure of the key becomes _schema:<table_name>.
The next question to answer is:
How do we store a struct like below into our key value store where the value is always string?
CreateTable{
TableName: "payments",
ColumnDetails: []Column{
{ColumnName: "amount", DataType: Int},
{ColumnName: "id", DataType: String},
{ColumnName: "status", DataType: String},
{ColumnName: "captured", DataType: Bool},
},
PrimaryKeyColumnPosition: 1,
}
One way is to serialise the entire struct into a string and store that directly. But in that case, deserialisation is a complex logic. JSON or struct serialisation and deserialisation is both space-heavy and compute intensive. This is because JSON and struct take up a lot of space, which is wasted space in case of a disk. They are good for external viewing purposes but not for internal use cases like this. Example: "ColumnDetails" is not needed to be stored and wasted space if we know that we need to write ColumnDetails first. Similar is the case for others fields like "ColumnName", "DataType" or "PrimaryKeyColumnPosition".
If we store the data in such a way that we already know the structure beforehand and can have an agreed common serialisation and deserialisation strategy, it would save up a lot of space. Example: value should start with the position of primary key column, followed by N different column types and data types.
Hence, the structure becomes something like:
[pkColumnPosition][columnDataType1][columnNameLength1][columnName1][columnDataType2][columnNameLength2][columnName2]...
Notice the following here: we are following the same binary serialisation strategy which we have been doing since the first and second blog. columnName is of type string (variable length), hence it is prefixed with length. On the other hand, pkColumnPosition, columnDataType are integers (fixed length), hence they are directly written. This also means that we will continue to write the data as array of bytes. In the end, it is bytes which is written to WAL or SS-Table Files.
// serialisation strategy: [PK_column_position][columnDataType1][columnNameLength1][columnName1][columnDataType2][columnNameLength2][columnName2]...
// secondary index serialisation is covered separately even though it is part of the same CREATE TABLE input.
func serialiseCreateTableInput(createTableInput sqlparser.CreateTable) []byte {
serialisedSchema := []byte{}
// 1. append primary key column position
serialisedSchema = binary.BigEndian.AppendUint32(serialisedSchema, uint32(createTableInput.PrimaryKeyColumnPosition))
for _, col := range createTableInput.ColumnDetails {
// 2. append column data type (byte: 8 bit integer)
serialisedSchema = append(serialisedSchema, byte(col.DataType))
// 3. append length of column name
serialisedSchema = binary.BigEndian.AppendUint32(serialisedSchema, uint32(len(col.ColumnName)))
// 4. append column name
serialisedSchema = append(serialisedSchema, []byte(col.ColumnName)...)
}
return serialisedSchema
}
There is one more interesting thing in the above code. Notice the second comment where we append the data type. Data type appears to be a string. But due to the limited set of possible values of a column data type, we use a byte (8 bit integer) here allowing us to save space. For example: if we are only supporting 3 different datatypes: INT, STRING, BOOL, then all of them can be represented as unique integers: 0, 1, and 2. 8 bit integer means 2^8 (= 256) possible values which we can support.
Once we have the key and the serialised value, this covers the write path. During the create table command, we just write this key value pair by utilising the Put command.
Deserialisation
In the earlier section, we discussed how the CREATE TABLE can be modelled into a Put operation by binary serialisation of the schema.
While inserting the row using INSERT command, we require knowing the schema of the table. This is because, within the AST struct we had represented every column value as string (500 was "500"). But while storing those values on disk, we require storing it as per the relevant data type.
In order to fetch the schema, we require firing a GET query for the specific table name as the key. It would be wasteful to fire this GET query everytime an INSERT query needs to be performed. Hence, a series of GET queries for all the tables should be performed during the application bootup itself to store the schema of each table in-memory.
Since, we already know the structure of create table value as below, we need to iterate through the byte array and read the required number of bytes.
[pkColumnPosition][columnDataType1][columnNameLength1][columnName1][columnDataType2][columnNameLength2][columnName2]...
Below code demonstrates this logic. This deserialisation logic is run for each table during the application bootup:
func deserialiseCreateTableInput(buf []byte) (*sqlparser.CreateTable, error) {
var createTableMeta sqlparser.CreateTable
i := 0
if len(buf) < 4 {
return nil, errors.New("unexpected error while reading primary key column position")
}
// 1. read 4 bytes of pk column position. primary key column position is a 32-bit integer.
// iterate byte array by 4 (can be done within a byte itself if we set a limit of 255 columns in a table)
primaryKeyColumnPosition := binary.BigEndian.Uint32(buf[i : i+4])
createTableMeta.PrimaryKeyColumnPosition = int(primaryKeyColumnPosition)
i += 4
columnDetails := []sqlparser.Column{}
for i < len(buf) {
var columnMeta sqlparser.Column
dataType := buf[i]
if i+1 > len(buf) {
return nil, errors.New("unexpected error while reading column data type")
}
// 2. read 1 byte of data type and convert to internal enum
// iterate byte array by 1
columnMeta.DataType = sqlparser.DataType(dataType)
i++
if i+4 > len(buf) {
return nil, errors.New("unexpected error while reading column length")
}
// 3. read 4 bytes of column name length
// iterate byte array by 4
columnNameLength := binary.BigEndian.Uint32(buf[i : i+4])
i += 4
if i+int(columnNameLength) > len(buf) {
return nil, errors.New("unexpected error while reading column name")
}
// 4. read column_name_length bytes to fetch column name
// iterate byte array by column_name_length
columnMeta.ColumnName = string(buf[i : i+int(columnNameLength)])
i += int(columnNameLength)
columnDetails = append(columnDetails, columnMeta)
}
createTableMeta.ColumnDetails = columnDetails
return &createTableMeta, nil
}
Atomicity in CREATE TABLE
We are still missing one piece in the application bootup process.
If we require fetching all create table rows, how do we come to know of all of the tables?
A simple solution is to write all of the table names in a separate key called _catalog:table_names with the value as comma separated list of all tables. This makes the Create Table operation non-atomic with multiple PUT commands (PUT for "table schema" and "table names").
In order to make the CREATE TABLE atomic, we will utilise the transaction capability we built in blog 4. Our CreateTable function would look something like:
func (db *DB) createTable(createTableInput sqlparser.CreateTable) error {
// 1. Transaction Begin
txn, err := db.Begin()
if err != nil {
return err
}
var tableNames string
for _, table := range db.tableNameVsSchemaMap {
tableNames += table.TableName
tableNames += ","
}
tableNamesLength := len(tableNames)
tableNames = tableNames[:tableNamesLength-1]
// 2. PERFORM PUT operation with _catalog key and all table names.
// If PUT operation fails, rollback the transaction
if err := txn.Put(CatalogKey, tableNames); err != nil {
txn.Rollback()
return errors.New(transactionRolledback)
}
tableName := createTableInput.TableName
// 3. PERFORM PUT operation with _schema:[table_name] key
// If PUT operation fails, rollback the transaction
if err := txn.Put(fmt.Sprintf(SchemaTemplate, tableName), string(
serialiseCreateTableInput(createTableInput))); err != nil {
txn.Rollback()
return errors.New(transactionRolledback)
}
// 4. Transaction Commit
txn.Commit()
return nil
}
INSERT INTO Example
We now have a fairly good understanding on how CREATE TABLE converts AST struct into raw bytes. We will now carry out a similar deep-dive with the INSERT INTO command.
INSERT INTO payments VALUES (500, payment_1, pending, 1)
Serialisation
Similar to CREATE TABLE case, we need to figure out what should be the key and the value. The key choice is straightforward in this case as well. A primary key is the unique identifier for a row. Storing the primary key as the key for the key-value store also ensures that we don't require scanning the full table to find out the required key. We can just fire a GET query with the specific key to fetch the specific row. So, the key can be something like _table:<table_name>:<primary_key_value>.
The value would contain all of the values. Example: (500, payment_1, pending, 1) in this case. To reduce space, we can remove primary key from the value. For simplicity, we have not done that in the current version.
In order to serialise the value, each column value is stored as per the column datatype. We utilise the schema saved in-memory during application bootup to check the schema instead of firing a GET query explicitly.
As of now, we only support 3 data types: Int, String and Bool. Only string values are prefixed with length while Int and Bool don't require length prefix.
So, the serialisation and deserialisation structure would be:
key: _table:<table_name>:<primary_key_value>
value: [value1][size_of_value2][value2][value3]
Note: value1 and value3 are fixed sized datatype like int and bool while value2 is variable sized datatype like string.
func (db *DB) serialiseInsertIntoTableInput(insertIntoTableInput sqlparser.InsertIntoTable) (
key string, valueSchemaBuf []byte, err error) {
tableName := insertIntoTableInput.TableName
table := db.tableNameVsSchemaMap[tableName]
primaryKeyValue := ""
for i, columnValue := range insertIntoTableInput.ColumnValues {
if i == table.PrimaryKeyColumnPosition {
primaryKeyValue = columnValue
}
switch table.ColumnDetails[i].DataType {
case sqlparser.Int:
valueInt, err := strconv.Atoi(columnValue)
if err != nil {
return "", nil, err
}
// 1. Integer case: append 4 byte integer directly
valueSchemaBuf = binary.BigEndian.AppendUint32(valueSchemaBuf, uint32(valueInt))
case sqlparser.String:
// 2. String case: first append length of the string which is 4 bytes and then append the string
valueSchemaBuf = binary.BigEndian.AppendUint32(valueSchemaBuf, uint32(len(columnValue)))
valueSchemaBuf = append(valueSchemaBuf, []byte(columnValue)...)
case sqlparser.Bool:
// 3. Boolean case: append 1 byte boolean directly
valueInt, err := strconv.Atoi(columnValue)
if err != nil {
return "", nil, err
}
if valueInt != 0 && valueInt != 1 {
return "", nil, errors.New("only 0 and 1 values supported for BOOL data type")
}
valueSchemaBuf = append(valueSchemaBuf, uint8(valueInt))
}
}
return fmt.Sprintf("_table:%s:%s", tableName, primaryKeyValue), valueSchemaBuf, nil
}
Optimising Space
When we implement more data types, we see the beauty on how they help optimise space of the row and in turn the entire table. A few datatype examples are:
VARCHAR(255)
As of now, the string datatype that we added is taking up 32 bit or 4 bytes for storing length. We would have frequently seen the VARCHAR datatypes capped at a length of 255 characters.
This number 255 is intentional (2^8 = 256). Keeping varchar limited till 255 ensures that a single byte is sufficient rather than requiring 4 bytes length prefix for an integer.
For most use cases 255 characters are sufficient for representing the required string datatype.
CHAR(14)
Apart from VARCHAR, we would have also seen constant character datatypes, CHAR used while creating tables in MySQL or Postgres. They are especially useful for columns which require storing a unique id.
These constant character datatypes help reduce space. This is because unlike regular string or VARCHAR datatypes, a prefix for indicating length is not required to be written, potentially saving 1 to 4 bytes of space.
TINYINT
TINYINT is a datatype which takes up 1 byte of space. This means that it can take up 2^8 values from -128 to 127. If we use UNSIGNED, values from 0 to 255 can be supported.
It can help save space from regular 4 bytes to 1 byte in tables where we know that the value will not exceed this range. Example: percentage or student marks or student ages.
ENUMs
ENUMs are a very useful datatype in cases where we know that the column has low cardinality values. This just means that the number of unique possible values are quite low.
As an example: payment status could only have a limited set of values. Instead of storing string every time, enums allow mapping each string to a unique number. For example: payment status "success" is mapped to number 0, "failed" is mapped to number 1, "captured" is mapped to number 2 and so on.
This means that every time we just need to store a 1 byte number or a TINYINT instead of storing the actual strings where the actual string could take around 21 bytes of space for a 20 character string (1 byte for indicating length and 20 bytes for the actual string).
Atomicity in INSERT INTO
Soon, similar to CREATE TABLE command, we will require wrapping the INSERT INTO command also in a transaction block to achieve atomicity. This is because secondary index updates require a separate PUT operation. We will deep-dive more on this in a future blog.
Deserialisation
Deserialisation of the value stored during INSERT would be required during SELECT query.
We already covered a deep-dive on deserialisation in the CREATE TABLE section by iterating through the byte array and reading bytes based on the common contract structure which is agreed during serialisation. The deserialisation implementation is hence kept out of the blog and can be tried out by the reader as an interesting exercise.
What's Next
In blog 5 and 6, we got the intuition behind how CREATE and INSERT SQL queries can be converted into PUT operations within our existing key-value store.
In the upcoming blogs, we shift the focus to the read path and supporting SELECT queries.
The code for SaarDB is available here:
GitHub: https://github.com/gagandeepahuja09/saardb
Top comments (0)