Clustered vs Non-Clustered Index: The Table Is the Index in MySQL

An index is a separate, sorted copy of one or more columns that lets the database find rows without reading the whole table, like the index at the back of a book. Both MySQL and PostgreSQL store their indexes as B-trees: a tree of pages, where the top page says which page below it holds which range of values, down to the bottom pages (the leaves) that hold the actual entries. A page is the unit the database reads from disk, 16 KB in InnoDB (MySQL’s storage engine) and 8 KB in PostgreSQL. Reading one row means reading the whole page it is on, so the number of pages a query touches is most of what it costs.

The term clustered index comes from SQL Server, and it means an index whose leaves are the table’s rows themselves, not pointers to them. InnoDB works that way: the table is stored inside its primary key’s B-tree, sorted by the primary key. Since rows can only be stored in one order, a table has exactly one clustered index. Every other index is non-clustered, and its leaves hold a value plus the primary key of the row, which the database then looks up in the clustered index. PostgreSQL has no clustered index at all. Its table is a heap, rows stored roughly in the order they arrived, and every index, the primary key included, points to a row’s physical location.

That difference decides which queries are cheap. Here is the whole post in one table, using a clients-and-assets schema where each client owns about 50 assets:

Every cell is measured below. The PostgreSQL insert times are left out because two different engines inserting through different code paths is not a fair race. The comparison that matters is MySQL against itself, with only the primary key changed.

Every number comes from MySQL 8.4.13 and PostgreSQL 18.6 in Docker with default settings. A clients table has 100,000 rows. An assets table has 5,000,000, each belonging to a random client, so a client’s assets arrive scattered over time, the way real data grows. The timed runs fetch the assets of 1,000 random clients with the container held to 1 GB of memory and 3,000 disk reads per second, roughly the baseline of an AWS gp3 volume, so that pages really come from disk. Page counts are averages over the same 1,000 clients. The test tables were loaded with asset_id values already assigned in increasing order, the order an AUTO_INCREMENT column produces, and the plans below name the test copies (a_by_id, a_by_client, assets_orig).

The clustered index is the table

Here is the table most people would write first, with an auto-increment asset_id as the primary key and an index on client_id for looking up a client’s assets:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

CREATE TABLE assets (
  asset_id    bigint NOT NULL AUTO_INCREMENT,
  client_id   int NOT NULL,
  asset_type  varchar(16) NOT NULL,
  serial      char(16) NOT NULL,
  name        varchar(64) NOT NULL,
  value       decimal(12,2) NOT NULL,
  acquired_at datetime NOT NULL,
  notes       varchar(100) NOT NULL,
  PRIMARY KEY (asset_id),
  KEY assets_client_id_idx (client_id)
);

The MySQL manual says it directly: “Each InnoDB table has a special index called the clustered index that stores row data. Typically, the clustered index is synonymous with the primary key.” So this table is stored sorted by asset_id. New assets get the next id, which puts them at the end, in arrival order. Client 621’s 50 assets were added at 50 different moments over the years, so they sit on 50 different pages, next to whatever other clients’ assets arrived at the same time.

Now fetch one client’s assets:

1

SELECT asset_id, asset_type, name, value FROM assets WHERE client_id = 621;

1

-> Index lookup on a_by_id using assets_client_id_idx (client_id=621)  (cost=55 rows=50) (actual time=0.0522..0.181 rows=50 loops=1)

The plan names one step, but there are two kinds of work hiding in it. assets_client_id_idx is a non-clustered index, and the manual describes what is in it: “each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index.” Its entries for client 621 are 50 pairs of (621, asset_id). To get name and value, InnoDB takes each asset_id and searches the clustered index for it, 50 separate searches that end on 50 different pages. Averaged over 1,000 clients, that was 45 pages read from disk per lookup.

PostgreSQL ends up in the same place by a different road:

1
2
3
4
5
6
7

 Bitmap Heap Scan on assets_orig  (cost=4.83..206.34 rows=51 width=47) (actual time=1.328..7.858 rows=50.00 loops=1)
   Recheck Cond: (client_id = 621)
   Heap Blocks: exact=50
   Buffers: shared hit=8 read=45
   ->  Bitmap Index Scan on assets_orig_client_id_idx  (cost=0.00..4.82 rows=51 width=0) (actual time=0.703..0.704 rows=50.00 loops=1)
         Index Cond: (client_id = 621)
         Buffers: shared read=3

The index on client_id holds 50 row addresses, and Heap Blocks: exact=50 says they pointed to 50 different heap pages. read=45 is the pages that had to come from outside PostgreSQL’s memory. The heap and the auto-increment clustered index have the same problem: both keep rows in arrival order, and this query wants them in client order.

Choose the order: keep a client’s assets together

