PostgreSQL Internals andIncremental View Maintenance
Implementation
Yu g o N a g a t a ( S R A O S S , I n c . J a p a n )https://2021.postgresconf.cn

About MeYugo Nagata
Software Engineer at SRA OSS, Inc. Japan

Research and Development on PostgreSQL

Incremental View Maintenance (IVM)

Lecture on PostgreSQL Internal

This Talk

PostgreSQL internals related to Incremental View Maintenance (IVM) implementation
Query and utility command processing related to materialized Views

Some components used in IVM implementation

For those who are interested in PostgreSQL internals

1. What is Incremental View
Maintenance?

CONTENT

2. Query Processing inPostgreSQL
3. Utility Command andMaterialized View
4. PostgreSQL Internal andIncremental View Maintenance
Implementation

What is Incremental View Maintenance?

What is Incremental View Maintenance? (1)A way to update materialized views rapidly

Clientquery
quick response

Table R

Table S

MaterializedView

View Definition Query“SELECT … FROM R, S ...”The results of the query arestored in database for quickresponse.

What is Incremental View Maintenance? (2)A way to update materialized views rapidly

Table R
ChangedTable S

Materialized Stale
View
inconsistent
View Definition Query“SELECT … FROM R, S ...”The results of the query are
stored in database for quick
response.
Needs to be maintained
after a base table is modified

What is Incremental View Maintenance? (3)A way to update materialized views rapidly=REFRESH MATERIALIZED VIEW
The latest stateof the table R

Table R

New!
Materialized
View

ChangedTable S

View Definition Query“SELECT … FROM R, S ...”

1.Re-compute the contents
using the latest state oftables.

What is Incremental View Maintenance? (4)A way to update materialized views rapidly=REFRESH MATERIALIZED VIEWNew!
The changeof the table R
ChangedMaterializedView

apply
Changeson the view

2.Compute and apply only theincremental change.

=

Table R

1.Re-compute the contents
using the latest state oftables.

Table S

View Definition Query“SELECT … FROM R, S ...”

Incremental View MaintenanceIncremental View Maintenance (IVM) on PostgreSQL
Not supported on PostgreSQL yet.

We have proposed to implement IVM on PostgreSQL.
Materialized views can be updated automatically and incrementally when a base table is updated.

Details will be explained in the last part.

PostgreSQL Query Processing

PostgreSQL Internals and Materialized View

Materialized Views needs to process SELECT query.


A view is created from the results of query processing.

CREATE MATERIALIZED VIEW mv AS
SELECT x, y FROM R, S WHERE R.i = S.i;

How a query is processed in PostgreSQL ?

Query Processing (1)query string
ParserParser

Check the syntax of the query

Build a parse tree

parse tree
Analyzer
src/backend/parser/gram.y

SELECT opt_all_clause opt_target_list
into_clause from_clause where_clausegroup_clause having_clause window_clause{
SelectStmt *n = makeNode(SelectStmt);n->targetList = $3;
n->intoClause = $4;
n->fromClause = $5;
n->whereClause = $6;
n->groupClause = ($7)->list;n->groupDistinct = ($7)->distinct;n->havingClause = $8;
n->windowClause = $9;$$ = (Node *)n;}syntax rule

query tree
Rewriterrewritten query tree

Building aquery tree
nodePlannerplan tree
ExecutortuplesQuery Processing (2)Analyzer

Perform semantic analysis

query stringParser
parse tree
Analyzer

system catalog look-up

Examples:table name → table OID

Expand “ * “ to column names

Identify OIDs of types, operators, etc.

Transform a parse tree to a query tree

query tree
Rewriterrewritten query tree
Planner
plan tree
ExecutortuplesQuery Processing (3)Rewriter

VIEW supportPlanner

Apply RULE to query tree

Create an optimal execution plan
Build a plan tree

Executor
Retrieve tuples in the way given by the plan tree
→ Where will the tuples go?

query string
Parserparse tree
Analyzer
query tree
Rewriterrewritten query tree
Planner
plan tree
ExecutortuplesqueryDestReceiverObject to manage tuple destination

In most queries, DestRemote is used.


ExecutortuplesResults are sent to frontend process.

Other cases:Sent to a file (COPY TO)

Sent to a new table (SELECT INTO, CREATE AS)

etc.

