<?xml version="1.0" encoding="UTF-8"?>
<feed xml:lang="en-US" xmlns="http://www.w3.org/2005/Atom">
  <title>Articles — brandur.org (postgres)</title>
  <id>tag:brandur.org,2013:/articles-postgres</id>
  <updated>2026-05-31T12:41:38+02:00</updated>
  <link rel="self" type="application/atom+xml" href="https://brandur.org/articles-postgres.atom"></link>
  <link rel="alternate" type="text/html" href="https://brandur.org"></link>
  <entry>
    <title>The Notifier Pattern for Applications That Use Postgres</title>
    <summary>Maximizing Postgres connection economy by using a single connection per program to receive and distribute all listen/notify notifications.</summary>
    <content type="html"><![CDATA[<p><a href="https://www.postgresql.org/docs/current/sql-listen.html">Listen/notify in Postgres</a> is an incredible feature that makes itself useful in all kinds of situations. I&rsquo;ve been using it a long time, started taking it for granted long ago, and was somewhat shocked recently looking into MySQL and SQLite to learn that even in 2024, no equivalent exists.</p>

<p>In a basic sense, listen/notify is such a simple concept that it needs little explanation. Clients subscribe on topics and other clients can send on topics, passing a message to each subscribed client. The idea takes only three seconds to demonstrate using nothing more than a psql shell:</p>

<pre><code class="language-sql">=# LISTEN test_topic;
LISTEN
Time: 2.828 ms

=# SELECT pg_notify('test_topic', 'test_message');
 pg_notify
-----------

(1 row)

Time: 17.892 ms
Asynchronous notification &quot;test_topic&quot; with payload &quot;test_message&quot; received from server process with PID 98481.
</code></pre>

<p>But despite listen/notify&rsquo;s relative simplicity, when it comes to applications built on top of Postgres, it&rsquo;s common to use it less than optimally, eating through scarce Postgres connections and with little regard to failure cases.</p>

<hr />

<p>Here&rsquo;s where the <strong>notifier pattern for Postgres</strong> comes in. It&rsquo;s an extremely simple idea, but in my experience, one that&rsquo;s rarely seen in practice. Let&rsquo;s start with these axioms:</p>

<ul>
<li><p><code>LISTEN</code>s are affixed to specific connections. After listening, the original connection must still be available somewhere to successfully receive messages.</p></li>

<li><p>There may be many components within an application that&rsquo;d like to listen on topics for completely orthogonal uses.</p></li>

<li><p>Despite optimizations over the years, connections in Postgres are still somewhat of a precious, limited resource, and should be conserved. We&rsquo;d like to minimize the number of them required for listen/notify use.</p></li>

<li><p>A single connection can listen on any number of topics.</p></li>
</ul>

<p>With those stated, we can explain the role of the notifier. Its job is to <strong>hold a single Postgres connection per process, allow other components in the same program to use it to subscribe to any number of topics, wait for notifications, and distribute them to listening components as they&rsquo;re received</strong>.</p>

<p>The &ldquo;single Postgres connection per process&rdquo; piece is key. Use of a notifier keeps the number of Postgres connections dedicated to use with listen/notify down to <strong>one per program</strong>, a major advantage compared to the naive version, which is <em>one connection per topic per program</em>. Especially for languages like Go that make a in-process concurrency easy and cheap, the notifier reduces listen/notify connection overhead to practically nil.</p>

<p><img src="/assets/images/notifier/notifier.svg" alt="Notifier distributing notifications to program components"></p>

<h2 id="implementation" class="link"><a href="#implementation">A few implementation details</a></h2>

<p>From a conceptual standpoint, the notifier&rsquo;s not difficult to understand, and with only this high level description, most readers would be able to implement it themselves. I&rsquo;m not going to go through an implementation in full detail, but let&rsquo;s look at a few important aspects of one. (For a complete reference, you can take a look <a href="https://github.com/riverqueue/river/tree/master/internal/notifier">at River&rsquo;s notifier</a>, which is quite well vetted.)</p>

<p>Here&rsquo;s a listen function to establish a new subscription:</p>

<pre><code class="language-go">// Listen returns a subscription that lets a caller receive values from a
// notification channel.
func (l *Notifier) Listen(channel string) *Subscription {
    l.mu.Lock()
    defer l.mu.Unlock()

    existingSubs := l.subscriptions[channel]

    sub := &amp;Subscription{
        channel:        channel,
        listenChan:     make(chan string, 100),
        notifyListener: l,
    }
    l.subscriptions[channel] = append(existingSubs, sub)

    if len(existingSubs) &gt; 0 {
        // If there's already another subscription for this channel, reuse its
        // established channel. It may already be closed (to indicate that the
        // connection is established), but that's okay.
        sub.establishedChan = existingSubs[0].establishedChan
        sub.establishedChanClose = func() {} // no op since not channel owner

        return sub
    }

    // The notifier will close this channel after it's successfully established
    // `LISTEN` for the given channel. Gives subscribers a way to confirm a
    // listen before moving on, which is especially useful in tests.
    sub.establishedChan = make(chan struct{})
    sub.establishedChanClose = sync.OnceFunc(func() { close(sub.establishedChan) })

    l.channelChanges = append(l.channelChanges,
        channelChange{channel, sub.establishedChanClose, channelChangeOperationListen})

    // Cancel out of blocking on WaitForNotification so changes can be processed
    // immediately.
    l.waitForNotificationCancel() 

    return sub
}
</code></pre>

<p>A few key details to notice:</p>

<ul>
<li><p>Subscriptions use a <strong>buffered channel</strong> like <code>make(chan string, 100)</code> and <strong>non-blocking sends</strong> (using <code>select</code> with <code>default</code>). A notifier may receive a high volume of notifications, and if it were to block on every component successfully receiving and processing each one, it could easily fall behind. Instead, a received notification is sent into the channel using a non-blocking send. The non-blocking send means that the send operation will never block: instead the notification is discarded if the channel is full. The buffer provides a tunable amount of slack to make sure this won&rsquo;t happen too easily. It&rsquo;s each component&rsquo;s job to make sure its processing its inbox in a timely manner. This is important because even in the event of one component falling behind, the system as a whole stays healthy.</p></li>

<li><p>Multiple components may want to subscribe to the same topic. Since only one connection is in use, the notifier only needs to issue one <code>LISTEN</code> per topic. Internally, it organizes subscriptions by topic, and if it notices that a topic already exists, a new subscription is added without issuing <code>LISTEN</code>.</p></li>

<li><p>Subscriptions provide an <strong>established channel</strong> that&rsquo;s closed when a <code>LISTEN</code> has been successfully issued and the notifier is up and listening. This isn&rsquo;t strictly necessary for most production uses, but it&rsquo;s invaluable for use in testing. If a test case issues <code>pg_notify</code> before the notifier has started listening, that notification is lost &ndash; a problem that can lead to tortuous test intermittency <sup id="footnote-1-source"><a href="#footnote-1">1</a></sup>. Instead, a test case tells the notifier to listen, <em>waits for the listen to succeed</em>, then moves on to send <code>pg_notify</code>.</p></li>
</ul>

<pre><code class="language-go">// EstablishedC is a channel that's closed after the notifier's successfully
// established a connection. This is especially useful in test cases, where it
// can be used to wait for confirmation that not only that the listener is
// started, but that it's successfully established started listening on a
// channel before continuing. For a new subscription on an already established
// channel, EstablishedC is already closed, so it's always safe to wait on it.
//
// There's no full guarantee that the notifier can ever successfully establish a
// listen, so callers will usually want to `select` on it combined with a
// context done, a stop channel, and/or a timeout.
//
// The channel is always closed as a notifier is stopping.
func (s *Subscription) EstablishedC() &lt;-chan struct{} { return s.establishedChan }
</code></pre>

<h3 id="interruptible-receives" class="link"><a href="#interruptible-receives">Interruptible receives</a></h3>

<p>There&rsquo;s no standard SQL for waiting for a notification. Typically, it&rsquo;s accomplished using a special driver-level function like <a href="https://pkg.go.dev/github.com/jackc/pgx/v5#Conn.WaitForNotification">Pgx&rsquo;s <code>WaitForNotification</code></a>.</p>

<p>These commonly block until receiving a notification, which can be problem since we&rsquo;re only using a single connection. What if the notifier is in a blocking receive loop, but another component wants to add a new subscription that requires <code>LISTEN</code> be issued?</p>

<p>You&rsquo;ll want to handle this case by making sure that the wait loop is interruptible. Here&rsquo;s one way to accomplish that in Go:</p>

<pre><code class="language-go">func (l *Notifier) runOnce(ctx context.Context) error {
    if err := l.processChannelChanges(ctx); err != nil {
        return err
    }

    // WaitForNotification is a blocking function, but since we want to wake
    // occasionally to process new `LISTEN`/`UNLISTEN` operations, we put a
    // context deadline on the listen, and as it expires don't treat it as an
    // error unless it's unrelated to context expiration.
    notification, err := func() (*pgconn.Notification, error) {
        const listenTimeout = 30 * time.Second

        ctx, cancel := context.WithTimeout(ctx, listenTimeout)
        defer cancel()

        // Provides a way for the blocking wait to be cancelled in case a new
        // subscription change comes in.
        l.mu.Lock()
        l.waitForNotificationCancel = cancel
        l.mu.Unlock()

        notification, err := l.conn.WaitForNotification(ctx)
        if err != nil {
            return nil, xerrors.Errorf(&quot;error waiting for notification: %w&quot;, err)
        }

        return notification, nil
    }()
    if err != nil {
        // If the error was a cancellation or the deadline being exceeded but
        // there's no error in the parent context, return no error.
        if (errors.Is(err, context.Canceled) ||
            errors.Is(err, context.DeadlineExceeded)) &amp;&amp; ctx.Err() == nil {
            return nil
        }

        return err
    }

    l.mu.RLock()
    defer l.mu.RUnlock()

    // Notify subscribers (this is a no-op if no subs/empty slice).
    for _, sub := range l.subscriptions[notification.Channel] {
        sub.listenChan &lt;- notification.Payload
    }

    return nil
}
</code></pre>

<p>The inner closure calls into <code>WaitForNotification</code>, but has a default context timeout of 30 seconds that automatically cycles the function periodically. It also stores the special context cancellation function <code>l.waitForNotificationCancel</code>.</p>

<p>When <code>Listen</code> is invoked and a new subscription needs to be added, <code>l.waitForNotificationCancel</code> is called. The wait is cancelled immediately, new subscriptions are processed, and the closure is reentered to wait anew.</p>

<h3 id="let-it-crash" class="link"><a href="#let-it-crash">Let it crash</a></h3>

<p>Given there&rsquo;s now a single master connection that&rsquo;s handling all notifications for a program, it&rsquo;s fairly critical that its health be monitored, and the notifier reacts appropriately. If not, all uses of listen/notify would degrade simultaneously.</p>

<p>The obvious way to react would be to close the connection, use a connection pool to procure a new connection, reissue <code>LISTEN</code>s for each active subscription, then reenter the wait loop.</p>

<p>It can be a little tricky sometimes to guarantee that state is reset cleanly, so another possibility is to adhere to the &ldquo;let it crash&rdquo; school of thought. If the connection becomes irreconcilably unhealthy, stop the program, and have it come back to a healthy state by virtue of its normal start up.</p>

<pre><code class="language-go">// If the notifier gets unhealthy, restart the worker. This will generally
// never happen as the notifier has a built-in retry loop that try its best
// to keep established before giving up.
notifier.AddUnhealthyCallback(closeShutdown)
</code></pre>

<p>We&rsquo;ve found this sort of edge to be so rare (I&rsquo;ve only seen it happen once in a year+ of use) that letting the program crash when it does happen hasn&rsquo;t produced any undue disruption.</p>

<h2 id="pgbouncer" class="link"><a href="#pgbouncer">PgBouncer</a></h2>

<p>Using <a href="https://www.pgbouncer.org/features.html">PgBouncer</a>, <code>LISTEN</code> is only supported using session pooling (as opposed to transaction pooling) because notifications are only sent to the original session that issued a <code>LISTEN</code> for them.</p>

<p>Use of a notifier requires an app to dedicate a single connection per program for listen/notify, but every other part of the application is free to use PgBouncer in transaction pooling or statement pooling mode, thereby maximizing the efficiency of connection use.</p>


]]></content>
    <published>2024-05-06T07:54:07+02:00</published>
    <updated>2024-05-06T07:54:07+02:00</updated>
    <link href="https://brandur.org/notifier"></link>
    <id>tag:brandur.org,2024-05-06:notifier</id>
    <author>
      <name>Brandur Leach</name>
      <uri>https://brandur.org</uri>
    </author>
  </entry>
  <entry>
    <title>Postgres: Boundless `text` and Back Again</title>
    <summary>The &lt;code&gt;text&lt;/code&gt; type in Postgres, why it&amp;rsquo;s awesome, and why you might want to use &lt;code&gt;varchar&lt;/code&gt; anyway. Also, a story about trying to get string parameters bounded at Stripe.</summary>
    <content type="html"><![CDATA[<p>One of the major revelations for almost every new user to Postgres is that there&rsquo;s no technical advantage of specifying columns as <code>varchar(n)</code> compared to just using bound-less <code>text</code>. Not only is the <code>text</code> type provided as a convenience (it&rsquo;s not in the SQL standard), but using it compared to constrained character types like <code>char</code> and <code>varchar</code> carries no performance penalty. From the Postgres <a href="https://www.postgresql.org/docs/current/datatype-character.html">docs on character type</a> (and note that <code>character varying</code> is the same thing as <code>varchar</code>):</p>

<blockquote>
<p>There is no performance difference among these three types, apart from increased storage space when using the blank-padded type, and a few extra CPU cycles to check the length when storing into a length-constrained column. While <code>character(n)</code> has performance advantages in some other database systems, there is no such advantage in PostgreSQL; in fact <code>character(n)</code> is usually the slowest of the three because of its additional storage costs. In most situations <code>text</code> or <code>character varying</code> should be used instead.</p>
</blockquote>

<p>For many of us this is a huge unburdening, as we&rsquo;re used to micromanaging length limits in other systems. Having worked in large MySQL and Oracle systems, I was in the habit of not just figuring out what column to add, but also how long it needed to be &ndash; should this be a <code>varchar(50)</code> or <code>varchar(100)</code>? <code>500</code>? (Or none of the above?) With Postgres, you just stop worrying and slap <code>text</code> on everything. It&rsquo;s freeing.</p>

<p>I&rsquo;ve since changed my position on that somewhat, and to explain why, I&rsquo;ll have to take you back to Stripe circa ~2018.</p>

<h2 id="s3ripe" class="link"><a href="#s3ripe">S3ripe</a></h2>

<p>One day we came to a rude awakening that we weren&rsquo;t checking length limits on text fields in Stripe&rsquo;s API. It wasn&rsquo;t just that a few of them weren&rsquo;t checked &ndash; it was that practically none of them were. While the API framework did allow for a maximum length, no one had ever thought to assign it a reasonable default, and as a matter of course the vast majority of parameters (of which there were thousands by this point) didn&rsquo;t set one. As long as senders didn&rsquo;t break any limits around size of request payload, they could send us whatever they wanted in any field they wanted. The API would happily pass it through and persist it to Mongo forever.</p>

<p>I don&rsquo;t remember how exactly we noticed, but sufficed to say we only did when it became a problem. Some user was sending us truly ginormous payloads and it was crashing HTTP workers, tying up database resources, or something equally bad.</p>

<p>As far as problems in computing go, checking string lengths isn&rsquo;t one that&rsquo;s considered to be particularly hard, so we set to work putting in a fix. But not so fast &ndash; these weren&rsquo;t the early days of the company anymore. We already had countless users, were processing millions of requests, and that meant by extension that we could expect many of those to include large-ish strings. We&rsquo;d never had rules around lengths before, and without a hard constraint, given enough users and enough time, someone (or many someones as it were) eventually starts sending long strings. Suddenly introducing maximums would break those integrations and create a lot of unhappy users. Stripe takes backwards compatibility very seriously, and would never do something like that on purpose.</p>

<p>Already fearing what I was about to find, I went ahead and put a probe in production that would generate statistics around text field lengths, including upper bounds and distribution, and waited a day to gather data.</p>

<p>It was even worse than we&rsquo;d thought &ndash; we had at least hundreds of users (and maybe thousands, my memory is bad) who were sending huge text payloads. Worse yet, these were all legitimate users &ndash; legitimate users who for one reason or another had decided over the years to build unconventional integration patterns. They&rsquo;d be doing something like sending us their whole product catalog, or a big JSON blob to store, and as part of their normal integration flows.</p>

<p>We&rsquo;d occasionally engage in active outreach campaigns to get users to change something, but it&rsquo;s a massive amount of work, and we have to offer generous deprecation timelines when we do. Given the nature of this problem and the number of users involved, it wasn&rsquo;t worth the effort. My dream of constraining most fields like customer or plan name to something reasonable like &ldquo;only&rdquo; 200 characters was a total non-starter.</p>

<p>Instead, we ran the numbers, and came up with a best fit compromise that would leave the maximum numbers of users unaffected while still bounding fields text fields to something not completely crazy (the chosen number was 5000, as viewable in the <a href="https://github.com/stripe/openapi">public OpenAPI spec</a>). And even the new very liberal limit was too long for a few users sending us giant payloads, so we gated them into an exemption.</p>

<p>Let me briefly restate Hyrum&rsquo;s law:</p>

<blockquote>
<p>With a sufficient number of users of an API, it does not matter what you promise in the contract: all observable behaviors of your system will be depended on by somebody.</p>
</blockquote>

<p>Truer words have rarely been spoken.</p>

<h2 id="varchars" class="link"><a href="#varchars">varchars considered ~harm~helpful</a></h2>

<p>Starting my <a href="/nanoglyphs/024-new-horizons">new position back in April</a>, one thing I checked early on is whether we were checking the length of strings that we were passing on through to the database. Nope. It turns out that this is a <em>very</em> easy mistake to make.</p>

<p>This is a downside to the common Postgres wisdom of &ldquo;just use <code>text</code>&rdquo;. It&rsquo;s generally fine, but there are ramifications at the edges that are harder to see.</p>

<p>I&rsquo;ve gone back to the habit of making most text fields <code>varchar</code> again. But I still don&rsquo;t like micromanaging character lengths, or how after a while every <code>varchar</code> column has a different length seemingly picked at random, so I&rsquo;ve pushed that we adopt some common order of magnitude &ldquo;tiers&rdquo;. For example:</p>

<ul>
<li><code>varchar(200)</code> for shorter-length strings like names, addresses, email addresses, etc.</li>
<li><code>varchar(2000)</code> for longer text blocks like descriptions.</li>
<li><code>varchar(20000)</code> for really long text blocks.</li>
</ul>

<p>The idea is to pick <em>liberal</em> numbers that are easily long enough to hold any even semi-valid data. Hopefully you never actually reach any of these maximums &ndash; they&rsquo;re just there as a back stop to protect against data that&rsquo;s wildly wrong. I wouldn&rsquo;t even go so far as to encourage the use of the numbers I pitched above &ndash; if you try this, go with your own based on what works for you.</p>

<p>Having a constraint in the database doesn&rsquo;t mean that you shouldn&rsquo;t <em>also</em> check limits in code. Most programs aren&rsquo;t written to gracefully handle database constraint failures, so for the sake of your users, put in a standard error-handling framework and descriptive error messages in the event this ever happens. Once again, the database is the back stop &ndash; there as a last layer of protection when the others fail.</p>

<h3 id="coercible-types" class="link"><a href="#coercible-types">Coercible types and operations</a></h3>

<p>Back in the old days, there was a decent argument to avoid <code>varchar</code> for operational resilience if nothing else. Changing a column&rsquo;s data type is often an expensive process involving full table scans and rewrites that can put a hot database at major risk. Is the potential agony really worth it just to use a <code>varchar</code> that&rsquo;s later found to be too short?</p>

<p>Luckily, when it comes to <em>relaxing</em> constraints, this isn&rsquo;t too much of a problem anymore. From the <a href="https://www.postgresql.org/docs/current/sql-altertable.html">Postgres docs on <code>ALTER TABLE</code></a>:</p>

<blockquote>
<p>Adding a column with a volatile <code>DEFAULT</code> or changing the type of an existing column will require the entire table and its indexes to be rewritten. As an exception, when changing the type of an existing column, if the <code>USING</code> clause does not change the column contents and the old type is either binary coercible to the new type or an unconstrained domain over the new type, a table rewrite is not needed; but any indexes on the affected columns must still be rebuilt.</p>
</blockquote>

<p>Note the wording of &ldquo;unconstrained domain&rdquo;. A <code>varchar(200)</code> is an unconstrained domain over a <code>varchar(100)</code> because it&rsquo;s strictly longer. Postgres can relax the constraint without needing to lock the table for a scan. Going back the other way isn&rsquo;t as easy, but you shouldn&rsquo;t need to do that.</p>

<h3 id="sql-domains" class="link"><a href="#sql-domains">SQL domains</a></h3>

<p>Another idea I&rsquo;ve been experimenting with is encoding a standard set of text tiers as <a href="https://www.postgresql.org/docs/current/sql-createdomain.html">domains</a>, which defines a new data type with more constraints:</p>

<pre><code class="language-sql">CREATE DOMAIN text_standard AS varchar(200) COLLATE &quot;C&quot;;
CREATE DOMAIN text_long AS varchar(2000) COLLATE &quot;C&quot;;
CREATE DOMAIN text_huge AS varchar(20000) COLLATE &quot;C&quot;;
</code></pre>

<p>The domains can then be used by convention in table definitions:</p>

<pre><code class="language-sql"># CREATE TABLE mytext (standard text_standard, long text_long, huge text_huge);

# \d+ mytext
                                       Table &quot;public.mytext&quot;
  Column  |     Type      | Collation | Nullable | Default | Storage  | Stats target | Description
----------+---------------+-----------+----------+---------+----------+--------------+-------------
 standard | text_standard |           |          |         | extended |              |
 long     | text_long     |           |          |         | extended |              |
 huge     | text_huge     |           |          |         | extended |              |
</code></pre>

<p>The only thing I don&rsquo;t like about this set up is that it somewhat obfuscates what those columns are because they&rsquo;re no longer a common type. It is quite easy to get Postgres to hand you back domain definitions with <code>\dD</code>:</p>

<pre><code class="language-sql"># \dD
                                      List of domains
 Schema |     Name      |           Type           | Collation | Nullable | Default | Check
--------+---------------+--------------------------+-----------+----------+---------+-------
 public | text_huge     | character varying(20000) | C         |          |         |
 public | text_long     | character varying(2000)  | C         |          |         |
 public | text_standard | character varying(200)   | C         |          |         |
</code></pre>

<p>But &hellip; almost nobody will know how to do that off the top of their head.</p>

<h2 id="integrity" class="link"><a href="#integrity">Integrity in depth</a></h2>

<p>Constraints on text fields are a very small part of a broader story in how relational databases are built to help you. In the beginning, all their pedantry around data types, foreign keys, check constraints, ACID, and insert triggers may seem unnecessarily obscure and inflexible, but in the long run these features serve as strong enforcers of data integrity. You don&rsquo;t have to wonder whether your data is valid &ndash; you know it is.</p>
]]></content>
    <published>2021-09-10T15:55:19Z</published>
    <updated>2021-09-10T15:55:19Z</updated>
    <link href="https://brandur.org/text"></link>
    <id>tag:brandur.org,2021-09-10:text</id>
    <author>
      <name>Brandur Leach</name>
      <uri>https://brandur.org</uri>
    </author>
  </entry>
  <entry>
    <title>How We Went All In on sqlc/pgx for Postgres + Go</title>
    <summary>Touring the ORM and Postgres landscape in Go, and why sqlc is today&amp;rsquo;s top pick.</summary>
    <content type="html"><![CDATA[<p>After a few months of research and experimentation with running a heavily DB-dependent Go app, we&rsquo;ve arrived at the conclusion that <a href="https://github.com/kyleconroy/sqlc">sqlc</a> is the figurative Correct Answer when it comes to using Postgres (and probably other databases too) in Go code beyond trivial uses. Let me walk you through how we got there.</p>

<p>First, let&rsquo;s take a broad tour of popular options in Go&rsquo;s ecosystem:</p>

<ul>
<li><p><code>database/sql</code>: Go&rsquo;s built-in database package. Most people agree &ndash; best to avoid it. It&rsquo;s database agnostic, which is kind of nice, but by extension that means it conforms to the lowest common denominator. No support for Postgres-specific features.</p></li>

<li><p><a href="https://github.com/lib/pq"><code>lib/pq</code></a>: An early Postgres frontrunner in the Go ecosystem. It was good for its time and place, but has fallen behind, and is no longer actively maintained.</p></li>

<li><p><a href="https://github.com/jackc/pgx"><code>pgx</code></a>: A very well-written and very thorough package for full-featured, performant connections to Postgres. However, it&rsquo;s opinionated about not offering any ORM-like features, and gets you very little beyond a basic query interface. Like with <code>database/sql</code>, hydrating database results into structs is painful &ndash; not only do you have to list target fields off ad nauseam in a <code>SELECT</code> statement, but you also have to <code>Scan</code> them into a struct manually.</p>

<ul>
<li><a href="https://github.com/georgysavva/scany"><code>scany</code></a>: Scany adds some quality-of-life improvement on top of pgx by eliminating the need to scan into every field of a struct. However, the desired field names must still be listed out in a <code>SELECT ...</code> statement, so it only reduces boilerplate by half.</li>
</ul></li>

<li><p><a href="https://github.com/go-pg/pg"><code>go-pg</code></a>: I&rsquo;ve used this on projects before, and it&rsquo;s a pretty good little Postgres-specific ORM. A little more below on why ORMs in Go aren&rsquo;t particularly satisfying, but another downside with go-pg is that it implements its own driver, and isn&rsquo;t compatible with pgx.</p>

<ul>
<li><a href="https://bun.uptrace.dev/guide/pg-migration.html#new-features">Bun</a>: go-pg has also been put in maintenance mode in favor of Bun, which is a go-pg rewrite that works with non-Postgres databases.</li>
</ul></li>

<li><p><a href="https://gorm.io/"><code>gorm</code></a>: Similar to go-pg except not Postgres specific. It can use pgx as a driver, but misses a lot of Postgres features.</p></li>
</ul>

<h2 id="strings" class="link"><a href="#strings">Queries as strings</a></h2>

<p>A big downside of vanilla <code>database/sql</code> or pgx is that SQL queries are strings:</p>

<pre><code class="language-go">var name string
var weight int64
err := conn.QueryRow(ctx, &quot;SELECT name, weight FROM widgets WHERE id = $1&quot;, 42).
	Scan(&amp;name, &amp;weight)
if err != nil {
	...
}
fmt.Println(name, weight)
</code></pre>

<p>This is fine for simple queries, but provides little in the way of confidence that queries actually work. The compiler just sees a string, so you need to write exhaustive test coverage to verify them.</p>

<p>And it gets worse. When you&rsquo;re writing a larger application that&rsquo;s trying to hydrate models, in an effort to reduce code duplication, you might start slicing and dicing those query strings &ndash; gluing little pieces together to share code. e.g.</p>

<pre><code class="language-go">err := conn.QueryRow(ctx, `SELECT ` + scanTeamFields + ` ...)
</code></pre>

<p>You can make it work, and still verify what you have is right by way of tests, but it gets messy fast.</p>

<h2 id="orms" class="link"><a href="#orms">ORMs</a></h2>

<p>ORMs like go-pg make this a little better by bringing some typing into the mix, which has some benefit for reducing mistakes:</p>

<pre><code class="language-go">story := new(Story)
err = db.Model(story).
    Relation(&quot;Author&quot;).
    Where(&quot;story.id = ?&quot;, story1.Id).
    Select()
if err != nil {
    panic(err)
}
</code></pre>

<p>However, without generics, Go&rsquo;s type system can only offer so much, and in practice, the compiler can&rsquo;t catch all that much more than when we were concatenating strings together. In the code above, <code>Model()</code> returns a <code>*Query</code> object. <code>Relation()</code> also returns a <code>*Query</code> object, and so does <code>Where()</code>. go-pq can  do some intelligent shuffling (e.g. putting a <code>LIMIT</code> before a <code>WHERE</code> wouldn&rsquo;t work in SQL, but go-pg will make it work because it&rsquo;s constructing the query lazily), but like with strings, there&rsquo;s a plethora of mistakes that will only be caught on runtime.</p>

<p>ORMs also have the problem of being an impedance mismatch compared to the raw SQL most people are used to, meaning you&rsquo;ve got the reference documentation open all day looking up how to do accomplish things when the equivalent SQL would&rsquo;ve been automatic. Easier queries are pretty straightforward, but imagine if you want to add an upsert or a <a href="https://www.postgresql.org/docs/current/queries-with.html">CTE</a>.</p>

<h2 id="sqlc" class="link"><a href="#sqlc">sqlc</a></h2>

<p>And that&rsquo;s where <a href="https://github.com/kyleconroy/sqlc">sqlc</a> comes in. With sqlc, you write <code>*.sql</code> files that contain table definitions along with queries annotated with a name and return type in a magic comment:</p>

<pre><code class="language-sql">CREATE TABLE authors (
  id   BIGSERIAL PRIMARY KEY,
  name text      NOT NULL,
  bio  text
);

-- name: CreateAuthor :one
INSERT INTO authors (
  name, bio
) VALUES (
  $1, $2
)
RETURNING *;
</code></pre>

<p>After running <code>sqlc generate</code> (which generates Go code from your SQL definitions) <sup id="footnote-1-source"><a href="#footnote-1">1</a></sup>, you&rsquo;re now able to run this:</p>

<pre><code class="language-go">author, err = dbsqlc.New(tx).CreateAuthor(ctx, dbsqlc.CreateAuthor{
    Name: &quot;Haruki Murakami&quot;,
    Bio:  &quot;Author of _Killing Commendatore_. Running and jazz enthusiast.&quot;,
    ...
})

if err != nil {
    return nil, xerrors.Errorf(&quot;error creating author: %w&quot;, err)
}

fmt.Printf(&quot;Author name: %s\n&quot;, author.Name)
</code></pre>

<p>sqlc isn&rsquo;t an ORM, but it implements one of the most useful features of one &ndash; mapping a query back into a struct without the need for boilerplate. If you have query with a <code>SELECT *</code> or <code>RETURNING *</code>, it knows which fields a table is supposed to have, and emits the result to a standard struct representing its records. All queries for a particular table that return its complete set of fields get to share the same output struct.</p>

<p>Rather than implement its own partially-complete SQL parser, sqlc uses PGAnalyze&rsquo;s <a href="https://github.com/pganalyze/pg_query_go">excellent <code>pg_query_go</code></a>, which bakes in the same query parser that Postgres really uses. It&rsquo;s never given me trouble so far &ndash; even complex queries with unusual Postgres embellishments work.</p>

<p>This query parsing also gives you some additional pre-runtime code verification. It won&rsquo;t protect you against logical bugs, but it won&rsquo;t compile invalid SQL queries, which is a far shot better than the guarantees you get with SQL-in-Go-strings. And thanks to SQL&rsquo;s declarative nature, it tends to produce fewer bugs than comparable procedural code. You&rsquo;ll still want to write tests, but you don&rsquo;t need to test every query and corner case as exhaustively.</p>

<h3 id="codegen" class="link"><a href="#codegen">Codegen</a></h3>

<p>I&rsquo;m slightly allergic to the idea of codegen on a philosophical level, and that made me reluctant to look too deeply into sqlc, but after finally getting into it, it&rsquo;s won me over.</p>

<p>Go makes programs like sqlc easily installable in one command (<code>go get github.com/kyleconroy/sqlc/cmd/sqlc</code>), and quickly with minimal fuss. Go&rsquo;s lightning fast startup and runtime speed means that your codegen loop runs in the blink of an eye. Our project is sitting around 100 queries broken up across a dozen input files and its codegen runs in (much) less than a second on commodity hardware:</p>

<pre><code class="language-go">$ time sqlc generate

real    0.07s
user    0.08s
sys     0.01s
</code></pre>

<p>Even if we expand our number of queries by 100x to 10,000, I think we&rsquo;ll still be comfortable with the timing on that development loop.</p>

<p>A GitHub Action verifies generated output, and between checkout, pulling down an sqlc binary, and running it, the whole job takes a grand total of 4 seconds to run.</p>

<h3 id="pgx" class="link"><a href="#pgx">pgx support appears</a></h3>

<p>Previously, a major reason not to use sqlc is that it didn&rsquo;t support pgx, which we were already bought into pretty deeply. A recent <a href="https://github.com/kyleconroy/sqlc/pull/1037">pull request</a> has addressed this problem by giving sqlc support for multiple drivers, and the feature&rsquo;s now available in the sqlc&rsquo;s latest release.</p>

<p>The authors also managed to write it in such a way that it&rsquo;s coupled very loosely &ndash; our mature codebase was making heavy use of pgx already and had a number of custom abstractions built on top of it, and yet I was able to get sqlc slotted in alongside them and fully operational in less than an hour. We could even weave sqlc invocations in amongst raw pgx invocations as part of the same transaction, giving us an easy way to migrate over to it incrementally.</p>

<h3 id="caveats" class="link"><a href="#caveats">Caveats and workarounds</a></h3>

<p>A few things in sqlc are less convenient compared to a more traditional ORM, but there are workarounds that land pretty well. For example, a noticeable one is that sqlc queries can&rsquo;t take an arbitrary number of parameters, so doing a multi-row insert doesn&rsquo;t work as easily as you&rsquo;d expect it to. However, you can get around this by sending batches as arrays which are unnested into distinct tuples in the SQL:</p>

<pre><code class="language-sql">-- Upsert many marketplaces, inserting or replacing data as necessary.
INSERT INTO marketplace (
    name,
    display_name
)
SELECT unnest(@names::text[]) AS name,
    unnest(@display_names::text[]) AS display_names
ON CONFLICT (name)
    DO UPDATE SET display_name = EXCLUDED.display_name
RETURNING *;
</code></pre>

<p>Another one is <code>UPDATE</code> where with a normal ORM you&rsquo;d just add as many target fields and values (i.e. <code>UPDATE foo SET a = 1, b = 2, c = 3, ...</code>) through the query builder as you wanted. Queries in sqlc must be fully structured in advance, so this doesn&rsquo;t work. What you can do is something like this where each field is conditionally updated based on the presence of an associated boolean:</p>

<pre><code class="language-sql">-- Update a team.
-- name: TeamUpdate :one
UPDATE team
SET
    customer_id = CASE WHEN @customer_id_do_update::boolean
        THEN @customer_id::VARCHAR(200) ELSE customer_id END,

    has_payment_method = CASE WHEN @has_payment_method_do_update::boolean
        THEN @has_payment_method::bool ELSE has_payment_method END,

    name = CASE WHEN @name_do_update::boolean
        THEN @name::text ELSE name END
WHERE
    id = @id
RETURNING *;
</code></pre>

<p>The Go code to update a field ends up looking like this:</p>

<pre><code class="language-go">team, err = queries.TeamUpdate(ctx, dbsqlc.TeamUpdateParams{
    NameDoUpdate: true,
    Name:         req.Name,
})
</code></pre>

<p>sqlc doesn&rsquo;t have any built-in conventions around how queries are named or organized, so you&rsquo;ll want to make sure to come up with your own so that you can find things.</p>

<h2 id="summary" class="link"><a href="#summary">Summary and future</a></h2>

<p>I&rsquo;ve largely covered sqlc&rsquo;s objective benefits and features, but more subjectively, it just <em>feels</em> good and fast to work with. Like Go itself, the tool&rsquo;s working for you instead of against you, and giving you an easy way to get work done without wrestling with the computer all day.</p>

<p>I won&rsquo;t go as far as to say that its the best answer across all ecosystems &ndash; the feats that Rust&rsquo;s SQL drivers can achieve with its type system are borderline wizardry &ndash; but sqlc&rsquo;s far and away my preferred solution when working in Go.</p>

<p>Lastly, generics are coming to Go, possibly <a href="https://go.dev/blog/generics-proposal">in beta form by the end of the year</a>, and that could change the landscape. I could imagine a world where they power a new generation of Go ORMs that can do better query checking and give you even better type completion. However, it&rsquo;s safe to say that&rsquo;s a good year or two out. Until then, we&rsquo;re happy with sqlc.</p>


]]></content>
    <published>2021-09-08T16:49:02Z</published>
    <updated>2021-09-08T16:49:02Z</updated>
    <link href="https://brandur.org/sqlc"></link>
    <id>tag:brandur.org,2021-09-08:sqlc</id>
    <author>
      <name>Brandur Leach</name>
      <uri>https://brandur.org</uri>
    </author>
  </entry>
  <entry>
    <title>Feature Casualties of Large Databases</title>
    <summary>Databases shed important RDMS features as they get big. Examining why this tends to be the case, and some ideas for preventing it.</summary>
    <content type="html"><![CDATA[<p>Big data has an unfortunate tendency to get messy. A few years in, a growing database that use to be small, lean, and well-designed, has better odds than not of becoming something large, bloated, and with best practices tossed aside and now considered unsalvageable.</p>

<p>There&rsquo;s a few common reasons that this happens, some better than others:</p>

<ul>
<li><strong>Technological limitation:</strong> The underlying tech doesn&rsquo;t support the scale. Say transactions or referential integrity across partitions in a sharded system.</li>
<li><strong>Stability:</strong> Certain operations come to be considered too risky. e.g. Batch update operations that have unpredictable performance properties.</li>
<li><strong>Cost/effort:</strong> Doing things the right way is too hard or too expensive. e.g. Back-migrating a large amount of existing data.</li>
<li><strong>Convenience:</strong> Similar to the previous point, poor data practice is simply by far the easiest thing to do, and gets your immediate project shipped more quickly, even if it makes future projects more difficult.</li>
</ul>

<p>The loss of these features is unfortunate because they&rsquo;re the major reason we&rsquo;re using sophisticated databases in the first place. In the <a href="https://eng.uber.com/schemaless-part-one-mysql-datastore/">most extreme cases</a>, advanced databases end up as nothing more than glorified key/value stores, and the applications they power lose important foundations for reliability and correctness.</p>

<h2 id="casualties" class="link"><a href="#casualties">The casualties of large applications/data</a></h2>

<h3 id="transactions" class="link"><a href="#transactions">Transactions</a></h3>

<p>ACID transactions tend to be one of the first things to go, especially since the value they provide isn&rsquo;t immediately obvious in a new system that&rsquo;s not yet seeing a lot of traffic or trouble. Between that and the facts that they add some friction in writing code quickly, and can lead to locking problems in production mean that they&rsquo;re often put in the chopping block early, especially when less experienced engineers are involved.</p>

<p>Losing transactions is bad news for an applications future operability, but as this subject&rsquo;s already covered extensively elsewhere (<a href="/acid">including by me</a>), I won&rsquo;t go into depth here.</p>

<h3 id="referential-integrity" class="link"><a href="#referential-integrity">Referential integrity</a></h3>

<p>Referential integrity guarantees that if a key exists somewhere in a database, then the object its referencing does as well. Foreign keys allow developers to control deletions such that if an object is being removed, but is still referenced, than that deletion should be blocked (<code>ON DELETE RESTRICT</code>), or, that referencing objects should be removed with it (<code>ON DELETE CASCADE</code>).</p>

<p>It&rsquo;s a powerful tool for correctness &ndash; having the database enforcing certain rules makes programs easier to write and easier to get right. <em>Not</em> having it tends to bleed out into code. Suddenly anytime a referenced object is loaded <em>anywhere</em>, the case that it came up without a result must be handled:</p>

<pre><code class="language-ruby">user = User.load(api_key.user_id)
if !user
  raise ObjectNotFound, &quot;couldn't find user!&quot;
end
</code></pre>

<p>Sacrificing referential integrity is rationalized away in a number of ways. Sometimes it&rsquo;s due to technological limitation, sometimes due to reliability concerns (a benign-looking delete triggering an unexpectedly large cascade), but more often it&rsquo;s for the simple-and-not-good reason that maintaining good hygiene around foreign key relations takes discipline and work.</p>

<h3 id="nullable" class="link"><a href="#nullable">Nullable, as far as the eye can see</a></h3>

<p>Relations in large databases tend to have a disproportionate number of nullable fields. This is a problem because in application code it&rsquo;s more difficult to work with objects that have a poorly defined schema. Every nullable field needs to be examined independently, and a fallback designed for it in case it didn&rsquo;t have a value. This takes time and introduces new avenues for bugs.</p>

<p>There&rsquo;s a few reasons that nullable-by-default is so common. The simplest is simply that nullable columns are literally the default in DDL &ndash; you&rsquo;ll get one unless you&rsquo;re really thinking about what you&rsquo;re doing and explicitly use <code>NOT NULL</code>.</p>

<p>A more common reason is that non-nullable columns often require that existing data be migrated, which is difficult, time consuming, and maybe even operationally fraught on nodes which are running very hot and which a migration unexpectedly pushes over the edge.</p>

<p>Lastly, there are often technological limitations as well. In Postgres for example, even after running a migration, taking that last step of changing a nullable column to non-nullable (<code>SET NOT NULL</code>) isn&rsquo;t safe. Postgres needs to verify that there are no nulls in the table, requiring a full table scan that blocks other operations. On a small table that&rsquo;ll run in an instant. On a large one, it could be the downfall of production <sup id="footnote-1-source"><a href="#footnote-1">1</a></sup>.</p>

<h3 id="indexing" class="link"><a href="#indexing">Suboptimal indexing</a></h3>

<p>Indexes are the easiest thing in the world to work with until they&rsquo;re not. In a large system, they might get complicated because:</p>

<ul>
<li>They need to be built on multiple clusters instead of just one.</li>
<li>Building them on very hot nodes gets risky as the build interferes with production operations. Internal teams may need to build tools to throttle or pause builds.</li>
<li>Data gets so large that building them takes a long time.</li>
<li>Data gets so large that each index is a significant non-trivial cost to store.</li>
</ul>

<p>Reduced performance is the most obvious outcome, but expensive index operations can have less obvious ones too. I worked on a project recently where product design was being driven by whether options would necessitate raising a new index on a particularly enormous collection which would take weeks and cost a large figure every year in storage costs alone.</p>

<h3 id="restricted-apis" class="link"><a href="#restricted-apis">Dangerous queries and restricted APIs</a></h3>

<p>SQL is the most expressive language ever for querying and manipulating data, and in the right hands, that power can make hard things easy.</p>

<p>However, the more complex the SQL statement, the more likely it is to impact production through problems like unpredictable performance or unanticipated locking. A common solution is for storage teams to simply ban non-trivial SQL wholesale, and constrain developers to a vastly simplified API &ndash; e.g. single row select, multi row select with index hint, single row update, single row delete.</p>

<pre><code class="language-ruby"># a simplified storage API
def insert(data:); end
def delete_one(id:); end
def load_many(predicate:, index:, limit:); end
def load_one(id:); end
def update_one(id:, data:); end
</code></pre>

<p>At a previous job, our MySQL DBA banned any database update that affected more than one row, even where it would be vastly beneficial to performance, due to concerns around them delaying replication to secondaries. This might have helped production, but had the predictable effect of reduced productivity along with some truly heinous workarounds for things that should have been trivial, and which instead resulted in considerable tech debt.</p>

<p>Where I work now, even with the comparative unexpressiveness of Mongo compared to SQL, every select in the system must be named and statically defined along with an index it expects to use. This is so that we can verify at build time that the appropriate index is already available in production.</p>

<h2 id="scalability-ideas" class="link"><a href="#scalability-ideas">Ideas for scalability</a></h2>

<p>There&rsquo;s a divide between the engineers who run big production systems and the developers who work on open-source projects in the data space, with neither group having all that much visibility into the other. Engineers who run big databases tend to adopt a nihilist outlook that every large installation inevitably trends towards a key/value store &ndash; at a certain point, the niceties available to smaller databases must get the axe. Open-source developers don&rsquo;t tend to value highly the features that would help big installations.</p>

<p>I don&rsquo;t think the nihilist viewpoint should be the inevitable outcome, and there&rsquo;s cause for optimism in the development of systems like Citus, Spanner, and CockroachDB, which enable previously difficult features like cross shard transactions. We need even more movement in that direction.</p>

<p>There&rsquo;s a variety of possible operations-friendly features that might be possible to counteract the entropic dumbing down of large databases. Some ideas:</p>

<ul>
<li>Make index builds pauseable so that they can be easily throttled in emergencies.</li>
<li>Make it easy to make a nullable field non-nullable, <em>not</em> requiring a problematic and immediate full table scan.</li>
<li>A &ldquo;strict&rdquo; SQL dialect that makes specifying fields as <code>NOT NULL</code> default, and specifying foreign keys required.</li>
<li>A communication protocol that allows the query to signal out-of-band with a query&rsquo;s results that it didn&rsquo;t run particularly efficiently, say that it got results but wasn&rsquo;t able to make use of an index. This would allow a test suite to fail early by signaling the problem to a developer instead of finding out about it in production.</li>
<li>A migrations framework built into the database itself that makes migrations easier and faster to write while also guaranteeing stability by allowing long-lived migration-related queries to be deprioritized and paused if necessary.</li>
</ul>

<p>Ideally, we get to a place where large databases enjoy all the same benefits as smaller ones, and we all get to reap the benefits of software that gets more stable and more reliable as a result.</p>


]]></content>
    <published>2020-12-01T20:06:51Z</published>
    <updated>2020-12-01T20:06:51Z</updated>
    <link href="https://brandur.org/large-database-casualties"></link>
    <id>tag:brandur.org,2020-12-01:large-database-casualties</id>
    <author>
      <name>Brandur Leach</name>
      <uri>https://brandur.org</uri>
    </author>
  </entry>
  <entry>
    <title>Doubling the Sorting Speed of Postgres Network Types with Abbreviated Keys</title>
    <summary>Making the sorting speed of network types in Postgres twice as fast by designing SortSupport abbreviated keys compatible with their existing sort semantics.</summary>
    <content type="html"><![CDATA[<p>A few months ago, I wrote about <a href="/sortsupport">how SortSupport works in
Postgres</a> to vastly speed up sorting on
large data types <sup id="footnote-1-source"><a href="#footnote-1">1</a></sup> like <code>numeric</code> or <code>text</code>, and
<code>varchar</code>. It works by generating <strong>abbreviated keys</strong> for
values that are representative of them for purposes of
sorting, but which fit nicely into the pointer-sized value
(called a &ldquo;<strong>datum</strong>&rdquo;) in memory that Postgres uses for
sorting. Most values can be sorted just based on their
abbreviated key, saving trips to the heap and increasing
sorting throughput. Faster sorting leads to speedup on
common operations like <code>DISTINCT</code>, <code>ORDER BY</code>, and <code>CREATE
INDEX</code>.</p>

<p>A <a href="https://www.postgresql.org/message-id/CABR_9B-PQ8o2MZNJ88wo6r-NxW2EFG70M96Wmcgf99G6HUQ3sw%40mail.gmail.com">patch</a> of mine was recently committed to add
SortSupport for the <code>inet</code> and <code>cidr</code> types, which by my
measurement, a little more than doubles sorting speed on
them. <code>inet</code> and <code>cidr</code> are the types used to store network
addresses or individual hosts and in either IPv4 or IPv6
(they generally look something like <code>1.2.3.0/24</code> or
<code>1.2.3.4</code>).</p>

<p><code>inet</code> and <code>cidr</code> have some important subtleties in how
they&rsquo;re sorted which made designing an abbreviated key that
would be faithful to those subtleties but still efficient,
a non-trivial problem. Because their size is limited,
abbreviated keys are allowed to show equality even for
values that aren&rsquo;t equal (Postgres will fall back to
authoritative comparison to confirm equality or tiebreak),
but they should never falsely indicate inequality.</p>

<h2 id="inet-cidr" class="link"><a href="#inet-cidr">Network type anatomy, and inet vs. cidr</a></h2>

<p>A property that&rsquo;s not necessarily obvious to anyone
unfamiliar with them is that network types (<code>inet</code> or
<code>cidr</code>) can either address a single host (what most people
are used to seeing) or an entire subnetwork of arbitrary
size. For example:</p>

<ul>
<li><p><code>1.2.3.4/32</code> specifies a 32-bit netmask on an IPv4 value,
which is 32 bits wide, which means that it defines
exactly one address: <code>1.2.3.4</code>. <code>/128</code> would work
similarly for IPv6.</p></li>

<li><p><code>1.2.3.0/24</code> specifies a 24-bit netmask. It identifies
the network at <code>1.2.3.*</code>. The last byte may be anywhere
in the range of 0 to 255.</p></li>

<li><p>Similarly, <code>1.0.0.0/8</code> specifies an 8-bit netmask. It
identifies the much larger possible network at <code>1.*</code>.</p></li>
</ul>

<p>We&rsquo;ll establish the following common vocabulary for each
component of an address (and take for example the value
<code>1.2.3.4/24</code>):</p>

<ol>
<li>A <strong>network</strong>, or bits in the netmask (<code>1.2.3.</code>).</li>
<li>A <strong>netmask size</strong> (<code>/24</code> which is 24 bits). Dictates
the number of bits in the network.</li>
<li>A <strong>subnet</strong>, or bits outside of the netmask (<code>.4</code>).
Only <code>inet</code> carries non-zero bits here, and combined
with the network, they identify a single <strong>host</strong>
(<code>1.2.3.4</code>).</li>
</ol>

<p>The netmask size is a little more complex than commonly
understood because while it&rsquo;s most common to see byte-sized
blocks like <code>/8</code>, <code>/16</code>, <code>/24</code>, and <code>/32</code>, it&rsquo;s allowed to
be any number between 0 and 32. It&rsquo;s easy to mentally
extract a byte-sized network out of a value (like <code>1.2.3.</code>
out of <code>1.2.3.4/24</code>) because you can just stop at the
appropriate byte boundary, but when it&rsquo;s not a nice byte
multiple you have to think at the binary level. For
example, if I have the value <code>255.255.255.255/1</code>, the
network is just the leftmost bit. 255 in binary is <code>1111
1111</code>, so the network is the bit <code>1</code> and the subnet is 31
consecutive <code>1</code>s.</p>

<figure>
    <img alt="The anatomy of inet and cidr values." class="overflowing" loading="lazy" src="/assets/images/sortsupport-inet/inet-cidr-anatomy.svg">
    <figcaption>The anatomy of inet and cidr values.</figcaption>
</figure>

<p>The difference between <code>inet</code> and <code>cidr</code> is that <code>inet</code>
allows a values outside of the netmasked bits. The value
<code>1.2.3.4/24</code> is possible in <code>inet</code>, but illegal in <code>cidr</code>
because only zeroes may appear after the network like
<code>1.2.3.0/24</code>. They&rsquo;re nearly identical, with the latter
being more strict.</p>

<p>In the Postgres source code, <code>inet</code> and <code>cidr</code> are
represented by the same C struct. Here it is in
<a href="https://github.com/postgres/postgres/blob/12afc7145c03c212f26fea3a99e016da6a1c919c/src/include/utils/inet.h:23"><code>inet.h</code></a>:</p>

<pre><code class="language-c">/*
 * This is the internal storage format for IP addresses
 * (both INET and CIDR datatypes):
 */
typedef struct
{
    unsigned char family;      /* PGSQL_AF_INET or PGSQL_AF_INET6 */
    unsigned char bits;        /* number of bits in netmask */
    unsigned char ipaddr[16];  /* up to 128 bits of address */
} inet_struct;
</code></pre>

<h2 id="sorting-rules" class="link"><a href="#sorting-rules">Sorting rules</a></h2>

<p>In Postgres, <code>inet</code>/<code>cidr</code> sort according to these rules:</p>

<ol>
<li>IPv4 always appears before IPv6.</li>
<li>The bits in the network are compared (<code>1.2.3.</code>).</li>
<li>Netmask size is compared (<code>/24</code>).</li>
<li>All bits are compared. Having made it here, we know that
the network bits are equal, so we&rsquo;re in effect just
comparing the subnet (<code>.4</code>).</li>
</ol>

<p>These rules combined with the fact that we&rsquo;re working at
the bit level produces ordering that in cases may not be
intuitive. For example, <code>192.0.0.0/1</code> sorts <em>before</em>
<code>128.0.0.0/2</code> despite 192 being the larger number &ndash; when
comparing them, we start by looking at the common bits
available in both networks, which comes out to just one bit
(<code>min(/1, /2)</code>). That bit is the same in the networks of
both values (remember, 192 = <code>1100 0000</code> and 128 = <code>1000
0000</code>), so we fall through to comparing netmask size. <code>/2</code>
is the larger of the two, so <code>128.0.0.0/2</code> is the larger
value.</p>

<h2 id="designing-keys" class="link"><a href="#designing-keys">Designing an abbreviated key</a></h2>

<p>Armed with the structure of <code>inet</code>/<code>cidr</code> and how their
sorting works, we can now design an abbreviated key for
them. Remember that abbreviated keys need to fit into the
pointer-sized Postgres datum &ndash; either 32 or 64 bits
depending on target architecture. The goal is to pack in as
much sorting-relevant information as possible while staying
true to existing semantics.</p>

<p>We&rsquo;ll be breaking the available datum into multiple parts,
with information that we need for higher precedence sorting
rules occupying more significant bits so that it compares
first. This allows us to compare any two keys as integers
&ndash; a very fast operation for CPUs (faster even than
comparing memory byte-by-byte), and also a common technique
in other abbreviated key implementations like the one for
<a href="/sortsupport#uuid">UUIDs</a>.</p>

<h3 id="family" class="link"><a href="#family">1 bit for family</a></h3>

<p>The first part is easy: all IPv4 values always appear
before all IPv6 values. Since there&rsquo;s only two IP families,
so we&rsquo;ll reserve the most significant bit of our key to
represent a value&rsquo;s family. 0 for IPv4 and 1 for IPv6.</p>

<figure>
    <img alt="One bit reserved for IP family." class="overflowing" loading="lazy" src="/assets/images/sortsupport-inet/ip-family.svg">
    <figcaption>One bit reserved for IP family.</figcaption>
</figure>

<p>It might seem short-sighted that we&rsquo;re assuming that only
two IP families will ever exist, but luckily abbreviated
keys are not persisted to disk (only in the memory of a
running Postgres system) and their format is therefore
non-binding. If a new IP family were to ever appear, we
could allocate another bit to account for it.</p>

<h3 id="network" class="link"><a href="#network">As many network bits as we can pack in</a></h3>

<p>The next comparison that needs to be done is against a
value&rsquo;s network bits, so we should include those in the
datum.</p>

<p>The less obvious insight is that we can <em>only</em> include
network bits in this part. Think back to our example of
<code>192.0.0.0/1</code> and <code>128.0.0.0/2</code>: if we included 192&rsquo;s full
bits of <code>1100 0000</code>, then when comparing it to 128&rsquo;s <code>1000
0000</code>, it would sort higher when it needs to come out
lower. In order to guarantee our keys will comply with the
rules, we have to truncate values to just what appears in
the network.</p>

<p>Both <code>192.0.0.0/1</code> and <code>128.0.0.0/2</code> would appear as <code>1000
0000</code> (two of 128&rsquo;s bits were extracted, but it has a 0 in
the second position) and would appear equal when
considering this part of the abbreviated key. In cases
where that&rsquo;s all the space in the key we have to work with,
Postgres will have to fall back to authoritative comparison
(which would be able to move on and compare netmask size)
to break the tie.</p>

<p>The network bits are where we need to stop for most of our
use cases because that&rsquo;s all the space in the datum there
is. An IPv6 value is 128 bits &ndash; after reserving 1 bit in
the datum for family, we have 31 bits left on a 32-bit
machine and 63 bits on a 64-bit machine, which will be
filled entirely with network. An IPv4 value is only 32
bits, but that&rsquo;s still more space than we have left on a
32-bit machine, so again, we&rsquo;ll pack in 31 of them.</p>

<figure>
    <img alt="Number of bits available to store network per datum size and IP family." class="overflowing" loading="lazy" src="/assets/images/sortsupport-inet/network-bits.svg">
    <figcaption>Number of bits available to store network per datum size and IP family.</figcaption>
</figure>

<p>But there is one case where we have some space left over:
IPv4 on a 64-bit machine. Even after storing all 32
possible bits of network, there&rsquo;s still 31 bits available.
Let&rsquo;s see what we can use them for.</p>

<h3 id="ipv4-64bit" class="link"><a href="#ipv4-64bit">IPv4 on 64-bit: network size and a few subnet bits</a></h3>

<p>As datums are being compared for IPv4 on a 64-bit machine,
we can be sure that having looked at the 33 bits that
we&rsquo;ve designed so far &ndash; IP family (1 bit) and
network (32 bits) &ndash; are equal. That leaves us with 31
bits (64 - 33) left to work with, and lets us move onto
the next comparison rule &ndash; netmask size. The largest
possible netmask size for an IPv4 address is 32, which
conveniently fits into only 6 bits (<code>32 = 10 0000</code>) <sup id="footnote-2-source"><a href="#footnote-2">2</a></sup>.</p>

<p>After adding netmask size to the datum we&rsquo;re left with 25
bits (31 - 6), which we can use for the next sorting rule
&ndash; subnet. Subnets can be as large as 32 bits for a <code>/0</code>
value, so we&rsquo;ll have to shift any that are too large to fit
down to the size available. That will only ever happen for
netmask sizes of <code>/6</code> or smaller &ndash; for all commonly seen
netmask sizes like <code>/8</code>, <code>/16</code>, or <code>/24</code> we can fit the
entirety of the subnet into the datum.</p>

<p>With subnet covered, we&rsquo;ve used up all the available key
bits, but also managed to cover every sorting rule &ndash; with
most <sup id="footnote-3-source"><a href="#footnote-3">3</a></sup> real-world data, Postgres should be able to sort
almost entirely with abbreviated keys without falling back
to authoritative comparison. The final key design looks
like this:</p>

<figure>
    <img alt="The design of abbreviated keys for inet and cidr." class="overflowing" loading="lazy" src="/assets/images/sortsupport-inet/key-design.svg">
    <figcaption>The design of abbreviated keys for inet and cidr.</figcaption>
</figure>

<h2 id="gymnastics" class="link"><a href="#gymnastics">Bit gymnastics in C</a></h2>

<p>Now that we have an encoding scheme for each different
case, we can build an implementation that puts everything
into place. This involves the use of many bitwise
operations that are common in C, but which many of us who
program in high-level languages day-to-day aren&rsquo;t as used
to.</p>

<p>I&rsquo;ll go through this implementation step-by-step, but you
may prefer to refer to the completed version in the
<a href="https://github.com/postgres/postgres/blob/12afc7145c03c212f26fea3a99e016da6a1c919c/src/backend/utils/adt/network.c#L561">Postgres source</a>, which we&rsquo;ve made an effort to
comment comprehensively.</p>

<h3 id="integer" class="link"><a href="#integer">Ingesting bytes as an integer</a></h3>

<p>Recall that an IP component is stored as a 16-byte
<code>unsigned char</code> array in the backing network type:</p>

<pre><code class="language-c">typedef struct
{
    ...
    unsigned char ipaddr[16];  /* up to 128 bits of address */
} inet_struct;
</code></pre>

<p>Our abbreviated keys will be compared as if they were
integers (one of the reasons that they&rsquo;re so fast), so the
first step is to extract a datum&rsquo;s worth of bytes from
<code>ipaddr</code> into an intermediate representation that&rsquo;ll be
used to more easily separate out the final components.
We&rsquo;ll use <code>memcpy</code> to copy it out byte-by-byte:</p>

<pre><code class="language-c">Datum ipaddr_datum;
memcpy(&amp;ipaddr_datum, ip_addr(authoritative), sizeof(Datum));
</code></pre>

<p><code>ipaddr</code> is laid out most significant byte first, which
will be fine when representing an integer on a big-endian
machine, but no good on one that&rsquo;s little-endian (like most
of our Intel processors), so do a byte-wise position swap
to re-form it (more detail on this talking about <a href="/sortsupport#uuid"><code>uuid</code>&rsquo;s
abbreviated key implementation</a>:</p>

<pre><code class="language-c">/* Must byteswap on little-endian machines */
ipaddr_datum = DatumBigEndianToNative(ipaddr_datum);
</code></pre>

<p>And for IPv6, make sure to shift a 1 bit into the leftmost
position so that it sorts after all IPv4 values:</p>

<pre><code>Datum res;
res = ((Datum) 1) &lt;&lt; (SIZEOF_DATUM * BITS_PER_BYTE - 1);
</code></pre>

<h3 id="network-bitmask" class="link"><a href="#network-bitmask">Extracting network via bitmask</a></h3>

<p>Next we&rsquo;ll extract the leading <strong>network</strong> component using a
technique called bitmasking. This common technique involves
using a bitwise-AND to extract a desired range of bits:</p>

<pre><code>  1010 1010 1010 1010       (original value)
&amp; 0000 1111 1111 0000       (bitmask)
  -------------------
  0000 1010 1010 0000       (final result)
</code></pre>

<p>We&rsquo;re going to create a bitmask for the <strong>subnet</strong> portion
of the value (reminder: that&rsquo;s the last part <em>after</em> the
network), and it&rsquo;s size depends on how many subnet bits we
expect to see in <code>ipaddr_datum</code>. For example, if the
network component occupies bits equal or greater to the
datum&rsquo;s size, then the subnet bitmask will be zero.</p>

<p>The code&rsquo;s broken into three separate conditionals. This
first section handles the case of no bits in the network
components. The subnet bitmask should be all ones, which we
get by starting with 0, subtracting 1, and allowing the
value to roll over to its maximum value:</p>

<pre><code class="language-c">Datum subnet_bitmask,
      network;

subnet_size = ip_maxbits(authoritative) - ip_bits(authoritative);
Assert(subnet_size &gt;= 0);

if (ip_bits(authoritative) == 0)
{
    /* Fit as many ipaddr bits as possible into subnet */
    subnet_bitmask = ((Datum) 0) - 1;
    network = 0;
}
</code></pre>

<p>The next section is the case where there are some bits for
both the network and subnet. We use a trick to get the
bitmask which involves shifting a 1 left out by the subnet
size, then subtracting one to get 1s in all positions that
were right of it:</p>

<pre><code>  0000 0001 0000 0000       (1 &lt;&lt; 8)
-                   1       (minus one)
  -------------------
  0000 0000 1111 1111       (8-bit mask)
</code></pre>

<p>Getting the network&rsquo;s value then involves ANDing the IP&rsquo;s
datum and the <em>negated</em> form of the subnet bitmask
(<code>ipaddr_datum &amp; ~subnet_bitmask</code>):</p>

<pre><code class="language-c">else if (ip_bits(authoritative) &lt; SIZEOF_DATUM * BITS_PER_BYTE)
{
    /* Split ipaddr bits between network and subnet */
    subnet_bitmask = (((Datum) 1) &lt;&lt; subnet_size) - 1;
    network = ipaddr_datum &amp; ~subnet_bitmask;
}
</code></pre>

<p>The final case represents no bits in the subnet. Set
<code>network</code> to the full value of <code>ipaddr_datum</code>:</p>

<pre><code class="language-c">else
{
    /* Fit as many ipaddr bits as possible into network */
    subnet_bitmask = 0;        /* Unused, but be tidy */
    network = ipaddr_datum;
}
</code></pre>

<h3 id="shifting" class="link"><a href="#shifting">Shifting things into place for IPv4 on 64-bit</a></h3>

<p>Recall that IPv4 on a 64-bit architecture is by far the
most complex case because we have room to fit a lot more
information. This next section involves taking the network
and subnet bitmask that we resolved above and shifting it
all into place.</p>

<p>The order of operations is:</p>

<ol>
<li><code>network</code>: Shift the network left 31 bits to make room
for netmask size and 25 bits worth of subnet.</li>
<li><code>network_size</code>: Shift the network size left 25 bits to
make room for the subnet.</li>
<li><code>subnet</code>: Extract a subnet using the bitmask calculated
above.</li>
<li><code>subnet</code>: If the subnet is longer than 25 bits, shift it
down to just occupy 25 bits.</li>
<li><code>res</code>: Get a final result by ORing the values from (1),
(2), and (4) above.</li>
</ol>

<pre><code class="language-c">#if SIZEOF_DATUM == 8
    if (ip_family(authoritative) == PGSQL_AF_INET)
    {
        /*
         * IPv4 with 8 byte datums: keep all 32 netmasked bits, netmask size,
         * and most significant 25 subnet bits
         */
        Datum        netmask_size = (Datum) ip_bits(authoritative);
        Datum        subnet;

        /* Shift left 31 bits: 6 bits netmask size + 25 subnet bits */
        network &lt;&lt;= (ABBREV_BITS_INET4_NETMASK_SIZE +
                     ABBREV_BITS_INET4_SUBNET);

        /* Shift size to make room for subnet bits at the end */
        netmask_size &lt;&lt;= ABBREV_BITS_INET4_SUBNET;

        /* Extract subnet bits without shifting them */
        subnet = ipaddr_datum &amp; subnet_bitmask;

        /*
         * If we have more than 25 subnet bits, we can't fit everything. Shift
         * subnet down to avoid clobbering bits that are only supposed to be
         * used for netmask_size.
         *
         * Discarding the least significant subnet bits like this is correct
         * because abbreviated comparisons that are resolved at the subnet
         * level must have had equal subnet sizes in order to get that far.
         */
        if (subnet_size &gt; ABBREV_BITS_INET4_SUBNET)
            subnet &gt;&gt;= subnet_size - ABBREV_BITS_INET4_SUBNET;

        /*
         * Assemble the final abbreviated key without clobbering the ipfamily
         * bit that must remain a zero.
         */
        res |= network | netmask_size | subnet;
    }
    else
#endif
</code></pre>

<h3 id="everything-else" class="link"><a href="#everything-else">Everything else</a></h3>

<p>The three other cases (refer to the figure above) are much
simpler because we only have room for network bits. Shift
them right by 1 bit to not clobber our previously set IP
family, then OR with <code>res</code> for the final result:</p>

<pre><code class="language-c">#endif
    {
        /*
         * 4 byte datums, or IPv6 with 8 byte datums: Use as many of the
         * netmasked bits as will fit in final abbreviated key. Avoid
         * clobbering the ipfamily bit that was set earlier.
         */
        res |= network &gt;&gt; 1;
    }
</code></pre>

<h2 id="speed-vs-sustainability" class="link"><a href="#speed-vs-sustainability">Speed vs. sustainability</a></h2>

<p>The abbreviated key implementation here is complex enough
that in most contexts I&rsquo;d probably consider it a poor trade
off &ndash; added speed is nice to have, but there is a cost in
the ongoing maintenance burden of the new code and its
understandability by future contributors.</p>

<p>However, Postgres is a highly leveraged piece of software.
This patch makes sorting and creating indexes on network
types <em>~twice as fast</em>, and that improvement will trickle
down automatically to hundreds of thousands of Postgres
installations around the world as they&rsquo;re upgraded to the
next major version. If there&rsquo;s one place where trading some
more complexity for speed is worth it, it&rsquo;s cases like this
one where only very few have to understand the code, but
very many will reap its benefits. We&rsquo;ve also made sure to
add extensive comments and test cases to keep future code
changes as easy as they can be.</p>

<p>Thanks to Peter Geoghegan for seeding the idea for this
patch, as well as for advice and very thorough
testing/review, and Edmund Horner for review.</p>


]]></content>
    <published>2019-08-07T16:50:44Z</published>
    <updated>2019-08-07T16:50:44Z</updated>
    <link href="https://brandur.org/sortsupport-inet"></link>
    <id>tag:brandur.org,2019-08-07:sortsupport-inet</id>
    <author>
      <name>Brandur Leach</name>
      <uri>https://brandur.org</uri>
    </author>
  </entry>
  <entry>
    <title>SortSupport: Sorting in Postgres at Speed</title>
    <summary>How Postgres makes sorting really fast by comparing small, memory-friendly abbreviated keys as proxies for arbitrarily large values on the heap.</summary>
    <content type="html"><![CDATA[<p>Most often, there&rsquo;s a trade off involved in optimizing
software. The cost of better performance is the opportunity
cost of the time that it took to write the optimization,
and the additional cost of maintenance for code that
becomes more complex and more difficult to understand.</p>

<p>Many projects prioritize product development over improving
runtime speed. Time is spent building new things instead of
making existing things faster. Code is kept simpler and
easier to understand so that adding new features and fixing
bugs stays easy, even as particular people rotate in and
out and institutional knowledge is lost.</p>

<p>But that&rsquo;s certainly not the case in all domains. Game code
is often an interesting read because it comes from an
industry where speed is a competitive advantage, and it&rsquo;s
common practice to optimize liberally even at some cost to
modularity and maintainability. One technique for that is
to inline code in critical sections even to the point of
absurdity. CryEngine, open-sourced a few years ago, has a
few examples of this, with <a href="https://github.com/CRYTEK/CRYENGINE/blob/release/Code/CryEngine/CryPhysics/livingentity.cpp#L1275">&ldquo;tick&rdquo; functions like this
one</a> that are 800+ lines long with 14 levels of
indentation.</p>

<p>Another common place to find optimizations is in databases.
While games optimize because they have to, databases
optimize because they&rsquo;re an example of software that&rsquo;s
extremely leveraged &ndash; if there&rsquo;s a way to make running
select queries or building indexes 10% faster, it&rsquo;s not an
improvement that affects just a couple users, it&rsquo;s one
that&rsquo;ll potentially invigorate millions of installations
around the world. That&rsquo;s enough of an advantage that the
enhancement is very often worth it, even if the price is a
challenging implementation or some additional code
complexity.</p>

<p>Postgres contains a wide breadth of optimizations, and
happily they&rsquo;ve been written conscientiously so that the
source code stays readable. The one that we&rsquo;ll look at
today is <strong>SortSupport</strong>, a technique for localizing the
information needed to compare data into places where it can
be accessed very quickly, thereby making sorting data much
faster. Sorting for types that have had Sortsupport
implemented usually gets twice as fast or more, a speedup
that transfers directly into common database operations
like <code>ORDER BY</code>, <code>DISTINCT</code>, and <code>CREATE INDEX</code>.</p>

<h2 id="abbreviated-keys" class="link"><a href="#abbreviated-keys">Sorting with abbreviated keys</a></h2>

<p>While sorting, Postgres builds a series of tiny structures
that represent the data set being sorted. These tuples have
space for a value the size of a native pointer (i.e. 64
bits on a 64-bit machine) which is enough to fit the
entirety of some common types like booleans or integers
(known as pass-by-value types), but not for others that are
larger than 64 bits or arbitrarily large. In their case,
Postgres will follow a references back to the heap when
comparing values (they&rsquo;re appropriately called
pass-by-reference types). Postgres is very fast, so that
still happens quickly, but it&rsquo;s slower than comparing
values readily available in memory.</p>

<figure>
    <img alt="An array of sort tuples." class="overflowing" loading="lazy" src="/assets/images/sortsupport/sort-tuples.svg">
    <figcaption>An array of sort tuples.</figcaption>
</figure>

<p>SortSupport augments pass-by-reference types by bringing a
representative part of their value into the sort tuple to
save trips to the heap. Because sort tuples usually don&rsquo;t
have the space to store the entirety of the value,
SortSupport generates a digest of the full value called an
<strong>abbreviated key</strong>, and stores it instead. The contents of
an abbreviated key vary by type, but they&rsquo;ll aim to store
as much sorting-relevant information as possible while
remaining faithful to pre-existing sorting rules.</p>

<p>Abbreviated keys should never produce an incorrect
comparison, but it&rsquo;s okay if they can&rsquo;t fully resolve one.
If two abbreviated keys look equal, Postgres will fall back
to comparing their full heap values to make sure it gets
the right result (called an &ldquo;authoritative comparison&rdquo;).</p>

<figure>
    <img alt="A sort tuple with an abbreviated key and pointer to the heap." class="overflowing" loading="lazy" src="/assets/images/sortsupport/abbreviated-keys.svg">
    <figcaption>A sort tuple with an abbreviated key and pointer to the heap.</figcaption>
</figure>

<p>Implementing an abbreviated key is straightforward in many
cases. UUIDs are a good example of that: at 128 bits long
they&rsquo;re always larger than the pointer size even on a
64-bit machine, but we can get a very good proxy of their
full value just by sampling their first 64 bits (or 32 on a
32-bit machine). Especially for V4 UUIDs which are almost
entirely random <sup id="footnote-1-source"><a href="#footnote-1">1</a></sup>, the first 64 bits will be enough to
definitively determine the order for all but unimaginably
large data sets. Indeed, <a href="https://www.postgresql.org/message-id/CAM3SWZR4avsTwwNVUzRNbHk8v36W-QBqpoKg%3DOGkWWy0dKtWBA%40mail.gmail.com">the patch that brought in
SortSupport for UUIDs</a> made sorting them about
twice as fast!</p>

<p>String-like types (e.g. <code>text</code>, <code>varchar</code>) aren&rsquo;t too much
harder: just pack as many characters from the front of the
string in as possible (although made somewhat more
complicated by locales). Adding SortSupport for them made
operations like <code>CREATE INDEX</code> <a href="http://pgeoghegan.blogspot.com/2015/01/abbreviated-keys-exploiting-locality-to.html">about three times
faster</a>. My only ever patch to Postgres was
implementing SortSupport for the <code>macaddr</code> type, which was
fairly easy because although it&rsquo;s pass-by-reference, its
values are only six bytes long <sup id="footnote-2-source"><a href="#footnote-2">2</a></sup>. On a 64-bit machine we
have room for all six bytes, and on 32-bit we sample the
MAC address&rsquo; first four bytes.</p>

<p>Some abbreviated keys are more complex. The implementation
for the <code>numeric</code> type, which allows arbitrary scale and
precision, involves <a href="https://en.wikipedia.org/wiki/Offset_binary">excess-K coding</a> and breaking
available bits into multiple parts to store sort-relevant
fields.</p>

<h2 id="implementation" class="link"><a href="#implementation">A glance at the implementation</a></h2>

<p>Let&rsquo;s try to get a basic idea of how SortSupport is
implemented by examining a narrow slice of source code.
Sorting in Postgres is extremely complex and involves
thousands of lines of code, so fair warning that I&rsquo;m going
to simplify some things and skip <em>a lot</em> of others.</p>

<p>A good place start is with <code>Datum</code>, the pointer-sized type
(32 or 64 bits, depending on the CPU) used for sort
comparisons. It stores entire values for pass-by-value
types, abbreviated keys for pass-by-reference types that
implement SortSupport, and a pointer for those that don&rsquo;t.
You can find it defined in <a href="https://github.com/postgres/postgres/blob/08ecdfe7e5e0a31efbe1d58fefbe085b53bc79ca/src/include/postgres.h#L367"><code>postgres.h</code></a>:</p>

<pre><code class="language-c">/*
 * A Datum contains either a value of a pass-by-value type or a pointer
 * to a value of a pass-by-reference type.  Therefore, we require:
 *
 * sizeof(Datum) == sizeof(void *) == 4 or 8
 */

typedef uintptr_t Datum;

#define SIZEOF_DATUM SIZEOF_VOID_P
</code></pre>

<h3 id="uuid" class="link"><a href="#uuid">Building abbreviated keys for UUID</a></h3>

<p>The format of abbreviated keys for the <code>uuid</code> type is one
of the easiest to understand, so let&rsquo;s look at that. In
Postgres, the struct <code>pg_uuid_t</code> defines how UUIDs are
physically stored in the heap (from <a href="https://github.com/postgres/postgres/blob/08ecdfe7e5e0a31efbe1d58fefbe085b53bc79ca/src/include/utils/uuid.h#L20"><code>uuid.h</code></a>):</p>

<pre><code class="language-c">/* uuid size in bytes */
#define UUID_LEN 16

typedef struct pg_uuid_t
{
    unsigned char data[UUID_LEN];
} pg_uuid_t;
</code></pre>

<p>You might be used to seeing UUIDs represented in string
format like <code>123e4567-e89b-12d3-a456-426655440000</code>, but
remember that this is Postgres which likes to be as
efficient as possible! A UUID contains 16 bytes worth of
information, so <code>pg_uuid_t</code> above defines an array of
exactly 16 bytes. No wastefulness to be found.</p>

<p>SortSupport implementations define a conversion routine
which takes the original value and produces a datum
containing an abbreviated key. Here&rsquo;s the one for UUIDs
(from <a href="https://github.com/postgres/postgres/blob/08ecdfe7e5e0a31efbe1d58fefbe085b53bc79ca/src/backend/utils/adt/uuid.c#L367"><code>uuid.c</code></a>):</p>

<pre><code class="language-c">static Datum
uuid_abbrev_convert(Datum original, SortSupport ssup)
{
    pg_uuid_t *authoritative = DatumGetUUIDP(original);
    Datum      res;

    memcpy(&amp;res, authoritative-&gt;data, sizeof(Datum));

    ...

    /*
     * Byteswap on little-endian machines.
     *
     * This is needed so that uuid_cmp_abbrev() (an unsigned integer 3-way
     * comparator) works correctly on all platforms.  If we didn't do this,
     * the comparator would have to call memcmp() with a pair of pointers to
     * the first byte of each abbreviated key, which is slower.
     */
    res = DatumBigEndianToNative(res);

    return res;
}
</code></pre>

<p><code>memcpy</code> (&ldquo;memory copy&rdquo;) extracts a datum worth of bytes
from a <code>pg_uuid_t</code> and places it into <code>res</code>. We can&rsquo;t take
the whole UUID, but we&rsquo;ll be taking its 4 or 8 most
significant bytes, which will be enough information for
most comparisons.</p>

<figure>
    <img alt="Abbreviated key formats for the `uuid` type." class="overflowing" loading="lazy" src="/assets/images/sortsupport/uuid.svg">
    <figcaption>Abbreviated key formats for the `uuid` type.</figcaption>
</figure>

<p>The call <code>DatumBigEndianToNative</code> is there to help with an
optimization. When comparing our abbreviated keys, we could
do so with <code>memcmp</code> (&ldquo;memory compare&rdquo;)  which would compare
each byte in the datum one at a time. That&rsquo;s perfectly
functional of course, but because our datums are the same
size as native integers, we can instead choose to take
advantage of the fact that CPUs are optimized to compare
integers really, really quickly, and arrange the datums in
memory as if they were integers. You can see this integer
comparison taking place in the UUID abbreviated key
comparison function:</p>

<pre><code class="language-c">static int
uuid_cmp_abbrev(Datum x, Datum y, SortSupport ssup)
{
    if (x &gt; y)
        return 1;
    else if (x == y)
        return 0;
    else
        return -1;
}
</code></pre>

<p>However, pretending that some consecutive bytes in memory
are integers introduces some complication. Integers might
be stored like <code>data</code> in <code>pg_uuid_t</code> with the most
significant byte first, but that depends on the
architecture of the CPU. We call architectures that store
numerical values this way <strong>big-endian</strong>. Big-endian
machines exist, but the chances are that the CPU you&rsquo;re
using to read this article stores bytes in the reverse
order of their significance, with the most significant at
the highest address. This layout is called
<strong>little-endian</strong>, and is in use by Intel&rsquo;s X86, as well as
being the default mode for ARM chips like the ones in
Android and iOS devices.</p>

<p>If we left the big-endian result of the <code>memcpy</code> unchanged
on little-endian systems, the resulting integer would be
wrong. The answer is to byteswap, which reverses the order
of the bytes, and corrects the integer.</p>

<figure>
    <img alt="Example placement of integer bytes on little and big endian architectures." class="overflowing" loading="lazy" src="/assets/images/sortsupport/endianness.svg">
    <figcaption>Example placement of integer bytes on little and big endian architectures.</figcaption>
</figure>

<p>You can see in <a href="https://github.com/postgres/postgres/blob/08ecdfe7e5e0a31efbe1d58fefbe085b53bc79ca/src/include/port/pg_bswap.h#L143"><code>pg_bswap.h</code></a> that
<code>DatumBigEndianToNative</code> is defined as a no-op on a
big-endian machine, and is otherwise connected to a
byteswap (&ldquo;bswap&rdquo;) routine of the appropriate size:</p>

<pre><code class="language-c">#ifdef WORDS_BIGENDIAN

        #define        DatumBigEndianToNative(x)    (x)

#else

    #if SIZEOF_DATUM == 8
        #define        DatumBigEndianToNative(x)    pg_bswap64(x)
    #else
        #define        DatumBigEndianToNative(x)    pg_bswap32(x)
    #endif

#endif
</code></pre>

<h4 id="abort" class="link"><a href="#abort">Conversion abort & HyperLogLog</a></h4>

<p>Let&rsquo;s touch upon one more feature of <code>uuid_abbrev_convert</code>.
In data sets with very low cardinality (i.e, many
duplicated items) SortSupport introduces some danger of
worsening performance. With so many duplicates, the
contents of abbreviated keys would often show equality, in
which cases Postgres would often have to fall back to the
authoritative comparator. In effect, by adding SortSupport
we would have added a useless additional comparison that
wasn&rsquo;t there before.</p>

<p>To protect against performance regression, SortSupport has
a mechanism for aborting abbreviated key conversion. If the
data set is found to be below a certain cardinality
threshold, Postgres stops abbreviating, reverts any keys
that were already abbreviated, and disables further
abbreviation for the sort.</p>

<p>Cardinality is estimated with the help of
<a href="https://en.wikipedia.org/wiki/HyperLogLog">HyperLogLog</a>, an algorithm that estimates the
distinct count of a data set in a very memory-efficient
way. Here you can see the conversion routine adding new
values to the HyperLogLog if an abort is still possible:</p>

<pre><code class="language-c">uss-&gt;input_count += 1;

if (uss-&gt;estimating)
{
    uint32        tmp;

#if SIZEOF_DATUM == 8
    tmp = (uint32) res ^ (uint32) ((uint64) res &gt;&gt; 32);
#else
    tmp = (uint32) res;
#endif

    addHyperLogLog(&amp;uss-&gt;abbr_card, DatumGetUInt32(hash_uint32(tmp)));
}
</code></pre>

<p>And where it makes an abort decision (from <a href="https://github.com/postgres/postgres/blob/08ecdfe7e5e0a31efbe1d58fefbe085b53bc79ca/src/backend/utils/adt/uuid.c#L301"><code>uuid.c</code></a>):</p>

<pre><code class="language-c">static bool
uuid_abbrev_abort(int memtupcount, SortSupport ssup)
{
    ...

    abbr_card = estimateHyperLogLog(&amp;uss-&gt;abbr_card);

    /*
     * If we have &gt;100k distinct values, then even if we were
     * sorting many billion rows we'd likely still break even,
     * and the penalty of undoing that many rows of abbrevs would
     * probably not be worth it. Stop even counting at that point.
     */
    if (abbr_card &gt; 100000.0)
    {
        uss-&gt;estimating = false;
        return false;
    }

    /*
     * Target minimum cardinality is 1 per ~2k of non-null inputs.
     * 0.5 row fudge factor allows us to abort earlier on genuinely
     * pathological data where we've had exactly one abbreviated
     * value in the first 2k (non-null) rows.
     */
    if (abbr_card &lt; uss-&gt;input_count / 2000.0 + 0.5)
    {
        return true;
    }

    ...
}
</code></pre>

<p>It also covers aborting the case where we have a data set
that&rsquo;s poorly suited to the abbreviated key format. For
example, imagine a million UUIDs that all shared a common
prefix in their first eight bytes, but were distinct in
their last eight <sup id="footnote-3-source"><a href="#footnote-3">3</a></sup>. Realistically this will be extremely
unusual, so abbreviated key conversion will rarely abort.</p>

<h3 id="tuples" class="link"><a href="#tuples">Tuples and data types</a></h3>

<p><strong>Sort tuples</strong> are the tiny structures that Postgres sorts
in memory. They hold a reference to the &ldquo;true&rdquo; tuple, a
datum, and a flag to indicate whether or not the first
value is <code>NULL</code> (which has its own special sorting
semantics). The latter two are named with a <code>1</code> suffix as
<code>datum1</code> and <code>isnull1</code> because they represent only one
field worth of information. Postgres will need to fall back
to different values in the event of equality in a
multi-column comparison. From <a href="https://github.com/postgres/postgres/blob/08ecdfe7e5e0a31efbe1d58fefbe085b53bc79ca/src/backend/utils/sort/tuplesort.c#L169"><code>tuplesort.c</code></a>:</p>

<pre><code class="language-c">/*
 * The objects we actually sort are SortTuple structs.  These contain
 * a pointer to the tuple proper (might be a MinimalTuple or IndexTuple),
 * which is a separate palloc chunk --- we assume it is just one chunk and
 * can be freed by a simple pfree() (except during merge, when we use a
 * simple slab allocator).  SortTuples also contain the tuple's first key
 * column in Datum/nullflag format, and an index integer.
 */
typedef struct
{
    void       *tuple;          /* the tuple itself */
    Datum       datum1;         /* value of first key column */
    bool        isnull1;        /* is first key column NULL? */
    int         tupindex;       /* see notes above */
} SortTuple;
</code></pre>

<p>In the code we&rsquo;ll look at below, <code>SortTuple</code> may reference
a <strong>heap tuple</strong>, which has a variety of different struct
representations. One used by the sort algorithm is
<code>HeapTupleHeaderData</code> (from <a href="https://github.com/postgres/postgres/blob/08ecdfe7e5e0a31efbe1d58fefbe085b53bc79ca/src/include/access/htup_details.h#L152"><code>htup_details.h</code></a>):</p>

<pre><code class="language-c">struct HeapTupleHeaderData
{
    union
    {
        HeapTupleFields t_heap;
        DatumTupleFields t_datum;
    }            t_choice;

    ItemPointerData t_ctid; /* current TID of this or newer tuple (or a
                             * speculative insertion token) */

    ...
}
</code></pre>

<p>Heap tuples have a pretty complex structure which we won&rsquo;t
cover, but you can see that it contains an
<code>ItemPointerData</code> value. This struct is what gives Postgres
the precise information it needs to find data in the heap
(from <a href="https://github.com/postgres/postgres/blob/08ecdfe7e5e0a31efbe1d58fefbe085b53bc79ca/src/include/storage/itemptr.h#L36"><code>itemptr.h</code></a>):</p>

<pre><code class="language-c">/*
 * ItemPointer:
 *
 * This is a pointer to an item within a disk page of a known file
 * (for example, a cross-link from an index to its parent table).
 * blkid tells us which block, posid tells us which entry in the linp
 * (ItemIdData) array we want.
 */
typedef struct ItemPointerData
{
    BlockIdData ip_blkid;
    OffsetNumber ip_posid;
}
</code></pre>

<h3 id="comparison" class="link"><a href="#comparison">Tuple comparison</a></h3>

<p>The algorithm to compare abbreviated keys is duplicated in
the Postgres source in a number of places depending on the
sort operation being carried out. We&rsquo;ll take a look at
<code>comparetup_heap</code> (from <a href="https://github.com/postgres/postgres/blob/08ecdfe7e5e0a31efbe1d58fefbe085b53bc79ca/src/backend/utils/sort/tuplesort.c#L3508"><code>tuplesort.c</code></a>) which
is used when sorting based on the heap. This would be
invoked for example if you ran an <code>ORDER BY</code> on a field
that doesn&rsquo;t have an index on it.</p>

<pre><code class="language-c">static int
comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
{
    SortSupport sortKey = state-&gt;sortKeys;
    HeapTupleData ltup;
    HeapTupleData rtup;
    TupleDesc     tupDesc;
    int           nkey;
    int32         compare;
    AttrNumber    attno;
    Datum         datum1,
                  datum2;
    bool          isnull1,
                  isnull2;


    /* Compare the leading sort key */
    compare = ApplySortComparator(a-&gt;datum1, a-&gt;isnull1,
                                  b-&gt;datum1, b-&gt;isnull1,
                                  sortKey);
    if (compare != 0)
        return compare;
</code></pre>

<p><code>ApplySortComparator</code> gets a comparison result between two
datum values. It&rsquo;ll compare two abbreviated keys where
appropriate and handles <code>NULL</code> sorting semantics. The
return value of a comparison follows the spirit of C&rsquo;s
<code>strcmp</code>: when comparing <code>(a, b)</code>, -1 indicates <code>a &lt; b</code>,
0 indicates equality, and 1 indicates <code>a &gt; b</code>.</p>

<p>The algorithm returns immediately if inequality (<code>!= 0</code>)
was detected. Otherwise, it checks to see if abbreviated
keys were used, and if so applies the authoritative
comparison if they were. Because space in abbreviated keys
is limited, two being equal doesn&rsquo;t necessarily indicate
that the values that they represent are.</p>

<pre><code class="language-c">if (sortKey-&gt;abbrev_converter)
{
    attno = sortKey-&gt;ssup_attno;

    datum1 = heap_getattr(&amp;ltup, attno, tupDesc, &amp;isnull1);
    datum2 = heap_getattr(&amp;rtup, attno, tupDesc, &amp;isnull2);

    compare = ApplySortAbbrevFullComparator(datum1, isnull1,
                                            datum2, isnull2,
                                            sortKey);
    if (compare != 0)
        return compare;
}
</code></pre>

<p>Once again, the algorithm returns if inequality was
detected. If not, it starts to look beyond the first field
(in the case of a multi-column sort):</p>

<pre><code class="language-c">    ...

    sortKey++;
    for (nkey = 1; nkey &lt; state-&gt;nKeys; nkey++, sortKey++)
    {
        attno = sortKey-&gt;ssup_attno;

        datum1 = heap_getattr(&amp;ltup, attno, tupDesc, &amp;isnull1);
        datum2 = heap_getattr(&amp;rtup, attno, tupDesc, &amp;isnull2);

        compare = ApplySortComparator(datum1, isnull1,
                                      datum2, isnull2,
                                      sortKey);
        if (compare != 0)
            return compare;
    }

    return 0;
}
</code></pre>

<p>After finding abbreviated keys to be equal, full values to
be equal, and all additional sort fields to be equal, the
last step is to <code>return 0</code>, indicating in classic libc
style that the two tuples are really, fully equal.</p>

<h2 id="leverage" class="link"><a href="#leverage">Fast code and leveraged software</a></h2>

<p>SortSupport is a good example of the type of low-level
optimization that most of us probably wouldn&rsquo;t bother with
in our projects, but which makes sense in an extremely
leveraged system like a database. As implementations are
added for it and Postgres&rsquo; tens of thousands of users like
myself upgrade, common operations like <code>DISTINCT</code>, <code>ORDER
BY</code>, and <code>CREATE INDEX</code> get twice as fast, for free.</p>

<p>Credit to Peter Geoghegan for some of the original
exploration of this idea and implementations for UUID and a
generalized system for SortSupport on variable-length
string types, Robert Haas and Tom Lane for adding the
<a href="https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=c6e3ac11b60ac4a8942ab964252d51c1c0bd8845">necessary infrastructure</a>, and Andrew
Gierth for a <a href="https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=abd94bcac4582903765be7be959d1dbc121df0d0">difficult implementation</a> for
<code>numeric</code>. (I hope I got all that right.)</p>


]]></content>
    <published>2019-02-04T16:56:52Z</published>
    <updated>2019-02-04T16:56:52Z</updated>
    <link href="https://brandur.org/sortsupport"></link>
    <id>tag:brandur.org,2019-02-04:sortsupport</id>
    <author>
      <name>Brandur Leach</name>
      <uri>https://brandur.org</uri>
    </author>
  </entry>
  <entry>
    <title>How to Manage Connections Efficiently in Postgres, or Any Database</title>
    <summary>Hitting the limit for maximum allowed connections is a common operational problem in Postgres. Here we look at a few techniques for managing connections and making efficient use of those that are available.</summary>
    <content type="html"><![CDATA[<p>You start building your new project. You&rsquo;ve heard good
things about Postgres, so you choose it as your database.
As advertised, it proves to be a satisfying tool and
progress is good. You put your project into production for
the first time and like you&rsquo;d hoped, things go smoothly as
Postgres turns out to be well-suited for production use as
well.</p>

<p>The first few months go well and traffic continues to ramp
up, when suddenly a big spike of failures appears. You dig
into the cause and see that your application is failing to
open database connections. You find this chilling artifact
littered throughout your logs:</p>

<pre><code>FATAL: remaining connection slots are reserved for
non-replication superuser connections
</code></pre>

<p>This is one of the first major operational problems that
new users are likely to encounter with Postgres, and one
that might prove to be frustratingly persistent. Like the
error suggests, the database is indicating that its total
number of connection slots are limited, and that the limit
has been reached.</p>

<p>The ceiling is controlled by the <code>max_connections</code> key in
Postgres&rsquo; configuration, which defaults to 100. Almost
every cloud Postgres provider like Google Cloud Platform or
Heroku limit the number pretty carefully, with the largest
databases topping out at 500 connections, and the smaller
ones at much lower numbers like 20 or 25.</p>

<p>At first sight this might seem a little counterintuitive.
If the connection limit is a known problem, why not just
configure a huge maximum to avoid it? As with many things
in computing, the solution isn&rsquo;t as simple as it might seem
at first glance, and there are a number of factors that
will limit the maximum number of connections that it&rsquo;s
practical to have; some obvious, and some not. Let&rsquo;s take a
closer look.</p>

<h2 id="concurrency-limits" class="link"><a href="#concurrency-limits">The practical limits of concurrency</a></h2>

<p>The most direct constraint, but also probably the least
important, is memory. Postgres is designed around a process
model where a central Postmaster accepts incoming
connections and forks child processes to handle them. Each
of these &ldquo;backend&rdquo; processes starts out at around 5 MB in
size, but may grow to be much larger depending on the data
they&rsquo;re accessing <sup id="footnote-1-source"><a href="#footnote-1">1</a></sup>.</p>

<figure>
    <img alt="A simplified view of Postgres' forking process model." class="overflowing" loading="lazy" src="/assets/images/postgres-connections/process-model.svg">
    <figcaption>A simplified view of Postgres' forking process model.</figcaption>
</figure>

<p>Since these days it&rsquo;s pretty easy to procure a system where
memory is abundant, the absolute memory ceiling often isn&rsquo;t
a main limiting factor. One that&rsquo;s more subtle and more
important is that the Postmaster and its backend processes
use shared memory for communication, and parts of that
shared space are global bottlenecks. For example, here&rsquo;s
the structure that tracks every ongoing process and
transaction:</p>

<pre><code class="language-c">typedef struct PROC_HDR
{
    /* Array of PGPROC structures (not including dummies for prepared txns) */
    PGPROC       *allProcs;
    /* Array of PGXACT structures (not including dummies for prepared txns) */
    PGXACT       *allPgXact;

    ...
}

extern PGDLLIMPORT PROC_HDR *ProcGlobal;
</code></pre>

<p>Operations that might happen in any backend requires
walking the entire list of processes or transactions.
Adding a new process to the proc array necessitates taking
an exclusive lock:</p>

<pre><code class="language-c">void
ProcArrayAdd(PGPROC *proc)
{
    ProcArrayStruct *arrayP = procArray;
    int            index;

    LWLockAcquire(ProcArrayLock, LW_EXCLUSIVE);

    ...
}
</code></pre>

<p>Likewise, <code>GetSnapshotData</code> is often called multiple times
for any operation and needs to loop through every other
process in the system:</p>

<pre><code class="language-c">Snapshot
GetSnapshotData(Snapshot snapshot)
{
    ProcArrayStruct *arrayP = procArray;

    ...

    /*
     * Spin over procArray checking xid, xmin, and subxids.  The goal is
     * to gather all active xids, find the lowest xmin, and try to record
     * subxids.
     */
    numProcs = arrayP-&gt;numProcs;
    for (index = 0; index &lt; numProcs; index++)
    {
        ...
    }
}
</code></pre>

<p>There are a few such bottlenecks throughout the normal
paths that Postgres uses to work, and they are of course in
addition to the normal contention you&rsquo;d expect to find
around system resources like I/O or CPU.</p>

<p>The cumulative effect is that within any given backend,
performance is proportional to the number of all active
backends in the wider system. I wrote a <a href="https://github.com/brandur/connections-test">benchmark</a> to
demonstrate this effect: it spins up a cluster of parallel
workers that each use their own connection to perform a
transaction that inserts ten times, selects ten times, and
deletes ten times before committing <sup id="footnote-2-source"><a href="#footnote-2">2</a></sup>. Parallelism starts
at 1, ramps up to 1000, and timing is measured for every
transaction. You can see from the results that performance
degrades slowly but surely as more active clients are
introduced:</p>

<figure>
    <img alt="Performance of a simple task degrading as the number of active connections in the database increases." class="overflowing" loading="lazy" src="/assets/images/postgres-connections/contention.png" srcset="/assets/images/postgres-connections/contention@2x.png 2x, /assets/images/postgres-connections/contention.png 1x">
    <figcaption>Performance of a simple task degrading as the number of active connections in the database increases.</figcaption>
</figure>

<p>So while it might be a little irking that platforms like
Google Cloud and Heroku limit the total connections even on
very big servers, they&rsquo;re actually trying to help you.
Performance in Postgres isn&rsquo;t reliable when it&rsquo;s scaled up
to huge numbers of connections. Once you start brushing up
against a big connection limit like 500, the right answer
probably isn&rsquo;t to increase it &ndash; it&rsquo;s to re-evaluate how
those connections are being used to and try to manage them
more efficiently.</p>

<h2 id="techniques" class="link"><a href="#techniques">Techniques for efficient connection use</a></h2>

<h3 id="connection-pool" class="link"><a href="#connection-pool">Connection pools</a></h3>

<p>A connection pool is a cache of database connections,
usually local to a specific process. Its main advantage is
improved performance &ndash; there&rsquo;s a certain amount of
overhead inherent to opening a new database connection in
both the client and the server. After finishing with a
connection, by checking it back into a pool instead of
discarding it, the connection can be reused next time one
is needed within the application. Connection pooling is
built into many database adapters including Go&rsquo;s
<a href="https://godoc.org/database/sql"><code>database/sql</code></a>, Java&rsquo;s <a href="https://en.wikipedia.org/wiki/Java_Database_Connectivity">JDBC</a>, or
Active Record in Ruby.</p>

<figure>
    <img alt="A deployment with a number of nodes, each of which maintains a local pool of connections for their workers to use." class="overflowing" loading="lazy" src="/assets/images/postgres-connections/connection-pooling.svg">
    <figcaption>A deployment with a number of nodes, each of which maintains a local pool of connections for their workers to use.</figcaption>
</figure>

<p>Connection pools also help manage connections more
efficiently. They&rsquo;re configured with a maximum number of
connections that the pool can hold which makes the total
number of connections that you can expect a single deployed
node to use deterministic. By writing application workers
to only acquire a connection when they&rsquo;re serving a
request, those per-node pools of connections can be shared
between a much larger pool of workers.</p>

<p>A limitation of connection pools is that they&rsquo;re usually
only effective in languages that can be deployed within a
single process. Rails implements a connection pool in
Active Record, but because Ruby isn&rsquo;t capable of real
parallelism, it&rsquo;s common to use forking servers like
Unicorn or Puma. This makes those connection pools much
less effective because each process needs to maintain its
own <sup id="footnote-3-source"><a href="#footnote-3">3</a></sup>.</p>

<h3 id="mvc" class="link"><a href="#mvc">Minimum viable checkouts</a></h3>

<p>For any given span of work, very often it&rsquo;s possible to
identify a critical span in the middle where core domain
logic is being run, and where a database connection needs
to be held. To take an HTTP request for example, there&rsquo;s
usually a phase at the beginning where a worker is reading
a request&rsquo;s body, decoding and validating its payload, and
performing other peripheral operations like rate limiting
before moving on to the application&rsquo;s core logic. After
that logic is executed there&rsquo;s a similar phase at the end
where it&rsquo;s serializing and sending the response, emitting
metrics, performing logging, and so on.</p>

<figure>
    <img alt="Workers should only hold connections as long as they're needed. There's work before and after core application logic where no connection is needed." class="overflowing" loading="lazy" src="/assets/images/postgres-connections/minimum-viable-checkout.svg">
    <figcaption>Workers should only hold connections as long as they're needed. There's work before and after core application logic where no connection is needed.</figcaption>
</figure>

<p>Workers should only have a connection checked out of the
pool while that core logic is executing. This <strong>minimum
viable checkout</strong> technique maximizes the efficient use of
connections by minimizing the amount of time any given
worker holds one, allowing a pool of connections to be
feasibly shared amongst a much larger pool of workers. Idle
workers don&rsquo;t hold any connections at all.</p>

<h4 id="foreign-mutations" class="link"><a href="#foreign-mutations">Releasing connections around foreign mutations</a></h4>

<p>I&rsquo;ve written previously about breaking units of application
work into <a href="/idempotency-keys#atomic-phases">atomic phases</a> around where an
application is making requests to foreign APIs. Utilization
can be made even more efficient by making sure to release
connections back to the pool while that slow network I/O is
in flight (an application should not be in a transaction
while mutating foreign state anyway), and reacquire
them afterwards.</p>

<h3 id="pgbouncer" class="link"><a href="#pgbouncer">PgBouncer & inter-node pooling</a></h3>

<p>Connection pools and minimum viable checkouts will go a
long way, but you may still reach a point where a hammer is
needed. When an application is scaled out to many nodes,
connection pools maximize the efficient use of connections
local to any of them, but can&rsquo;t do so between nodes. In
most systems work should be distributed between nodes
roughly equally, but because it&rsquo;s normal to use randomness
to do that (through something like HAProxy or another load
balancer), and because work durations vary, an equal
distribution of work across the whole cluster at any given
time isn&rsquo;t likely.</p>

<p>If we have <em>N</em> nodes and <em>M</em> maximum connections per node,
we may have a configuration where <em>N</em> × <em>M</em> is greater than
the database&rsquo;s <code>max_connections</code> to protect against the
case where a single node is handling an outsized amount of
work and needs more connections. Because nodes aren&rsquo;t
coordinating, if the whole cluster is running close to
capacity, it&rsquo;s possible for a node trying to get a new
connection to go over-limit and get an error back from
Postgres.</p>

<p>In this case it&rsquo;s possible to install
<a href="https://pgbouncer.github.io/">PgBouncer</a> to act as a global pool by proxying
all connections through it to Postgres. It functions almost
exactly like a connection pool and has a few modes of
operation:</p>

<ul>
<li><p><strong>Session pooling:</strong> A connection is assigned when a
client opens a connection and unassigned when the client
closes it.</p></li>

<li><p><strong>Transaction pooling:</strong> Connections are assigned only
for the duration of a transaction, and may be shared
around them. This comes with a limitation that
applications cannot use features that change the &ldquo;global&rdquo;
state of a connection like <code>SET</code>, <code>LISTEN</code>/<code>NOTIFY</code>, or
prepared statements <sup id="footnote-4-source"><a href="#footnote-4">4</a></sup>.</p></li>

<li><p><strong>Statement pooling:</strong> Connections are assigned only
around individual statements. This only works of course
if an application gives up the use of transactions, at
which point it&rsquo;s losing a big advantage of using
Postgres in the first place.</p></li>
</ul>

<figure>
    <img alt="Using PgBouncer to maintain a global connection pool to optimize connection use across all nodes." class="overflowing" loading="lazy" src="/assets/images/postgres-connections/pgbouncer.svg">
    <figcaption>Using PgBouncer to maintain a global connection pool to optimize connection use across all nodes.</figcaption>
</figure>

<p>Transaction pooling is the best strategy for applications
that are already making effective use of a node-local
connection pool, and will allow such an application that&rsquo;s
configured with an <em>N</em> × <em>M</em> greater than <code>max_connections</code>
to closely approach the maximum possible theoretical
utilization of available connections, and to also avoid
connection errors caused by going over-limit (although
delaying requests while waiting for a connection to become
available from PgBouncer is still possible).</p>

<p>Probably the more common use of PgBouncer is to act as a
node-local connection pool for applications that can&rsquo;t do a
good job of implementing their own, like a Rails app
deployed with Unicorn. Heroku, for example, provides and
recommends the use of a standardized buildpack that deploys
a per-dyno PgBouncer to accomplish this. It&rsquo;s a handy tool
to cover this case, but it&rsquo;s advisable to use a more
sophisticated technique if possible.</p>

<h2 id="resource" class="link"><a href="#resource">Connections as a resource</a></h2>

<p>There was a trend in frameworks for some time to try and
simplify software development for their users by
abstracting away the details of connection management. This
might work for a time, but in the long run anyone
deploying a large application on Postgres will have to
understand what&rsquo;s happening or they&rsquo;re likely to run into
trouble. It&rsquo;ll usually pay to understand them earlier so
that applications can be architected smartly to maximize
the efficient use of a scarce resource.</p>

<p>Developers should be aware of how many connections each
node can use, how many connections a cluster can use by
multiplying that number by the number of nodes, and where
that total sits relative to Postgres&rsquo; <code>max_connections</code>.
It&rsquo;s common to hit limits during a deploy because a
graceful restart spins up new workers or nodes before
shutting down old ones, so know expected connection numbers
during deployments as well.</p>

<p>Finally, although we&rsquo;ve talked mostly about Postgres here,
there will be practical bottlenecks like the ones described
here in any database, so these techniques for managing
connections should be widely portable.</p>


]]></content>
    <published>2018-10-15T15:42:51Z</published>
    <updated>2018-10-15T15:42:51Z</updated>
    <link href="https://brandur.org/postgres-connections"></link>
    <id>tag:brandur.org,2018-10-15:postgres-connections</id>
    <author>
      <name>Brandur Leach</name>
      <uri>https://brandur.org</uri>
    </author>
  </entry>
  <entry>
    <title>A Missing Link in Postgres 11: Fast Column Creation with Defaults</title>
    <summary>How a seemingly minor enhancement in Postgres 11 fills one of the system&amp;rsquo;s biggest operational holes.</summary>
    <content type="html"><![CDATA[<p>If you read through the release notes for <a href="https://www.postgresql.org/docs/11/static/release-11.html">upcoming
Postgres 11</a>, you might see a somewhat
inconspicuous addition tucked away at the bottom of the
enhancements list:</p>

<blockquote>
<p>Many other useful performance improvements, including
making <code>ALTER TABLE .. ADD COLUMN</code> with a non-null column
default faster</p>
</blockquote>

<p>It&rsquo;s not a flagship feature of the new release, but it&rsquo;s
still one of the more important operational improvements
that Postgres has made in years, even though it might not
be immediately obvious why. The short version is that it&rsquo;s
eliminated a limitation that used to make correctness in
schema design difficult, but let&rsquo;s take a look at the
details.</p>

<h2 id="alterations" class="link"><a href="#alterations">Alterations and exclusive locks</a></h2>

<p>Consider for a moment one of the simplest database
statements possible, one that adds a new column to a table:</p>

<pre><code class="language-sql">ALTER TABLE users
    ADD COLUMN credits bigint;
</code></pre>

<p>Although it&rsquo;s altering the table&rsquo;s schema, any modern
database is sophisticated enough to make this operation
practically instantaneous. Instead of rewriting the
existing representation of the table (thereby forcing all
existing data to be copied over at great expense),
information on the new column is added to the system
catalog, which is cheap. That allows new rows to be written
with values for the new column, and the system is smart
enough to return <code>NULL</code> for current rows where no value
previously existed.</p>

<p>But things get complicated when we add a <code>DEFAULT</code> clause
to the same statement:</p>

<pre><code class="language-sql">ALTER TABLE users
    ADD COLUMN credits bigint NOT NULL DEFAULT 0;
</code></pre>

<p>The SQL looks so similar as to be almost identical, but
where the previous operation was trivial, this one is
infinitely more expensive in that it now requires a full
rewrite of the table and all its indexes. Because there&rsquo;s
now a non-null value involved, the database ensures data
integrity by going back and injecting it into every
existing row.</p>

<p>Despite that expense, Postgres is still capable of doing
the rewrite efficiently, and on smaller databases it&rsquo;ll
appear to happen instantly.</p>

<p>It&rsquo;s bigger installations where it becomes a problem.
Rewriting a table with a large body of existing data will
take about as long as you&rsquo;d expect, and in the meantime,
the rewrite will take an <a href="https://www.postgresql.org/docs/current/static/explicit-locking.html"><code>ACCESS EXCLUSIVE</code> lock</a>
on the table. <code>ACCESS EXCLUSIVE</code> is the coarsest
granularity of table lock possible, and it&rsquo;ll block <em>every</em>
other operation until it&rsquo;s released; even simple <code>SELECT</code>
statements have to wait. In any system with a lot of
ongoing access to the table, that&rsquo;s a huge problem.</p>

<figure>
    <img alt="Transactions blocking during a table rewrite." class="overflowing" loading="lazy" src="/assets/images/postgres-default/blocking.svg">
    <figcaption>Transactions blocking during a table rewrite.</figcaption>
</figure>

<p>Historically, accidentally locking access to a table when
adding a column has been a common pitfall for new Postgres
operators because there&rsquo;s nothing in the SQL to tip them
off to the additional expense of adding that <code>DEFAULT</code>
clause. It takes a close reading of <a href="https://www.postgresql.org/docs/10/static/sql-altertable.html">the
manual</a> to find out, or the pyrrhic wisdom
acquired by causing a minor operational incident.</p>

<h2 id="constraints" class="link"><a href="#constraints">Constraints, relaxed by necessity</a></h2>

<p>Because it&rsquo;s not possible to cheaply add a <code>DEFAULT</code>
column, it&rsquo;s also not possible to add a column set to <code>NOT
NULL</code>. By definition non-null columns need to have values
for every row, and you can&rsquo;t add one to a non-empty table
without specifying what values the existing data should
have, and that takes <code>DEFAULT</code>.</p>

<p>You can still get a non-null column by first adding it as
nullable, running a migration to add values to every
existing row, then altering the table with <code>SET NOT NULL</code>,
but even that&rsquo;s not perfectly safe because <code>SET NOT NULL</code>
requires a full stable scan as it verifies the new
constraint across all existing data. The scan is faster
than a rewrite, but still needs an <code>ACCESS EXCLUSIVE</code> lock.</p>

<p>The amount of effort involved in getting a new non-null
column into any large relation means that in practice you
often don&rsquo;t bother. It&rsquo;s either too dangerous, or too time
consuming.</p>

<h2 id="why-bother" class="link"><a href="#why-bother">Why bother with non-null anyway?</a></h2>

<p>One of the biggest reasons to prefer relational databases
over document stores, key/value stores, and other less
sophisticated storage technology is data integrity. Columns
are strongly typed with the likes of <code>INT</code>, <code>DECIMAL</code>, or
<code>TIMESTAMPTZ</code>. Values are constrained with <code>NOT NULL</code>,
<code>VARCHAR</code> (length), or <a href="https://www.postgresql.org/docs/current/static/ddl-constraints.html#DDL-CONSTRAINTS-CHECK-CONSTRAINTS"><code>CHECK</code> constraints</a>.
Foreign key constraints guarantee <a href="https://en.wikipedia.org/wiki/Referential_integrity">referential
integrity</a>.</p>

<p>With a good schema design you can rest assured that your
data is in a high quality state because the very database
is ensuring it. This makes querying or changing it easier,
and prevents an entire class of application-level bugs
caused by data existing in an unexpected state. Enthusiasts
like me have always argued in favor of strong data
constraints, but knew also that new non-null fields often
weren&rsquo;t possible in Postgres when it was running at scale.</p>

<h2 id="whats-new" class="link"><a href="#whats-new">So what's new in Postgres 11?</a></h2>

<p>Postgres 11 brings in a change that makes <code>ADD COLUMN</code> with
<code>DEFAULT</code> values fast by marshaling them for existing rows
only as necessary. The expensive table rewrite and long
hold on <code>ACCESS EXCLUSIVE</code> are eliminated, and a gaping
hole in Postgres&rsquo; operational story is filled. It will now
be possible to have both strong data integrity and strong
operational guarantees.</p>

<h2 id="under-the-hood" class="link"><a href="#under-the-hood">Appendix: Under the hood</a></h2>

<p>The change adds two new fields to
<a href="https://www.postgresql.org/docs/current/static/catalog-pg-attribute.html"><code>pg_attribute</code></a>, a system table that tracks
information on every column in the database:</p>

<ul>
<li><code>atthasmissing</code>: Set to <code>true</code> when there are missing
default values.</li>
<li><code>attmissingval</code>: Contains the missing value.</li>
</ul>

<p>As scans are returning rows, they check these new fields
and return missing values where appropriate. New rows
inserted into the table pick up the default values as
they&rsquo;re created so that there&rsquo;s no need to check
<code>atthasmissing</code> when returning their contents.</p>

<figure>
    <img alt="Fast column creation with existing rows loading defaults from pg_attribute." class="overflowing" loading="lazy" src="/assets/images/postgres-default/implementation.svg">
    <figcaption>Fast column creation with existing rows loading defaults from pg_attribute.</figcaption>
</figure>

<p>The <code>pg_attribute</code> fields are only used as long as they
have to be. If at any point the table is rewritten,
Postgres takes the opportunity to insert the default value
for every row and unset <code>atthasmissing</code> and
<code>attmissingval</code>.</p>

<p>Due to the relative simplicity of <code>attmissingval</code>, this
optimization only works for default values and function
calls that are <em>non-volatile</em> <sup id="footnote-1-source"><a href="#footnote-1">1</a></sup>. Using it with a volatile
function like <code>random()</code> won&rsquo;t set <code>atthasmissing</code> and
adding the default will have to rewrite the table like it
did before. Non-volatile function calls work fine though.
For example, adding <code>DEFAULT now()</code> will put the
transaction&rsquo;s current value of <code>now()</code> into <code>atthasmissing</code>
and all existing rows will inherit it, but any newly
inserted rows will get a current value of <code>now()</code> as you&rsquo;d
expect.</p>

<p>There&rsquo;s nothing all that difficult conceptually about this
change, but its implementation wasn&rsquo;t easy because the
system is complex enough that there&rsquo;s a lot of places where
the new missing values have to be considered. See <a href="https://github.com/postgres/postgres/commit/16828d5c0273b4fe5f10f42588005f16b415b2d8">the
patch</a> that brought it in for full details.</p>


]]></content>
    <published>2018-08-28T16:46:39Z</published>
    <updated>2018-08-28T16:46:39Z</updated>
    <link href="https://brandur.org/postgres-default"></link>
    <id>tag:brandur.org,2018-08-28:postgres-default</id>
    <author>
      <name>Brandur Leach</name>
      <uri>https://brandur.org</uri>
    </author>
  </entry>
</feed>