Geekly Articles each Day
📜 ⬆️ ⬇️

How a relational database works

Relational databases (DDB) are used everywhere. They come in all sorts of ways, from small and useful SQLite to powerful Teradata. But at the same time there are very few articles explaining the principle of operation and the device of relational databases. Yes, and those that are - quite superficial, without much detail. But in more “fashionable” areas (big data, NoSQL or JS) many more articles are written, and much more profound. Probably, this situation is due to the fact that relational databases are “old” and too boring to be disassembled outside university programs, research papers and books.

In fact, few people really understand how relational databases work. And many developers do not like it when they do not understand something. If relational databases use about 40 years, then there is a reason. RBD is a very interesting thing, because it is based on useful and widely used concepts. If you would like to understand how RBDs work, then this article is for you.

Immediately you need to emphasize: from this material you will not learn how to use the database. However, to assimilate the material, you should be able to write at least a simple connection request and a CRUD request. This is quite enough for understanding the article, the rest will be explained.

The article consists of three parts:
  1. Overview of low-level and high-level database components.
  2. Overview of query optimization.
  3. Overview of transaction and buffer pool management.

')

1. Basics


Once upon a time (in a far-away galaxy), developers had to keep in mind the exact number of operations they code. They felt the algorithms and data structures with all their hearts, because they could not afford to waste processor and memory resources on their slow computers of the past. In this chapter, we will recall some concepts that are necessary for understanding database operation.

1.1. O (1) vs O (n 2 )


Today, many developers do not really think about the time complexity of algorithms ... and they are right! But when you have to work with a large amount of data, or if you need to save milliseconds, the time complexity becomes extremely important.

1.1.1. Concept

The time complexity is used to evaluate the performance of the algorithm, how long the algorithm will be executed for the input data of a certain size. The time complexity is denoted as “O” (read as “O big”). This designation is used in conjunction with a function that describes the number of operations performed by the algorithm for processing input data.

For example, if you say “this algorithm is O large from a certain function”, then this means that for a certain amount of input data, the algorithm needs to perform a number of operations proportional to the value of the function from this certain amount of data.

Here it is not the volume of data that is important, but the dynamics of the increase in the number of operations with increasing volume. The time complexity does not allow to calculate the exact amount, but it is a good way to estimate.



In this graph, you can see how different classes of complexity change. For clarity, a logarithmic scale is used. In other words, the amount of data is rapidly increasing from 1 to 1,000,000. We see that:


1.1.2. Examples

With a small amount of input data, the difference between O (1) and O (n 2 ) is negligible. Suppose we have an algorithm that needs to process 2000 elements.

It seems that the difference between O (1) and O (n 2 ) is huge, but in fact you will lose no more than 2 ms. Eye blink do not have time, literally. Modern processors perform hundreds of millions of operations per second , and that is why in many projects, developers neglect performance optimization.

But now we take 1 000 000 elements, which is not too much by the standards of the database:

In the case of the last two algorithms, you can have time to drink coffee. And if you add another 0 to the number of elements, then during the processing you can take a nap.

1.1.3. Some more details

So that you can navigate:

Below we look at these algorithms and data structures.

There are several time complexity classes:

The most common third grade. By the way, the concept of "complexity" is also applicable to the consumption by the algorithm of memory and I / O operations of the disk system.

There are difficulties far worse than n 2 :


1.2. Merge sort


What do you do when you need to sort a collection? Call the sort () function, right? But do you understand how it works?

There are a few good sorting algorithms, but here we look at only one of them: merge sort. Perhaps now this knowledge does not seem useful to you, but you will change your opinion after the chapters on query optimization. Moreover, an understanding of the operation of this algorithm will help to understand the principle of an important operation - merge merging.

1.2.1. Merger

The merge sorting algorithm is based on one trick: to merge two sorted arrays of size N / 2, each requires only N operations, called merge.

Consider an example of a merge operation:



As you can see, to create a sorted array of 8 elements, for each of them you need to carry out one iteration in two source arrays. Since they are already sorted in advance, then:
  1. First, they compare the available elements
  2. the smallest of them is transferred to the new array,
  3. and then returns to the array from which the previous element was taken.
  4. Steps 1-3 are repeated until only one element remains in one of the source arrays.
  5. After that, all the remaining elements are transferred from the second array.

This algorithm works well only because both source arrays were sorted in advance, so it does not need to return to their beginning during the next iteration.

An example of merge sort pseudo code:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

( « »). , , :

1.2.2.



, . , log(N) ( N=8, log(N) = 3). , . 2.

1.2.3.



, . 8 :

log(N), N * log(N).

1.2.4.

?

! ( ) , . , , .

1.3. , -


, ό . , .

1.3.1.

— . :



- , — . ( , , ..).

