Relational Memory:

Native In-Memory Accesses on Rows and Columns

Data Layouts

row-stores

column-stores

2

Data Layouts

row-stores

column-stores

3

Transactional

Data Layouts

row-stores

column-stores

4

Analytical

Adaptive layout

5

row store

queries accessing �the entire rows

E.g., H2O (ACM SIGMOD, 2014), HyPer (IEEE ICDE , 2011), Peloton (ACM SIGMOD, 2016), OctopusDB (CIDR, 2011)

Adaptive layout

6

row store

column store

multiple copies of data with different layouts

queries accessing �the entire rows

queries accessing�some of columns

→ complexity ↑�less scalable

E.g., H2O (ACM SIGMOD, 2014), HyPer (IEEE ICDE , 2011), Peloton (ACM SIGMOD, 2016), OctopusDB (CIDR, 2011)

How can we access �only the desired columns�without storing or maintaining�multiple copies of data?

7

a novel hardware design 

for data transformation

Relational Memory

PS-PL �Platforms

8

DRAM

CPU

Processing System

Programmable

Logic

Any logic can be programmed!

Relational �Memory �Engine

9

�

DRAM

Programmable

Logic

CPU

Processing System

Relational �Memory �Engine

10

DRAM

On-the-fly �vertical�partitioning

CPU

Processing System

Relational �Memory �Engine

11

�

DRAM

On-the-fly �vertical�partitioning

CPU

Processing System

Q1: how to build?

Q2: how to use?

ephemeral variable

a simple, lightweight programming abstraction

to use Relational Memory

​

12

struct row table[ ];

leads to normal memory accesses

[[ephemeral]] struct col_group cg[ ];

fake address that CPU thinks it exists

intercepted by RME

13

CPU

base row store

struct row {

string name;

int ID ;

int age ;

int height ;

int weight ;

};

ephemeral variable

Not instantiated in main memory

optimal layout

[[ephemeral]] struct column_group cg[];

SELECT NAME

FROM table� WHERE weight/height>25;

struct column_group {

string NAME ;

int height ;

int weight ;

};

14

CPU

base row store

SELECT NAME

FROM table� WHERE weight/height>25;

optimal layout

struct row {

string name;

int ID ;

int age ;

int height ;

int weight ;

};

Programmable logic

ephemeral variable

on-the-fly

data transformation

[[ephemeral]] struct column_group cg[];

15

CPU

base row store

SELECT NAME

FROM table� WHERE weight/height>25;

optimal layout

ephemeral variable

struct row {

string name;

int ID ;

int age ;

int height ;

int weight ;

};

Programmable logic

[[ephemeral]] struct column_group cg[];

16

CPU

base row store

SELECT NAME

FROM table� WHERE weight/height>25;

optimal layout

ephemeral variable

[[ephemeral]] struct column_group cg[];

struct column_group {

string NAME ;

int height ;

int weight ;

};

17

CPU

base row store

optimal layout

ephemeral variable

struct row {

string name;

int ID ;

int age ;

int height ;

int weight ;

};

struct column_group {

string ID ;

int age;

};

SELECT ID FROM table

WHERE age>40;

• Transparent data transformation

​

• Optimal layout

[[ephemeral]] struct column_group cg[];

Relational �Memory �Engine

18

�

DRAM

On-the-fly �vertical�partitioning

CPU

Processing System

Q1: how to build?

Q2: how to use?

Relational Memory Engine

19

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Processing System

Programmable logic

Core

Core

Core

Processing System

Relational Memory Engine

20

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Processing System

Programmable logic

Core

Core

Core

Processing System

Intercepts CPU-oriented memory requests

Relational Memory Engine

21

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Processing System

Core

Core

Core

Processing System

Monitors the completion of each reorganized cache line

Programmable logic

Relational Memory Engine

22

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Processing System

Programmable logic

Core

Core

Core

Processing System

Orchestrates accesses to main memory

using DB geometry

Relational Memory Engine

