PostgreSQL Cluster Bootstrap — initdb, the Bootstrap Backend, and genbki

Contents:

• Theoretical Background
• Common DBMS Design
• PostgreSQL’s Approach
• Source Walkthrough
• Source verification (as of 2026-06-05)
• Beyond PostgreSQL — Comparative Designs & Research Frontiers
• Sources

Theoretical Background

Every relational database is self-describing: the schema of every table is itself stored in tables (the system catalogs). pg_class lists every relation; pg_attribute lists every column of every relation; pg_type lists every type; and so on. This recursion is elegant for runtime — a generic tuple-access routine can read any table, including a catalog — but it poses a chicken-and-egg problem at creation time. To insert a row into pg_class you need a tuple descriptor for pg_class; that descriptor is built from pg_attribute rows; but those pg_attribute rows are themselves stored in pg_attribute, which does not yet exist. The very first catalogs must be conjured into being by code that does not read the catalogs, because there is nothing to read yet.

This is the bootstrap problem, and it is structurally identical to the compiler-bootstrapping problem (you cannot compile the compiler with the compiler the first time) and to OS boot loaders (the loader cannot be loaded by the thing it loads). The classic resolution is a two-stage strategy: a small, special-purpose loader written against hard-wired, compiled-in knowledge of the most primitive structures brings the system to a point where it becomes self-sustaining, after which the normal, general machinery takes over.

Database System Concepts (Silberschatz et al.) frames the data dictionary / system catalog as “metadata — data about data” and notes that “the relations representing the data dictionary themselves form a recursive structure” that the storage manager must be able to read with the same code it uses for ordinary relations. The System R design (Astrahan et al. 1976) is the lineage PostgreSQL inherits: System R stored its catalogs as ordinary relations accessible to the same RSS (Research Storage System) interface used for user data, and likewise needed a special routine to lay down the catalog-of-catalogs first.

PostgreSQL also faces a second axis of the problem that pure runtime systems do not: the catalog contents (which built-in types, functions, operators, and access methods exist) are an enormous, hand-maintained data set that must be kept consistent with C code — e.g. the OID of int4’s input function must be the same constant the C type machinery compiles against. PostgreSQL solves this with build-time code generation: a Perl program (genbki.pl) reads the same pg_*.h / pg_*.dat source files that define the catalog schema and initial data, and emits both (a) a flat, position-free initialization script (postgres.bki) consumed at cluster-creation time, and (b) a fan-out of C headers (pg_*_d.h, schemapg.h, syscache_info.h, …) compiled into the backend so the OIDs agree on both sides. The single source of truth is the .h/.dat pair; everything downstream is derived.

Three design properties characterise the whole pipeline:

1. Hard-wired primitives. A minimal set of types (bool, int4, oid, name, …) and their I/O function OIDs is compiled into the bootstrap backend so the first heaps can be formed before pg_type is readable.
2. Declarative initialization, imperative interpretation. The catalog data is declarative (.dat files); genbki.pl flattens it into a tiny imperative command stream (BKI) that a 6-keyword interpreter executes in order.
3. Phase escalation. Cluster creation climbs from “no catalogs” → “raw bootstrap backend speaking BKI” → “ordinary standalone backend speaking SQL” → “three real databases (template1, template0, postgres)”.

Common DBMS Design

This section names the engineering patterns shared by most self-describing DBMSs, so PostgreSQL’s specifics read as choices within a known space.

A compiled-in description of the catalog-of-catalogs

Because the catalog schema cannot be read from the catalog during the first insert, every self-describing engine compiles a description of its most primitive relations directly into the executable. In PostgreSQL this is the schemapg.h mechanism (the Schema_pg_class, Schema_pg_attribute macros) plus a small hard-wired TypInfo[] table in the bootstrap backend. The relcache’s formrdesc() uses these compiled descriptors to “nail” a handful of catalogs into cache without reading disk.

A separate, restricted load language

Loading the seed data through the full SQL parser/planner/executor would require those subsystems to already be functional against catalogs that do not yet exist. The universal escape is a stripped-down load language that bypasses SQL: it has no expressions, no joins, no transactions beyond “do everything in one”, and a one-to-one correspondence between a command and a low-level storage operation. PostgreSQL’s BKI (“Backend Interface”) language is exactly this — create, open, insert, declare index, build indices, close — each mapping to one heap_create / heap_insert / DefineIndex call.

Build-time generation of the seed from a single source

To avoid drift between “the C struct that describes a catalog” and “the rows that initialise that catalog”, mature systems generate the load script from the same source that defines the structs. PostgreSQL’s genbki.pl reads the CATALOG(...) annotations in pg_*.h and the rows in pg_*.dat, resolves symbolic references (a function named boolin → its OID) via lookup tables it builds from the same data, and emits both the BKI and the matching pg_*_d.h OID macros.

Template databases as a copy-on-create prototype

Rather than running the expensive seed process once per new database, production engines build a prototype database and physically copy it to create new ones. PostgreSQL bootstraps exactly one database (template1), then issues CREATE DATABASE template0 ... STRATEGY = file_copy and CREATE DATABASE postgres ... — CREATE DATABASE foo TEMPLATE template1 later clones the same prototype for users. template0 is a pristine, connection-locked copy kept as a recovery baseline.

