The A part of PostgreSQL We Hate the Most

There are a number of selections in databases (897 as of April 2023). With so many programs, it’s onerous to know what to choose! However there may be an attention-grabbing phenomenon the place the Web collectively decides on the default selection for brand new purposes. Within the 2000s, the standard knowledge chosen MySQL as a result of rising tech stars like Google and Fb have been utilizing it. Then within the 2010s, it was MongoDB as a result of non-durable writes made it “webscale“. Within the final 5 years, PostgreSQL has grow to be the Web’s darling DBMS. And for good causes! It’s reliable, feature-rich, extensible, and well-suited for many operational workloads.

However as a lot as we love PostgreSQL at OtterTune, sure facets of it aren’t nice. So as an alternative of writing one more weblog article like everybody else touting the awesomeness of everybody’s favourite elephant-themed DBMS, we need to talk about the one main factor that sucks: how PostgreSQL implements multi-version concurrency control (MVCC). Our research at Carnegie Mellon College and expertise optimizing PostgreSQL database situations on Amazon RDS have proven that its MVCC implementation is the worst among the many different broadly used relational DBMSs, together with MySQL, Oracle, and Microsoft SQL Server. And sure, Amazon’s PostgreSQL Aurora nonetheless has these issues.

On this article, we’ll dive into MVCC: what it’s, how PostgreSQL does it, and why it’s horrible. Our purpose at OtterTune is to present you fewer issues to fret about along with your databases, so we’ve thought lots about coping with this downside. We’ll cowl OtterTune’s answer for managing PostgreSQL’s MVCC points robotically for RDS and Aurora databases in a follow-up article subsequent week.

What’s Multi-Model Concurrency Management?

The purpose of MVCC in a DBMS is to permit a number of queries to learn and write to the database concurrently with out interfering with one another when doable. The essential thought of MVCC is that the DBMS by no means overwrites current rows. As an alternative, for every (logical) row, the DBMS maintains a number of (bodily) variations. When the appliance executes a question, the DBMS determines which model to retrieve to fulfill the request in line with some model ordering (e.g., creation timestamp). The good thing about this method is that a number of queries can learn older variations of rows with out getting blocked by one other question updating it. Queries observe a snapshot of the database because it existed when the DBMS began that question’s transaction (snapshot isolation). This method eliminates the necessity for express record locks that block readers from accessing information whereas writers modify the identical merchandise.

David Reed’s 1978 MIT Ph.D. dissertation, “Concurrency Control in Distributed Database Systems,” was, we imagine, the primary publication to explain MVCC. The primary industrial DBMS implementation of MVCC was InterBase within the Nineteen Eighties. Since then, almost each new DBMS created within the final twenty years that helps transactions implements MVCC.

A programs engineer has to make a number of design selections when constructing a DBMS that helps MVCC. At a excessive stage, it comes right down to the next:

1. Easy methods to retailer updates to current rows.
2. Easy methods to discover the right model of a row for a question at runtime.
3. Easy methods to take away expired variations which are not seen.

These selections aren’t mutually unique. Within the case of PostgreSQL, it’s how they determined to deal with the primary query within the Nineteen Eighties that brought on issues with the opposite two that we nonetheless need to take care of as we speak.

For our dialogue, we’ll use the next instance of a desk containing film data. Every row within the desk contains the film identify, launch 12 months, director, and a singular ID serving as the first key, with secondary indexes on the film identify and director. Right here is the DDL command to create this desk:

CREATE TABLE films (
  id INTEGER PRIMARY KEY GENERATED ALWAYS AS IDENTITY,
  identify VARCHAR(256) NOT NULL,
  12 months SMALLINT NOT NULL,
  director VARCHAR(128)
);
CREATE INDEX idx_name ON films (identify);
CREATE INDEX idx_director ON films (director);

The desk incorporates a major index (movies_pkey) and two secondary B+Tree indexes (idx_name, idx_director).

PostgreSQL’s Multi-Model Concurrency Management

As mentioned in Stonebraker’s system design document from 1987, PostgreSQL was designed from the start to assist multi-versioning. The core thought of PostgreSQL’s MVCC scheme is seemingly easy: when a question updates an current row in a desk, the DBMS makes a replica of that row and applies the modifications to this new model as an alternative of overwriting the unique row. We check with this method because the append-only model storage scheme. However as we now describe, this method has a number of non-trivial implications in the remainder of the system.

Multi-Versioned Storage

PostgreSQL shops all row variations in a desk in the identical cupboard space. To replace an current tuple, the DBMS first acquires an empty slot from the desk for the brand new row model. It then copies the row content material of the present model to the brand new model, and applies the modifications to the row within the newly allotted model slot. You may see this course of within the instance under when an software executes an replace question on the flicks database to vary the discharge 12 months of “Shaolin and Wu Tang” from 1985 to 1983:

