09 Aug

GiST Support in GPORCA

We look at how GIST indexes can be supported in GPORCA, allowing GPORCA to generate plans providing better query execution times.

Introduction

Pivotal’s SQL Optimizer, GPORCA, does not handle GiST indexes, making any GPORCA generated plan extremely slow when the input grew large. In this blog post, we will look at what GiST indexes are, how we implemented them in GPORCA, and the resulting performance improvement.

What are GiST Indexes?

GiST stands for Generalized Search Trees. These trees are a template structure that allows a user to create an index in a database on any complex data type, provided they define a set of seven methods. It is a balanced tree-structured access method that allows users to do more than just the standard less than “<“, equal to “=” or greater than “>”  queries when doing an index scan. GiST indexes are particularly great for ranges as well as full text search. Furthermore, using the user-defined methods, GiST tries to cluster data in a way that creates as little overlap as possible.

In order to create a GiST index, the user must define 7 functions: the Consistent[1], Union[2], Compress[3], Decompress[4], Penalty[5], Picksplit[6] and Same[7] methods. Then GiST will do the rest of the underlying work required of an index, such as reindex-ing and vacuuming. More information about GiST indexes can be found here: http://gist.cs.berkeley.edu/ or at PostgreSQL 9.5 here: https://www.postgresql.org/docs/9.5/static/gist.html  

The user must also define functions for the custom data type that would be used in the predicate. For example, PostGIS has a function called ST_DWithin that returns true given the two points are within a specified distance of each other.  We could then use it in a query such as “SELECT * FROM foo, bar where ST_DWithin(foo.a, bar.b, 0.0005)”, which would give all the rows where point ‘a’ from foo and point ‘b’ from bar are within 0.0005 meter from each other.

Greenplum DB ships with operator classes for some data types (such as Point, Box or Polygon)  that can use a GiST index but it is also possible to install extensions like PostGIS that include data types like geometry which can can be used in a GiST index.

Introduction to GiST in the Query Optimizer

In the Greenplum Database, there are two query optimizers: Planner and GPORCA (designed specifically for the MPP environment to help accelerate queries). Currently, Planner in Greenplum Database supports GiST indexes and can generate an optimal plan that efficiently uses the GiST index available. However, GPORCA – Pivotal’s SQL Optimizer – is not GiST aware and therefore selects a query plan that does not use any available GiST indexes. The result: a query plan that takes orders of magnitudes longer than a plan that uses the GiST index.

Say that we had two tables called foo and bar that each had a column called ‘geom’ of type geometry. Geometry is a GiST-indexable data type from PostGIS that is commonly used for spatial and geographical queries. We now want to find the number of points that are within 0.0005 meters of each other.

 

Since it is not GIST-aware, the optimal plan generated by GPORCA uses two Table Scans inside a nested loop join. This can be significantly slow in execution if the tables have a large number of rows.

Original GPORCA Generated Plan

This plan generated by GPORCA takes a total of 303 seconds in execution, which is quite long for a simple nested loop join. In contrast, the same query run by the planner using the GiST index in its plan, produced the results in under a second.

Planner Generated Plan   

As can be seen above, the plan generated by the planner is at least 3000x (87ms vs 302930ms) faster than GPORCA.

Implementing GIST support in ORCA

In order to find the fastest way to execute these SQL queries using GiST indexes, GPORCA needs to become GiST aware. To achieve this, GPORCA needs to first receive information regarding the GiST index and it needs to know how to generate plans using the index information.

When a SQL statement is given, the information is first translated into DXL (a system-independent XML representation of the query) and sent to GPORCA to be optimized. During this process, only the information necessary for the query and basic information about the involved tables are sent. This can include statistic information, whether or not the table contains an index, and what type of index it is. Since GPORCA did not implement support for  GiST indexes, we did not send any GiST index information over at all. This meant that any table with a GiST index was sent to GPORCA as a table that contained no index at all.

Initial Steps

The first step of this process: send information about GiST indexes to GPORCA. In Planner, GiST indexes are treated as a general index. What this means is that GiST indexes can follow either the Bitmap Index path or the B-Tree index path when creating a plan. That is, during the intermediate stages of planning, GIST indexes appear either as Bitmap Indexes or B-Tree indexes. But, when the plan is finally executed, , the executor recognizes (based off the index’s unique access method id) that the actual index to be used during execution is the GiST index and not the index type printed in the plan.

When sending index information, GPORCA requires a few key components: The index’s unique access method id, the index’s type and the columns the index is on. For Bitmap and B-Tree, which GPORCA is already aware of, the index type is, respectively, Bitmap and Btree.