Since a table gets one clustered index, the decision is which order the rows should be in. Assets belong to clients, and the application mostly reads them client by client: show me this client’s laptops, total this client’s asset value. So the schema is two tables. clients keeps its own simple key, and assets puts client_id first in its primary key:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

CREATE TABLE clients (
  client_id  int NOT NULL,
  name       varchar(32) NOT NULL,
  region     varchar(16) NOT NULL,
  created_at datetime NOT NULL,
  PRIMARY KEY (client_id)
);

CREATE TABLE assets (
  asset_id    bigint NOT NULL AUTO_INCREMENT,
  client_id   int NOT NULL,
  asset_type  varchar(16) NOT NULL,
  serial      char(16) NOT NULL,
  name        varchar(64) NOT NULL,
  value       decimal(12,2) NOT NULL,
  acquired_at datetime NOT NULL,
  notes       varchar(100) NOT NULL,
  PRIMARY KEY (client_id, asset_id),
  UNIQUE KEY assets_asset_id_uq (asset_id)
);

The columns are the same as before, and only the last two lines changed. The primary key is now (client_id, asset_id), so the clustered index sorts rows by client first, and asset_id puts each client’s assets in the order they arrived. Every asset of client 621 ends up next to the others, on one or two pages, wherever in time they were added:

In a real schema assets.client_id would also be a foreign key to clients, and the primary key that starts with client_id already provides the index the foreign key needs. The test tables left the foreign key out, so the insert timings further down do not include that check. asset_id alone is still unique and still auto-increments, and the UNIQUE KEY is not optional. Without it, MySQL 8.4 refuses the table:

1

ERROR 1075 (42000): Incorrect table definition; there can be only one auto column and it must be defined as a key

An AUTO_INCREMENT column has to be the first column of some index, and in the primary key it is second. The same query now reads the clustered index directly:

1

-> Index lookup on a_by_client using PRIMARY (client_id=621)  (cost=6.07 rows=50) (actual time=0.0123..0.0199 rows=50 loops=1)

using PRIMARY means the search went straight into the clustered index, found the first row for client 621, and read forward through the next 49, which were on the same page or the one after it. That was 1.7 pages from disk on average, against 45.

On a disk that allows 3,000 reads a second, every page read costs a third of a millisecond, so the page count turns straight into time: 15.0 ms on average for the default table, 0.53 ms for the one clustered by client. With everything already in memory the gap shrinks to well under a millisecond (0.66 against 0.25 ms in a warm run), which is why this kind of change looks pointless on a laptop (I have dismissed it that way myself) and matters on a server whose data does not fit in memory.

What every other index pays

The clustered key is copied into every non-clustered index, and every lookup through a non-clustered index ends with a search of the clustered index. Changing the primary key changes both.

Look up one asset by its id on the client-clustered table:

1

SELECT client_id, asset_type, name, value FROM assets WHERE asset_id = 4995192;

EXPLAIN shows key: assets_asset_id_uq, the unique index, with type: const, one row. What it does not show is that the unique index only holds asset_id and the primary key (client_id, asset_id). InnoDB finds the entry, reads client_id out of it, and then searches the clustered index for (621, 4995192). Two trees instead of one: 8.4 pages touched per lookup, against 4.0 when asset_id was the primary key. Both are small. A lookup by id is fast either way, and the extra cost only matters for an application that does millions of them.

Size is the other cost. I added an index on acquired_at to both MySQL tables. With asset_id as the primary key, each entry holds a date and an 8-byte id, and the index came to 133 MB. With (client_id, asset_id), each entry also carries the 4-byte client_id, and it came to 162 MB, 22 percent bigger, for the same 6.5 million dates. The manual’s advice follows from that: “If the primary key is long, the secondary indexes use more space, so it is advantageous to have a short primary key.” A 16-byte UUID primary key is copied into every index the same way, which is part of what random UUIDs cost.

PostgreSQL’s indexes store a 6-byte row address no matter what the primary key is, so its acquired_at index was 139 MB whatever the key. Its index on client_id was 34 MB against 149 MB in MySQL, because PostgreSQL (since version 13) stores a repeated value once with a list of row addresses, while InnoDB stores a full (client_id, asset_id) entry for each of the 5 million rows.

The price: every new row goes into the middle

The read numbers above can make the composite key look like the obvious choice. It is not the default. When the table fits in memory, the client lookup went from 0.66 ms to 0.25 ms, and for that the table pays on every insert.

An auto-increment primary key puts every new row at the end of the table, on the last page, which is the cheapest place to write. Clustering by client means a new asset for client 621 has to go into client 621’s page, somewhere in the middle. If that page is full, InnoDB splits it into two half-full pages to make room, which is a page split. I inserted 1.5 million new assets for random clients into both tables, in batches of 10,000. Random clients is the worst case: if most new assets belong to recently created clients, and client_id is itself an auto-increment, the inserts land near the end of the index anyway, which I reasoned through but did not measure.