Now with two bodily variations representing the identical logical row, the DBMS must report the lineage of those variations in order that it is aware of how you can discover them sooner or later. MVCC DBMSs obtain this by making a model chain by way of a singly linked-list. The model chain solely goes in a single route to scale back storage and upkeep overhead. Because of this the DBMS has to determine what order to make use of: newest-to-oldest (N2O) order or oldest-to-newest (O2N). For the N2O order, every tuple model factors to its earlier model and the model chain’s head is all the time the most recent model. For the O2N order, every tuple model factors to its new model, and the top is the oldest tuple model. The O2N method avoids the necessity for the DBMS to replace indexes to level to a more moderen model of the tuple every time it’s modified. Nevertheless, it might take longer for the DBMS to seek out the most recent model throughout question processing, probably traversing a protracted model chain. Most DBMSs, together with Oracle and MySQL, implement N2O. However PostgreSQL stands alone in utilizing O2N (apart from Microsoft’s In-Memory OLTP engine for SQL Server).

The following concern is how PostgreSQL determines what to report for these model pointers. The header for every row in PostgreSQL incorporates a tuple id area (t_tcid) of the subsequent model (or its personal tuple id if it’s the newest model). Thus, as proven on this subsequent instance, when a question requests the most recent model of a row, the DBMS traverses the index, lands on the oldest model, after which follows the pointer till it finds a model that it wants.

PostgreSQL builders realized early on that there are two issues with its MVCC scheme. First, making a brand new copy of a whole tuple each time it’s up to date is pricey. And second, traversing the whole model chain simply to seek out the most recent model (which is what most queries need) is wasteful. After all there may be additionally the issue of cleansing up outdated variations, however we’ll cowl that under.

To keep away from traversing the whole model chain, PostgreSQL provides an entry to a desk’s indexes for every bodily model of a row. Which means if there are 5 bodily variations of a logical row, there will likely be (at most) 5 entries for that tuple within the index! Within the instance under, we see that the idx_name index incorporates entries for every of the “Shaolin and Wu Tang” rows which are on separate pages. This allows direct entry to the most recent model of the tuple, with out the necessity to traverse the lengthy model chain.

PostgreSQL tries to keep away from having to put in a number of index entries and storing associated variations over a number of pages by creating a brand new copy in the identical disk web page (block) because the outdated model to scale back disk I/O. This optimization is named heap-only tuple (HOT) updates. The DBMS makes use of the HOT method if an replace doesn’t modify any columns referenced by a desk’s indexes and the brand new model is saved on the identical information web page because the outdated model (if there may be house in that web page). Now in our instance, after the replace the index nonetheless factors to the outdated model and queries retrieve the most recent model by traversing the model chain. Throughout regular operation, PostgreSQL additional optimizes this course of by eradicating outdated variations to prune the model chain.

Model Vacuum

We’ve established that PostgreSQL makes a replica of rows every time an software updates them. The following query is how the system removes older variations (referred to as “lifeless tuples”). The unique model of PostgreSQL from the Nineteen Eighties didn’t take away lifeless tuples. The concept was that holding all of the older variations allowed purposes to execute “time-travel” queries to look at the database at a specific cut-off date (e.g., run a SELECT question on the state of the database because it existed on the finish of final week). However by no means eradicating lifeless tuples means tables by no means shrink in dimension if the appliance deletes tuples. It additionally means lengthy model chains for steadily up to date tuples, which might decelerate queries, besides that PostgreSQL provides index entries that enable queries to rapidly soar to the right model as an alternative of traversing the chain. However now, this implies the indexes are bigger, making them slower and including further reminiscence stress. Hopefully, you’ll be able to perceive now why all these points are interconnected.

To beat these issues, PostgreSQL makes use of a vacuum process to scrub up lifeless tuples from tables. The vacuum performs a sequential scan on desk pages modified since its final run and discover expired variations. The DBMS considers a model “expired” if it’s not seen to any energetic transaction. This implies no present transaction is accessing that model, and future transactions will use the most recent “dwell” model as an alternative. Thus, eradicating the expired model and reclaiming the house for reuse is protected.

PostgreSQL robotically executes this vacuum process (autovacuum) at common intervals primarily based on its configuration settings. Along with the worldwide settings that have an effect on the vacuum frequency for all tables, PostgreSQL gives the pliability to configure autovacuum on the desk stage to fine-tune the method for particular tables. Customers can even set off the vacuum manually to optimize database efficiency by way of the VACUUM SQL command.

Why PostgreSQL’s MVCC is the Worst