, , - . , , . , , “UK”. N (N — ). , . .

: , (, ). .

1.3.2.

— , :



.

N = 15 . , 208:

, 40:

. Log(N), .

.

, , . . , “UK”, , , ID , . , log(N) . .

( , , , ..), (.. ). .

+

, , . á (N), . , /, . . — +. , (ID ) («»), .



, . « » , ID . (log(N)) ( ). B- , «» .

, 40 100:

N , . log(N) , . , . + log(N) , N . , + log(N) , . (, 200), N — , , (1 000 000), .

. , , , +, :

, + . , + . , «» . : + (log(N)). : . // , , (log(N)) . , .

+ , (, ) MySQL. , InnoDB ( MySQL) .

1.3.3. -

, . - , - (hash join). - ( , ). . - :

-:



10 , - 10 . : 0, 0, 1, 1, .. .

, 78:

: .

7 .

, . -, 1 000 000 ( 6 ). 59 , 000059 . -, .

. . -, :

..
-, (1).

-

? , :

Java HashMap, -. Java, .

2.


. .

, . . , , SQLite, . , , SQLite :

:



, , . . , , .

(Core Components):

(Tools):

(Query Manager):

(Data Manager):

, SQL- :

3.




— - /. API (JDBC, ODBC, OLE-DB ..), .

:

4.




. , , . :

, :

4.1.


SQL- . , . , SLECT SELECT.

. , . , WHERE SELECT, .

. :

, ( ) . DBA.

SQL- ( ). , .

4.2.


:

. , . :

, :

SELECT PERSON.*
FROM PERSON
WHERE PERSON.person_key IN
(SELECT MAILS.person_key
FROM MAILS
WHERE MAILS.mail LIKE 'christophe%');

:

SELECT PERSON.*
FROM PERSON, MAILS
WHERE PERSON.person_key = MAILS.person_key
and MAILS.mail LIKE 'christophe%';



, .

4.3.


, , . , , .

?

, . , ( 4 8 ). 1 , - . .

. , :

/, .

. , : «» «». , 1 000 «» 1 000 000 — «». — «, », «, »: , , 2-3 .

. . . , , .. . (WHERE AGE=18) (WHERE AGE > 10 AND AGE < 40), , (, ).

. , :

. , , , 500 , 1 000 000. , , . , . , (, 10%) . , , . .

, . PostgreSQL.

4.4.


CBO (Cost Based Optimization), . , «», «» .

, . ỳ , «» , /. á — , , , if, , ..

:

. , , .

4.4.1.

, -. , . , , , (bitmap index). , -. , , .

4.4.2.

, . .

4.4.3.

, , , . : . :

, -. , A JOIN B , , — .

A JOIN B B JOIN A.

, N , — . , . N M .

?

, . :

DB2, ORACLE SQL Server.

4.4.4.

, , . :

:

SELECT * from PERSON, MOBILES, MAILS,ADRESSES, BANK_ACCOUNTS
WHERE
PERSON.PERSON_ID = MOBILES.PERSON_ID
AND PERSON.PERSON_ID = MAILS.PERSON_ID
AND PERSON.PERSON_ID = ADRESSES.PERSON_ID
AND PERSON.PERSON_ID = BANK_ACCOUNTS.PERSON_ID

. :
  1. ? (-, , ), 0, 1 2 . , .
  2. ?

, :



, ?
  1. -. . . , 34=81 . , (2 * 4)! / (4 + 1)!.. , 34 * (2 * 4)! / (4 + 1)! = 27 216. , 0, 1 2 -, 210 000. , ?
  2. . , , .
  3. . , , .
  4. «» .
    :
    1. «», . . , « ».
    2. . , « , , — -».

. : OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT .. .

?

4.4.5. , «»

, . . , .

. . .

, .



A JOIN B. , , . , , .

ό (2*N)!/(N+1)! « » 3N. 336 81. 8 ( ), 57 657 600 6 561.

, :

procedure findbestplan(S)
if (bestplan[S].cost infinite)
   return bestplan[S]
// else bestplan[S] has not been computed earlier, compute it now
if (S contains only 1 relation)
         set bestplan[S].plan and bestplan[S].cost based on the best way
         of accessing S  /* Using selections on S and indices on S */
     else for each non-empty subset S1 of S such that S1 != S
   P1= findbestplan(S1)
   P2= findbestplan(S - S1)
   A = best algorithm for joining results of P1 and P2
   cost = P1.cost + P2.cost + cost of A
   if cost < bestplan[S].cost
       bestplan[S].cost = cost
      bestplan[S].plan = “execute P1.plan; execute P2.plan;
                 join results of P1 and P2 using A”
return bestplan[S]

, (), :



, , — .

