CF 7365 v9: heap_truncate_find_FKs() with the index on confrelid ================================================================ Builds, all on master dfd7ede529f, production (-O2), no cassert: master no index; the lookup is a seqscan of pg_constraint range v6/v7: one range scan of the index from the lowest to the highest OID in the list probe v9 (0001+0002): one index probe per relation in the list Method: single-user backend under perf stat (user-space instructions), plus the pg_constraint and pg_constraint_confrelid_index scan counters. v9 is v8 split in two patches, with the same code once both are applied; these counts were taken with that code (as v8). Counts, not times. 3 runs per side in alternating order; median, with min-max in brackets when the spread matters. Produced by fk-lookup-counts.sh.txt (attached); section 3 uses the repro-counts.sh.txt posted with v6. 1. Alvaro's case: an old table and a new one, with many FKs in between ----------------------------------------------------------------------- An old table and its FK; then K foreign keys from other tables, to tables created later; then a new table and its FK. 100 x TRUNCATE old_pk, old_fk, new_pk, new_fk; "Lookup" = instructions per TRUNCATE minus a TRUNCATE of four tables without triggers (which skips the lookup). In this schema almost every pg_constraint row is a foreign key. K FKs pg_constraint rows read per TRUNCATE lookup, instr. between rows master range probe master range probe 1,000 1,220 1,220 1,002 2 1.23M 1.54M 0.95M 10,000 10,400 10,400 10,002 2 3.55M 7.09M 1.00M 100,000 102,200 102,200 100,002 2 26.40M 62.04M 1.00M The range scan reads every FK to a table created between the two, and here costs more than master's seqscan. The probes read the 2 FKs that reference the list, whatever K is. amcheck (heapallindexed) is clean on all 6 pg_constraint indexes after the 100,000 runs with v9. 2. Long lists in a fresh cluster (the case that favours one range scan) ------------------------------------------------------------------------ TRUNCATE of N tables in one statement, each with a trigger, so the lookup runs and finds nothing; pg_constraint has 194 rows, no FKs. Instructions per TRUNCATE statement (whole statement): N master range probe 1 0.963M 0.923M 0.929M 10 3.923M 3.885M 3.947M 100 25.54M 25.52M 26.18M 1000 262.1M [256-265] 262.6M [258-263] 263.4M [263-271] At N = 100 the probes add about 6,600 instructions per relation, 2.5% of the statement; TRUNCATE itself spends about 255,000 per relation. At N = 1000 the run-to-run spread (about 3%) is larger than any difference. 3. The load measured for v6 (1/10 of David's repro, 95,759 constraints) ------------------------------------------------------------------------ 100 x TRUNCATE of a referenced table and its FK: master 2.915G, range 0.203G, probe 0.204G 100 commits touching an ON COMMIT DELETE ROWS temp table with a trigger: master 2.818G, range 0.084G, probe 0.084G 4. bloomfilter.c (measurement-only variants of v7, not proposed) ----------------------------------------------------------------- bloom-range v7's range scan; the filter is built from the list with bloom_create(list_length(oids), work_mem, 0), and each row is tested with bloom_lacks_element() before list_member_oid() bloom-all the same filter, but the scan key is confrelid > 0 (every foreign key) instead of the range Alvaro's case, lookup per TRUNCATE rows read bloom-range bloom-all K = 1,000 1,002 1.72M 1.72M K = 10,000 10,002 8.58M 8.57M K = 100,000 100,002 76.67M 76.65M (range 1.54M / 7.09M / 62.04M; probe 0.95M / 1.00M / 1.00M) Load of section 3 bloom-range bloom-all 100 x TRUNCATE of a referenced table 0.206G 0.452G 100 commits, ON COMMIT temp with trigger 0.087G 0.336G (range 0.203G / 0.084G; probe 0.204G / 0.084G) With the range, the filter does not change which entries are read, and bloom_create() zeroes a bitset of at least 1MB on every call (bloomfilter.c). Without the range, the cost no longer depends on the OIDs, but every call reads every foreign key in the database: 3,232 of them in the section 3 cluster. 5. TRUNCATE ... CASCADE down a chain of N tables ------------------------------------------------- c1 <- c2 <- ... <- cN, each referencing the previous one; 3 x TRUNCATE c1 CASCADE; in a fresh cluster. ExecuteTruncateGuts() looks up the referencers once per level, so there are N lookups. "probe, v8a" is an earlier version with the same probes but without the change to that loop, which passed the whole, growing list each time. Per TRUNCATE: N rows read instructions master range probe,v8a probe master range probe,v8a probe 10 2,230 54 54 9 20.5M 20.3M 20.7M 20.3M 100 49,300 5,049 5,049 99 83.9M 75.8M 112.5M 69.5M 1000 3,193,000 500,499 500,499 999 4.07G 2.69G 6.60G 0.65G Master reads all of pg_constraint at each level; the range scan and the probes without the loop change read about N^2/2 rows. With it, v9 reads the N-1 foreign keys once. After each run, one more TRUNCATE ... CASCADE of the chain with a row in every table leaves 0 rows on every side. 6. ON COMMIT DELETE ROWS with N temp tables, by catalog size ------------------------------------------------------------ N temp tables, each with a trigger; every commit that touches temp tables truncates all of them and looks up their referencers. Catalog of the section 1 schema with K FKs (0 = fresh database). Instructions per commit, from (100 - 10) commits: pg_constraint N = 100 N = 1000 rows master range probe master range probe 194 3.53M 3.49M 4.20M 33.9M 33.8M 42.6M 1,220 4.28M 3.51M 4.16M 39.1M 33.8M 40.4M 10,400 10.9M 3.50M 4.30M 86.1M 33.9M 42.1M 102,200 76.8M 3.52M 4.36M 557M 33.9M 41.8M The probes cost about 7,000-9,000 instructions per temp table per commit, whatever the catalog size. Master's seqscan grows with the catalog and, through list_member_oid(), with N. So the probes lose only in a nearly empty database: up to 26% with 194 rows, even at about 1,200 rows, ahead from there on. The range scan is cheapest here because the temp tables have consecutive OIDs; section 1 is its weak case. Holding the index lock across the probes (a variant, not proposed) only saved about 1,300 instructions per probe. 7. Other shapes --------------- Per statement, fresh cluster, master / range / probe: TRUNCATE w0 CASCADE, N tables referencing w0 N = 1000 647M / 625M / 654M (spread 605-654) TRUNCATE pp CASCADE, pp partitioned in 100 partitions, 10 FKs to it 82.0M / 84.8M / 82.7M TRUNCATE pp_1 CASCADE, same (climbs to pp and restarts) 19.1M / 20.9M / 17.5M TRUNCATE of 1,000 tables failing on the last one (error path of heap_truncate_check_FKs(), one more lookup per relation) 637M / 54.9M / 62.6M Every CASCADE run is followed by one with a row in every table, which leaves 0 rows on every side. 8. Concurrency, pg_upgrade --------------------------- - Isolation spec (TRUNCATE ... CASCADE against ALTER TABLE ... ADD FOREIGN KEY on a relation it reaches): the new FK waits for the TRUNCATE, and a TRUNCATE that has to wait for the new FK sees it once it gets the lock and cascades to its table. Same output on master and v9. - David's repro at 1/10, upgraded with v9: no seqscan of pg_constraint, 3,200 scans of the index, amcheck clean on all 6 indexes, as with v6. 9. Not covered -------------- - No wall-clock times. - With ignore_system_indexes, systable_beginscan() turns each probe into a heap scan with a key, so a long list costs one seqscan per relation instead of one in total (from reading genam.c; not measured). - meson/clang builds were not tried; gcc only.