We will likely be blunt: if somebody goes to construct a brand new MVCC DBMS as we speak, they need to not do it the best way PostgreSQL does (e.g., append-only storage with autovacuum). In our 2018 VLDB paper (aka “the best paper ever on MVCC“), we didn’t discover one other DBMS doing MVCC the best way PostgreSQL does it. Its design is a relic of the Nineteen Eighties and earlier than the proliferation of log-structured system patterns from the Nineties.

Let’s discuss 4 issues that come up with PostgreSQL’s MVCC. We can even discuss why different MVCC DBMSs like Oracle and MySQL keep away from these issues.

Drawback #1: Model Copying

With the append-only storage scheme in MVCC, if a question updates a tuple, the DBMS copies all its columns into the brand new model. This copying happens irrespective of if the question updates a single or all of its columns. As you’ll be able to think about, append-only MVCC leads to large information duplication and elevated storage necessities. This method signifies that PostgreSQL requires extra reminiscence and disk storage to retailer a database than different DBMS, which suggests slower queries and better cloud prices.

As an alternative of copying a whole tuple for a brand new model, MySQL and Oracle retailer a compact delta between the brand new and present variations (consider it like a git diff). Utilizing deltas signifies that if a question solely updates a single column in a tuple for a desk with 1000 columns, then the DBMS solely shops a delta report with the change to that one column. Alternatively, PostgreSQL creates a brand new model with the one column that the question modified and the 999 different untouched columns. We are going to ignore TOAST attributes as a result of PostgreSQL handles them differently.

There was an try to modernize PostgreSQL’s model storage implementation. EnterpriseDB began the zheap project in 2013 to exchange the append-only storage engine to make use of delta variations. Sadly the last official update was in 2021, and to the perfect of our information the hassle has fizzled out.

Drawback #2: Desk Bloat

Expired variations in PostgreSQL (i.e., lifeless tuples) additionally occupy more room than delta variations. Though PostgreSQL’s autovacuum will ultimately take away these lifeless tuples, write-heavy workloads may cause them to build up sooner than the vacuum can catch up, leading to steady database progress. The DBMS has to load lifeless tuples into reminiscence throughout question execution because the system intermingles lifeless tuples with dwell tuples in pages. Unfettered bloat slows question efficiency by inflicting the DBMS to incur extra IOPS and eat extra reminiscence than needed throughout desk scans. Moreover, inaccurate optimizer statistics brought on by lifeless tuples can result in poor question plans.

Suppose our films desk has 10 million dwell and 40 million lifeless tuples, making 80% of the desk out of date information. Assume additionally that the desk additionally has many extra columns than what we’re displaying and that the typical dimension of every tuple is 1KB. With this situation, the dwell tuples occupy 10GB of cupboard space whereas the lifeless tuples occupy ~40GB of storage; the entire dimension of the desk is 50GB. When a question performs a full desk scan on this desk, PostgreSQL has to retrieve all 50GB from the disk and retailer it in reminiscence, even when most of it’s out of date. Though Postgres has a protection mechanism to keep away from polluting its buffer pool cache from sequential scans, it doesn’t assist stop IO prices.

Even when you guarantee that PostgreSQL’s autovacuum is operating at common intervals and capable of sustain along with your workload (which isn’t all the time simple to do, see under), the autovacuum can not reclaim cupboard space. The autovacuum solely removes lifeless tuples and relocates dwell tuples inside every web page, but it surely doesn’t reclaim empty pages from the disk.

When the DBMS truncates the final web page as a result of absence of any tuple, different pages stay on disk. In our instance above, even when PostgreSQL eliminated the 40GB of lifeless tuples from the flicks desk, it nonetheless retains the 50GB of allotted cupboard space from the working system (or, within the case of RDS, from Amazon). To reclaim and return such unused house, one should use VACUUM FULL or the pg_repack extension to rewrite the whole desk to a brand new house with no wasted storage. Working both of those operations shouldn’t be a straightforward endeavor that one ought to take with out contemplating the efficiency implications for manufacturing databases; they’re resource-intensive and time-consuming operations that can crush question efficiency. The next determine reveals how VACUUM and VACUUM FULL work.

Drawback #3: Secondary Index Upkeep

A single replace to a tuple requires PostgreSQL to replace all of the indexes for that desk. Updating all of the indexes is critical as a result of PostgreSQL makes use of the precise bodily places of a model in each major and secondary indexes. Until the DBMS shops the brand new model in the identical web page because the earlier model (HOT replace), the system does this for each replace.

Returning to our UPDATE question instance, PostgreSQL creates a brand new model by copying the unique model into a brand new web page identical to earlier than. Nevertheless it additionally inserts entries pointing to the brand new model in desk’s major key index (movies_pkey) and the 2 secondary indexes (idx_director, idx_name).

