Database Internel Architecture: SQLite

Introduction

A database is an essential part of building a software system which used to store and read data efficiently. Here, We are going to discuss some architectural details of database implementation by using an early version of SQLite.

SQLite is a small database application which used in millions of software and devices. SQLite invented by D.Richard Hipp in August 2000. SQLite is a high performance, lightweight relational database. If you are willing to learn internal of a database in coding level, then SQLite is the best open source database available out there with highly readable source code with lots of documentation. Reading later versions of SQLite become a little harder since it contains lots of new features. In order to understand the basic implementation of database internals, You should have good knowledge about data structures, some knowledge about Theory of Computing and how an operating system works.

Here we are looking into the SQLite 2.5.0 version. Here below you can find out a simple implementation of SQLite backend at Github. https://github.com/madushadhanushka/simple-sqlite

Why database?

Keeping data in a flat file is not that so efficient to access and keep data. Database organize the data in proper order such that data reading and writing make much more faster. Data can be structured, semi-structured or unstructured. Databases are mainly to store structured and semi-structured data. Databases can be dived as follows based on the type of data structure which used to implement the software.

1. Relational database: Commonly used database type which has a table structure. Tables can have relations with other tables. SQL language used to manipulate data on this type of database.
2. Key-value database: data stored along with a key associated with it. Data can be retrieved back with the given key. In-memory databases are commonly found as this type of database.
3. Object database: Data structure is more like an object rather than a table.
4. Graph database: Graph database is a collection of node and edges which mostly used in data mining and social media applications.

Database architecture

SQLite database architecture split into two different sections named as core and backend. Core section contains Interface, Tokenizer, Parser, Code generator and the virtual machine which create execution order for database transactions. Backend contains B-tree, Pager and OS interface to access the file system. Tokenizer, Parser and code generator altogether named as the compiler which generates a set of opcodes that runs on a virtual machine.

Where do I start?

To understand the architecture of a database you need to have following prerequisite.

1. Good understanding of data structures and algorithm. Especially data structures such as B-tree, Linked list, Hashmaps etc.
2. Some understanding of computer architecture. How to read-write into a disk, how paging and caching works.
3. Theoretical computers such as finite automata and some regular expression knowledge.

SQLite Architecture

VFS (Virtual File System)

File access on Unix and Windows are different from each other. VFS provides common API to access files without considering the type of the operating system it runs on. This API includes functions to open, read, write and close a file. Here follows are some of the API used in VFS to read, write data into a file.

/* 
Create a connection to file to read write 
zFilename : file name 
id : file pointer 
pReadonly : read or write 
*/
int sqliteOsOpenReadWrite(const char *zFilename, OsFile *id,int *pReadonly);

/* 
Acqure the lock to read file. Return 0 if success 5 if failed
id : file pointer 
*/
int sqliteOsReadLock(OsFile *id);

/* 
Get the write lock to write into a file. Return 0 if success 5 if failed
id : file pointer
*/
int sqliteOsWriteLock(OsFile *id);

/* 
Move to the given number of offest to read or write into the file
*/
int sqliteOsSeek(OsFile *id, int offset);

/* 
Read the amt bytes from the file with offset pointed by sqliteOsSeek
*/
int sqliteOsRead(OsFile *id, void *pBuf, int amt);

/* 
Write amt bytes from the pBuf buffer into the file
*/
int sqliteOsWrite(OsFile *id, const void *pBuf, int amt);

Pager

Pages are the smallest unit of transaction on the file system. When database needs to read data from a file, it request it as a page. Once the page loaded into the database engine it can store page if it access frequently on its cache. Pages are numbered and start from one. The first page is called the root page. Size of a page is constant.

/*
Open pager with the given file name and nPage maximum cache limit
*/
int sqlitepager_open(Pager **ppPager,const char *zFilename,int nPage,int nEx);

/*
Get page specified by the page number
*/
int sqlitepager_get(Pager *pPager, Pgno pgno, void **ppPage);

/*
Start to write data into a page specified in pData
*/
int sqlitepager_write(void *pData);

/*
Commit page changes into the file
*/
int sqlitepager_commit(Pager*);

/*
Close the connection to the file
*/
int sqlitepager_close(Pager *pPager);

Btree

Btree is a data structure that used to store data as a tree based on its value. The simplest form of the BTree is the Binary tree. Databases use Btree data structure to store indexes to improve the performance of the database. A cursor is a special pointer which used to point a record wich given with page id and offset idx.

/*
Open file connection to a page file name specified by zFileName with nCache size cache
*/
int sqliteBtreeOpen(const char *zFilename, int mode, int nCache, Btree **ppBtree)

/*
Start transaction. This function should called before any btree modification operations
*/
int sqliteBtreeBeginTrans(Btree *pBt)

/* Insert key pKey with nKey byte and value pData with nData byte put into the Btree
*/
int sqliteBtreeInsert(BtCursor *pCur, const void *pKey, int nKey, const void *pData, int nData)

/*
Write data into the file
*/
int sqliteBtreeCommit(Btree *pBt)

/*
Move cursor to the matching pKey with nKey bytes
*/
int sqliteBtreeMoveto(BtCursor *pCur, const void *pKey, int nKey, int *pRes)

VDBE(Virtual Database Engine)

VDBE is a virtual machine that runs a set of operations which was generated by Code Generator. All SQL commands including insert, delete, update, select converted into a set of opcodes and then it runs on this virtual machine. Each opcode contains three input named as p1, p2, and p3. You can think this input as input for a function.

The most interesting thing in SQLite for me is I can see the set of VBDE opcode instruction for a give SQL code by just appending explain keyword at the beginning of SQL query. Here below the sample execution opcodes stack for following SQL select statement. Here, the first column is operation id, Second column is opcode, third, fourth and fifth column is arguments provided for the opcode.

explain select * from foo where value = "value";

0 |ColumnCount   |1 |0 |
1 |ColumnName    |0 |0 |value
2 |Open          |0 |3 |foo     // Open cursor and point it to third page which is root page for foo table(p3 is not important )

3 |VerifyCookie  |46|0 |       // Make sure schema not changed
4 |Rewind        |0 |11|       // Go to first entry
5 |Column        |0 |0 |       // read data and push it on stack
6 |Column        |0 |0 |
7 |Ne            |1 |10|       //Pop the top two elements from the stack.  If they are not equal, then jump to instruction P2.  Otherwise, continue to the next instruction.

8 |Column        |0 |0 |
9 |Callback      |1 |0 |       // Pop P1 values off the stack and form them into an array

10|Next          |0 |5 |       // Move cursor to next record, if data exit goto P2 else go to next line

11|Close         |0 |0 |       // Close the cursor

Compiler

Tokenizer, Parser and Code Generator together known as Compiler which generates sets of opcode which runs on VBDE. Tokenizer generates a set of token by scanning SQL code. Then it validates the syntax and generates the parse tree. Code Generator converts this parse tree into a mini program, written in SQLite opcodes.

Conclusion

SQLite is a simple lightweight, high-performance, relational database which is widely used in software designs. Early version of SQLite was written with simple architecture and highly readable code. Pager provides an abstraction layer to read-write data into the file system as fixed size blocks. While Btree provides a way to store data in the memory efficient way to access data faster. When SQL comes into the SQLite, it converts SQL into the SQLite machine code and runs it on VBDE. The result sends back to the user through the API.