COMP9315 Introduction

COMP9315 DBMS Implementation1/139

( Data structures and algorithms inside relational DBMSs )

[Diagram:Pics/intro/pgsql-small.jpg]

Lecturer:   John Shepherd

Web Site:   http://www.cse.unsw.edu.au/~cs9315/

(If WebCMS unavailable, use http://www.cse.unsw.edu.au/~cs9315/16s1/)

Lecturer2/139

Name:John Shepherd
Office:K17-410 (turn right from lift)
Phone:9385 6494
Email:jas@cse.unsw.edu.au
Consults:Tue 3-4, Wed 2-3
Research: Information Extraction/Integration
Information Retrieval/Web Search
e-Learning Technologies
Multimedia Databases
Query Processing

What this Course is NOT3/139

Official course title: Database Systems Implementation

More accurate: Implementation of Database Engines

This is a course about

It is not a course about

Course Goals4/139

Introduce you to:

Develop skills in:

... Course Goals5/139

A major course goal is to give you significant exposure to:

Concepts will also be illustrated via their PostgreSQL implementation.

PostgreSQL is a good vehicle for this purpose, because:

... Course Goals6/139

At the end of this course you should understand:

At the end of this course you should be able to:

Pre-requisites7/139

We assume that you are already familiar with

If you don't know this material well, you will struggle to pass ...

Syllabus Overview8/139

  1. Relational DBMS Architecture
  2. Storage Management
  3. Relation Alegbra Operations
  4. Query Processing
  5. Transaction Processing
  6. Parallel and Distributed Databases
  7. Object Data, Document Data, Graph Data

Teaching/Learning9/139

Stuff that's available for you:

The onus is on you to use all of this material.

Note: Lecture slides, exercises and videos will be available only after the lecture.

... Teaching/Learning10/139

Things that you need to do:

Dependencies:

... Teaching/Learning11/139

Scheduled classes?

What to do if you have problems understanding stuff? Debugging is most easily done in person.

... Teaching/Learning12/139

The course web site site is where you can:

URL: http://www.cse.unsw.edu.au/~cs9315/

If WebCMS is ever down, most material is accessible via:

http://www.cse.unsw.edu.au/~cs9315/16s1/index.php

Prac Work13/139

Prac Work requires you to compile PostgreSQL from source code

Make sure you do the first Prac Exercise when it becomes available.

Sort out any problems ASAP (preferably at a consultation).

You can do prac work in groups, if you wish.

Assignments14/139

Schedule of assignment work:

Ass Description Due Marks
1 Storage Management Week 5 11%
2 Query Processing Week 11 14%

Assignments will be carried out in pairs (see WebCMS)

Choose your own online tools to share code (e.g. git,DropBox).

Ultimately, submission is via CSE's give system.

Will spend some time in lectures reviewing assignments.

Assignments will require up-front code-reading (see Pracs).

... Assignments15/139

Don't leave assignments to the last minute; you can submit early.

As a "carrot", bonus marks are available for early submissions.

As a "stick", marks deducted (from max) for late submissions.

[Diagram:Pics/intro/assline-small.png]

... Assignments16/139

More comments on assignments ...

You are responsible for managing your own time, and for committing enough time to complete your work in this course.

"Work pressure" is not an acceptable excuse for late assignments.

Plagiarism will be checked for and punished.

Slacking off and letting your partner do the work is unhelpful.

The exam will contain questions related to the assignment work.

Quizzes17/139

Over the course of the semester ...

Quizzes are primarily a review tool to check progress.

But they contribute 10% of your overall mark for the course.

Exam18/139

There will be a three-hour exam in the November exam period.

Exam is held in CSE Labs, but is mainly a written (typed) Exam.

The Course Notes (only) will be available in the exam.

Things that we can't reasonably test in the exam:

Everything else is potentially examinable.

The exam will be a mixture of descriptive questions, quantitative analysis, and small programming exercises.

The exam contributes 65% of the overall mark for this course.

Supplementary Assessment Policy19/139

Everyone gets exactly one chance to pass the Exam.

If you attend the Exam

If you're sick just before or on the day of the Exam

... Supplementary Assessment Policy20/139

All Special Consideration requests:

Supplementary Exams are on Wed 10 December Excuses like "I have already bought a plane ticket home" are not acceptable.

Passing this Course21/139

There is only one way to pass this course:

You are assessed based on your demonstrated competence.

Pleading for a pass on compassionate grounds won't work.

Assessment Summary22/139

Your final mark/grade will be computed according to the following: 

ass1   = mark for assignment 1      (out of 11)
ass2   = mark for assignment 2      (out of 14)
quiz   = mark for on-line quizzes   (out of 10)
exam   = mark for final exam        (out of 65)
okExam = exam > 26/65           (after scaling)

mark   = ass1 + ass2 + quiz + exam
grade  = HD|DN|CR|PS,  if mark ≥ 50 && okExam
       = FL,           if mark < 50 && okExam
       = UF,           if !okExam

Reading Material23/139

All of these textbooks have relevant material (to varying depths):

... Reading Material24/139

Useful material can also be found in:

These (and others) are available via the course web site.

PostgreSQL25/139

In this course, we will be using PostgreSQL v9.4.6   (compulsory)

PostgreSQL tarball is available for copying from the course web site.
(Don't waste your IP quota downloading it from www.postgresql.org)

Install/modify your own PostgreSQL server at CSE (from source code).

(This is not the same setup as for COMP3311; COMP3311 used a shared binary)

Working on a home PC is simple if you run Linux or Mac OSX.

Alternatively, use putty to connect to CSE from home.

However, you can do it all on Windows (see Chap.16 PostgreSQL manual)

... PostgreSQL26/139

PostgreSQL is a large software system:

You won't be required to understand all of it :-)

You will need to learn to navigate this code effectively.

Will discuss relevant parts in lectures to help with this.

... PostgreSQL27/139

Some comments on PostgreSQL books:

There's no need to buy a PostgreSQL reference book ...

Relational Database Revision

Relational Databases29/139

Relational databases build on relational theory

Relational theory provides the foundation, plus ... leading to modern relational DBMSs.

... Relational Databases30/139

We begin by looking at relational databases top-down

For the remainder of the semster, we work bottom-up.

Database Management Systems31/139

Relational DBMSs provide critical infrastructure for modern computing

Nowadays, some very large web sites are developing their own large-scale distributed solutions But even they run relational DBMSs in their "back-office".

DBMS History32/139

1960sFiles, Hierachical and network databases
1970Relational data model (Ted Codd)
1975First RDBMS and SQL (IBM Almaden)
1979First version of Oracle
1980sRefinement of technology, distributed systems, new data types (objects, Prolog)
1990sObject-relational DBMSs, OLAP, data mining, data warehousing, multimedia data, SQL standards
2000sDatabases for XML, bioinformatics, telecomms, SQL3
2000salso, very-large, distributed, relaxed-consistency storage

DBMS Functionality33/139

DBMSs provide a variety of functionalities:

Common feature of all relational DBMSs: relational model, SQL.

DBMS for Data Definition34/139

Critical function of DBMS: defining relational data   (DDL sub-language)

Relational data: relations/tables, tuples, values, types, constraints.

E.g. 

create domain WAMvalue float
   check (value between 0.0 and 100.0);

create table Students (
   id          integer,  -- e.g. 3123456
   familyName  text,     -- e.g. 'Smith'
   givenName   text,     -- e.g. 'John'
   birthDate   date,     -- e.g. '1-Mar-1984'
   wam         WAMvalue, -- e.g. 85.4
   primary key (id)
);

Executing the above adds meta-data to the database.

DBMSs typically store meta-data as special tables (catalog).

... DBMS for Data Definition35/139

Input: DDL statements

[Diagram:Pics/intro/ddl-stat-small.png]

Result: meta-data in catalog is modified

... DBMS for Data Definition36/139

Specifying constraints is an important aspect of data definition:

Examples: 

create table Employee (
   id      integer primary key,
   name    varchar(40),
   salary  real,
   age     integer check (age > 15),
   worksIn integer
              references Department(id),
   constraint PayOk check (salary > age*1000)
);

DBMS for Data Modification37/139

Critical function of DBMS: manipulating data   (DML sub-language)

E.g. 

insert into Enrolments(student,course,mark)
values (3312345, 5542, 75);

update Enrolments set mark = 77
where  student = 3354321 and course = 5542;

delete Enrolments where student = 331122333;

... DBMS for Data Modification38/139

Input: DML statements

[Diagram:Pics/intro/dml-stat-small.png]

Result: tuples are added, removed or modified

... DBMS for Data Modification39/139

Most DBMSs also provide bulk download/upload mechanisms:

For PostgreSQL:

DBMS as Query Evaluator40/139

Most common function of relational DBMSs

E.g. 

select s.id, c.code, e.mark
from   Students s, Courses c, Enrolments e
where  s.id = e.student and e.course = c.id;

... DBMS as Query Evaluator41/139

Input: SQL query

[Diagram:Pics/intro/query-small.png]

Output: table (displayed as text)

DBMS Architecture42/139

The aim of this course is to

Why should we care? (apart from passing the exam)

Practical reason:

Educational reason:

... DBMS Architecture43/139

Fundamental tenets of DBMS architecture:

Implications: In the past, DBMSs attempted to solve this by completely controlling disks themselves.

Modern DBMSs interact with storage via the O/S file-system.

... DBMS Architecture44/139

Implementation of DBMS operations is complicated by

Locking helps with concurrency, but may degrade performance.

In practice, may need new "concurrency-tolerant" data structures.

Transactions/reliability require some form of logging.

... DBMS Architecture45/139

Path of a query through a typical DBMS:

[Diagram:Pics/intro/qryeval1-small.png]

... DBMS Architecture46/139

Accoring to Silberschatz/Korth/Sudarshan (SKS) ...

[Diagram:Pics/intro/korth-dbms-small.png]

... DBMS Architecture47/139

Accoring to Elmasri/Navathe (EN) ...

[Diagram:Pics/intro/elmasri-dbms-small.png]

... DBMS Architecture48/139

According to Ramakrishnan/Gerhke (RG) ...

[Diagram:Pics/intro/dbmsarch-small.png]

... DBMS Architecture49/139

Query optimiser translates queries into efficient sequence of relational ops
Query executor controls execution of sequence of relational ops
Access methods basis for implementation of relational operations
Buffer manager manages data transfer between disk and main memory
Storage manager manages allocation of disk space and data structures
Concurrency manager controls concurrent access to database
Recovery manager ensures consistent database state after system failures
Integrity manager verifies integrity constraints and user privileges

Database Engine Operations50/139

DB engine = "relational algebra virtual machine":

selection (σ) projection (π) join (⋈)
union (∪) intersection (∩) difference (-)
sort group aggregate

For each of these operations:

... Database Engine Operations51/139

Different implementations of Selection:

Relational Algebra52/139

Relational algebra (RA) can be viewed as ...

Relational algebra consists of: RA can be viewed as the "machine language" for RDBMSs

... Relational Algebra53/139

Select, project, join provide a powerful set of operations for constructing relations and extracting relevant data from them.

[Diagram:Pics/intro/spj-small.png]

Adding set operations and renaming makes RA complete.

Notation54/139

Standard treatments of relational algebra use Greek symbols.

We use the following notation (because it is easier to reproduce):

Operation Standard
Notation		 Our
Notation
Selection σexpr(Rel) Sel[expr](Rel)
Projection πA,B,C(Rel) Proj[A,B,C](Rel)
Join Rel1 ⋈expr Rel2 Rel1  Join[expr]  Rel2
Rename ρschemaRel Rename[schema](Rel)

For other operations (e.g. set operations) we adopt the standard notation.

... Notation55/139

We define the semantics of RA operations using

... Notation56/139

All RA operators return a result relation (no DB updates).

For convenience, we can name a result and use it later.

E.g. 

Temp = R op1 S op2 T
Res  = Temp op3 Z
-- which is equivalent to
Res  = (R op1 S op2 T) op3 Z

Each "intermediate result" has a well-defined schema.

Sample Relations57/139

Example database #1 to demonstrate RA operators:

[Diagram:Pics/intro/db0-small.png]

... Sample Relations58/139

Example database #2 to demonstrate RA operators:

[Diagram:Pics/intro/db1-small.png]

Selection59/139

Selection returns a subset of the tuples in a relation r that satisfy a specified condition C.

σC(r)   =   Sel[C](r)   =   { t  |  t ∈ r ∧ C(t) },     where r(R)

C is a boolean expression on attributes in R.

Result size:   |σC(r)| ≤ |r|

Result schema:   same as the schema of r   (i.e. R)

Computational view: 

result = {}
for each tuple t in relation r
    if (C(t)) { result = result ∪ {t} }

... Selection60/139

Example selections:

[Diagram:Pics/intro/sel-eg-small.png]

... Selection61/139

Example queries:

Projection62/139

Projection returns a set of tuples containing a subset of the attributes in the original relation.

πX(r)   =   Proj[X](r)   =   { t[X]  |  t ∈ r },     where r(R)

X specifies a subset of the attributes of R.

Note that removing key attributes can produce duplicates.

In RA, duplicates are removed from the result set.
(In many RDBMS's, duplicates are retained   (i.e. they use bag, not set, semantics))

Result size:   |πX(r)| ≤ |r|     Result schema:   R'(X)

Computational view: 

result = {}
for each tuple t in relation r
    result = result ∪ {t[X]}

... Projection63/139

Example projections:

[Diagram:Pics/intro/proj-eg-small.png]

... Projection64/139

Example queries:

Union65/139

Union combines two compatible relations into a single relation via set union of sets of tuples.

r1 ∪ r2   =   { t  |  t ∈ r1 ∨ t ∈ r2 },     where r1(R), r2(R)

Compatibility = both relations have the same schema

Result size:   |r1 ∪ r2|   ≤   |r1| + |r2|     Result schema: R

Computational view: 

result = r1
for each tuple t in relation r2
    result = result ∪ {t}

... Union66/139

Example queries:

The union operator is symmetric i.e.   R ∪ S   =   S ∪ R.

Intersection67/139

Intersection combines two compatible relations into a single relation via set intersection of sets of tuples.

r1 ∩ r2   =   { t  |  t ∈ r1 ∧ t ∈ r2 },     where r1(R), r2(R)

Uses same notion of relation compatibility as union.

Result size:   |r1 ∪ r2|   ≤   min(|r1|,|r2|)     Result schema: R

Computational view: 

result = {}
for each tuple t in relation r1
    if (t ∈ r2) { result = result ∪ {t} }

... Intersection68/139

Example queries:

The intersection operator is symmetric i.e.   R ∩ S   =   S ∩ R.

Difference69/139

Difference finds the set of tuples that exist in one relation but do not occur in a second compatible relation.

r1 - r2   =   { t  |  t ∈ r1 ∧ ¬ t ∈ r2 },     where r1(R), r2(R)

Uses same notion of relation compatibility as union.

Note: tuples in r2 but not r1 do not appear in the result

i.e. set difference != complement of set intersection

Computational view: 

result = {}
for each tuple t in relation r1
    if (!(t ∈ r2)) { result = result ∪ {t} }

... Difference70/139

Example difference:

[Diagram:Pics/intro/diff-eg-small.png]

s1 = Sel [B = 1] (r1)

s2 = Sel [C = x] (r1)

s1 - s2

s2 - s1

... Difference71/139

Example queries:

Natural Join72/139

Natural join is a specialised product:

Consider relation schemas R(ABC..JKLM), S(KLMN..XYZ).

The natural join of relations r(R) and s(S) is defined as:

r ⋈ s   =   r Join s   =  
{ (t1[ABC..J] : t2[K..XYZ])  |  t1 ∈ r ∧ t2 ∈ s ∧ match }

where    match   =   t1[K] = t2[K] ∧ t1[L] = t2[L] ∧ t1[M] = t2[M]

Computational view: 

result = {}
for each tuple t1 in relation r
   for each tuple t2 in relation s
      if (matches(t1,t2))
         result = result ∪ {combine(t1,t2)}

... Natural Join73/139

Natural join can also be defined in terms of other relational algebra operations:

r Join s   =   Proj[R ∪ S] ( Sel[match] ( r × s) )

We assume that the union on attributes eliminates duplicates.

If we wish to join relations, where the common attributes have different names, we rename the attributes first.

E.g. R(ABC) and S(DEF) can be joined by

R Join Rename[S(DCF)](S)

Note: |r ⋈ s| ≪ |r × s|, so join not implemented via product.

... Natural Join74/139

Example natural join:

[Diagram:Pics/intro/natjoin-eg-small.png]

... Natural Join75/139

Example queries:

Theta Join76/139

The theta join is a specialised product containing only pairs that match on a supplied condition C.

r ⋈C s   =   { (t1 : t2)  |  t1 ∈ r ∧ t2 ∈ s ∧ C(t1 : t2) },
where r(R),s(S)

Examples:   (r1 Join[B>E] r2) ... (r1 Join[E<D ∧ C=G] r2)

Can be defined in terms of other RA operations:

r ⋈C s   =   r Join[C] s   =   Sel[C] ( r × s )

Unlike natural join, "duplicate" attributes are not removed.

Note that   r ⋈true s   =   r × s.

... Theta Join77/139

Example theta join:

[Diagram:Pics/intro/thetajoin-eg-small.png]

... Theta Join78/139

Comparison between join operations:

Equijoin is a specialised theta join; natural join is like theta join followed by projection.

Outer Join79/139

r Join s eliminates all s tuples that do not match some r tuple.

Sometimes, we wish to keep this information, so outer join

... Outer Join80/139

Example outer join:

[Diagram:Pics/intro/join-eg-small.png]

Contrast this to the result for theta-join presented earlier.

... Outer Join81/139

There are three variations of outer join R OuterJoin S:

Which one to use depends on the application e.g.

If we want to know about all Branches, regardless of whether they have Customers as their homeBranch:

Branches LeftOuterJoin[branchName=homeBranch] Customer

... Outer Join82/139

Computational description of r(R) LeftOuterJoin s(S): 

result = {}
for each tuple t1 in relation r
   nmatches = 0
   for each tuple t2 in relation s
      if (matches(t1,t2))
         result = result ∪ {combine(t1,t2)}
         nmatches++
   if (nmatches == 0)
      result = result ∪
                 {combine(t1,Snull)}

where Snull is a tuple from S with all atributes set to NULL.

Aggregation83/139

Two types of aggregation are common in database queries:

Generalised Projection84/139

In standard projection, we select values of specified attributes.

In generalised projection we perform some computation on the attribute value before placing it in the result tuple.

Examples:

PostgreSQL

PostgreSQL86/139

PostgreSQL is a full-featured open-source (O)RDBMS.

Brief History of PostgreSQL87/139

1977-1985 Ingres (Stonebraker)
research prototype
→ Relational Technologies
→ bought by Computer Associates
1986-1994 Postgres (Stonebraker)
research prototype
→ Illustra → bought by Informix
1994-1995 Postgres95 (Chen, Yu)
added SQL, spawned PostgreSQL
1996-... PostgreSQL (Momjian,Lane,...)
open-source DBMS with Oracle-level functionality, platform for experiments with new DBMS implementation ideas

PostgreSQL Online88/139

Web site: www.postgresql.org

Key developers: Bruce Momjian, Tom Lane, Marc Fournier, ...

Full list of developers: www.postgresql.org/developer/bios

Local copy of source code:

/home/cs9315/web/16s1/postgresql/src.tar.bz2

Documentation is available via WebCMS menu.

User View of PostgreSQL89/139

Users interact via SQL in a client process, e.g. 


$ psql webcms
psql (9.4.6)
Type "help" for help.
webcms2=# select * from calendar;
 id | course |   evdate   |      event
----+--------+------------+---------------------------
  1 |      4 | 2001-08-09 | Project Proposals due
 10 |      3 | 2001-08-01 | Tute/Lab Enrolments Close
 12 |      3 | 2001-09-07 | Assignment #1 Due (10pm)
 ...

or 


$dbconn = pg_connect("dbname=webcms");
$result = pg_query($dbconn,"select * from calendar");
while ($tuple = pg_fetch_array($result))
   { ... $tuple["event"] ... }

PostgreSQL Functionality90/139

PostgreSQL systems deal with various kinds of entities:

... PostgreSQL Functionality91/139

PostgreSQL's dialect of SQL is mostly standard (but with extensions).

Differences visible at the user-level:

Differences at the implementation level: Example: 


create view myview as select * from mytab;
-- is implemented as
create type as myview (same fields as mytab);
create rule myview as on select to myview
            do instead select * from mytab;

... PostgreSQL Functionality92/139

PostgreSQL stored procedures differ from SQL standard:

Example: 


create or replace function
    barsIn(suburb text) returns setof Bars
as $$ 
declare
    r record;
begin
    for r in
        select * from Bars where location = suburb
    loop
       return next r;
    end loop;
end;
$$ language plpgsql;
used as e.g.
select * from barsIn('Randwick');

... PostgreSQL Functionality93/139

Concurrency is handled via multi-version concurrency control (MVCC)

Disadvantages of this approach:

... PostgreSQL Functionality94/139

Allows transactions to specify a consistency level for concurrency

Explicit locking is also available. Access methods need to implement their own concurrency control.

... PostgreSQL Functionality95/139

PostgreSQL has a well-defined and open extensibility model:

... PostgreSQL Functionality96/139

Because of its extensibility, PostgreSQL has extra data types:

Also has a wider-than-usual range of access methods: And provides a range of replication services.

Installing PostgreSQL97/139

PostgreSQL is available via the COMP9315 web site.

Provided as tarball and zip in ~cs9315/web/16s1/postgresql/

Brief summary of installation: 

$ configure --prefix=~/your/pgsql/directory
$ make
$ make install
$ source ~/your/environment/file
   # set up environment variables
$ initdb
   # set up postgresql configuration
$ pg_ctl start
   # do some work with PostgreSQL databases
$ pg_ctl stop

... Installing PostgreSQL98/139

Simplified version of running the server: 

$ source ~/your/environment/file
   # set up environment variables
$ pgs setup
   # runs initdb and fixes configuration
$ pgs start
   # do some work with PostgreSQL databases
$ pgs stop
   # stops server
$ pgs cleanup
   # removes all data files

pgs is a shell script in /home/cs9315/bin

PostgreSQL Configuration99/139

PostgreSQL configuration parameters (some important ones):

Note: if not using TCP/IP, PGHOST holds name of directory where Unix socket files reside.

... PostgreSQL Configuration100/139

A typical envrionment setup for COMP9315: 

# Set up environment for running PostgreSQL
# Must be "source"d from sh, bash, ksh, ...

PGHOME=/home/jas/srvr/pgsql
export PGDATA=$PGHOME/data
export PGHOST=$PGDATA
export PGPORT=5432
export PATH=$PGHOME/bin:$PATH
export PGDATA PGHOST PATH

alias p0="$D/bin/pg_ctl stop"
alias p1="$D/bin/pg_ctl -l $PGDATA/log start"

... PostgreSQL Configuration101/139

Other configuration files live in $PGDATA.

postgresql.conf: server configuration

pg_hba.conf: authorisation/user access

Using PostgreSQL for Assignments102/139

You will need to modify then re-start the server: 

# edit source code to make changes
$ pg_ctl stop
$ make
$ make install
# restore postgresql configuration
$ pg_ctl start
# run tests and analyse results

Assumes no changes that affect storage structures.

I.e. existing databases will continue to work ok.

... Using PostgreSQL for Assignments103/139

If you change storage structures ... 

# edit source code to make changes
$ pg_dump testdb > testdb.dump
$ make
$ pg_ctl stop
$ rm -fr /your/pgsql/directory/data
$ make install
$ initdb
# restore postgresql configuration
$ pg_ctl start
$ createdb testdb
$ psql testdb -f testdb.dump
# run tests and analyse results

Need to save a copy of postgresql.conf before re-installing.

PostgreSQL Architecture104/139

Client/server architecture:

[Diagram:Pics/intro/proc-arch-small.png]


Note: nowadays the postmaster process is also called postgres.

... PostgreSQL Architecture105/139

Notes:

... PostgreSQL Architecture106/139

Memory/storage architecture:

[Diagram:Pics/intro/mem-arch-small.png]

... PostgreSQL Architecture107/139

Notes:

... PostgreSQL Architecture108/139

File-system architecture:

[Diagram:Pics/intro/file-arch-small.png]

... PostgreSQL Architecture109/139

Interesting files in $PGDATA:

PG_VERSION which server version made this directory
pg_hba.conf who can access which databases from where
postgresql.conf server parameters   (e.g. max connections)
postmaster.opts how was current postmaster invoked
postmaster.pid process id of current postmaster

PostgreSQL Source Code

PostgreSQL Source Code111/139

Top-level of PostgreSQL distribution contains:

... PostgreSQL Source Code112/139

How to get started understanding the workings of PostgreSQL:

Some helpful information is available via:

... PostgreSQL Source Code113/139

The source code directory (src) contains:

along with Makefiles to build system and other directories not relevant for us Code for backend (DBMS engine)

... PostgreSQL Source Code114/139

We introduce the code

PostgreSQL manual has detailed description of internals: See also "How PostgreSQL Processes a Query"

Life-cycle of a PostgreSQL query115/139

How a PostgreSQL query is executed:

... Life-cycle of a PostgreSQL query116/139

[Diagram:Pics/intro/pg-processes-small.png]

PostgreSQL server117/139

PostgresMain(int argc, char *argv[], ...)

... PostgreSQL server118/139

As well as handling SQL queries, PostgresqlMain also

... PostgreSQL server119/139

exec_simple_query(const char *query_string)

... PostgreSQL server120/139

Functions involved in exec_simple_query(...) 


parsetree_list = pg_parse_query(query_string);
foreach(parsetree, parsetree_list) {
  querytree_list = pg_analyze_and_rewrite(parsetree, ...);
  plantree_list = pg_plan_queries(querytree_list, ...);
  portal = CreatePortal(...); // query execution env
  PortalDefineQuery(portal, ..., plantree_list, ...);
  receiver = CreateDestReceiver(dest); // client
  PortalRun(portal, ..., receiver, ...);
  ...
}

(For the time being, to simplify description, many details omitted)

PostgreSQL Data Types121/139

Data types defined in *.h files under src/include/

Two important data types: Node and List

... PostgreSQL Data Types122/139

Generic Node = type tag + specific node struct

Node structures are defined for

Other structures defined in PostgreSQL include: See under src/include/ for full details.

Query Parser123/139

pg_parse_query(char *sqlStatements)

... Query Parser124/139

[Diagram:Pics/intro/parse-tree-small.png]

Query Rewriter125/139

pg_analyze_and_rewrite(Node *parsetree, ...)

... Query Rewriter126/139

Raw parse tree from parser is a syntax tree.

parse_analyze() performs semantic analysis

Checking yields data about objects used in query.

Object data is added to parse tree data to make Query

... Query Rewriter127/139

Each query is represented by a Query structure

... Query Rewriter128/139

[Diagram:Pics/intro/query-struct-small.png]

Query Planner129/139

pg_plan_queries(querytree_list, ...)

... Query Planner130/139

Each executable query is represented by a PlannedStmt node

Each Plan node represents one relational operation

... Query Planner131/139

[Diagram:Pics/intro/plan-tree-small.png]

... Query Planner132/139

PlannedStmt *planner(Query *parse, ...)

... Query Planner133/139

PostgreSQL has two methods of generating execution orders

See src/backend/optimizer/README for full details

Query Executor134/139

Queries run in a Portal environment containing

Portal defined in src/include/utils/portal.h

PortalRun() functions also require

... Query Executor135/139

How query evaluation is invoked:

... Query Executor136/139

Run-time data structures: QueryDesc, EState, PlanState

QueryDesc structure holds run-time state of query

EState structure holds working state for executor

... Query Executor137/139

PlanState nodes contain state for one physical operation

Plus fields for specific operations in PlanState subclasses.

PlanStates implement iterators: init()...next()...end()

... Query Executor138/139

ExecutePlan(eState, planState, ...)

... Query Executor139/139

ExecProcNode(PlanState *node)

Produced: 28 Feb 2016