Temporal PostgreSQL

A Range Merge Join for PostgreSQL

The objective of this project is to provide an implementation of a range join in PostgreSQL based on the sort-merge paradigm. This project is based on the BSc thesis of Thomas Mannhart.

Examples

Joining available employees with events

Given a relation emps that records employees (name) working in a department (dept) for the period eperiod, and a relation events that records events (event) within a department dept taking place on a specific date (day). Find which employees are available for a specific event.

name	dept	eperiod
Anton	Sales	[01-01-2020, 31-03-2020]
Thomas	Marketing	[01-01-2020, 30-06-2020]
Michael	Marketing	[01-03-2020, 31-12-2020]
Hans	Sales	[01-01-2020, 31-12-2020]
Thomas	Accounting	[01-07-2020, 31-12-2020]

event	dept	day
Fair CH	Marketing	05-03-2020
Presentation	Sales	15-06-2020
Fair IT	Marketing	03-08-2020
Balance Report	Accounting	03-08-2020
Product launch	Marketing	15-10-2020

SELECT name, emps.dept, event, day FROM emps JOIN events ON emps.dept = events.dept AND day <@ eperiod;;

name	dept	event	day
Thomas	Marketing	Fair CH	05-03-2020
Michael	Marketing	Fair CH	05-03-2020
Michael	Marketing	Fair IT	03-08-2020
Michael	Marketing	Product launch	15-10-2020
Hans	Sales	Presentation	15-06-2020
Thomas	Accounting	Balance Report	03-08-2020

QUERY PLAN --------------------------------------------------------------------------------------------- Range Merge Join (cost=106.73..118.01 rows=3 width=100) (actual rows=6 loops=1) Merge Cond: (emps.dept = events.dept) Range Cond: (events.day <@ emps.eperiod) -> Sort (cost=46.87..48.49 rows=650 width=96) (actual rows=5 loops=1) Sort Key: emps.dept, emps.eperiod Sort Method: quicksort Memory: 25kB -> Seq Scan on emps (cost=0.00..16.50 rows=650 width=96) (actual rows=5 loops=1) -> Sort (cost=59.86..61.98 rows=850 width=68) (actual rows=6 loops=1) Sort Key: events.dept, events.day Sort Method: quicksort Memory: 25kB -> Seq Scan on events (cost=0.00..18.50 rows=850 width=68) (actual rows=5 loops=1) Planning Time: 0.088 ms Execution Time: 0.074 ms (13 rows)

Joining student marks with grading ranges

Given a relation marks that records students (name), their student number (snumber) along with their achieved mark (mark), and a relation grades that records the grade (grade) to assign when achieving a mark between mmin mmax. Find for each student the grade to assign.

name	snumber	mark
Anton	1232	23.5
Thomas	4356	95
Michael	1125	72
Hans	3425	90

mmin	mmax	grade
0.0	18	1
18.5	36	2
36.5	54	3
54.5	72	4
72.5	90	5
90.5	100	6

SELECT name, snumber, grade FROM marks JOIN grades ON mark BETWEEN mmin AND mmax;

name	snumber	grade
Anton	1232	2
Thomas	4356	6
Michael	1125	4
Hans	3425	5

QUERY PLAN -------------------------------------------------------------------------------------------- Range Merge Join (cost=2.22..2.32 rows=3 width=14) (actual rows=4 loops=1) Range Cond: ((marks.mark >= grades.mmin) AND (marks.mark <= grades.mmax)) -> Sort (cost=1.14..1.15 rows=6 width=20) (actual rows=6 loops=1) Sort Key: grades.mmin Sort Method: quicksort Memory: 25kB -> Seq Scan on grades (cost=0.00..1.06 rows=6 width=20) (actual rows=6 loops=1) -> Sort (cost=1.08..1.09 rows=4 width=18) (actual rows=7 loops=1) Sort Key: marks.mark Sort Method: quicksort Memory: 25kB -> Seq Scan on marks (cost=0.00..1.04 rows=4 width=18) (actual rows=4 loops=1) Planning Time: 0.116 ms Execution Time: 0.056 ms (12 rows)