Repository files navigation

I interned at Citus Data this summer, and implemented a vectorized executor forPostgreSQL. We observed performance improvements of 3-4x for simple SELECTqueries with vectorized execution, and decided to open source my project as aproof of concept.

This readme first describes the motivation behind my internship, and my journeywith PostgreSQL, database execution engines, and GProf. If you'd like to skip that,you can also jump tobuild instructions.

I'm a second year student at Bogazici University in Istanbul, and I interned atCitus. When I started my internship, my mentor Metindescribed to me a common question they were hearing from customers: "I can fitmy working set into memory, thanks to cheaper RAM, columnar stores, or scalingout of data to multiple machines. Now my analytic queries are bottlenecked onCPU. Can these queries go faster?"

Since this question's scope was too broad, we decided to pick a simple, yetuseful and representative query. My goal was to go crazy with this (class of)query's performance. Ideally, my changes would also apply to other queries.

postgres=# SELECT l_returnflag,             sum(l_quantity) as sum_qty,          count(*) as count_order       FROM lineitem       GROUP BY l_returnflag;

I started my challenge by compiling PostgreSQL for performance profiling, andrunning it with a CPU-profiler called GProf. I then ran our example SELECTquery 25 times to make sure GProf collected enough samples, and looked at theprofile output.

In particular, I was looking for any "hot spot" functions whose behavior I couldunderstand and change without impacting correctness. For this, I digged down theGProf call graph, and found the top three functions whose behavior lookedself-contained enough for me to understand.

index  %time    self  children    called      name...[7]     43.3    0.77    17.20    150030375    LookupTupleHashEntry [7][9]     24.0    1.37     8.60    150030375    advance_aggregates [9][17]    12.0    0.26     4.73    150030400    SeqNext [17]

These numbers discouraged me in three ways. First, I was hoping to find a singlefunction thatwas the performance bottleneck. Instead, PostgreSQL wasspending a proportional amount of time scanning over the lineitem table's tuples[17], projecting relevant columns from each tuple and grouping them [7], andapplying aggregate functions on grouped values [9].

Second, I read the code for these functions, and found that they were alreadyoptimized. I also found out through profile results that Postgres introduced aper-tuple overhead. For each tuple, it stored and cleared tuples, dispatched torelevant executor functions, performed MVCC checks, and so forth.

Third, I understood at a higher level that PostgreSQL was scanning tuples,projecting columns, and computing aggregates. What I didn't understand was thedependencies between the thousand other functions involved in query execution.In fact, whenever I made a change, I spent more time crashing and debugging thedatabase than the change itself.

To mitigate these issues, we decided to redefine the problem one month into myinternship. To simplify the problem of understanding many internal PostgreSQLfunctions, we decided to apply my performance optimizations on the columnarstore extension. This decision had the additional benefit of slashing CPU usagerelated to column projections [7].

Then, to speed up tuple scans and aggregate computations, and also to reduce theper-tuple CPU overhead, we decided to try an interesting idea called vectorizedexecution.

Vectorized executionwas popularized by theMonetDB/X100team. This idea is based on the observation that most database engines follow aniterator-based execution model, where each database operator implements a next()method. Each call to next() produces one new tuple that may in turn be passed toother operators. This "tuple at a time" model introduces an interpretation overheadand also adversely affects high performance features in modern CPUs. Vectorizedexecution reduces these overheads by using bulk processing. In this new model,rather than producing one tuple on each call, next() operates on and produces abatch of tuples (usually 100-10K).

With the vectorization idea in mind, I started looking into cstore_fdw to seehow I could implement aggregate functions. Sadly, PostgreSQL didn't yet haveaggregate push downs for foreign tables. On the bright side, it provided thesepowerful hooks that enabled developers to intercept query planning and executionlogic however they liked.

I started simple this time. I initially overlooked groupings, and implementedvectorized versions of simple sum(), avg(), and count() on common data types. Ithen grabbed the execution hook, and routed any relevant queries to myvectorized functions.

Next, I generated TPC-H data with a scale factor of 1, loaded the data into thedatabase, and made sure that data was alwaysin-memory. I then ransimple "Select sum(l_quantity) From lineitem" type queries, and compared theregular executor to the vectorized version.