Our next step was to determine whether a new index type was required for GiST indexes. We tried sending over GiST index information with the correct unique access method id, but with the index type as type Bitmap. We quickly realized that though this was feasible, there are certain conditions that are GiST specific. For example, Bitmap indexes can only be used if the predicate is a standard predicate. However, with GiST, standard predicates are almost never used. In order to make an ORCA generated plan using GiST while following the Bitmap Index path, we needed to either set the predicate type as a standard query (which is not ideal) or we needed to be able to differentiate when we were working with a GiST index versus a Bitmap Index. When sending the index over as a Bitmap type, we lost the ability to make such distinctions within GPORCA’s optimization process and the ability to generate a B-Tree path for GiST indexes. So, in order to deal with this, any solution to make GPORCA GiST aware would involve the creation of a new index type within GPORCA specifically for GiST so that a distinction could be made between different index types when necessary.  

With the addition of the new GiST index type, we considered two implementation alternatives in GPORCA:

Alternative 1

The first alternative is to mimic what the planner does. GPORCA could allow GiST indexes to take either the B-Tree or Bitmap path, generating alternatives for both before picking an optimal plan during costing.

 

Pros Cons
  1. Use of existing optimized paths
  2. No additional changes necessary to be able to execute the plan generated
  3. Similar to an implementation that has already proven to work (planner)
  4. Support for partitioned tables and AO tables would already be implemented
  1. Costing would be done based off the path taken instead of a GiST specific cost model
  2. GiST indexes would be disabled if both bitmap and btree indexes are disabled.

 

Alternative 2

Instead of allowing GiST indexes to follow either the B-Tree or Bitmap path, GPORCA would have a separate path in the code base (much like how Bitmap and Btree do) that would be specific to GiST. This would allow a different alternative altogether separate from the B-Tree and Bitmap path with its own costing and transforms.

Pros Cons
  1. A GiST specific path that could be configurable via GUCs
  2. A cost model specific to GiST
  1. Duplication of existing code by creating new transforms/classes
  2. Addition of Executor nodes/or a translation back into existing nodes
  3. Adding support for partitioned tables and AO tables would be slow and incremental

Implementation and Performance Improvements

When exploring the first alternative, we realized that the addition of the new index type and a few extra conditional checks, GiST would have full support in GPORCA. This includes partitioned tables as well as Append Only Row / Column Oriented  tables. In contrast, research into the second alternative indicated that much of the Bitmap and B-Tree transforms would have been duplicated in the process of creating a GiST transform. An additional node would also need to be added to the executor for a GiST specific scan as well.

By choosing the first alternative we were able to take advantage of the existing paths for indexes in GPORCA, allowing for full GiST support while minimizing code duplication. Going back to our motivating PostGIS example, we see that plan generated by GPORCA now matches that created by the planner.

GiST Aware GPORCA Generated Plan

Notice that GPORCA now uses a Bitmap Index Scan in the plan generated instead of a Table Scan. The use of a Bitmap Index Scan in the above plan indicates that the GiST index took the Bitmap path to create the plan. While the plan itself says Bitmap, when the query goes to execution, the actual index used is the GiST index.

The query execution time reduced to 309 milliseconds from 300 seconds, which is 1000x faster than what it was performing before GiST support. Meanwhile, GPORCA’s query optimization time stays the same  (around 250 ms).

After an initial run of the “Installcheck-good” test suite for GPDB, we observed a clear performance improvement among the different test cases, even with the addition of 4 new tests.

Test Name Before After % Improvement
qp_gist_indexes2 196.23 sec 110.62 sec 44%
qp_gist_indexes3 19.83 sec 13.75 sec 33%
qp_gist_indexes4 67.67 sec 50.66 sec 25%

 

Future Work

While GiST is now supported in GPORCA, there is still more work to be done. In regards to GiST indexes themselves, they currently do not support partial indexes or index expressions (such as IS NULL or NOT). The cost model still follows that of the Bitmap/B-Tree indexes and further performance tests are necessary to determine the best cost model for GiST indexes.

Additionally, there are other indexes that are not yet supported in GPORCA such as GIN or Hash indexes. However, these can be implemented in a manner similar to GIST index.

Conclusion

GiST indexes are a versatile template index structure that allows for the creation of indexes on custom data types. In the Greenplum Database, GPORCA originally did not handle GiST indexes, making any GPORCA generated plan extremely slow when the input grew large. We compared two different alternatives and chose the path that avoided excessive code duplication. Our final fix took advantage of existing index paths in GPORCA to allow the creation of GiST index plans. This created no/minor differences in the time it took to optimize, but is 1000x faster to run than the original plan.

