Future of storage

== The future of Storage ==
For some use cases, our current storage design is sub-optimal. We believe it can be improved by adding an abstraction layer between the "heap" operations and storage.
Currently, the storage is assumed to be row-organized pages: heapam.h is written in assumption that each tuple has exactly one tuple header and a single data area, a HeapTuple, and at the same time contains code for logical operations such as tuple deletion, updating, and tuple locking. Similarly, the executor code represents tuples in the TupleTableSlot abstraction layer which currently assumes HeapTuple underneath.
During 2015, 2ndQuadrant worked on a project to implement columnar storage in Postgres. What follows is a plan derived from the lessons learned during that implementation:
== Project Outline ==
There are six sub-projects:
* Vertical partitioning
* Executor batching
* Executor vectorization
* Columnar indexes
* Pluggable storage for tables
* Columnar storage plug-in
The highest performance gains reported by other "columnar" database systems
are found when using a vectorized execution engine plugged
to columar storage:
it is possible to do columnar storage without vectorization,
but the gains are modest [citation needed]
(because CPUs still need to work on one element at a time);
and it's possible to do vectorization without columnar storage,
and the gains are also modest [citation needed]
(because for vectorization to work it's necessary to convert the row-based data
into column-based, a slow operation).
=== Vertical Partitioning ===
The ability to split a table's storage area in several pieces,
putting a subset of columns into each storage area.
There are several points to this:
* skip reading any storage area containing columns not used in the query
* different columns can use different storage strategies (row-based or column-based; different implementations for column-based, for experimentation; compression or no; etc)
* reading tuples on a tuple with more than one storage area requires joins between them.
Challenges:
* Joining between table and storage area needs separate handling
* Join elimination is key
* Logical/physical tuple representation needs to change (in particular, pg_attribute with a single attrelid value no longer represents the tuple descriptor for a table)
=== Executor Batching ===
This refers to the ability of the executor
to process multiple tuples at a time
in a single node execution,
rather than one at a time as currently.
Requires changes to TupleTableSlot with large fallout;
also, changes to individual node execution routines.
This is intended for 9.7.
=== Executor Vectorization ===
This refers to the ability of the executor
to have specialized functions for using SIMD at the CPU level.
This builds on top of executor batching.
Aggregates need to provide specialized code to do this.
=== Columnar indexes ===
This project is about a new index access method that uses columnar storage.
One obvious output is insight into what columnar storage methods work best.
Advantages:
* Indexes are much more compact than standard indexes, so scans are faster
=== Pluggable storage for tables ===
This project is about creating an access-method-like interface
for table storage.
Currently, all storage goes through heapam.c;
this would enable different implementations
to be written.
The heapam.c interface assumes that the user has a Relation
and a TID (tuple identifier).
Currently the TID is simply the (block,item number) physical position
of the tuple within the relation.
This project might need to change tuple identifiers
to suit different storage implementations.
At the same time, the current heapam.c implementation
returns a HeapTuple struct containing a tuple,
but different implementations might have completely different ways
to represent tuples in storage.
Because we will want to utilize the different representation
of tuples without having to "heapify" them,
some more changes might be necessary so that the tuple
can be passed to the executor code.
How this works is unclear;
this needs more research.
Executor batching could rely on this
to act on several tuples at once.
==== Cautionary tale from Tom Lane ====
We need to avoid a rewrite of the DDL code.
Currently, all the utility code assumes that HeapTuples
can be passed all over the place.
This would fail completely with different storage formats.
We need some way to avoid this project from becoming tangled in endless refactoring of utility code.
The solution seems simple: we do not need to attack this problem in system catalogs right away:
if we forbid the use of different storage formats for system catalogs
we are protected from having to edit enormous amounts of utility code.
In the future,
somebody could refactor code touching an individual catalog
to allow pluggable (non-heapam) storage to be used for that catalog.
This could be done piecemeal, lifting the restriction
on one specific catalog as the code to handle that catalog
is reworked.
=== Columnar storage plug-in ===
This would be a mechanism that plugs as a storage module for tables
and acts (per the subproject above)
as columnar-oriented storage for them.
== Analysis of existing use-cases ==
While there is a lot of discussion about what PostgreSQL pluggable storage API should look like, it's useful to analyze experience of other DBMS'es in this field.
=== MySQL/MariaDB ===
MySQL and MariaDB provide pluggable table engines. See documentation for MySQL and MariaDB.
Table engine name(s) 	Description 	Resume: do we need something like this in PostgreSQL?
InnoDB 	Provides index-organized tables where previous versions of rows are displaced into undo tablespace. Secondary indexes are indirect with separate versioning. 	Yes. Index-organized tables, undo tablespace and indirect indexes are useful features. It seems, that at least some of them could be implemented using pluggable storage API.
MyISAM 	Table engine without transactions and recovery. 	No. We have unlogged tables if needed.
CSV, Federated, Cassandra, CONNECT, SphinxSE	These table engines are accessing either local or remote foreign data sources. 	No, because we have FDWs.
MGR_MyIsam, Merge 	These engines allow defining tables which are union of primary tables set. Such union is updatable: updates are pushed down to primary tables. 	No, because we have updatable view, partitioning, table inheritance etc.
Archive 	Storage for archive data: append-only, compressed storage 	Yes, archive storage would be useful.
Blackhole 	Table engine which silently "eats" all the inserted data. It have useful usecases in proxy which reduces network traffic in partial replication by filtering replication traffic on master side. 	No, our logical decoding already provides such capability. Moreover, there is Blackhole FDW with same functionality.
Mroonga 	Mroonga implements non-transactional tables with FTS, geospatial and other indexes. 	No, because in PostgreSQL new index types should be implemented as index access methods.
OQGraph 	Table engine which allows querying and indexing of graph. OQGraph let users query some kind of view while primary data is stored in another table. 	No, because this table engine is not intended to store primary data. If we would need similar solution, we should implement it using index access methods, views, materialized views and so on.
Sequence 	This table engine provides functional analogue of generate_series() function. 	No, generate_series() is completely sufficient for that purpose.
Aria, XtraDB 	Enhanced versions of MyISAM and InnoDB from MariaDB. 	No, we should evade fragmentation if possible.
TokuDB, RocksDB 	These engines provide write-optimized tables. TokuDB implements fractal trees while RocksDB implements LSM trees. 	Yes, write-optimized tables are nice to have.
ScaleDB, Spider 	Provide clusters built in the table engines. 	No, pluggable storage doesn't seem to be appropriate mechanism for clustering.
Memory 	Memory table engine implements non-persistent tables which resides completely in memory. Besides shortcomings of MySQL implementation, in-memory engine could give us following benefits: faster in-memory operations bypass buffer manager; optimized work with disk for persistent in-memory tables due to full data snapshots and row-level WAL.	Yes, it would be nice to have in-memory tables if they would perform faster. Somebody could object that PostgreSQL is on-disk database which shouldn't utilize in-memory storage. But users would be interested in such storage engine if it would give serious performance advantages.
=== MongoDB ===
MongoDB provides pluggable table engines. See documentation.