The results looked cheerful. Vectorized functions showed performance benefits of4-6x across different aggregate functions and data types. The simplest of thesefunctions also had the greatest benefits, plain count(*). This wasn't all thatsurprising. The standard executor was calling count(*) on one new tuple,count(*) was incrementing a counter, and then onto the next tuple. Thevectorized version was instead a simple for() loop over a group of values.

From there, I started looking into queries that aggregated and grouped theirresults on one dimension. This time, I made changes to implement vectorized"hash aggregates", and again routed any relevant queries to my vectorizedfunctions. I then compared the two executors for simple group bys withaggregates.

These results showed performance benefits of around 3x. These improvements weresmall in comparison to plain aggregate vectorization because of the generic hashfunction's computational overhead. Also, I only had time to implement hashvectorization for Postgres' pass-by-value data types. In fact, it took me quitea while to understand that Postgres even had pass-by-value types, and that thosediffered from pass-by-reference ones.

If I had the time, I'd look into making my hash aggregate logic more generic.I'd also try an alternate hashing function that's more specialized, one thatonly operates on 1-2 columns, and as a result, that goes faster.

In the end, I feel that I learned a lot during my internship at Citus. My firsttakeaway was that reading code takes much more time than writing it. In fact,only after two months of reading code and asking questions, did I start tounderstand how the PostgreSQL aggregate logic worked.

Second, it's exciting to try out new ideas in databases. For beginners, the bestway to start is to carve out a specific piece of functionality, find the relatedPostgreSQL extension API,and start implementing against it.

Finally, I'm happy that we're open sourcing my work. I realize that the codeisn't as robust or generic as PostgreSQL is. That said, I know a lot more aboutPostgreSQL and love it, and I can only hope that the ideas in here willstimulate others.

The vectorized execution logic builds on thecstore_fdw extension. Therefore,the dependencies and build steps are exactly the same between the twoextensions. The difference is that cstore_fdw reduces the amount of disk I/Oby only reading relevant columns and compression data. This extension helps morewhen the working set fits into memory. In that case, it reduces the CPU overheadby vectorizing simple SELECT queries.

My primary goal with this extension was to test vectorization's potentialbenefits. As such, we'd love for you to try this out and give us any feedback.At the same time, please don't consider this extension as generic andproduction-ready database code. PostgreSQL does set a high bar there.

cstore_fdw depends on protobuf-c for serializing and deserializing table metadata.So we need to install these packages first:

# Fedora 17+, CentOS, and Amazon Linuxsudo yum install protobuf-c-devel# Ubuntu 10.4+sudo apt-get install protobuf-c-compilersudo apt-get install libprotobuf-c0-dev# Mac OS Xbrew install protobuf-c