The necessity for PostgreSQL to switch all of a desk’s indexes for every replace has a number of efficiency implications. Clearly, this makes replace queries slower as a result of the system has to do extra work. The DBMS incurs further I/O to traverse every index and insert the brand new entries. Accessing an index introduces lock/latch rivalry in each the index and the DBMS’s inside information buildings (e.g., buffer pool’s web page desk). Once more, PostgreSQL does this upkeep work for all a desk’s indexes, even when queries are by no means going to make use of them (by the best way, OtterTune automatically finds unused indexes in your database). These additional reads and writes are problematic in DBMSs that cost customers primarily based on IOPS, like Amazon Aurora.

As described above, PostgreSQL avoids updating indexes every time if it will possibly carry out a HOT write the place the brand new model is on the identical web page as the present model. Our evaluation of OtterTune clients’ PostgreSQL databases reveals that roughly 46% of updates use the HOT optimization on common. Though that’s a powerful quantity, it nonetheless means greater than 50% of the updates are paying this penalty.

There are numerous examples of customers fighting this facet of PostgreSQL’s MVCC implementation. Essentially the most well-known testomony of that is Uber’s 2016 weblog article about why they switched from Postgres to MySQL. Their write-heavy workload was experiencing vital efficiency issues on tables with many secondary indexes.

Oracle and MySQL shouldn’t have this downside of their MVCC implementation as a result of their secondary indexes don’t retailer the bodily addresses of latest variations. As an alternative, they retailer a logical identifier (e.g., tuple id, major key) that the DBMS then makes use of to search for the present model’s bodily deal with. Now this will make secondary index reads slower because the DBMS has to resolve a logical identifier, however these DBMS produce other benefits of their MVCC implementation to scale back overhead.

Drawback #4: Vacuum Administration

PostgreSQL’s efficiency depends closely on the effectiveness of the autovacuum to take away out of date information and reclaim house (because of this OtterTune instantly checks the well being standing of the autovacuum while you first join your database). It doesn’t matter in case you are operating RDS, Aurora, or Aurora Serverless; all variants of PostgreSQL have the identical autovacuum points.

However ensuring that PostgreSQL’s autovacuum is operating as finest as doable is tough attributable to its complexity. PostgreSQL’s default settings for tuning the autovacuum aren’t perfect for all tables, notably for big ones. For instance, the default setting for the configuration knob that controls what proportion of a desk PostgreSQL has to replace earlier than the autovacuum kicks in (autovacuum_vacuum_scale_factor) is 20%. This threshold signifies that if a desk has 100 million tuples, the DBMS doesn’t set off the autovacuum till queries replace not less than 20 million tuples. As such, PostgreSQL could unnecessarily maintain round a number of lifeless tuples in a desk (thereby incurring IO and reminiscence prices) for a very long time.

One other downside with the autovacuum in PostgreSQL is that it might get blocked by long-running transactions, which may end up in the buildup of extra lifeless tuples and rancid statistics. Failing to scrub expired variations in a well timed method results in quite a few efficiency issues, inflicting extra long-running transactions that block the autovacuum course of. It turns into a vicious cycle, requiring people to intervene manually by killing long-running transactions.

Contemplate the graph under that reveals the variety of lifeless tuples in an OtterTune buyer’s database over two weeks:

The sawtooth sample within the chart reveals that the autovacuum performs a significant clean-up about as soon as each day. For instance, on February 14th, the DBMS cleaned up 3.2 million lifeless tuples. This graph is definitely an instance of an unhealthy PostgreSQL database. The chart clearly reveals an upward development within the variety of lifeless tuples as a result of the autovacuum can not sustain.

At OtterTune, we see this downside typically in our clients’ databases. One PostgreSQL RDS occasion had a long-running question brought on by stale statistics after bulk insertions. This question blocked the autovacuum from updating the statistics, leading to extra long-running queries. OtterTune’s automated well being checks recognized the issue, however the administrator nonetheless needed to kill the question manually and run ANALYZE after bulk insertions. The excellent news is that the lengthy question’s execution time went from 52 minutes to only 34 seconds.

There are all the time onerous design selections one has to make when constructing a DBMS. And these selections will trigger any DBMS to carry out in another way on various workloads. For Uber’s particular write-intensive workload, PostgreSQL’s index write amplification attributable to MVCC is why they switched to MySQL. However please don’t misunderstand our diatribe to imply that we don’t suppose it’s best to ever use PostgreSQL. Though its MVCC implementation is the flawed technique to do it, PostgreSQL continues to be our favourite DBMS. To like one thing is to be prepared to work with its flaws (see Dan Savage’s “The Price of Admission”).

So how does one work round PostgreSQL’s quirks? Effectively, you’ll be able to spend an unlimited quantity of effort and time tuning it your self. Good luck with that.

We’ll cowl extra about what we are able to do in our subsequent article.