DestReceiver...
FilefrontendTableRecap: Query Processing
query string
ParserParserAnalyzer

RewriterPlannerExecutorparse tree
Analyzer
query tree
Rewritertuplesrewritten query tree
Planner

DestReceiverplan tree

The destination of tuples are managed
by DestReceiver
Filefrontend

Table...

ExecutorUtility Command and Materialized View

Utility Command

query string

CREATE, DROP, ALTER, COPY, VACUUM, REFRESH, etc..

Commands have to be parsed first.

Parserquery tree

parse tree
Analyzer

Some commands including SELECT need Analyzer.
SELECT INTO

CREATE TABLE AS

CREATE MATERIALIZED VIEW

etc...

Rewriter, Planner, and Executor are not required.

query tree
UtilityCommandRewriterrewritten query tree
Planner
plan tree
Executortuples

CREATE MATERIALIZED VIEW

The behavior is similar to CREATE AS / SELECT INTO

A relation is created from query results.

Implemented in the same function.
(ExecCreateTableAs in backend/commands/createas.c)

The view definition query are executed.
Rewriter, Planner, and Executor are called internally.

The results of the query are stored into a new table(= a materialized view).

Also, the query is stored in system catalog as a query tree.

CREATE MATERIALIZED VIEW
AS SELECT … FROM ...
view definition
Analyzer
query tree
ExecutortuplesDestIntoRel

MaterializedView

SystemCatalog

REFRESH MATERIALIZED VIEW

Update a materialized view by re-execute the view definition queryBasically, same as CREATE MATERIALIZED VIEW
The results of the view definition query are stored into atransient table.

The transient table and the materialized view are swapped.

Require a strong lock.

view definition
query tree

SystemCatalogExecutor
tuplesDestTransientRelMaterialized
View

Transient
Tableswap

REFRESH MATERIALIZED VIEW CONCURRENTLY

Update a materialized view with a weaker lock
The results of the view definition query are stored into a temporary
table.
Create the diff table by comparing the results and the materialized
view (using LEFT JOIN).
Finally, merge it to the materialized view(using DELETE and INSERT).

view definition
query tree

SystemCatalog

ExecutortuplesDestTransientRel

SQL queries are executed via SPI.
Materialized
View

Temporary
Table
make diffmerge

diffTableSPI: Server Programming Interface

A set of interface functions for running SQL commands in C functions.

Example:

SPI_exec("INSERT INTO tbl ...", 0);SPI_exec("SELECT ... FROM tbl WHERE ...", 0);

The results are stored in memory.
Can be accessed via a global variable SPI_tuptable.

SPI_exec(“SELECT … FROM ...”, 0);ExecutortuplesDestSPI

SPI_tuptableRecap: Utility Command of Materialized View


The view definition query are executed in commands.
The results are stored into various types of destinations
depending on the situation.
query tree
Executor

Controlled by DestReceiver.

tuplesDestReceiver

SQL queries are executed by using SPI.
(in REFRESH MATERIALIZED VIEW CONCURRENTLY command)

Transient
Table

Materialized
View

Temporary
TablePostgreSQL Internal andIncremental View Maintenance
Implementation

Incremental View Maintenance Implementation
Modification

extract

Changes
Deltaon
Delta
Delta
TablestablestablestablesBase
BaseTables
talbescalc
Changes
ビュー差分差分on（一次差分）
View

View Definition
Query
Materialized
View

apply

Incremental View Maintenance Implementation
Modification

AFTER trigger and Transition Tables
extract

Changes
Deltaon
Delta
Delta
TablestablestablestablesBase
BaseTables
talbesexecuting the view definition query
rewritten by using Transition Tables

calc

Changes
ビュー差分差分on（一次差分）
View

View Definition
Query
Materialized
View

apply

SQL via SPI

Creating Incrementally Maintainable Materialized Views (1)Syntax:Parser needs changes:

CREATE INCREMENTAL MATERIALIZED VIEW mv AS
SELECT x, y FROM R, S WHERE R.i = S.i;
src/backend/parser/gram.yCreateMatViewStmt:
CREATE OptNoLog incremental MATERIALIZED VIEW create_mv_target AS SelectStmt opt_with_data{
CreateTableAsStmt *ctas = makeNode(CreateTableAsStmt);
ctas->query = $8;
ctas->into = $6;
ctas->objtype = OBJECT_MATVIEW;...
$6->ivm = $3;$$ = (Node *) ctas;}...
incremental:
INCREMENTAL{ $$ = true; }| /*EMPTY*/{ $$ = false; }Creating Incrementally Maintainable Materialized Views (2)Changes in ExecCreateTableAs() (backend/commands/createas.c)