23

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Processing System

Programmable logic

Core

Core

Core

Processing System

Retrieves data from main memory

Relational Memory Engine

24

PL

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

​

​

000000000000A0A0A0A0A0A0

A0A0A0A00000000000000000

000000000000000000000000

0000000000000000A1A1A1A1

A1A1A1A1A1A1000000000000

000000000000000000000000

00000000000000000000A2A2

A2A2A2A2A2A2A2A200000000

000000000000000000000000

000000000000000000000000

A3A3A3A3A3A3A3A3A3A30000

000000000000000000000000

000000000000000000000000

0000A4A4A4A4A4A4A4A4A4A4

000000000000000000000000

000000000000000000000000

…

0000AEAEAEAEAEAEAEAEAEAE

RME gets

DB geometry

row size, row count, �# columns, columns widths, column offsets

useful data

useless data

Bus Width

PS

PL

PS

Core

Core

Core

Relational Memory Engine

25

PL

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Core

Core

Core

​

​

000000000000A0A0A0A0A0A0

A0A0A0A00000000000000000

000000000000000000000000

0000000000000000A1A1A1A1

A1A1A1A1A1A1000000000000

000000000000000000000000

00000000000000000000A2A2

A2A2A2A2A2A2A2A200000000

000000000000000000000000

000000000000000000000000

A3A3A3A3A3A3A3A3A3A30000

000000000000000000000000

000000000000000000000000

0000A4A4A4A4A4A4A4A4A4A4

000000000000000000000000

000000000000000000000000

…

0000AEAEAEAEAEAEAEAEAEAE

useful data

useless data

Bus Width

PS

PL

PS

Read accesses towards ephemeral variable

Relational Memory Engine

26

PL

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Core

Core

Core

​

​

000000000000A0A0A0A0A0A0

A0A0A0A00000000000000000

000000000000000000000000

0000000000000000A1A1A1A1

A1A1A1A1A1A1000000000000

000000000000000000000000

00000000000000000000A2A2

A2A2A2A2A2A2A2A200000000

000000000000000000000000

000000000000000000000000

A3A3A3A3A3A3A3A3A3A30000

000000000000000000000000

000000000000000000000000

0000A4A4A4A4A4A4A4A4A4A4

000000000000000000000000

000000000000000000000000

…

0000AEAEAEAEAEAEAEAEAEAE

useful data

useless data

Bus Width

PS

PL

PS

Trapper notifies the MB about the access

Relational Memory Engine

27

PL

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Core

Core

Core

​

​

000000000000A0A0A0A0A0A0

A0A0A0A00000000000000000

000000000000000000000000

0000000000000000A1A1A1A1

A1A1A1A1A1A1000000000000

000000000000000000000000

00000000000000000000A2A2

A2A2A2A2A2A2A2A200000000

000000000000000000000000

000000000000000000000000

A3A3A3A3A3A3A3A3A3A30000

000000000000000000000000

000000000000000000000000

0000A4A4A4A4A4A4A4A4A4A4

000000000000000000000000

000000000000000000000000

…

0000AEAEAEAEAEAEAEAEAEAE

useful data

useless data

Bus Width

PS

PL

PS

MB checks the corresponding Metadata

Relational Memory Engine

28

PL

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Core

Core

Core

​

​

000000000000A0A0A0A0A0A0

A0A0A0A00000000000000000

000000000000000000000000

0000000000000000A1A1A1A1

A1A1A1A1A1A1000000000000

000000000000000000000000

00000000000000000000A2A2

A2A2A2A2A2A2A2A200000000

000000000000000000000000

000000000000000000000000

A3A3A3A3A3A3A3A3A3A30000

000000000000000000000000

000000000000000000000000

0000A4A4A4A4A4A4A4A4A4A4

000000000000000000000000

000000000000000000000000

…

0000AEAEAEAEAEAEAEAEAEAE

useful data

useless data

Bus Width

PS

PL

PS

