A Look at How Postgres Executes a Tiny Join - Part 1

aside from saving and retrieving data, the primary feature of a relational database is the ability to execute join queries, to  relate  data in one table with data from another. while many developers are turning to nosql solutions, joining one set of data values with another remains one of our most common and important use cases while writing server code.

but what does the word “join” actually mean? and what really happens when i execute a join query? too often we take our tools for granted, without really understanding what they are doing. this month i decided to look at the source code for  postgresql  , a popular open source database server, to see how it implements join queries.

reading and experimenting with the postgres source code turned out to be a great learning experience. today i’d like to report my observations; i’ll show you exactly how postgres executed a tiny join consisting of just a few records, using the  hash join  algorithm. in future articles i’ll show you some interesting optimizations postgres uses for larger joins, and other computer science algorithms at work inside of postgres.

what is a join?

but, before we get to the postgres source code, let’s start by reviewing what join queries are. here’s an introduction from  the excellent postgres documentation  :

the postgres docs then explain how to use joins: inner vs. outer joins, joining a table with itself, etc. but, i’m intrigued by the highlighted disclaimer. what is that “more efficient manner”? and, how could postgres possibly get away with not “actually comparing each possible pair of rows”?

a tiny join

as an example today, let’s work with two tables:  publications  , which contains three ground breaking computer science journal articles i never read in college, and  authors  , which records where each author worked.

> select * from publications;

                         title                          |   author   | year 
--------------------------------------------------------+------------+------
 a relational model of data for large shared data banks | edgar codd | 1970
 relational completeness of data base sublanguages      | edgar codd | 1972
 the transaction concept: virtues and limitations       | jim gray   | 1981
(3 rows)

> select * from authors;

    name    |         company         
------------+-------------------------
 edgar codd | ibm research laboratory
 jim gray   | tandem computers
(2 rows)

today’s goal is to understand exactly what happens when postgres joins one table with the other:

> select title, company from publications, authors where author = name;

                         title                          |         company         
--------------------------------------------------------+-------------------------
 relational completeness of data base sublanguages      | ibm research laboratory
 a relational model of data for large shared data banks | ibm research laboratory
 the transaction concept: virtues and limitations       | tandem computers
(3 rows)

a conceptual model for joining two tables

before we look at the algorithm postgres actually uses, let’s review what join queries do conceptually. above the documentation stated that postgres implements joins by “comparing each possible pair of rows” and then selecting “the pairs of rows where these values match”.

reading this, i imagine postgres takes each publication and loops over all of the authors, looking for that publication’s author:

in blue on the left are the publications, and i show the author records on the right in green. this process of iterating over the rows in the authors table is known as a scan in the postgres source code. we are scanning over all of the authors for the first publication, trying to find matching names.

what do we do with each publication-author pair? we have to evaluate the where clause from my example sql statement:

do the names match? yes. this pair should be included in the result set. what about the second pair?

do these names match? this time they don’t–this pair of rows should be filtered out.

once we have a matching pair of rows, we copy just the selected columns into a new, joined record and return that to the client:

a nested loop

what’s wrong with this conceptual model? it seems like a very simple, straightforward way of obtaining the values we need. if we proceed to scan through the rest of the publications, it produces the same result that postgres does, although in a different order. (we’ll see why the order changes later.)

the problem is that it’s very inefficient. first we scan over all of the authors for the first row in the publications table:

and then, we repeat the same scan of the authors table for the second publication:

and again for the third row. to find all of the matching pairs, in fact, we need to loop over all the authors for each publication:

for my tiny query this isn’t a problem. there are 3*2 or 6 combinations of rows; comparing names 6 times would only take a few microseconds on a modern computer. however, as the number of rows increases in either table, the total number of comparisons will explode. if we have 1000 publications and 1000 authors, suddenly we would have to compare name strings 1000*1000 or 1 million times! computer scientists describe this algorithm as o(n  ²  ).

but do we really need to search the entire authors table for each publication? “edgar codd” appears in the publications table twice–why do we need to scan the authors table for the same name more than once? after we find edgar the first time, there should be some way of recording where he was so we can find him again. and, even if there were no repeated author names in publications, it still seems wasteful to loop over the authors table over and over again. there must be some way of avoiding all of these repeated scans.

and there is; we can use a  hash table  .

avoiding repeated scans

the problem with our naive algorithm, the conceptual model from the postgres documentation, is that we loop over the authors table over and over again. to avoid those repeated loops, imagine if we scanned the authors only once and then saved them in some kind of data structure:

now that we have the author records, what do we need to do with them? well, we have to scan the publications, obtain each publication’s author, and find the matching author records, if any. in other words, we need to be able to quickly and easily find the author record with a given name:

you’ve probably seen this data structure before; in fact, it might be something you use everyday in your own code. if you’re a rubyist like me, you call this a  hash  . if you prefer python it’s a  dictionary  , or in clojure it’s  hash map  .

with all the authors organized by their names, we can scan over the publications and quickly find out if there’s a matching author record:

but what are hash tables, exactly? and, how do they work? if only we could go back in time and sneak back into our college computer science classroom again. but if you installed postgres from source, using homebrew or with some linux package manager, you already have an open source, world class implementation of the hash table algorithm right on your computer! to learn more about it, all we have to do is read the postgres source code.

calculating hashes

it turns out that for this query postgres actually hashes the publications and then iterates over the authors. before starting to execute a query, postgres first parses the sql we give it and generates a “query plan.” probably because the publications table is larger (i’m not sure), postgres’s query planner decides to save the publications, not the authors, in the hash table.

to do this, postgres has to scan the publications just as we did above:

and for each publication, postgres selects just two of the three columns: author and title. postgres refers to the query plan and finds out it will need the author for the where join condition, and the title for the final select returning the result set. it leaves the year values behind.

 edgar codd 

this process of selecting the desired attributes from the matching pair is known in the postgres c source code as a  projection  . we “project” a few values from one set of columns to another. (the term  project  is actually much older even than postgres; edgar codd first used it in this context in  a relational model of data for large shared data banks  back in 1970.)

next, postgres calculates a  hash  based on the author string. a hash is some integer value that can be calculated quickly in a repeatable, reproducible way. for the same author string, e.g. “edgar codd,” postgres always calculates the same hash number. as we’ll see in a moment, postgres uses the hash value to decide where to save the author name in the hash table.

you can find postgres’s hash algorithm in a c file called hashfunc.c. even if you’re not a c developer, there are extensive code comments explaining what’s going on, along with a link to  an article written by bob jenkins  , who developed the algorithm in 1997.

("hash_any" method -  view on postgresql.org  )

in my example, postgres passes “edgar codd,” the string value in the author column in the first publication record, to hash_any. the complex bitwise calculations in hash_any step over the characters in edgar’s name and return this hash value:

(stay tuned for  part 2  of this entry.)