How Database Works: Frontend Architecture

By madushandhanushka

In a computer program, the database is the heart of handling data. It provides an efficient way of storing and retrieving data fast. Learning Database internal architecture in code level is not that so easy since Database has complex architecture. Looking into a complex database is not that easy because of the complexity. But, SQLite is a nice little compact database that used in millions of devices and operating systems. Interesting fact about the SQLite database is that, code is highly readable. All most all of the codes are well commented and architecture is highly layered. This post is to look at the high-level architecture of the SQLite database.
As I early mentioned, SQLite has a highly layered architecture and that can be separated into seven layers. We will go through each of the layers one by one.
1_t5ygkzu6a28fO41ynZ8kgQ.jpeg
First Layer is called Tokenizer. Purpose of the tokenizer is to create tokens for a given SQL query. Tokenizer scans SQL query from left to right and generates a list of tokens. Following are some of the types of tokens used in SQL tokenizer.
  1. Operator tokens Operator token used to tokenized arithmetic operators in SQL queries. Here are some of the example set of Operator tokens.
  2. “(” as token LP
  3. Keyword tokens Keyword token used to tokenized the keywords used in SQL queries. ADD, SELECT, ROW, INSERT are examples for Keyword tokens.
  4. Whitespace tokens This token used to separate other tokens. Here comments are also identified as white space tokens
Paser used to generate a parse tree by reading a stream of tokens. SQLite uses Lemon parser to parse SQL queries. Lemon parser allows SQLite C compiler to generate relevant C code from given sets of language rules. Language rules are defined by using Context Free Grammer(CFG). Example parser tree for the following SQL statement as follows.
SELECT title FROM StartsIn, MovieStar WHERE starName=”Jack” AND birthday like “%1990”slide_6.jpg
Here below an example, CFG rules to generate a program to evaluate a simple mathematical expression.
 1 program ::= expr(A). { std::cout << "Result=" << A << std::endl; } 2 3 expr(A) ::= expr(B) MINUS expr(C). { A = B - C; } 4 expr(A) ::= expr(B) PLUS expr(C). { A = B + C; } 5 expr(A) ::= expr(B) TIMES expr(C). { A = B * C; } 6 expr(A) ::= expr(B) DIVIDE expr(C). { 7 if(C != 0){ 8 A = B / C; 9 }else{ 10 std::cout << "divide by zero" << std::endl; 11 } 12 } 13 expr(A) ::= INTEGER(B). { A = B; }
Here MINUS, PLUS, TIMES and DIVIDE are the operator token generated by the tokenizer. In this code from line number 3 to 6 defined the CFG for mathematical operation. Lemon parser takes the precedence of these to operate as same as the given order. Think the given expression to evaluate is “3+5*6/3”. Tokenized output will be
3 PLUSE 5 TIMES 6 DIVIDE 3
According to the precedence, Lemon parser evaluate line #6 first and evaluate 6/3. Then it evaluates TIMES operation in line #5 and the result would be 10. Finally, it evaluates line #4 and generates the final result as 13. This result will be printed in line #1 which has the least precedence.
All of the SQL rules are defined in the same kind of structure as I described in the previous example.
While SQL query parsing, SQLite generate a sequence of instruction that needs to runs in order to generate the result. Each of these instructions has some operation to perform and inputs. It same as calling to a function with arguments. These generated codes are running on top of the Virtual machine. The virtual machine read each of this instruction one by one and evaluate it. To understand what are the available operations and how Virtual Machine works, we need to have a good understanding of Btree.
Btree is a data structure used to store data as a tree based on its value. The simplest form of the BTree is the Binary tree. Databases use a B-tree data structure to store indexes to improve the performance of the database. Data records are stored in a B+tree structure. If no indexing use, only B+tree used to store the data. A cursor is a special pointer which used to point a record( or row) which given with page id and offset. You can travel through all data records by using the cursor. To find the data in given Btree which used indexing, SQLite start move cursor to the root node first element and perform a B-tree search. If there are no Btree indexing available, SQLite searches the matching record in the B+tree by using linear search. You can find out more details about Btree in this article.
To search for data on a B+tree, the sequence of operation that generated by Code Generator as follows. You can check what was the sequence of instruction that needs to run for a particular SQL query by adding “explain” keyword at the beginning of the query.
explain select * from foo where value = "value";
0 |ColumnCount |1 |0 |
1 |ColumnName |0 |0 |value
2 |Open |0 |3 |foo 3 |VerifyCookie |46|0 | 4 |Rewind |0 |11| 5 |Column |0 |0 | 6 |Column |0 |0 |
7 |Ne |1 |10| 8 |Column |0 |0 |
9 |Callback |1 |0 | 10|Next |0 |5 | 11|Close |0 |0 | 
Pages are the smallest unit of a transaction on the file system. Btree and B+tree stored on the page. When the database needs to read data from a file, it requests it as a page. Once the page loaded into the database engine it can store page if it accesses 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.
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.
In this post, I tried to explain the SQLite database implementation at a high level. If you are interested to know more about the internal architecture of SQLite, I like to share my knowledge with you. So, comment down if there is any clarification/ improvement that needs to add. Also here my backend implementation that used to understand the SQLite architecture. In this repository, I tried to separate each of the layers in SQLite and write some test for each of the layers. You can find out SQLite 2.5 source code also that used to implement this project over here.