When the data is not in Data Buffer

MB notifies the Requestor about the missing data

Relational Memory Engine

29

PL

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Core

Core

Core

​

​

000000000000A0A0A0A0A0A0

A0A0A0A00000000000000000

000000000000000000000000

0000000000000000A1A1A1A1

A1A1A1A1A1A1000000000000

000000000000000000000000

00000000000000000000A2A2

A2A2A2A2A2A2A2A200000000

000000000000000000000000

000000000000000000000000

A3A3A3A3A3A3A3A3A3A30000

000000000000000000000000

000000000000000000000000

0000A4A4A4A4A4A4A4A4A4A4

000000000000000000000000

000000000000000000000000

…

0000AEAEAEAEAEAEAEAEAEAE

useful data

useless data

Bus Width

PS

PL

PS

When the data is not in Data Buffer

Requestor programs the Fetch-Unit and it fires the read request toward the DRAM

Relational Memory Engine

30

PL

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Core

Core

Core

​

​

000000000000A0A0A0A0A0A0

A0A0A0A00000000000000000

000000000000000000000000

0000000000000000A1A1A1A1

A1A1A1A1A1A1000000000000

000000000000000000000000

00000000000000000000A2A2

A2A2A2A2A2A2A2A200000000

000000000000000000000000

000000000000000000000000

A3A3A3A3A3A3A3A3A3A30000

000000000000000000000000

000000000000000000000000

0000A4A4A4A4A4A4A4A4A4A4

000000000000000000000000

000000000000000000000000

…

0000AEAEAEAEAEAEAEAEAEAE

useful data

useless data

Bus Width

PS

PL

PS

When the data is not in Data Buufer

0000000000A0A0A0A0A0A0

Relational Memory Engine

31

PL

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Core

Core

Core

​

​

000000000000A0A0A0A0A0A0

A0A0A0A00000000000000000

000000000000000000000000

0000000000000000A1A1A1A1

A1A1A1A1A1A1000000000000

000000000000000000000000

00000000000000000000A2A2

A2A2A2A2A2A2A2A200000000

000000000000000000000000

000000000000000000000000

A3A3A3A3A3A3A3A3A3A30000

000000000000000000000000

000000000000000000000000

0000A4A4A4A4A4A4A4A4A4A4

000000000000000000000000

000000000000000000000000

…

0000AEAEAEAEAEAEAEAEAEAE

useful data

useless data

Bus Width

PS

PL

PS

When the data is not in Data Buffer

Extracted Data being sent toward the (DATA) SPM and Metadate table gets updated

Extracted Data being sent toward the DATA and Metadate table gets updated

Relational Memory Engine

32

PL

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Core

Core

Core

​

​

000000000000A0A0A0A0A0A0

A0A0A0A00000000000000000

000000000000000000000000

0000000000000000A1A1A1A1

A1A1A1A1A1A1000000000000

000000000000000000000000

00000000000000000000A2A2

A2A2A2A2A2A2A2A200000000

000000000000000000000000

000000000000000000000000

A3A3A3A3A3A3A3A3A3A30000

000000000000000000000000

000000000000000000000000

0000A4A4A4A4A4A4A4A4A4A4

000000000000000000000000

000000000000000000000000

…

0000AEAEAEAEAEAEAEAEAEAE

useful data

useless data

Bus Width

PS

PL

PS

A0A0A0A0A0A0A0A0A0A0A1A1�A1A1A1A1A1A1A1A1A2A2A2A2

A2A2A2A2A2A2A3A3A3A3A3A3

A3A3A3A3A4A4A4A4A4A4A4A4

A4A4A5A5A5A5A5A5A5A5A5A5

only the desired columns

When the data is not in Data Buffer

Cache Line

Relational Memory Engine

33

PL

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Core

Core

Core

​

​

000000000000A0A0A0A0A0A0

A0A0A0A00000000000000000

000000000000000000000000

0000000000000000A1A1A1A1