CREATE INCREMENTAL MATERIALIZED VIEW
AS SELECT … FROM ...

view definitionCheck the view definition to forbid unsupported query.
The query is rewritten before execution.
For aggregates and DISTINCT support



A unique index is created on the view if possible.

AFTER triggers are created on all base tables.

Analyzer
check!

query tree

SystemCatalog

rewriteExecutortuplesDestIntoRel
index
MaterializedView

triggers
TablesTablesTablesAFTER trigger

Fired just after a base table is modified.

In the IVM AFTER trigger function:
Changes on the table are extracted.

Changes on the view are calculated.

The calculated changes are applied to the view.

The changes on the table is extracted using Transition Table.

INSERT INTO R …
DELETE R …
UPDATE R ...

Executor

firetriggers

modifyMaterialized
View

TablesTablesTablesincrementallyupdate

Transition Tables (1): What is Transition Table?
Transition Tables:A feature of AFTER trigger.

Changes on tables can be referred to in the trigger function like normal tables by specified names.
AFTER trigger function
INSERT
UPDATE
DELETE

tuples deleted from the tablechangesold_tablerefer toTable

new_table
tuples inserted into the tableSELECT * FROM old_table;
SELECT * FROM new_table;

Transition Tables (2): How are the changes collected?
During modifying a table, each old and/or new tuple is put into tuplestores.
Table
INSERT
UPDATE
DELETEold tuple

old_tuplestore

tuplestoresnew_tuplestore
new tuple

Tuplestore

Temporary storage of tuples (in memory or disk)Used also for holdable cursor, CTE, set-returning functions, etc.

Transition Tables (3): How to access to Transition Tables?
A transition table is accessed as an Ephemeral Named Relation (ENR)
Tuples are stored in a tuplestore instead of database.

Referenced by the names instead of OID
Not exist in the catalogs

Ephemeral Named Relations
name: old_table

TableINSERTUPDATE
DELETE

oldtupleold_tuplestore
name: new_tablenewtuplenew_tuplestore

SELECT * FROM old_table;referenceby name SELECT * FROM new_table;view definition

Calculating Changes on Viewquery tree

Execute the view definition query with some rewrite:
SELECT x, y FROM R, S WHERE ...
SELECT x, y FROM new_table_R, S WHERE ...
transition table



Changes on Tables

Replacing the modified table with the transition table.
modified table

The results are stored into a tuplestores.

SystemCatalog

rewriteExecutortuplesDestTuplestore

Transition
Tuplestore
TablesChanges on View
Tuplestores
Tuplestoreview definition

Applying the Change to View

query tree

Create Ephemeral Named Relations (ENRs) from tuplestores that
contains changes on the view.

Changes on Tables

Apply these tuples in ENRs into the view.
Executing SQL by using SPI.


Use DELETE to remove tuples from the view.
Use INSERT to insert tuples into the view.

SystemCatalog

rewriteExecutortuples
DestTuplestore

Use UPDATE to update aggregated values in the view.
MaterializedView

Transition
Tuplestore
TablesChanges on View
ENRs
Tuplestore

apply by SQL

Recap: Incremental View Maintenance Implementation
CREATE INCREMENTAL MATERIALIZED VIEW

Transition Tables is used to extract the table changes

The parser and the function for this command are changed.

Tuples are stored in tuplestore and accessed as an Ephemeral
Named Relation (ENR).

Tuplestore and ENR are also used for calculating and applying theview changes.
The view changes are applied by using SQL via SPI.

view definition
query tree

Changes on Tables
Transition
Tuplestore
TablesrewriteExecutortuplesDestTuplestore

MaterializedView

Changes on View
ENRs
Tuplestore

apply by SQL

SummaryOverview of query processing and utility commands
The destination of results tuples are managed by DestReceiver

SPI can be used to run SQL queries.

Materialized View uses these infrastructure.

Incremental View Maintenance Implementation uses also:
AFTER trigger and transition tables

tuplestore and Ephemeral Named Relation

THANK YOUYugo Nagata(nagata @ sraoss.co.jp)