A relation mapper for relations whose location is itself catalog data

There is a deeper recursion: the physical file backing pg_class is normally found by reading pg_class.relfilenode — but you cannot read pg_class to find pg_class. Engines break this with an out-of-band relation map: a tiny flat file (global/pg_filenode.map, base/<db>/pg_filenode.map) mapping the OIDs of “mapped” (nailed) catalogs to their file numbers. The bootstrap backend writes this file last, via RelationMapFinishBootstrap().

flowchart TD
  A["pg_*.h catalog headers<br/>(CATALOG macro = schema)"] --> G["genbki.pl<br/>(build time)"]
  B["pg_*.dat data files<br/>(initial rows)"] --> G
  G --> BKI["postgres.bki<br/>(flat command stream)"]
  G --> H["pg_*_d.h / schemapg.h<br/>syscache_info.h / system_fk_info.h<br/>(compiled into backend)"]
  G --> SQL["system_constraints.sql<br/>(PK/UNIQUE constraints)"]
  BKI --> I["initdb (--boot backend)<br/>BKI interpreter"]
  H --> I
  I --> T1["template1<br/>(seeded catalogs on disk)"]
  T1 --> POST["standalone backend<br/>runs SQL post-bootstrap"]
  POST --> T0["template0 (file_copy)"]
  POST --> PG["postgres (file_copy)"]

PostgreSQL’s Approach

PostgreSQL splits cluster birth across two binaries and three phases. initdb (a frontend program in src/bin/initdb/) is the orchestrator: it never touches catalogs directly. It lays out the directory tree, writes config files, and then spawns the backend twice — once in bootstrap mode to consume postgres.bki, once in ordinary standalone mode to run SQL.

Phase 0 — genbki at build time

Long before any cluster exists, the build runs genbki.pl over every catalog header. Its core loop walks each catalog, emits a create command followed by insert commands for the seed rows, and resolves symbolic OID references. The crucial trick is that OID synonyms in .dat files (writing proname => 'boolin' instead of a raw number) are resolved against lookup tables built from the same data set:

# genbki.pl — src/backend/catalog/genbki.pl
# procedure OID lookup
my %procoids;
foreach my $row (@{ $catalog_data{pg_proc} })
{
    my $prokey = $row->{proname};
    if (defined $procoids{$prokey})
        { $procoids{$prokey} = 'MULTIPLE'; }
    else
        { $procoids{$prokey} = $row->{oid}; }
    # ... also proname(argtypes) ...
}

When a column carries a BKI_LOOKUP(pg_proc) annotation, genbki.pl substitutes the looked-up OID into the emitted insert:

# genbki.pl — the per-column substitution in the catalog emit loop
if ($column->{lookup})
{
    my $lookup = $lookup_kind{ $column->{lookup} };
    # ... oidvector / _oid / scalar cases ...
    $lookupnames[0] = $bki_values{$attname};
    @lookupoids = lookup_oids($lookup, $catname, $attname, $lookup_opt,
                              \%bki_values, @lookupnames);
    $bki_values{$attname} = $lookupoids[0];
}

pg_attribute is special — its rows are not in a .dat file; they are derived from the schema of every other catalog. gen_pg_attribute() walks each catalog’s columns, copies type metadata from pg_type, and for bootstrap catalogs also emits the six system columns (ctid, xmin, cmin, xmax, cmax, tableoid) so the interpreter can build a complete pg_attribute heap:

# gen_pg_attribute — src/backend/catalog/genbki.pl
my @SYS_ATTRS = (
    { name => 'ctid', type => 'tid' },
    { name => 'xmin', type => 'xid' },
    { name => 'cmin', type => 'cid' },
    { name => 'xmax', type => 'xid' },
    { name => 'cmax', type => 'cid' },
    { name => 'tableoid', type => 'oid' });
foreach my $attr (@SYS_ATTRS)
{
    $attnum--;
    my %row;
    $row{attnum} = $attnum;
    $row{attrelid} = $table->{relation_oid};
    morph_row_for_pgattr(\%row, $schema, $attr, 1);
    print_bki_insert(\%row, $schema);
}

Auto-assigned OIDs (rows without an explicit oid =>) are handed out from a reserved band, [FirstGenbkiObjectId, FirstUnpinnedObjectId), per catalog:

# assign_next_oid — src/backend/catalog/genbki.pl
$GenbkiNextOids{$catname} = $FirstGenbkiObjectId
  if !defined($GenbkiNextOids{$catname});
my $result = $GenbkiNextOids{$catname}++;
die "genbki OID counter for $catname ... overrunning FirstUnpinnedObjectId\n"
  if $result >= $FirstUnpinnedObjectId;

