We all know that DBMS (database management system) is used to store (a massive amount of) data. However, have you ever wondered how is data stored in DBMS? In this post, we will focus on data storage in RDBMS, the most traditional relational database systems.

Physical Storage

Data can be stored in many different kinds of medium or devices, from the fastest but costy registers to the slow but cheap hard drives, or even magnetic tapes. Nowadays, IaaS providers such as AWS even provides services such as S3 Glacier as a low-cost archiving storage solution. The diagram below shows the memory hierarchy of common devices.

This post talks about some basic implementation of relational operators in traditional RDBMS (relational database management systems). It was based on Chapter 14 of the textbook by Raghu Ramakrishnan and Johannes Gehrke.

Below we will talk about the classical evaluation & implementation of relational operators one-by-one, namely:

• Selection
• Projection
• Join, cross product
• Set operations (intersection, union, difference)
• Grouping & aggregation

Recently, I was looking at some research papers on the join reorderability. To start with, let’s understand what do we mean by “join reorderability” and why it is important.

Background Knowledge

Here, we are looking at a query optimization problem, specifically join optimization. As mentioned by Benjamin Nevarez, there are two factors in join optimization: selection of a join order and choice of a join algorithm.

As stated by Tan Kian Lee’s lecture notes, common join algorithms include iteration-based nested loop join (tuple-based, page-based, block-based), sort-based merge join and partition-based hash join. We should consider a few factors when deciding which algorithm to use: 1) types of the join predicate (equality predicate v.s. non-equality predicate); 2) sizes of the left v.s. right join operand; 3) available buffer space & access methods.

For a query attempting to join n tables together, we need n - 1 individual joins. Apart from the join algorithm applied to each join, we have to decide in which order these n tables should be joined. We could represent such join queries on multiple tables as a tree. The tree could have different shapes, such as left-deep tree, right-deep tree and bushy tree. The 3 types of trees are compared below on an example of joining 4 tables together.

In this post, I will discuss a few common partition techniques in distributed cache. Especially, I will elaborate on my understanding on the use of Redis Cluster.

Please understand that at the time of writing, the latest version of Redis is 4.0.10. Many articles on the same topic have a different idea from this post. This is mainly because, those articles are probably outdated. In particular, they may refer to the Redis Cluster implementation in Redis 3. Redis Cluster has been improved a lot since Redis 4.

(This article was based on part of my project report. You may want to take a look at the full report here. You may need a valid account to gain access to NUS SoC Digital Library.)

Common Partition Techniques

Here, we refer to horizontal partitioning, which is also known as data sharding. Traditionally, there are 3 approaches to achieve data partitioning, namely, server-side partitioning, cluster proxy, and client-side partitioning.