Re: Bug in GiST paring heap comparator

On 02/09/2019 07:54, Alexander Korotkov wrote:
> Andrey Borodin noticed me that results of some KNN-GIST tests are
> obviously wrong and don't match results of sort node.
>
> SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
> f1
> -------------------
> (10,10)
> (NaN,NaN)
> (0,0)
> (1e-300,-1e-300)
> (-3,4)
> (-10,0)
> (-5,-12)
> (5.1,34.5)
>
> (1e+300,Infinity)
> (10 rows)

So we've memorized incorrect results in the expected output. Ouch!

> It appears to be related to implementation of comparison function in
> pairing heap used as priority queue for KNN. It used plain float
> comparison, which doesn't handle Inf and Nan values well. Attached
> patch replaced it with float8_cmp_internal().
>
> Also, note that with patch KNN results still don't fully match results
> of sort node.
>
> SELECT * FROM point_tbl ORDER BY f1 <-> '0,1';
> f1
> -------------------
> (0,0)
> (1e-300,-1e-300)
> (-3,4)
> (-10,0)
> (10,10)
> (-5,-12)
> (5.1,34.5)
> (1e+300,Infinity)
>
> (NaN,NaN)
> (10 rows)
>
> NULL and '(NaN,NaN)' are swapped. It happens so, because we assume
> distance to NULL to be Inf, while float8_cmp_internal() assumes NaN to
> be greater than NULL. If even we would assume distance to NULL to be
> Nan, it doesn't guarantee that NULLs would be last. It looks like we
> can handle this only by introduction array of "distance is null" flags
> to GISTSearchItem. But does it worth it?

I don't think we have much choice, returning wrong results is not an
option. At first I thought we could set the "recheck" flag if we see
NULLs or NaNs, but that won't work because rechecking is not supported
with Index-Only Scans.

Looking at the corresponding SP-GiST code,
pairingheap_SpGistSearchItem_cmp() gets this right. I'd suggest
copy-pasting the implementation from there, so that they would be as
similar as possible. (SP-GiST gets away with just one isNull flag,
because it doesn't support multi-column indexes. In GiST, you need an
array, as you said.)

- Heikki