A1A1A1A1A1A1000000000000

000000000000000000000000

00000000000000000000A2A2

A2A2A2A2A2A2A2A200000000

000000000000000000000000

000000000000000000000000

A3A3A3A3A3A3A3A3A3A30000

000000000000000000000000

000000000000000000000000

0000A4A4A4A4A4A4A4A4A4A4

000000000000000000000000

000000000000000000000000

…

0000AEAEAEAEAEAEAEAEAEAE

Cache Line

useful data

useless data

Bus Width

PS

PL

PS

Upon availability, MB receives back the ID and Offset

When the data is already in Data Buffer

Relational Memory Engine

34

PL

Core

Trapper

Monitor-

Bypass

Fetch-Unit

Requestor

Main Memory (DRAM)

Core

Core

Core

​

​

000000000000A0A0A0A0A0A0

A0A0A0A00000000000000000

000000000000000000000000

0000000000000000A1A1A1A1

A1A1A1A1A1A1000000000000

000000000000000000000000

00000000000000000000A2A2

A2A2A2A2A2A2A2A200000000

000000000000000000000000

000000000000000000000000

A3A3A3A3A3A3A3A3A3A30000

000000000000000000000000

000000000000000000000000

0000A4A4A4A4A4A4A4A4A4A4

000000000000000000000000

000000000000000000000000

…

0000AEAEAEAEAEAEAEAEAEAE

Cache Line

useful data

useless data

Bus Width

PS

PL

PS

Trapper gets notified by MB and fetches the Data from Data Buffer  

When the data is already in Data Buffer

Relational Memory Engine

35

Core

Trapper

Monitor-

Bypass

Requestor

Main Memory (DRAM)

Processing System

Programmable logic

Core

Core

Core

Processing System

Fetch-Unit

2MB << Data size

Target Platform

36

area utilization �less than 3%

Relational Memory Benchmark

37

Q1: SELECT A1 , A2 , ... , Ak FROM S;

Q2: SELECT A1 , A2 , ... , Ak FROM S WHERE C1, C2, … ,Ci;

Q3: SELECT AVG (A1) FROM S WHERE A3 < k GROUP BY A2;

Q4: SELECT S.A1 , R.A3 FROM S JOIN R ON S.A2 = R.A2;

projection

both projection & selection

group by

Approach tested

​

ROW : Direct row-wise access

COL   : Direct columnar access

RME  : using Relational Memory Engine

join over two tables

Processing System

Slow FPGA (100MHz)

Queries Varying Projectivity

Q1: SELECT A1 , A2 , ... , Ak FROM S;

​

38

Row size: 64 Bytes, Column size: 4 Bytes

Queries Varying Projectivity

Q1: SELECT A1 , A2 , ... , Ak FROM S;

​

39

Row size: 64 Bytes, Column size: 4 Bytes

tuple reconstruction cost

prefetcher supports up to four parallel streams

Queries Varying Projectivity

Q1: SELECT A1 , A2 , ... , Ak FROM S;

​

40

Row size: 64 Bytes, Column size: 4 Bytes

RME provides stable performance irrespectively of projectivity

RME close to COL

for low projectivity

RME >> faster than COL

for high projectivity

RME for Multiple Selection and Projection Attributes

Q3: SELECT A1 , A2 , ... , Ak FROM S WHERE C1, C2, … ,Ci;

41

Row size: 64 Bytes, Column size: 4 Bytes

RME vs COL

RME for Multiple Selection and Projection Attributes

Q3: SELECT A1 , A2 , ... , Ak FROM S WHERE C1, C2, … ,Ci;

42

Row size: 64 Bytes, Column size: 4 Bytes

RME can be up to 2.23× faster than columnar access

RME vs COL

RME vs ROW

RME always outperforms row access by being 1.3 − 1.5× faster

COL faster

Group by

43

Q4: SELECT AVG (A1) FROM S WHERE A3 < k GROUP BY A2;

Selectivity: 10%