(). . JOIN, JOIN .

. 4 5 (A, B, C, D E). , . « ».

, B, C .. , .

« ».

, N*log(N) . á (N*log(N)) (3N) . 20 , 26 3 486 784 401. , ?

. , , . A JOIN B , (A JOIN C) JOIN B , (A JOIN B) JOIN C.

, .



, . .

. - . , , ..

. . , . , , , .

:

, . , , .
, PostgreSQL.

, (Simulated Annealing), (Iterative Improvement), (Two-Phase Optimization). , , , — .

4.4.6.

, .

. , SQLite. «» , :

. IBM DB2, , 7 :

5. :

, , , — . , , .

(GROUP BY, DISTINCT ..) .

4.4.7.

, . . , . , , , , .


. , , . , (JOIN, SORT BY ..) , , . .

5.




. , :

5.1.


, . .



, , . , . , , :

, : «» , SSD, RAID . , 100-100 000 , .

. , . .

5.1.1.

, , , , .

, . , , .

. (, latch), .

, , . (speculative prefetching) (, 1, 3, 5, 7, 9, 11) (sequential prefetching) ( .

« /» (buffer/cache hit ratio). , , . . Oracle.

, . . . , . .

5.1.2.

( , SQL Server, MySQL, Oracle DB2) LRU (Least Recently Used). , , , .



, (latch), . :
  1. 1 .
  2. 4 .
  3. 3.
  4. 9. - . 1, . 9.
  5. 4. , .
  6. 1. , 3, .

, . ? , / ? , , , .



, . Oracle:

« , , . , . , LRU, ».

LRU — LRU-K. SQL Server LRU-K = 2. , , . , , . . , , , . , , - . , .

, SQL Server LRU-K 2. . 1993- .



, LRU-K . 2Q CLOCK ( LRU-K), MRU (Most Recently Used, LRU, , LRFU (Least Recently and Frequently Used) .. , .

5.1.3.

, , , . /.
, ( ), . «», , . , . .

5.2.


, . , ACID-.

5.2.1. « » ( , )

ACID- (Atomicity, Isolation, Durability, Consistency) — , , 4 :




- SQL- , , . , . — . , :

ACID-:

, .

, . SQL 4 :


(, , PostgreSQL, Oracle SQL Server). , .

. .

5.2.2.

, , , (, ).

, , .
, , . , , .

.

. ( ), .

( ):

, . , . . , .

5.2.3.

(locks) / .
- , . , , .

.

, . ? . , . . - , , . . , .



— , . - ( ). , .

(deadlock)

, :



1 2. 2 1.

, ( ). :

, , .

- , . , . ( , , ), : . , .

, . , . .



, . , , . , .

DB2 SQL Server , :

, :



X = 1 Y = 1. Y = 1, . Y = 2.

, :

, , , . , . , .

, , ( , , , , ), .



— .

, :

, , , , . .

— — , , ( ). , PostgreSQL.

(DB2 9.7, SQL Server) . , PostgreSQL, MySQL Oracle, .

: . , , ..

, , , . .

, : MySQL, PostgreSQL, Oracle.

5.2.4.

, . , . .

, , , .

, , .

:

WAL

/ . . .

( , Oracle, SQL Server, DB2, PostgreSQL, MySQL SQLite) WAL (Write-Ahead Logging). :
  1. , , .
  2. .
  3. , .



. . , , . ?

! , , , « ». , , , . , .

ARIES

1992 IBM WAL, ARIES. ARIES . , .

, ARIES Algorithms for Recovery and Isolation Exploiting Semantics. :
  1. .
  2. .

, :
  1. .
  2. .
  3. . , UNIQUE, .
  4. .

, , .

? , , .


(//) . :

, ( , ) LSN , .

, UNDO PostgreSQL. , . .

, , UPDATE FROM PERSON SET AGE = 18;. 18:



LSN. , ( ).


, .



:
  1. .
  2. .
  3. , , , , .
  4. . .
  5. . .

, , 1 5. , « - ». , , .

STEAL FORCE

5 , REDO. « NO-FORCE».

FORCE . 5 .

, ( STEAL) , , (NO-STEAL). , : ?

:



, ? , ( №1: !). .
ARIES :
  1. . , , . , . . , .
  2. . REDO. . LSN , , .

    LSN(__)>=LSN(__), . , . , .

    LSN(__)<LSN(__), .

    , , . .
  3. . . UNDO PrevLSN.

, . , . , , . ARIES , .

«», , - , . REDO UNDO , :

, . , .

. ARIES . , LSN. , LSN.

6.


Architecture of a Database System. , .

, , . :

, NoSQL . , NoSQL- . , .

, - , , , , :



.

Source: https://habr.com/ru/post/266811/

More articles:


All Articles