Note. In CentOS 5 and 6, you may need to install or update EPEL 5 or EPEL 6repositories. See [this page](http://www.rackspace.com/knowledge_center/article/installing-rhel-epel-repo-on-centos-5x-or-6x)for instructions.

Note. In Amazon Linux, EPEL 6 repository is installed by default, but it is notenabled. Seethese instructionsfor how to enable it.

Once you have protobuf-c installed on your machine, you are ready to buildcstore_fdw. For this, you need to include the pg_config directory path inyour make command. This path is typically the same as your PostgreSQLinstallation's bin/ directory path. For example:

PATH=/usr/local/pgsql/bin/:$PATH makesudo PATH=/usr/local/pgsql/bin/:$PATH make install

Note. postgres_vectorization_test requires PostgreSQL 9.3. It doesn't supportother versions of PostgreSQL.

Before using cstore_fdw, you also need to add it toshared_preload_librariesin yourpostgresql.conf and restart Postgres:

shared_preload_libraries = 'cstore_fdw'    # (change requires restart)

You can use PostgreSQL'sCOPY command to load or append data into the table.You can use PostgreSQL'sANALYZE table_name command to collect statisticsabout the table. These statistics help the query planner to help determine themost efficient execution plan for each query.

As an example, we demonstrate loading and querying data to/from a column storetable from scratch here. Let's start with downloading and decompressing the datafiles.

wget http://examples.citusdata.com/customer_reviews_1998.csv.gzwget http://examples.citusdata.com/customer_reviews_1999.csv.gzgzip -d customer_reviews_1998.csv.gzgzip -d customer_reviews_1999.csv.gz

Then, let's log into Postgres, and run the following commands to create a columnstore foreign table:

-- load extension first time after installCREATE EXTENSION cstore_fdw;-- create server objectCREATE SERVER cstore_server FOREIGN DATA WRAPPER cstore_fdw;-- create foreign tableCREATE FOREIGN TABLE customer_reviews(    customer_idTEXT,    review_dateDATE,    review_ratingINTEGER,    review_votesINTEGER,    review_helpful_votesINTEGER,    product_idCHAR(10),    product_titleTEXT,    product_sales_rankBIGINT,    product_groupTEXT,    product_categoryTEXT,    product_subcategoryTEXT,    similar_product_idsCHAR(10)[])SERVER cstore_server;

Next, we load data into the table:

COPY customer_reviewsFROM'/home/user/customer_reviews_1998.csv' WITH CSV;COPY customer_reviewsFROM'/home/user/customer_reviews_1999.csv' WITH CSV;

Note. If you are gettingERROR: cannot copy to foreign table "customer_reviews" when trying to run the COPY commands, double check that youhave added cstore_fdw toshared_preload_libraries inpostgresql.confand restarted Postgres.

Next, we collect data distribution statistics about the table. This is optional,but usually very helpful:

ANALYZE customer_reviews;

Finally, let's run some simple SQL queries and see how vectorized executionperforms. We also encourage you to load the same data into a regular PostgreSQLtable, and compare query performance differences.

-- Number of customer reviewsSELECTcount(*)FROM customer_reviews;-- Average and total votes for all customer reviewsSELECTavg(review_votes),sum(review_votes)FROM customer_reviews;-- Total number of helpful votes per product categorySELECT    product_group,sum(review_helpful_votes)AS total_helpful_votesFROM    customer_reviewsGROUP BY    product_group;-- Number of reviews by date (year, month, day)SELECT    review_date,count(review_date)AS review_countFROM    customer_reviewsGROUP BY    review_date;

The vectorized executor intercepts PostgreSQL's query execution hook. If theextension can't process the current query, it hands the query over to thestandard Postgres executor. Therefore, if your query isn't going any faster,then we currently don't support vectorization for it.

The current set of vectorized queries are limited to simple aggregates (sum,count, avg) and aggregates with group bys. The next set of changes I wanted toincorporate into the vectorized executor are: filter clauses, functions orexpressions, expressions within aggregate functions, groups by that supportmultiple columns or aggregates, and passing vectorized tuples from groupings toorder by clauses.

I think all except the last one are relatively easy, but I didn't have the timeto work on them. The last one is harder as PostgreSQL's query planner followsa recursive pull model. In this model, each relational operator is calledrecursively to traverse the operator tree from the root downwards, with theresult tuples being pulled upwards. Such a recursion occurs with the aggregateoperator, and I could intercept all operators that are below the aggregateoperator in the query plan tree. If there was an operator on top of theaggregate operator, such as an order by, I may have had to copy code from theexecutor to properly intercept the recursion.

The example above illustrated how to load data into a PostgreSQL database runningon a single host. However, sometimes your data is too large to analyze effectivelyon a single host. CitusDB is a product built by Citus Data that allows you to runa distributed PostgreSQL database to analyze your data using the power of multiplehosts. CitusDB is based on a modern PostgreSQL version and allows you to easilyinstall PostgreSQL extensions and foreign data wrappers, including cstore_fdw. Foran example of how to use cstore_fdw with CitusDB see the[CitusDB documentation][citus-cstore-docs].

Before uninstalling the extension, first you need to drop all the cstore tables:

postgres=# DROP FOREIGN TABLE cstore_table_1;...postgres=# DROP FOREIGN TABLE cstore_table_n;

Then, you should drop the cstore server and extension:

postgres=# DROP SERVER cstore_server;postgres=# DROP EXTENSION cstore_fdw;

cstore_fdw automatically creates some directories inside the PostgreSQL's datadirectory to store its files. To remove them, you can run:

$ rm -rf $PGDATA/cstore_fdw

Then, you should remove cstore_fdw fromshared_preload_libraries inyourpostgresql.conf:

shared_preload_libraries = ''    # (change requires restart)

Finally, to uninstall the extension you can run the following command in theextension's source code directory. This will clean up all the files copied duringthe installation:

$ sudo PATH=/usr/local/pgsql/bin/:$PATH make uninstall

Copyright (c) 2014 Citus Data, Inc.

This module is free software; you can redistribute it and/or modify it under theApache v2.0 License.

For all types of questions and comments about the wrapper, please contact us atengage @ citusdata.com.