Re: Let an ordering index scan hand its ORDER BY value to the target list

Hello,

v11 attached, now eight patches. It brings back the box opclasses,
documents the EXPLAIN line, and cuts the planning overhead of what was
0006 and is now 0007. Oleg, the end of this mail I hope to answer
your point about a static COST.

The new 0001 is a geometry fix that stands on its own. The distance
between a point and a box went through the line-segment code, whose
EPSILON comparisons can pick the wrong edge for a point near an edge's
line. The point (0.9999996,2) is 1 from the box ((0,0),(1,1)), but
<-> said 1.00000000000008. GiST and SP-GiST compute the true distance
and order kNN scans by it, so on master an index scan can return rows
out of the operator's order:

CREATE TABLE b (id int, b box);
INSERT INTO b VALUES (1, '((0,0),(1,1))'),
(2, box(point(0.4999996, 0), point(1.4999996, 0.99999999999996)));
CREATE INDEX ON b USING gist (b);
SET enable_seqscan = off;
SELECT id, b <-> point(0.9999996, 2) FROM b
ORDER BY b <-> point(0.9999996, 2);
id | ?column?
----+------------------
1 | 1.00000000000008
2 | 1.00000000000004

SP-GiST does the same. A box's edges are parallel to the axes, so the
closest point is the point clamped to the box. 0001 computes it that
way and has both AMs call the same function. In a randomized check of
80 points against 50,000 boxes, master's operator differed from the
exact distance for 7.5% of sampled pairs, and both AMs returned rows
out of order. With 0001 both counts are zero. Four rows of the
geometry regression output change, all corrections. 0001 could go in
before the rest.

With the distances equal, 0002 lets GiST and SP-GiST box_ops return
them. In v9 I had withdrawn box_ops because of this mismatch.

0002 also documents "Order By Values Used": in the EXPLAIN chapter
next to the other per-node lines, and in the nearest-neighbor
paragraph of the index types chapter.

0007 reduces the planning cost of carrying a value through joins.
That cost came from the prechecks. add_path_precheck() can't see the
values, so v10 skipped it for every join path over an input that
emits one, and built each path in full. 0007 now adds
add_path_precheck_extras() and add_partial_path_precheck_extras(),
which take the values the path will emit. They let an existing path
dominate the new one only if it emits them all too. The old functions
keep their signatures. These are the N-way joins with the expensive
expression from the v7 mail [1], on a c6id.metal (Xeon 8375C, turbo
off, server and client pinned to separate cores), median of 41
planning times in each of five rounds, v10 and v11 interleaved:

rels overhead v10 overhead v11 planner memory v10 -> v11
7 +69% +32% 8.5 -> 6.5 MB
11 +90% +49% 26.3 -> 19.3 MB

"Overhead" is against the same join without the expression, which
plans in 5.8 ms at seven rels and 17.5 ms at eleven, within 1% of v10.
The five rounds agreed to within 1%. The plans and estimated costs of
all 18 join queries in that set were byte for byte the same in v10 and
v11.

The planner already decides early whether to carry a value at all. It
carries one only if the value costs more than 10 times
cpu_operator_cost to compute, so queries without such an expression
plan as before. The remaining overhead appears only when the value is
worth carrying. It comes from the extra paths add_path() keeps, and
those are what make the join over an index-only scan possible.

Oleg, about COST not following document size: I don't think the series
needs to solve this. The planner gets every function's cost from
add_function_cost(), and when the function has a support function,
that is where SupportRequestCost comes in. The request carries the
FuncExpr itself, so a ranking function's support function can look at
its tsvector argument, find the column's average width in its
statistics, and scale the per-call cost by it. The series computes
its credit (0003, 0005, 0007) with cost_qual_eval_node(), which goes
through add_function_cost(), so it uses that estimate as-is. To
check, I indexed a COST 100000 function and the planner chose the
index-only scan. Then I attached regress.c's test_support_func, which
answers 2 * cpu_operator_cost, and the planner went back to a seq
scan, with no change to the series.

The estimate is still an average per row, as all costs are. A
document much longer than average costs more than the planner thinks,
but the credit and the charge use the same estimate, so the comparison
between plans stays fair. On the index side, your AM's
amcostestimate can scale its own scoring cost by the same width.

0007 also stops collecting index expressions the children's index-only
scans can't return, which used to stop the Append from passing up the
ones they can, and 0008 adds a NULL check. Everything else is as in
v10. The series applies to master as of 0019a1ecf4c.

best.

-greg

[1] https://postgr.es/m/O7LiKSyMJH9pKrU0jxstopxs00AioGMev0lpPwq2uhUwzurMTQBFUKOdFPq0LXd4GHxxrIpajWq9Vy8QwkCsb3LgJrCdgfU7fn36dc4FFWQ=@burd.me