Original blog post can be found here with the list of co-authors: http://engineering.pivotal.io/post/gist/

Footnotes

[1] Consistent returns false if, given a predicate on a tree page, the user query and predicate is not true, and returns maybe otherwise.
[2] Union consolidates information in the tree.
[3] Compress converts the entry into a suitable format for storage. This is usually what makes GiST indexes lossy.
[4] Reverse of compress.
[5] Penalty tells you the cost of inserting the entry into a path would be, it will pick the cheapest path.
[6] PickSplit helps decide which entries go to which page when an insert requires a page split.
[7] Same returns true if the two entries are the same.

 

20 Jun

Greenplum 5.9.0: A Minor but Powerful Release

We have recently released Greenplum 5.9.0. The release has  a good number of exciting features, including:

This is very impressive for a minor release and an indicator of the magnitude of the Greenplum user value creation. This is possible thanks to Pivotal’s agile development methodologies and a close collaboration with the PostgreSQL community.

For more information:

03 Jan

Self-Healing Greenplum – The Doctor Is Always In

Analytics On IaaS Must Think Differently Than It’s On Premise Implementations

We have always maintained that having a data platform that is portable is not only one of the key differentiators of Greenplum, but should be a core functional requirement on anyone’s roadmap for how to best architect for their needs.  But doing so should never be a straight port of what is on premise over to infrastructure in the cloud.  Instead, an understanding of both how our users are leveraging the data platform combined with the power of the cloud should lead us down an alternate, more advanced architecture.  One such innovation that has recently become available is the notion of self-healing Greenplum.   Read More

Head of Data for Pivotal

29 Nov

IoT, CEP, storage and NATS in between. Part 1 of 3.

Intro

Hello, my name is Dmitry Dorofeev, I’m a software architect working for Luxms Group. We are a team of creative programmers touching technology which moves faster than we can imagine these days. This blog post is about building a small streaming analytics pipeline which is minimalistic, but can be adapted for bigger projects easily. It can be started on a notebook (Yes, I tried that), and quickly deployed to the cloud if the need arises. Read More

01 Nov

Using The Greenplum Connector To Load Data Into Gemfire

One use case organizations face is the need to bulk load data into Gemfire Regions where regions in GemFire are similar to the table concept in a database.   Unlike a database, bulk-loading data into GemFire is more of a programming exercise than encountered with traditional bulk loading capabilities of a modern database product.  If the data sources and formats are relatively static, than a GemFire data loader will work for repeated loads of the source data types and formats.   As we all know, data sources, formats and types can be a moving target.

Read More

02 Oct

High Concurrency, Low Latency Index Lookups with Pivotal Greenplum Database

By Cyrille Lintz, Dino Bukvic, Gianluca Rossetti

You may have heard or read that Pivotal Greenplum is not suitable for small query processing or low latency lookups, but like any data platform, your mileage may vary depending on the use case and how you architect it. This post explains how to tune Pivotal Greenplum for an unusual workload: a “warm” layer below an in-memory key value store. We will explain how to tune Pivotal Greenplum to achieve a millisecond-range answer on key values access by using data populated by using a native JSON datatype store in the “key” column. Read More

19 Sep

Greenplum Next Generation Big Data Platform: Top 5 reasons

What are the Top 5 reasons that Greenplum is gaining in popularity and is the world’s next generation data platform? Read More

Working on enterprise software since 2002, and on big data and database management systems since 2007. Started on Greenplum Database in 2009 as a performance engineer and worked in various R&D and support capacities until shifting into product management for the world’s greatest database: Greenplum.

14 Sep

Pivotal Greenplum: Life in a Vacuum by Howard Goldberg

Vacuuming your home is a laborious task that you would rather not do.  However, vacuuming your home is an essential chore that must be done. The same is true for vacuuming the catalog in a Pivotal Greenplum database (“Greenplum”). The proper maintenance and care is required for the Greenplum catalog to keep the database functioning at its peak efficiency. Read More

Howard Goldberg – Executive Director
Morgan Stanley
Head of Greenplum Engineering

13 Sep

Introduction of Readable External Protocol of gpfdist

As the fundamental of all ETL operation of Greenplum, it worth explaining a little more  about the detail of gpfdist to understand why it is faster than other tools and how could we improve in future.

This blog will focus on the detail of communication of readable external table between gpfdist server and Greenplum, and introduce the traffic flow and protocol of gpfdist external table. Read More