Re: Yet another vectorized engine - Mailing list pgsql-hackers

Hi hackers,

We just want to introduce another POC for vectorized execution engine https://github.com/zhangh43/vectorize_engine and want to get some feedback on the idea.

The basic idea is to extend the TupleTableSlot and introduce VectorTupleTableSlot, which is an array of datums organized by projected columns.  The array of datum per column is continuous in memory. This makes the expression evaluation cache friendly and SIMD could be utilized. We have refactored the SeqScanNode and AggNode to support VectorTupleTableSlot currently.

Below are features in our design.
1. Pure extension. We don't hack any code into postgres kernel.

2. CustomScan node. We use CustomScan framework to replace original executor node such as SeqScan, Agg etc. Based on CustomScan, we could extend the CustomScanState, BeginCustomScan(), ExecCustomScan(), EndCustomScan() interface to implement vectorize executor logic.

3. Post planner hook. After plan is generated, we use plan_tree_walker to traverse the plan tree and check whether it could be vectorized. If yes, the non-vectorized nodes (SeqScan, Agg etc.) are replaced with vectorized nodes (in form of CustomScan node) and use vectorized executor. If no, we will revert to the original plan and use non-vectorized executor. In future this part could be enhanced, for example, instead of revert to original plan when some nodes cannot be vectorized, we could add Batch/UnBatch node to generate a plan with both vectorized as well as non-vectorized node. 

4. Support implement new vectorized executor node gradually. We currently only vectorized SeqScan and Agg but other queries which including Join could also be run when vectorize extension is enabled.

5. Inherit original executor code. Instead of rewriting the whole executor, we choose a more smooth method to modify current Postgres executor node and make it vectorized. We copy the current executor node's c file into our extension, and add vectorize logic based on it. When Postgres enhance its executor, we could relatively easily merge them back. We want to know whether this is a good way to write vectorized executor extension?

6. Pluggable storage. Postgres has supported pluggable storage now. TupleTableSlot is refactored as abstract struct TupleTableSlotOps. VectorTupleTableSlot could be implemented under this framework when we upgrade the extension to latest PG.

We run the TPCH(10G) benchmark and result of Q1 is 50sec(PG) V.S. 28sec(Vectorized PG). Performance gain can be improved by:

1. heap tuple deform occupy many CPUs. We will try zedstore in future, since vectorized executor is more compatible with column store.

2. vectorized agg is not fully vectorized and we have many optimization need to do. For example, batch compute the hash value, optimize hash table for vectorized HashAgg. 

3. Conversion cost from Datum to actual type and vice versa is also high, for example DatumGetFloat4 & Float4GetDatum. One optimization maybe that we store the actual type in VectorTupleTableSlot directly, instead of an array of datums.

Related works:

1. VOPS is a vectorized execution extension. Link: https://github.com/postgrespro/vops.
It doesn't use custom scan framework and use UDF to do the vectorized operation e.g. it changes the SQL syntax to do aggregation.

2. Citus vectorized executor is another POC. Link: https://github.com/citusdata/postgres_vectorization_test.
It uses ExecutorRun_hook to run the vectorized executor and uses cstore fdw to support column storage.

Note that the vectorized executor engine is based on PG9.6 now, but it could be ported to master / zedstore with some effort.  We would appreciate some feedback before moving further in that direction.

Thanks, 

Hubert Zhang, Gang Xiong, Ning Yu, Asim Praveen

Hi,

I think that vectorized executor is absolutely necessary thing for Postgres, especially taken in account that now we have columnar store prototype (zedstore).
To take all advantages of columnar store we definitely need a vectorized executor.

But I do not completely understand why you are proposing to implement it as extension.
Yes, custom nodes makes it possible to provide vector execution without affecting Postgres core.
But for efficient integration of zedstore and vectorized executor we need to extend table-AM (VectorTupleTableSlot and correspondent scan functions).
Certainly it is easier to contribute vectorized executor as extension, but sooner or later I think it should be added to Postgres core.

As far as I understand you already have some prototype implementation (otherwise how you got the performance results)?
If so, are you planning to publish it or you think that executor should be developed from scratch?

Some my concerns based on VOPS experience:

1. Vertical (columnar) model is preferable for some kind of queries, but there are some classes of queries for which it is less efficient.
Moreover, data is used to be imported in the database in row format. Inserting it in columnar store record-by-record is very inefficient.
So you need some kind of bulk loader which will be able to buffer input data before loading it in columnar store.
Actually this problem it is more related with data model rather than vectorized executor. But what I want to express here is that it may be better to have both representation (horizontal and vertical)
and let optimizer choose most efficient one for particular query.

2. Columnar store and vectorized executor are most efficient for query like "select sum(x) from T where ...".
Unfortunately such simple queries are rarely used in real life. Usually analytic queries contain group-by and joins.
And here vertical model is not always optimal (you have to reconstruct rows from columns to perform join or grouping).
To provide efficient execution of queries you may need to create multiple different projections of the same data (sorted by different subset of attributes).
This is why Vertica (one of the most popular columnar store DBMS) is supporting projections.
The same can be done in VOPS: using create_projection function you can specify which attributes should be scalar (grouping attributes) and which vectorized.
In this case you can perform grouping and joins using standard Postgres executor, while perform vectorized operations for filtering and accumulating aggregates.

This is why Q1 is 20 times faster in VOPS and not 2 times as in your prototype.
So I think that columnar store should make it possible to maintain several projections of table and optimizer should be able to automatically choose one of them for particular query.
Definitely synchronization of projections is challenged problem. Fortunately OLAP usually not require most recent data.

3. I wonder if vectorized executor should support only built-in types and predefined operators? Or it should be able to work with any user defined types, operators and aggregates?
Certainly it is much easier to support only built-in scalar types. But it contradicts to open and extensible nature of Postgres.

4. Did you already think about format of storing data in VectorTupleTableSlot? Should it be array of Datum? Or we need to represent vector in more low level format (for example
as array of floats for real4 type)?

-- 
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company