RME outperforms both ROW and COL

Column size: 4 Bytes

Join Over Two Tables

Column size: 4 Bytes

44

Q4: SELECT S.A1 , R.A3 FROM S JOIN R ON S.A2 = R.A2;

RME reduces data movement �up to 41% 

CPU

Data

RME Scales with Data Size

TPC-H Q1

TPC-H Q6

45

CPU-bound (sort, group by)

IO-bound

RME Scales with Data Size

TPC-H Q1

TPC-H Q6

46

CPU overhead dominates �data movement cost

RME benefits regardless of data size

CPU-bound (sort, group by)

IO-bound

Summary

• Relational Memory
• a novel SW/HW co-design paradigm
• every query always has access to the optimal data layout
• ephemeral variables
• a simple and lightweight abstraction to use RM

47

• Relational Memory
• a novel SW/HW co-design paradigm
• every query always has access to the optimal data layout

​

​

​

​

​

​

• Relational Memory enables opportunities for innovation across the data system architecture. 

Relational Fabric, ICDE ‘23

Future Work

48

Thank you

Ju Hyoung Mun ( jmun@bu.edu )

49

Thank you

Ju Hyoung Mun ( jmun@bu.edu )

50

How big is the overhead of fetching the data?

RME Cold vs. Hot

RME is comparable with directly accessing a single column!

RME Cold has virtually the same performance as RME Hot!

SELECT A1, A3, A5 FROM S;

Row size: 64 Bytes

Updates

52

Can we perform updates through ephemeral variables?

How to cater for HTAP workloads?

No, ephemeral variables are read-only, but …

… RME can manage timestamps, allowing MVCC

Updates go to base row-oriented data (invalidated old/add new version of row)

In flight-queries will always read correct data (MVCC)

Updates - Example

53

Updates - Example

54

DELETE FROM table WHERE ID = 11;

​

At t₃:

Data inserted at time t₁ and now valid

Data inserted at time t₂ and now valid

Updates - Example

55

UPDATE weight=82 FROM table WHERE ID = 8;

At t₅:

DELETE FROM table WHERE ID = 11;

​

At t₃:

Updates - Example

56

UPDATE weight=82 FROM table WHERE ID = 8;

At t₅:

DELETE FROM table WHERE ID = 11;

​

At t₃:

Updates - Example

57

SELECT avg(weight) FROM table;

At t₃:

At t₅:

cg1 = configure (table, column_group, t₃);

cg1 = configure (table, column_group, t₅);

RME will discard through hardware invalid rows

With MVCC enabled, RME is always faster than ROW and COL!

Data Compression

58

How do we support compression?

Relational Memory natively supports

dictionary and delta (frame of reference) encoding

to exploit dictionary encoding

RME Scales with Data Size

TPC-H Q1

SELECT l_returnflag, l_linestatus,� SUM(l_quantity), SUM(l_extendedprice),� SUM(l_extendedprice*(1-l_discount)),� SUM(l_extendedprice*(1-l_discount)*(1+l_tax)),� AVG(l_quantity), AVG(l_extendedprice), � AVG(l_discount),� COUNT(*)�FROM lineitem �WHERE � l_shipdate <= '1998-12-01' - '[DELTA]' day (3)

GROUP BY l_returnflag, l_linestatus

ORDER BY l_returnflag, l_linestatus;

​

TPC-H Q6

SELECT� SUM(l_extendedprice*l_discount)

FROM lineitem

WHERE

l_shipdate >= '[DATE]’ and� l_shipdate < '[DATE]' + 1 year and� l_discount > [DISCOUNT] - 0.01 and � l_discount < [DISCOUNT] + 0.01 and� l_quantity < [QUANTITY];

​

59

Selectivity: 95%, projectivity: 24%

Selectivity: 15%, projectivity: 18%

60

Architecture of Programmable Logic

61

Any logic can be programmed!

Configurable Logic Block

Switch Matrix

(Programmable Interconnect)