Summary
compareStats in pkg/sql/plan/stats.go is not a transitive (strict weak) ordering, so it cannot be used as a slices.SortFunc comparator and blocks migrating its two call sites in pkg/sql/plan/join_order.go off sort.Slice.
func compareStats(stats1, stats2 *Stats) bool {
if math.Abs(stats1.Selectivity-stats2.Selectivity) > 0.01 {
return stats1.Selectivity < stats2.Selectivity
}
return stats1.Outcnt < stats2.Outcnt
}The 0.01 selectivity tolerance makes it intransitive. Counter-example (from review):
A=(sel=0.000, outcnt=3), B=(sel=0.009, outcnt=2), C=(sel=0.018, outcnt=1):
B < A — |0.009-0.000| ≤ 0.01 → compare outcnt: 2 < 3 ✓C < B — |0.018-0.009| ≤ 0.01 → compare outcnt: 1 < 2 ✓A < C — |0.000-0.018| > 0.01 → compare selectivity: 0.000 < 0.018 ✓
So B < A < C < B — a cycle. sort.Slice tolerates this (produces some order); slices.SortFunc requires a strict weak ordering and its result is undefined for a comparator like this.
Impact / status
Proposed fix
Refactor compareStats into a genuinely transitive ordering key, e.g. bucket the selectivity onto a fixed 0.01 grid and sort lexicographically by (bucket, outcnt), so equal-bucket selectivities compare by outcnt and the relation is transitive. Note this changes tie behavior at bucket edges, so it may shift some join-order plans and require EXPLAIN golden updates — hence it is tracked separately from the mechanical sort→slices migration.
Once transitive, migrate the two join_order.go sites to slices.SortFunc.
Related: #25646 (the same class of non-strict/undefined comparator in the filter-cost sort).
Summary
compareStatsinpkg/sql/plan/stats.gois not a transitive (strict weak) ordering, so it cannot be used as aslices.SortFunccomparator and blocks migrating its two call sites inpkg/sql/plan/join_order.gooffsort.Slice.The 0.01 selectivity tolerance makes it intransitive. Counter-example (from review):
A=(sel=0.000, outcnt=3),B=(sel=0.009, outcnt=2),C=(sel=0.018, outcnt=1):B < A— |0.009-0.000| ≤ 0.01 → compare outcnt: 2 < 3 ✓C < B— |0.018-0.009| ≤ 0.01 → compare outcnt: 1 < 2 ✓A < C— |0.000-0.018| > 0.01 → compare selectivity: 0.000 < 0.018 ✓So
B < A < C < B— a cycle.sort.Slicetolerates this (produces some order);slices.SortFuncrequires a strict weak ordering and its result is undefined for a comparator like this.Impact / status
join_order.gosorts join sub-trees (subTrees) and dimensions withcompareStats. In PR perf: replace stdlib sort.Slice with slices pkg to eliminate heap escapes #25616 these two sites are kept onsort.Slice(not migrated) because of this.Proposed fix
Refactor
compareStatsinto a genuinely transitive ordering key, e.g. bucket the selectivity onto a fixed 0.01 grid and sort lexicographically by(bucket, outcnt), so equal-bucket selectivities compare byoutcntand the relation is transitive. Note this changes tie behavior at bucket edges, so it may shift some join-order plans and require EXPLAIN golden updates — hence it is tracked separately from the mechanical sort→slices migration.Once transitive, migrate the two
join_order.gosites toslices.SortFunc.Related: #25646 (the same class of non-strict/undefined comparator in the filter-cost sort).