PostgreSQL for the SQL Server Pro
Dude! Where’s my Clustered Index?!
Heaps of fun ahead!
In the SQL Server world, there are essentially 2 types of disk-based tables: heaps and clustered tables. A clustered table is one where there is a clustered index defined on the table and a heap is a table where there is no clustered index defined.
A clustered index defines the order in which the table is logically (and often times physically) ordered. Logical order is always maintained by the underlying B-tree index structure. The logical ordering ensures you’re always able to quickly look for the values you’re searching for. Physical ordering often matches the logical ordering, but things like page splits from data modifications can result in physical pages not matching the logical order — known as logical fragmentation.
Out in the wild, its very common to see most production tables in SQL Server “having” a clustered index. They’re great for finding rows in the table based on the clustered key and for range lookups for that key since the data is ordered. Below is a simplified graphic of a B-tree clustered index. For a seek, traversal always begins with the root page and the searches conclude once the value is found at the leaf level. Once the searched value is found at the leaf, the rest of the columns for the row are contained at that level. There is no duplication of data — the clustered index IS the table.
Clustered indexes are not a feature that exists in PostgreSQL. All PostgreSQL tables are heap tables. That is a super weird concept if you’re coming from a SQL Server background. Clustered indexes make things faster, so you NEED to have them, right? Well, not so fast.
Note: I am NOT talking about the CLUSTER command in PostgreSQL. CLUSTER physically reorders a table by an index once — it does not maintain the order like a clustered index in SQL Server does.
To understand this a bit better, we are going to have to dig into the weeds a bit. I am going to talk a bit today about how some of PostgreSQL’s Internals work. In the SQL Server world, there has been a ton of blog posts out there that show you how to view page contents using DBCC PAGE and some other internal functions. So I will skip most of that for today’s writing. If you’re interested in more on this, I cover a fair amount of this in an article I wrote while I was at Microsoft. You can view that article here.
Lets begin by starting up our PostgreSQL container we created from this article.
podman start pg-playground
Now lets log into the PostgreSQL instance in the container.
podman exec -it pg-playground psql -U postgres
Lets create a database to run our demos from. Aptly, we will name it heaptables.
create database heaptables;
We will need a tool to help us look at the underlying database structures. pageinspect is similar in concept to SQL Server’s DBCC PAGE. It ships with PostgreSQL and exposes low-level functions that show you the raw byte layout and metadata for blocks (database pages). Also —the extension is available on most major cloud providers, but every function in pageinspect is superuser-only and managed services do not hand you a real superuser, so you’ll likely run into issues trying to run it there.
Note: think of a PostgreSQL extension as something that extends the engine’s functionality — kinda like trace flags in SQL Server. The biggest difference is that there are built-in and community extensions, which is really cool.
create extension if not exists pageinspect;
Now to create a table for the demo.
create table customers(
customerid int generated always as identity,
email text not null,
fullname text not null);
Next we will add a couple of records to the table. (I know, I know - this isn’t 3rd normal form. It will be just fine.)
insert into customers(email,fullname)
values('chapmantim@google.com', 'Tim Chapman'),
('bob@google.com', 'Bobby Tables');
And to finish up with the demo prep, lets put a secondary (non-clustered) index on our heap customers table.
create index idx_customers_email ON customers(email);
Note: secondary indexes in PostgreSQL are, for all intents and purposes, the same as non-clustered indexes in SQL Server. They contain a copy of the data in the underlying table - a copy that is optimized for searching and sorting.
In the following query, I reference the internal/hidden ctid column — which stands for “current tuple id” and it represents the physical location of a row version on disk. It is formatted as (block-number, offset-number).
Get Tim Chapman’s stories in your inbox
Join Medium for free to get updates from this writer.
Note: ctid in PostgreSQL is very similar in concept to passing the value %%physloc%% to the function sys.fn_PhysLocFormatter in SQL Server.
select ctid, * from customers;
This output tells us that both rows are on the same block/page (block 0 in this case) and the offset is the pointer to the row in the table.
In SQL Server, page numbers are unique inside a single file. Each data file (mdf/ndf) is divided into 8KB pages numbered consecutively from 0, and every file starts its own count at 0 again. So a page address has two parts, FileID:PageNumber, as in 1:352. The file ID is what makes the address unique across the database.
A filegroup can hold several files, and SQL Server spreads new allocations across them using proportional fill. So one table’s extents can end up scattered over several files. The Index Allocation Map (IAM) page covers one 4GB interval in one file, and SQL Server links those pages into a chain that records which extents belong to which allocation unit.
PostgreSQL, by contrast, is relation-centric. Every table gets its own underlying file on disk. I’ll say that again - every table (and index) in PostgreSQL gets its own file on disk. A crazy concept for us coming from SQL Server.
Every table in PostgreSQL starts at Block 0. A ctid like (0, 2) does not need a file ID because the block number is already scoped to that specific relation.
In terms of how disk space is allocated, SQL Server allocates 64 KB extents (eight contiguous 8 KB pages) and records their allocation in two bitmaps, GAM and SGAM; a separate structure — the Page Free Space page (PFS), uses one byte per page to track how full each individual page is. PostgreSQL has no concept of extents. It checks the relation’s Free Space Map (_fsm) for room in existing pages. When they’re all full, it extends the file by appending new 8 KB blocks — one at a time in the simple case, or up to 64 at once during bulk inserts.
Once a PostgreSQL table (or index) passes 1 GB in size, the engine splits the physical relation into gigabyte-sized segment files. The first segment keeps the plain relfilenode name; later ones are relfilenode.1, relfilenode.2, and so on. Block numbering stays globally linear across them, so locating a block is integer math — at the default 8 KB block size and 1 GB segment, that’s 131072 blocks per segment:
• Segment File: BlockNumber / 131072
• Byte Offset: (BlockNumber % 131072) * 8192
OK, since I have mentioned them its a good time to talk a bit more about SQL Server's Page Free Space pages and PostgreSQL’s Free Space Map pages as they are very relevant to this discussion today.
When a record is INSERTed into either engine, they need to figure out where that row can fit. In SQL Server that job belongs to Page Free Space (PFS) pages, which live inside the data file itself at page 1 and every 8,088 pages after that. Each PFS page holds one byte for every page it tracks, and that byte does two separate jobs. First it records whether the page is allocated at all, which matters for every object in the database. Second it records roughly how full the page is, in five buckets: empty, 1–50%, 51–80%, 81–95%, and 96–100%. SQL Server only maintains that second job for heap and text/LOB pages, because a B-tree’s insertion point is dictated by the index key rather than by available space. Finding a page is then a two-structure lookup: the IAM chain identifies which extents belong to the allocation unit, and the PFS bytes for those extents say which page has room. If no page in those extents has room, SQL Server allocates a new extent. B-tree indexes use that same lookup whenever they need a new page, such as during a page split.
PostgreSQL does the same work with a Free Space Map (FSM) page, kept it in its own separate file alongside the relation file, named after the filenode with an _fsm suffix. Every heap and index object gets one (except hash indexes), so unlike SQL Server, PostgreSQL tracks free space for B-tree indexes too, which is how whole index pages emptied by VACUUM get recycled (a discussion for a different day). The FSM is a tree of pages, and inside each page the bytes form a binary tree (NOT a B-tree) in which every parent holds the largest free-space value among its children, so the engine navigates from the root straight to a page with enough room. SQL Server splits the operation across two structures — IAM for which extents belong to the object, PFS for whether a page has space — while PostgreSQL folds both into a single searchable tree.
OK, back to demos. Lets next use the bt_page_items PostgreSQL function to dump out the data in the secondary index we created earlier.
SELECT itemoffset, ctid as heap_row_pointer, data
FROM bt_page_items('idx_customers_email', 1);Here we see the index entry offset (itemoffset) and the ctid pointer to where the row exists in the base table (heap). The data column is hex data, which is not terribly useful for our purposes here, so I’ll need to convert it.
We can use this query to do the conversion. There are a couple of ways to do this, but I’ll just show this one today.
WITH items AS (
SELECT itemoffset, ctid, decode(replace(data, ' ', ''), 'hex') AS b
FROM bt_page_items('idx_customers_email', 1)
)
SELECT
itemoffset,
ctid AS heap_row_pointer,
convert_from(substr(b, 2, (get_byte(b, 0) >> 1) - 1), 'UTF8') AS email
FROM items;Now that the conversion is done, we can see the email column as part of the index. We see that the row in the index for chapmantim@google.com is row 2 in the secondary index but points back to row 1 in the heap table.
OK, lets have a look at how these lookups present themselves in a query execution plan. (I’ll dig deep into PostgreSQL execution plans in a future post.) The query below asks for customerid and fullname, neither of which live in idx_customers_email, so PostgreSQL has no choice but to go out to the heap to grab the extra column data. EXPLAIN (ANALYZE, BUFFERS) shows us which plan the engine picked and, more importantly, how many pages it had to touch from disk or memory to get there.
SET enable_seqscan = off;
EXPLAIN (ANALYZE, BUFFERS)
SELECT customerid, email, fullname
FROM customers
WHERE email = 'chapmantim@google.com';I turn sequential scans off before running this, with SET enable_seqscan = off. On a table this small PostgreSQL would likely otherwise skip the index and read the whole table, which breaks my demo. The setting does not ban sequential scans (the docs are clear that suppressing them entirely is impossible), it just prices them high enough that the planner reaches for the index instead. Reset it with RESET enable_seqscan afterward. On a production-sized table you would never need it.
The text based plan is show in the graphic below.
What I want to show in the execution plan is the engine pulling what it can from the secondary index and then going out to the base heap table for the columns the index does not include. In SQL Server that second step is a bookmark lookup — a Key Lookup against the clustered index, or a RID Lookup against a heap (more on this in a minute) and the optimizer implements this with a nested loop operator. These are very common to see and they can be very expensive.
Scanning a table is a fixed cost - all of the pages in the table are read once. A lookup is iterative, once per qualifying row, and past a certain point that iteration costs dramatically more than just reading the entire table. The optimizer knows this and will abandon your index seek for a scan once it estimates enough rows coming back. My good friend Kimberly Tripp named this the tipping point, and it arrives at a far smaller fraction of the table than most people expect. Alas, this is not a chat about SQL Server performance tuning.
In the PostgreSQL execution plan above, the Index Scan using idx_customers_email on customers is doing the seek and the lookup together. The Index Cond is the seek half, where the engine walks the B-tree for idx_customers_email down to leaf block 1 and finds the entry for ‘chapmantim@google.com’. That is the row you already saw with bt_page_items at itemoffset 2, and sitting right beside the key, ctid = (0,1). The ctid is a physical address: block 0, line pointer 1. Since customerid and fullname are not in the index, the engine follows that address into the heap, reads line pointer 1 out of the array just past the page header, and pulls the row. Same node, no second operator.
Buffers counts the pages PostgreSQL had to touch to answer the query. Here shared hit=2: PostgreSQL touched two pages, and found both already sitting in shared_buffers (similar in concept to SQL Server's buffer pool), so it never had to ask the operating system for either one. No physical reads at all. One page was the index leaf holding the key and the ctid. The other was heap block 0 holding the row. That is the entire cost of the lookup. Note that the plan reports a total, not a breakdown.
So why is PostgreSQL fine without clustered indexes? Look again at what that lookup actually costs. In SQL Server, every non-clustered index stores the clustered key as its row locator, so a Key Lookup is a second B-tree traversal — root to intermediate to leaf — just to reach the row. PostgreSQL stored a ctid instead, which is a physical address. Block 0, line pointer 1. There is no tree to walk. The engine reads the block and takes the row.
Note: when a table in SQL Server is a heap, the semantics for record lookups is very similar to how it works in PostgreSQL. A non-clustered index on a heap stores a RID — FileID:PageID:SlotID — and the lookup jumps straight to that physical address with no second B-tree traversal. A ctid does the same job, minus the file number, since PostgreSQL scopes block numbers to the relation.
As with everything with computing, there is a trade-off. In SQL Server that row locator is static — as long as the clustered key values do not change, the non-clustered indexes never notice. A ctid is a physical address, and it is only good for one version of the row. PostgreSQL never updates in place — every UPDATE writes a new version of the row at a new ctid and leaves the old one sitting there for any transaction still entitled to read it. A new ctid means every index on the table needs a new entry, including indexes on columns your UPDATE never touched. That is what you trade for skipping the second B-tree traversal. (MVCC is getting its own post. There is a lot going on down there.)
PostgreSQL does have an optimization called Heap-Only Tuple (HOT), which skips the index writes entirely when the table update doesn’t touch any indexed columns and the new version fits on the same page.
The other trade-off is that giving up guaranteed physical ordering costs you on range scans. In exchange, every index is the same kind of index. There is no key to choose that decides how the table is ordered, and no wide clustered key getting copied into every secondary index. When you do need a covering index, PostgreSQL gives you INCLUDE columns and index-only scans. When you really do want physical order, CLUSTER will do a one-time pass — just remember it takes an exclusive lock and rewrites the table, so it is a maintenance-window job, not a tuning knob.
Wrapping Up
Today we dug into PostgreSQL’s lack of Clustered Index and why it is OK that they do not have them. Every table is a heap, every row has a physical address, and every index points at that address the same way.
That does not mean there is nothing left to tune. It means the tuning moved somewhere else, to covering indexes, to VACUUM, and to the free space map doing its job. We will get into all of that in future articles.
Thanks for reading!
