java-topology/tools/tickets/scans/postgresql.md

id	priority	status	created
scan-postgresql	high	unscanned	2026-03-23

Target

Repo: https://github.com/postgres/postgres Language: C Why: Query planner join graph traversal — linear list scans in path enumeration or join-order search inflate planning time on queries with many joined tables.

Scan command

# Shallow clone
git clone --depth 1 https://github.com/postgres/postgres /tmp/postgresql

# Submit to unsandbox
cat > /tmp/scan-postgresql.sh << 'EOF'
#!/usr/bin/env bash
set -euo pipefail
GRAPH_KW="tarjan|strongly.connected|dfs|scc|topolog|topo.sort|cycle|reachab|postorder|dominator|liveness|digraph|shortest.path|path.find"
MEM="lappend|list_member|listMember|foreach.*list|list_cell|for_each_cell|lcons|list_concat"
find /tmp/postgresql/src/backend/optimizer -name "*.c" -o -name "*.h" | sort | while read f; do
  graph_lines=$(grep -inE "$GRAPH_KW" "$f" 2>/dev/null | cut -d: -f1 | head -5 || true)
  [ -z "$graph_lines" ] && continue
  while IFS= read -r lineno; do
    s=$(( lineno > 20 ? lineno - 20 : 1 )); e=$(( lineno + 20 ))
    hit=$(sed -n "${s},${e}p" "$f" 2>/dev/null | grep -iE "$MEM" | head -1 | sed 's/^\s*//' || true)
    [ -n "$hit" ] && echo "CANDIDATE\t${f}:${lineno}\t${hit}"
  done <<< "$graph_lines"
done
EOF
export UNSANDBOX_PUBLIC_KEY=unsb-pk-russ-test-isth-best
export UNSANDBOX_SECRET_KEY=unsb-sk-rk46c-3zvpg-zjf6z-hjrge
~/git/un-inception/build/un /tmp/scan-postgresql.sh

Key files to check

• src/backend/optimizer/path/allpaths.c — Path enumeration for join graph; rel/path list membership
• src/backend/optimizer/path/joinpath.c — Join path construction; inner/outer relation list scans
• src/backend/optimizer/plan/planmain.c — Plan generation; join relation set operations
• src/backend/nodes/list.c — Core List implementation; list_member is O(N)

Expected pattern

list_member(visited, rel) or equivalent foreach loop checking whether a RelOptInfo or Path node has already been processed, inside make_rel_from_joinlist or a similar join-graph enumeration function — O(N) per check producing O(N²) overall.

Acceptance criteria

• Scan run and results saved to tools/scan-results/postgresql.txt
• All CANDIDATE hits triaged (confirmed defect or false positive)
• If confirmed: defect ticket created in tools/tickets/defects/