The first line of the emitted BKI is a version marker (# PostgreSQL 18); the last command is always build indices. Constraints that cannot be expressed in BKI (primary keys, uniqueness) are emitted to a separate system_constraints.sql for the later SQL phase.

Phase 1 — initdb lays out the directory and runs the bootstrap backend

initialize_data_directory() is the top-level driver. It creates the directory skeleton, writes the cluster-wide PG_VERSION, tests and writes config files, then calls bootstrap_template1():

// initialize_data_directory — src/bin/initdb/initdb.c
create_data_directory();
create_xlog_or_symlink();
/* ... mkdir each of subdirs[] ... */
write_version_file(NULL);          /* top-level PG_VERSION */
set_null_conf();
test_config_settings();
setup_config();
bootstrap_template1();             /* <-- runs the --boot backend */
write_version_file("base/1");      /* template1's per-db PG_VERSION */

bootstrap_template1() reads the build-time postgres.bki, checks its version header against PG_MAJORVERSION, substitutes a handful of platform/locale tokens that genbki deliberately left as placeholders (NAMEDATALEN, SIZEOF_POINTER, FLOAT8PASSBYVAL, ENCODING, LC_COLLATE, …), then pipes the whole script into a freshly spawned postgres --boot process:

// bootstrap_template1 — src/bin/initdb/initdb.c
bki_lines = readfile(bki_file);
if (strcmp(headerline, *bki_lines) != 0)   /* "# PostgreSQL <ver>\n" */
    { pg_log_error("input file \"%s\" does not belong to PostgreSQL %s", ...); exit(1); }
bki_lines = replace_token(bki_lines, "NAMEDATALEN", buf);
bki_lines = replace_token(bki_lines, "FLOAT8PASSBYVAL", FLOAT8PASSBYVAL ? "true" : "false");
bki_lines = replace_token(bki_lines, "ENCODING", encodingid_to_string(encodingid));
/* ... */
printfPQExpBuffer(&cmd, "\"%s\" --boot %s %s", backend_exec, boot_options, extra_options);
PG_CMD_OPEN(cmd.data);
for (line = bki_lines; *line != NULL; line++)
    PG_CMD_PUTS(*line);            /* feed each BKI line to the backend's stdin */
PG_CMD_CLOSE();

The token substitution happens here, in initdb.c, not in genbki.pl, and the reason is a deliberate boundary: genbki may only bake in things constant across a release (fixed OIDs); anything platform- or configuration-dependent (pointer size, encoding, locale) must be filled in at cluster-creation time when the actual target environment is known.

Phase 2 — the bootstrap backend interprets BKI

BootstrapModeMain() is the backend’s entry when argv[1] is --boot. It runs as a standalone single process — no postmaster, no shared-memory children speaking a protocol — sets BootstrapProcessing mode, turns off system-index use, lays down the WAL with BootStrapXLOG(), then drives a flex/bison parser over the BKI on stdin:

// BootstrapModeMain — src/backend/bootstrap/bootstrap.c
Assert(!IsUnderPostmaster);
InitStandaloneProcess(argv[0]);
/* ... getopt over "B:c:d:D:Fkr:X:-:" ... */
SetProcessingMode(BootstrapProcessing);
IgnoreSystemIndexes = true;
/* ... shared mem, InitProcess, BaseInit ... */
BootStrapXLOG(bootstrap_data_checksum_version);
InitPostgres(NULL, InvalidOid, NULL, InvalidOid, 0, NULL);
/* ... */
StartTransactionCommand();
boot_yyparse(scanner);             /* the BKI interpreter loop */
CommitTransactionCommand();
RelationMapFinishBootstrap();      /* write pg_filenode.map */

The grammar has exactly the keywords emitted by genbki. A create ... bootstrap for a nailed catalog goes through heap_create() directly (building the file but not cataloguing it — it is already in pg_class’s seed data); a non-bootstrap create goes through the full heap_create_with_catalog():

// Boot_CreateStmt — src/backend/bootstrap/bootparse.y
mapped_relation = ($4 || shared_relation);   /* $4 = optbootstrap */
if ($4)
    boot_reldesc = heap_create($2, PG_CATALOG_NAMESPACE,
                               shared_relation ? GLOBALTABLESPACE_OID : 0,
                               $3, InvalidOid, HEAP_TABLE_AM_OID, tupdesc,
                               RELKIND_RELATION, RELPERSISTENCE_PERMANENT,
                               shared_relation, mapped_relation, true,
                               &relfrozenxid, &relminmxid, true);
else
    id = heap_create_with_catalog($2, PG_CATALOG_NAMESPACE, ...);

Each insert ( ... ) becomes a heap_insert into the currently open relation. The interpreter holds at most one open relation (boot_reldesc); the genbki output therefore interleaves open/insert*/close for ordinary catalogs, while bootstrap catalogs are implicitly opened by their create bootstrap. Index creation is declared (queued) during the scan and built once at the very end by build indices, because the index relations themselves need pg_class/pg_attribute rows that are only complete after all inserts.

flowchart TD
  S["boot_yyparse over postgres.bki"] --> C{command?}
  C -->|create bootstrap| HC["heap_create<br/>nailed/mapped catalog"]
  C -->|create| HCC["heap_create_with_catalog"]
  C -->|open name| OR["boot_openrel<br/>set boot_reldesc<br/>(populate Typ from pg_type)"]
  C -->|insert| IT["InsertOneValue x N<br/>then InsertOneTuple<br/>= heap_insert"]
  C -->|declare index| DI["index_register<br/>(queued, skip_build)"]
  C -->|close| CL["closerel"]
  C -->|build indices| BI["build_indices<br/>(index_build each queued)"]
  BI --> END["CommitTransactionCommand<br/>RelationMapFinishBootstrap"]

Anatomy of postgres.bki

It helps to see what genbki actually emits. The file is line-oriented; # introduces a comment (the scanner drops everything after it), _null_ is the single reserved word, and identifiers match [-A-Za-z0-9_]+ with anything else single-quoted. A bootstrap catalog like pg_type comes out roughly as:

// shape of postgres.bki emitted by genbki.pl (illustrative, condensed)
# PostgreSQL 18
create pg_type 1247 bootstrap rowtype_oid 71
 (
 oid = oid ,
 typname = name ,
 typlen = int2 ,
 typbyval = bool ,
 ...
 typinput = regproc ,
 typoutput = regproc ,
 ...
 )
insert ( 16 bool 1 't' ... boolin boolout ... )
insert ( 17 bytea -1 'f' ... byteain byteaout ... )
...
close pg_type

Several things are worth noting against the scanner/parser. The keyword bootstrap after the OID marks this as a nailed/mapped catalog (the optbootstrap production), so the interpreter uses heap_create and does not try to insert a pg_class row for it — that row is itself one of the seed inserts into pg_class. The regproc columns in the schema show why genbki’s lookup machinery matters: the .dat file wrote typinput => 'boolin', and genbki rewrote it to the function name boolin, which the bootstrap backend’s regprocin (or the Typ/TypInfo escalation) resolves to an OID at insert time. Tokens like FORCE NOT NULL / FORCE NULL (from a column’s BKI_FORCE_NOT_NULL annotation) let genbki override the automatic nullability inference. Non-bootstrap catalogs additionally get an explicit open <catname> / close <catname> pair around their inserts, since they are not auto-opened by a create bootstrap.

The keyword set is genuinely tiny — the scanner recognises only open, close, create, OID, bootstrap, shared_relation, rowtype_oid, insert, _null_, declare, build, indices, unique, index, on, using, toast, FORCE, NOT, NULL, plus punctuation. There is no arithmetic, no string concatenation, no conditional. That austerity is the whole point: the interpreter must run before the SQL engine is usable, so it can afford to know nothing but “make a heap, stuff tuples into it, queue an index, build the queue.”

The hard-wired type table and the Typ escalation

Before pg_type exists on disk, the interpreter still has to know the on-disk width, alignment, and I/O functions of the column types used in the bootstrap catalogs. Those are compiled in as TypInfo[]:

// TypInfo[] — src/backend/bootstrap/bootstrap.c
static const struct typinfo TypInfo[] = {
    {"bool", BOOLOID, 0, 1, true, TYPALIGN_CHAR, TYPSTORAGE_PLAIN, InvalidOid,
     F_BOOLIN, F_BOOLOUT},
    {"int4", INT4OID, 0, 4, true, TYPALIGN_INT, TYPSTORAGE_PLAIN, InvalidOid,
     F_INT4IN, F_INT4OUT},
    {"name", NAMEOID, CHAROID, NAMEDATALEN, false, TYPALIGN_CHAR, TYPSTORAGE_PLAIN,
     C_COLLATION_OID, F_NAMEIN, F_NAMEOUT},
    /* ... oid, regproc, text, _oid, _text, ... */
};

DefineAttr() consults this table while a catalog is being created. The moment the first open command runs, boot_openrel() notices pg_type now has rows and escalates: it reads pg_type into the in-memory Typ list, after which type lookups go through the real catalog rather than the compiled table:

// boot_openrel — src/backend/bootstrap/bootstrap.c
/* pg_type must be filled before any OPEN command is executed, hence we
 * can now populate Typ if we haven't yet. */
if (Typ == NIL)
    populate_typ_list();
/* ... */
boot_reldesc = table_openrv(makeRangeVar(NULL, relname, -1), NoLock);

gettype() embodies the escalation explicitly: while Typ == NIL it returns an index into TypInfo[]; once Typ is loaded it returns a real OID and sets the global Ap to the matching row. Callers must check which regime they are in — a deliberately “really ugly” interface the source comments flag as such.

Phase 3 — the standalone backend finishes the job in SQL

The bootstrap backend produces only the seed catalogs of template1. Most of the system — views, the pg_* SQL functions, descriptions, collations, privileges, information_schema, PL/pgSQL, and the other two databases — is created by a second backend invocation, this time an ordinary standalone backend (postgres ... template1) reading SQL on stdin. initialize_data_directory() opens it and replays a sequence of SQL files and generated statements:

// initialize_data_directory (post-bootstrap) — src/bin/initdb/initdb.c
printfPQExpBuffer(&cmd, "\"%s\" %s %s template1 >%s",
                  backend_exec, backend_options, extra_options, DEVNULL);
PG_CMD_OPEN(cmd.data);
setup_auth(cmdfd);                              /* REVOKE on pg_authid */
setup_run_file(cmdfd, system_constraints_file); /* PK/UNIQUE from genbki */
setup_run_file(cmdfd, system_functions_file);
setup_depend(cmdfd);                            /* pg_stop_making_pinned_objects */
setup_run_file(cmdfd, system_views_file);
setup_description(cmdfd);
setup_collation(cmdfd);
setup_run_file(cmdfd, dictionary_file);
setup_privileges(cmdfd);
setup_schema(cmdfd);                            /* information_schema */
load_plpgsql(cmdfd);                            /* CREATE EXTENSION plpgsql */
vacuum_db(cmdfd);                               /* ANALYZE; VACUUM FREEZE */
make_template0(cmdfd);
make_postgres(cmdfd);

setup_depend() calls pg_stop_making_pinned_objects() — the pivot after which newly created objects are not pinned (i.e. they become DBA-droppable). Everything created before that point is a pinned, undroppable part of the system. make_template0() clones template1:

// make_template0 — src/bin/initdb/initdb.c
PG_CMD_PUTS("CREATE DATABASE template0 IS_TEMPLATE = true ALLOW_CONNECTIONS = false"
            " OID = " CppAsString2(Template0DbOid)
            " STRATEGY = file_copy;\n\n");
PG_CMD_PUTS("UPDATE pg_database SET datcollversion = NULL WHERE datname = 'template0';\n\n");
PG_CMD_PUTS("REVOKE CREATE,TEMPORARY ON DATABASE template0 FROM public;\n\n");
PG_CMD_PUTS("COMMENT ON DATABASE template0 IS 'unmodifiable empty database';\n\n");

template0 is given a fixed OID (so pg_upgrade can preserve database OIDs), is marked IS_TEMPLATE and ALLOW_CONNECTIONS = false, and has its datcollversion cleared so that databases cloned from it skip collation version checks. make_postgres() similarly clones the default postgres database with a fixed OID. Both use STRATEGY = file_copy because the checkpoints initdb triggers are cheap and wal_log would only bloat the WAL and the new cluster. (Database-creation strategy and the physical clone mechanics belong to a separate analysis — see cross-references below.)

The catalog contents and the schema-macro / syscache fan-out that genbki also emits are detailed in postgres-system-catalogs.md; the postmaster side of how the running server later forks per-connection backends is in postgres-postmaster.md. This document stays on the cluster-birth path.

Source Walkthrough

The pipeline spans one build-time Perl script, one frontend C program, and one backend C program with its flex/bison front end. Symbols below are grouped by the three phases; line numbers are in the position-hint table at the end (they decay; the symbol names are the durable anchors).

genbki.pl — build-time code generation

• %lookup_kind — the master dispatch table mapping a BKI_LOOKUP kind (pg_proc, pg_type, pg_operator, encoding, …) to the per-catalog OID hash built earlier in the script. The %procoids, %typeoids, %operoids, %classoids, %collationoids (and a dozen more) hashes are populated by walking $catalog_data{pg_*}.
• the main foreach my $catname (@catnames) loop — for each catalog: opens a pg_<cat>_d.h, emits relation/rowtype/index/toast OID #defines and Anum_* / Natts_* macros, writes the create <cat> BKI command with its column list, then for each data row performs lookup-substitution and calls print_bki_insert.
• gen_pg_attribute — synthesises pg_attribute rows from every other catalog’s schema (user columns + the six system columns for bootstrap catalogs) and accumulates schemapg.h entries via %schemapg_entries / @tables_needing_macros.
• morph_row_for_pgattr — copies pg_type metadata (attlen, attbyval, attalign, attstorage) into a synthesised pg_attribute row and computes attnotnull using the same fixed-width/prior-column rule that DefineAttr() uses at runtime (the two must agree).
• print_bki_insert — formats one insert ( ... ) line, doubling single quotes and quoting any value containing characters outside the bootstrap scanner’s [-A-Za-z0-9_]+ id pattern.
• lookup_oids — resolves a list of OID-synonym names against a lookup hash; warns and increments $num_errors on an unresolved or illegal-zero reference (this is how a typo in a .dat file fails the build).
• assign_next_oid — hands out auto OIDs per catalog from FirstGenbkiObjectId, dying if it would reach FirstUnpinnedObjectId.
• form_pg_type_symbol — derives the FOOOID / FOOARRAYOID macro name from a pg_type row’s typname.
• trailer emission — after all catalogs: the queued @toast_decls and @index_decls are printed, then the literal build indices, then the separate output files schemapg.h, system_fk_info.h, system_constraints.sql, syscache_ids.h, syscache_info.h are completed and atomically renamed via Catalog::RenameTempFile.

initdb.c — frontend orchestration

• main → setup_data_file_paths / setup_bin_paths locate the postgres backend and postgres.bki; initialize_data_directory is the phase driver.
• subdirs[] — the static list of directories mkdir’d under PGDATA (global, base, base/1, pg_wal/*, pg_xact, pg_multixact/*, …).
• write_version_file — writes PG_VERSION (cluster-level with extrapath == NULL, then base/1 for template1). The bootstrapper checks the cluster-level file, so it is created first.
• set_null_conf / test_config_settings / setup_config — probe a workable shared_buffers/max_connections pair with a throwaway backend, then write postgresql.conf, pg_hba.conf, pg_ident.conf.
• bootstrap_template1 — the Phase-1 driver: reads postgres.bki, version-checks its header against PG_MAJORVERSION, applies the replace_token substitutions (NAMEDATALEN, SIZEOF_POINTER, ALIGNOF_POINTER, FLOAT8PASSBYVAL, POSTGRES, ENCODING, LC_COLLATE, LC_CTYPE, DATLOCALE, ICU_RULES, LOCALE_PROVIDER), and pipes the result to postgres --boot.
• PG_CMD_OPEN / PG_CMD_PUTS / PG_CMD_CLOSE / PG_CMD_PRINTF — the macro family that popens a backend, feeds it lines, and checks the exit status; used by both the bootstrap and standalone phases.
• the post-bootstrap block in initialize_data_directory — opens the standalone backend and calls, in order: setup_auth, setup_run_file(system_constraints_file), setup_run_file(system_functions_file), setup_depend, setup_run_file(system_views_file), setup_description, setup_collation, setup_run_file(dictionary_file), setup_privileges, setup_schema, load_plpgsql, vacuum_db, make_template0, make_postgres.
• setup_depend — emits SELECT pg_stop_making_pinned_objects(), the pinned/unpinned watershed.
• make_template0 / make_postgres — CREATE DATABASE with fixed OIDs (Template0DbOid, PostgresDbOid) and STRATEGY = file_copy.

bootstrap.c + bootparse.y — the BKI interpreter

• BootstrapModeMain — backend entry for --boot / --check: sets up a standalone process, BootstrapProcessing mode, IgnoreSystemIndexes, shared memory, BootStrapXLOG, InitPostgres, then boot_yyparse, commit, and RelationMapFinishBootstrap.
• CheckerModeMain — the --check early-exit path: proves shared memory and semaphores can be created under the given GUCs, then exits.
• Boot_CreateStmt (bootparse.y) — dispatches create to heap_create (bootstrap/mapped catalog) or heap_create_with_catalog (ordinary catalog), setting mapped_relation for nailed/shared rels.
• boot_openrel — implements open: lazily populates Typ from pg_type, closes any prior open relation, table_openrvs the named one, and snapshots its attribute descriptors into attrtypes[].
• DefineAttr — implements one <name = type> column in a create, filling attlen/attbyval/attalign/attstorage from either TypInfo (pre-pg_type) or the loaded Typ list, and forcing C collation on collation-aware system columns.
• InsertOneValue / InsertOneNull / InsertOneTuple — implement insert: convert each field via its type’s input function (boot_get_type_io_data + OidInputFunctionCall), then heap_form_tuple + simple_heap_insert.
• gettype / populate_typ_list / boot_get_type_io_data — the TypInfo[]→Typ escalation machinery.
• Boot_DeclareIndexStmt / Boot_DeclareUniqueIndexStmt / index_register — implement declare index: build an IndexStmt, DefineIndex(... skip_build = true), and queue the index on ILHead.
• Boot_DeclareToastStmt — implements declare toast via BootstrapToastTable.
• Boot_BuildIndsStmt / build_indices — implement build indices: walk the queued ILHead list and index_build each, now that all heap data (including the indexes’ own catalog rows) is present.

Position hints (as of 2026-06-05, REL_18 273fe94)

Symbol	File	Line
%lookup_kind dispatch table	src/backend/catalog/genbki.pl	415
main foreach my $catname (@catnames) emit loop	src/backend/catalog/genbki.pl	466
print $bki "build indices\n" (trailer)	src/backend/catalog/genbki.pl	719
gen_pg_attribute	src/backend/catalog/genbki.pl	858
morph_row_for_pgattr	src/backend/catalog/genbki.pl	939
print_bki_insert	src/backend/catalog/genbki.pl	994
lookup_oids	src/backend/catalog/genbki.pl	1077
form_pg_type_symbol	src/backend/catalog/genbki.pl	1116
assign_next_oid	src/backend/catalog/genbki.pl	1138
subdirs[]	src/bin/initdb/initdb.c	231
PG_CMD_OPEN / PG_CMD_PUTS macros	src/bin/initdb/initdb.c	319
write_version_file	src/bin/initdb/initdb.c	1024
bootstrap_template1	src/bin/initdb/initdb.c	1545
setup_depend	src/bin/initdb/initdb.c	1716
setup_run_file	src/bin/initdb/initdb.c	1729
make_template0	src/bin/initdb/initdb.c	2011
make_postgres	src/bin/initdb/initdb.c	2065
initialize_data_directory	src/bin/initdb/initdb.c	3044
main	src/bin/initdb/initdb.c	3158
TypInfo[]	src/backend/bootstrap/bootstrap.c	87
CheckerModeMain	src/backend/bootstrap/bootstrap.c	180
BootstrapModeMain	src/backend/bootstrap/bootstrap.c	198
boot_openrel	src/backend/bootstrap/bootstrap.c	440
DefineAttr	src/backend/bootstrap/bootstrap.c	522
InsertOneTuple	src/backend/bootstrap/bootstrap.c	629
InsertOneValue	src/backend/bootstrap/bootstrap.c	657
populate_typ_list	src/backend/bootstrap/bootstrap.c	726
gettype	src/backend/bootstrap/bootstrap.c	766
boot_get_type_io_data	src/backend/bootstrap/bootstrap.c	837
index_register	src/backend/bootstrap/bootstrap.c	932
build_indices	src/backend/bootstrap/bootstrap.c	982
Boot_CreateStmt	src/backend/bootstrap/bootparse.y	157
Boot_InsertStmt	src/backend/bootstrap/bootparse.y	254
Boot_DeclareIndexStmt	src/backend/bootstrap/bootparse.y	273
Boot_DeclareToastStmt	src/backend/bootstrap/bootparse.y	379
Boot_BuildIndsStmt	src/backend/bootstrap/bootparse.y	391

Source verification (as of 2026-06-05)

Claims in this document were checked against the REL_18_STABLE tree at commit 273fe94. Spot checks worth recording:

• Two backend invocations, one frontend. initialize_data_directory calls bootstrap_template1 (which spawns postgres --boot) and then separately PG_CMD_OPENs a postgres ... template1 standalone backend for the SQL phase. Confirmed: the two printfPQExpBuffer(&cmd, ...) call sites differ by the --boot flag (bootstrap_template1) vs. plain backend_options (the post-bootstrap block). Verified at initdb.c lines ~1612 and ~3112.

• BKI keyword set is exactly six command shapes. bootparse.y’s Boot_Query alternatives are Boot_OpenStmt, Boot_CloseStmt, Boot_CreateStmt, Boot_InsertStmt, Boot_DeclareIndexStmt / Boot_DeclareUniqueIndexStmt, Boot_DeclareToastStmt, Boot_BuildIndsStmt. The matching scanner tokens in bootscanner.l (open, close, create, insert, declare, build, indices, index, unique, toast, on, using) confirm there is no general-purpose computation in BKI. Verified.

• pg_attribute has no .dat file; its rows are generated. genbki’s catalog loop special-cases if ($catname eq 'pg_attribute') { gen_pg_attribute($schema); } rather than iterating a $catalog_data{pg_attribute}. The six system columns are appended only for $table->{bootstrap} catalogs. Verified at genbki.pl lines ~583 and ~908.

• Token substitution is in initdb, not genbki, by policy. genbki.pl carries an explicit caution comment (“be wary about what symbols you substitute … Do not substitute anything that could depend on platform or configuration. The right place … is in initdb.c’s bootstrap_template1()”). The replace_token calls for NAMEDATALEN, FLOAT8PASSBYVAL, ENCODING, locale tokens, etc. all live in bootstrap_template1. Verified.

• template0/postgres use fixed OIDs and file_copy. Both make_template0 and make_postgres emit CREATE DATABASE ... OID = CppAsString2(...) ... STRATEGY = file_copy, with explicit source comments explaining the pg_upgrade OID-preservation motivation. Verified.

• Index build is deferred to the end. Boot_DeclareIndexStmt passes skip_build = true to DefineIndex, index_register queues onto ILHead, and only build_indices (driven by the final build indices command) actually calls index_build. The source comment on index_register states the rationale (“the indexes themselves have catalog entries, and those have to be included in the indexes on those catalogs”). Verified.

• Relation mapper is written last. BootstrapModeMain calls RelationMapFinishBootstrap() after CommitTransactionCommand(), with the comment “We should now know about all mapped relations”. Verified at bootstrap.c line ~396.

Beyond PostgreSQL — Comparative Designs & Research Frontiers

The lineage: System R and the Berkeley POSTGRES catalog

PostgreSQL’s bootstrap shape descends directly from System R (Astrahan et al. 1976), which pioneered storing the catalog as ordinary relations readable through the same low-level storage interface (RSS) used for user data. That decision — catalogs are tables — is precisely what creates the chicken-and-egg problem, and System R already needed a special routine to lay down the catalog-of-catalogs before the general machinery could run. The Berkeley POSTGRES design (Stonebraker & Rowe 1986; “The Implementation of POSTGRES”, Stonebraker, Rowe & Hirohama 1990) extended this with an aggressively extensible type and access-method system: new types, operators, and index AMs are catalog rows, not compiled-in special cases. That extensibility is exactly why PostgreSQL needs the genbki/BKI_LOOKUP machinery — the built-in types and functions are just the seed rows of an open system, and they must be expressed as data (.dat files) with symbolic cross-references rather than as ad-hoc C initializers. The bootstrap backend’s hard-wired TypInfo[] is the irreducible minimum that cannot be expressed as data, because it is the floor the data machinery stands on.

How other engines solve the same problem

• SQLite sidesteps bootstrap almost entirely: its sole catalog, sqlite_schema (formerly sqlite_master), is an ordinary B-tree at a fixed root page (page 1) of the database file. There is no separate seeding program; creating a database is writing a 100-byte header and an empty root page. The trade is that SQLite has no extensible type system to seed — types are dynamic and per-value, so there is no large built-in catalog data set to manage. PostgreSQL’s heavier pipeline is the cost of a rich, statically-typed, extensible catalog.

• MySQL/InnoDB historically kept “data dictionary” information split between InnoDB internal tables and .frm files; since 8.0 it moved to a transactional data dictionary stored in InnoDB tables, with a small set of bootstrap tablespaces and an embedded DDL bootstrap that runs at first start. The conceptual structure is the same two-stage escalation — a minimal compiled-in description brings up the dictionary tables, which then describe everything else.

• Oracle runs catalog.sql / catproc.sql scripts at database creation against a minimal SYS-owned bootstrap segment whose layout is compiled into the kernel; the bootstrap$ table is the analogue of PostgreSQL’s pg_filenode.map + nailed catalogs. Again: a tiny hard-wired core, then SQL scripts to build the rest — the same “imperative-loader-then-SQL” two-phase pattern initdb uses across its --boot and standalone passes.

Code generation as a build-time consistency contract

The deeper architectural idea in genbki.pl is single-source-of-truth code generation: one declarative description (pg_*.h + pg_*.dat) drives both the runtime C side (struct layouts, OID #defines, syscache descriptors, FK metadata) and the seed-data side (the BKI). The build fails if the two diverge (duplicate OIDs, unresolved synonyms, an OID counter overrun). This is the same discipline behind protobuf/Thrift IDL compilers, ORM migration generators, and Linux’s syscall_64.tbl: hand- maintained data in one place, machine-derived artifacts everywhere else, with the generator acting as a consistency checker. The pattern’s payoff is that adding a built-in function is a one-line .dat edit, not a coordinated change across a header, an initializer, and a syscache table.

A research-frontier note: there is recurring interest in making the catalog fully data-driven and hot-pluggable (loadable type/AM packs without a recompile), which PostgreSQL approximates with extensions but not for the bootstrap core. The genbki boundary — what must be compiled in vs. what can be seed data vs. what can be a runtime extension — is a live design tension every extensible DBMS negotiates. PostgreSQL draws the line conservatively: the floor (TypInfo[], nailed relcache descriptors) is compiled, the built-in catalog is generated seed data, and everything past pg_stop_making_pinned_objects() is droppable runtime state.

Operational corollaries

• template0 as a clean-room baseline. Because template0 is never connected to and never modified, it is the guaranteed-pristine source for CREATE DATABASE ... TEMPLATE template0, including encoding/locale combinations that differ from template1. Its cleared datcollversion is what makes cross-collation cloning legal.
• --check mode. The same BootstrapModeMain path with check_only set is reused by the postmaster’s resource self-test (CheckerModeMain) — a nice example of the bootstrap backend being the cheapest available “minimal backend” to validate shared-memory sizing.
• pg_upgrade and fixed OIDs. The fixed Template0DbOid / PostgresDbOid assignments in make_template0/make_postgres exist purely so a major-version upgrade can preserve database OIDs without collisions — a bootstrap-time decision driven by a tool that runs years later.

Sources

• Source tree: PostgreSQL REL_18_STABLE @ 273fe94 (PG 18.x).
  • src/bin/initdb/initdb.c — frontend orchestration: directory layout, config generation, bootstrap_template1, post-bootstrap SQL phase, make_template0/make_postgres.
  • src/backend/bootstrap/bootstrap.c — BootstrapModeMain, the BKI command implementations (boot_openrel, DefineAttr, InsertOne*, index_register, build_indices), and the TypInfo[]→Typ type escalation.
  • src/backend/bootstrap/bootparse.y, bootscanner.l — the flex/bison front end defining the six BKI command shapes.
  • src/backend/catalog/genbki.pl — build-time generator of postgres.bki, pg_*_d.h, schemapg.h, system_fk_info.h, system_constraints.sql, syscache_ids.h, syscache_info.h.
  • src/include/catalog/pg_*.h, pg_*.dat — the single source of truth for catalog schema and seed data (consumed by genbki).
• Theory anchors (see .omc/plans/postgres-paper-bibliography.md):
  • Database System Concepts (Silberschatz, Korth, Sudarshan, 7e) — data dictionary / system catalog as self-describing recursive metadata. knowledge/research/dbms-general/database-system-concepts.md.
  • System R (Astrahan et al. 1976) — catalogs-as-relations lineage, dbms-papers/systemr.md.
  • Berkeley POSTGRES design series (Stonebraker & Rowe 1986; Stonebraker, Rowe & Hirohama 1990) — extensible type/AM catalog that motivates the BKI_LOOKUP data-driven seed.
• Cross-references (sibling docs):
  • postgres-system-catalogs.md — what the seeded catalogs contain and the schemapg/syscache fan-out genbki also emits.
  • postgres-postmaster.md — how the running server forks per-connection backends after the cluster exists.
  • postgres-relcache.md — relcache “nailing” / formrdesc using the compiled schemapg.h descriptors.
  • postgres-xlog-wal.md — BootStrapXLOG and the initial WAL.