The first batch was the worst, because the table had just been loaded in sorted order and every page was nearly full, so almost every new row split a page. Once the pages were half empty there was room, and the second batch split far fewer, but it was still three times slower than appending at the end. The table also more than doubled in size, since all those split pages were half empty. OPTIMIZE TABLE rebuilds the table packed again. For InnoDB it runs as online DDL, and the manual says “an exclusive table lock is only taken briefly during the prepare phase and the commit phase”, so reads and writes keep going while it works.

A rebuild can also leave room for the rows that will arrive later. innodb_fill_factor sets how full InnoDB packs each page when it builds or rebuilds an index in sorted order, and the manual notes that even the default of 100 “leaves 1/16 of the space in clustered index pages free for future index growth.” I rebuilt the client-clustered table at three settings and inserted the same 500,000 assets into each:

1
2
3

SET GLOBAL innodb_fill_factor = 70;
ALTER TABLE assets FORCE;          -- OPTIMIZE TABLE rebuilds the same way
SET GLOBAL innodb_fill_factor = 100;

At 70 the new assets fit into the room the rebuild left, and the table stayed the size it started. The client lookup barely noticed the emptier pages: 1.6 to 1.9 pages read from disk, against 1.6 when packed. The space is paid up front instead of after the splits, and it only lasts as long as the room does. These inserts added 10 percent more rows into 30 percent of free space; a table that keeps growing needs the rebuild repeated before the room runs out. innodb_fill_factor is a global setting that applies to every sorted index build on the server, which is why the example sets it back afterwards. (These runs came from a fresh container, so the packed table’s 58.0 s is a little faster than the 65.6 s above. The page splits and sizes matched exactly.)

PostgreSQL: sort it once, or copy the columns into an index

PostgreSQL offers two ways to get close to the client-clustered layout, and neither one is a clustered index.

The first is the CLUSTER command, which rewrites the table sorted by an index:

1

CLUSTER assets USING assets_client_id_idx;

It took 23.5 seconds on 5 million rows, and afterwards one client’s assets came back in 3.1 pages from disk and 1.02 ms under the disk limit, close to MySQL’s client-clustered table. The PostgreSQL documentation is clear about what it is: “Clustering is a one-time operation: when the table is subsequently updated, the changes are not clustered.” New rows still go wherever the heap has room, usually the end. While it runs, CLUSTER holds an ACCESS EXCLUSIVE lock, which “prevents any other database operations (both reads and writes) from operating on the table until the CLUSTER is finished.”

After I added 10 percent more assets, the clustered PostgreSQL table read 4.7 pages per client, and after 30 percent, 14.8 pages and 5.22 ms under the disk limit. The same inserts left MySQL’s client-clustered table at 2.4 pages, since InnoDB put each new asset on its client’s page. That is the trade from the previous section showing up from the other side: InnoDB pays on every insert to keep the order, and PostgreSQL pays nothing on insert and loses the order.

The second option is a covering index, an index that carries the columns the query needs so that the table is never read:

1

CREATE INDEX assets_client_cov ON assets (client_id) INCLUDE (asset_id, asset_type, name, value);

1
2
3
4

 Index Only Scan using assets_orig_cov on assets_orig  (cost=0.56..5.45 rows=51 width=47) (actual time=0.049..0.061 rows=50.00 loops=1)
   Index Cond: (client_id = 621)
   Heap Fetches: 0
   Buffers: shared hit=4 read=4

Index Only Scan with Heap Fetches: 0 means the answer came entirely from the index, whose entries are sorted by client_id, so a client’s 50 entries sit together. It read 1.7 pages from disk and took 0.60 ms, the same as MySQL’s clustered table, and since an index is kept in order on every insert, it does not wear off the way CLUSTER does. It cost a 398 MB index in place of the 34 MB plain one, and it only helps queries that ask for the included columns. Heap Fetches also rises when rows change until VACUUM catches up, which One Column Added to a SELECT measures.

How to choose the clustered key

In MySQL, the primary key is the most important index decision on a table, because it is also the table’s physical order and part of every other index. An auto-increment id is the right default when rows are mostly written once and read one at a time, or in the order they arrived. A composite key that leads with the owner, such as (client_id, asset_id) or (tenant_id, order_id), pays off when the application nearly always reads a parent’s children together and the table does not fit in memory, and it costs slower inserts, a bigger table between rebuilds, and slightly bigger secondary indexes. Rebuilding with innodb_fill_factor below 100 trades some of that size up front for far fewer page splits. Measure the read you care about in pages, not milliseconds on a warm laptop.

In PostgreSQL there is no such choice to make, and the table stays in arrival order. If one access pattern dominates, a covering index gives the clustered read without the decay, at the price of the index’s size. CLUSTER is the one-off option for a table that is mostly read and can be locked for the rewrite.