The one thing to understand first
The <a class="sev1-termlink" href="https://thesev1database.com/glossary/query-planner/" title="Query planner">optimizer does its work in two different currencies. First it sketches many lightweight candidates called Paths — cheap to create, cheap to compare, annotated only with cost. Then it converts the single winning Path into a heavyweight Plan — the detailed, executable form. Understanding why there are two representations explains almost everything about how PostgreSQL picks one strategy over another, and why a more expensive-looking option sometimes wins.
Why two representations at all?
Think of planning a drive. Comparing routes on a map — distance, estimated time — is fast, and you might weigh dozens. Writing out the turn-by-turn directions is detailed work you only do once, for the route you actually pick. Paths are the routes on the map; the Plan is the turn-by-turn directions. Generating thousands of Paths and costing them has to be cheap, so a Path carries only what is needed to compare alternatives. Only the survivor pays the price of becoming a full Plan.
Stage 1 — Path generation
Path search lives in src/backend/optimizer/path/. For every relation (a RelOptInfo), set_rel_pathlist() in allpaths.c generates candidate access paths: a sequential-scan path, one index-scan path per usable index, bitmap-scan paths, and so on. Each is built by a helper in pathnode.c — create_seqscan_path(), create_index_path() — and costed by functions in costsize.c (cost_seqscan(), cost_index()). Joins add their own combinatorics in joinpath.c: nested loop, merge join, and hash join paths across different join orders.