Re: Optimize mergejoinscansel() by avoiding redundant computations

Optimize mergejoinscansel() by avoiding redundant computations

0. Add a call to is_same_simple_base_var() at the beginning of the function. If the left and right
nodes of the clause are Vars, and their top-level semantics are identical except for varno, varattno,
varnosyn, varattnosyn, and location, and their underlying references point to the same column of
the same table, with all semantics identical except for varnosyn, varattnosyn, and location, the function returns true.

1. If is_same_simple_base_var() returns true, the two calls to examine_variable() will obtain the same
statistics, if available. We can call examine_variable() first on the node that is already a simple base Var,
and reuse its results for the second call.

2. If is_same_simple_base_var() returns true, and lstatop == rstatop in the "Try to get ranges of both inputs" logic,
the two calls to get_variable_range() will return the same MIN/MAX values. We can avoid the second call and
reuse the results of the first call.

3. If is_same_simple_base_var() returns true, and leop == revleop && rightmax == leftmax && op_righttype == op_lefttype,
the inputs to the first and second calls to scalarineqsel() are identical, so both calls return the same selec. We can
avoid the second call and reuse the result of the first call.
After these two calls, because leftend == rightend, the subsequent logic sets leftend = rightend = 1.0.

4. If is_same_simple_base_var() returns true, and ltop == revltop && rightmin == leftmin && op_righttype == op_lefttype,
the inputs to the third and fourth calls to scalarineqsel() are identical, so both calls return the same selec. We can
avoid the fourth call and reuse the result of the third call.
After these two calls, because leftstart == rightstart, the subsequent logic sets leftstart = rightstart = 0.0.

(For points 3 and 4, MIN/MAX are compared directly using Datum values, rather than extracting and comparing the underlying values, which would be a more expensive operation. This is done to keep the implementation simple.)

5. If all the conditions in points 0/1/2/3/4 are satisfied, skip the checks in points 3 and 4 after obtaining the maximum
and minimum values. Since all these conditions are satisfied, the logic following the two pairs of scalarineqsel() calls
would check whether the returned values are equal and then perform the following assignments:
If leftend == rightend, set leftend = rightend = 1.0.
If leftstart == rightstart, set leftstart = rightstart = 0.0.
Both outcomes are equivalent to the default values set at the beginning of the function.

Based on the design above, run some tests covering the following scenarios:
EQ:
explain (summary) select a.reltype from pg_class_1 a, pg_class_2 b where a.reltype = b.reltype; --not sme base var
explain (summary) select a.reltype from pg_class_1 a, pg_class_1 b where a.reltype = b.reltype; --sme base var

IN:
explain (summary) select a.reltype from pg_class_1 a where a.reltype in (select b.reltype from pg_class_2 b); --not sme base var
explain (summary) select a.reltype from pg_class_1 a where a.reltype in (select b.reltype from pg_class_2 b); --sme base var

IN_LIMIT:
explain (summary) select a.relname from pg_class_1 a where a.relname in (select b.relname from pg_class_2 b limit 1); --not sme base var
explain (summary) select a.relname from pg_class_1 a where a.relname in (select b.relname from pg_class_1 b limit 1); --sme base var

Based on the test output:
0. The execution plans shown by EXPLAIN are identical.
1. The estimated selectivity values returned by mergejoinscansel(), as shown in the log output, are as follows:
EQ & IN:
master v2
leftstart leftend rightstart rightend leftstart leftend rightstart rightend
not sme base var 0.0 1.0 0.0 1.0 0.0 1.0 0.0 1.0
sme base var 0.0 1.0 0.0 1.0 0.0 1.0 0.0 1.0
------------------------------------------------------------------------------------------------

IN_LIMIT:
master v2
leftstart leftend rightstart rightend leftstart leftend rightstart rightend
not sme base var 0.0001 0.9999 0.0001 0.9999 0.0001 0.9999 0.0001 0.9999
sme base var 0.0001 0.9999 0.0001 0.9999 0.0 1.0 0.0 1.0
------------------------------------------------------------------------------------------------

The returned values are consistent. However, in the IN_LIMIT case, the V2 output differs in the “same base Var” scenario.

For IN_LIMIT, both master and V2 treat the “not same base Var” case as not involving the same base Var. When calling:
selec = scalarineqsel(root, revleop, isgt, true, collation, &rightvar, leftmax, op_lefttype);
selec = scalarineqsel(root, revltop, isgt, false, collation, &rightvar, leftmin, op_lefttype);

the Var in rightvar corresponds to a Var in a sub-join of a semi-join that has been pulled up. When ineq_histogram_selectivity()
calls get_actual_variable_range(), the RelOptInfo corresponding to rightvar->var has no index, so get_actual_variable_range()
returns false. Consequently, ineq_histogram_selectivity() adjusts the result as follows:
{
double cutoff = 0.01 / (double) (sslot.nvalues - 1);

if (hist_selec < cutoff)
hist_selec = cutoff;
else if (hist_selec > 1.0 - cutoff)
hist_selec = 1.0 - cutoff;
}
The same adjustment also exists in the other branch of ineq_histogram_selectivity(), namely "else if (sslot.nvalues > 1)".

(Could this issue be addressed as follows? get_actual_variable_range() matches vardata->rel and vardata->var against
indexes to retrieve the index's minimum and maximum values. If semantic equivalence is established, we could look up
the indexes using the underlying vardata->rel and vardata->var and attempt to find a match to retrieve the index's
minimum and maximum values. If this approach works, we could start a separate thread to discuss it.)

3. Performance results are shown below.
master(ms) v2(ms) Improvement%
mergejoinscansel() Planning Time mergejoinscansel() Planning Time mergejoinscansel() Planning Time
eq_not_same_var 0.118 2.012 0.119 2.008 -1.21% 0.20%
eq_same_var 0.117 2.027 0.024 1.933 79.84% 4.61%
in_not_same_var 0.120 3.070 0.119 3.024 0.22% 1.49%
in_same_var 0.118 3.045 0.025 2.909 78.84% 4.48%
in_limit_not_same_var 0.362 1.992 0.352 1.955 3.01% 1.84%
in_limit_same_var 0.356 1.959 0.024 1.629 93.35% 16.80%

Based on the test results, my observations are as follows:
- In all not_same_var scenarios, V2 shows no performance regression.
- In all same_var scenarios, at the function level, master remains relatively stable at 0.118 ms and 0.360 ms,
while V2 remains stable at 0.025 ms, delivering a performance improvement of over 78%.
- In the in_limit_same_var scenario, there are substantial performance improvements both at the function level and in planning time.

(For each set of 128 measurements, I excluded the first measurement, removed the maximum and minimum values from the remaining measurements, and calculated the arithmetic mean of the rest.)

I've attached the corresponding test shell script and analysis results in an XLS file. The XLS file also contains the shell commands used to extract the data, making it easier to aggregate and analyze the results.

regards,
--
ZizhuanLiu (X-MAN) 
44973863(at)qq(dot)com