<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";}
span.EmailStyle17
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:"Courier New";}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Just to add to the mix, here is Robert Haas' later comment to my further questions from full conversation thread – <o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>https://www.postgresql.org/message-id/flat/000001d26260%24d4a2d7b0%247de88710%24%40pcorp.us#000001d26260$d4a2d7b0$7de88710$@pcorp.us<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>On Tue, Jan 3, 2017 at 12:36 AM, Regina Obe <lr(at)pcorp(dot)us> wrote:<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>>> cmp would return 0 if the estimated distance returned by the index AM were greater than the actual distance.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>>> The estimated distance can be less than the actual distance, but it isn't allowed to be more. See gist_bbox_distance for an example of a "lossy" distance calculation, and more generally "git show 35fcb1b3d038a501f3f4c87c05630095abaaadab".<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>> Did you mean would return < 0 ?<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>Yes, sorry.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>> Since I thought 0 meant exact and not where it's Erroring?<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>> I think for points then maybe we should turn it off, as this could just be floating point issues with the way we compute the index.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>> That would explain why it doesn't happen for other cases like polygon / point in our code<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>> or polygon /polygon in our code since the box box distance in our code would always be <= actual distance for those.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>> So maybe the best course of action is just for us inspect the geometries and if both are points just disable recheck.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>> It's still not quite clear to me even looking at that git commit, why those need to error instead of going thru recheck aside from efficiency.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>The code that reorders the returned tuples assumes that (1) the actual<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>distance is always greater than or equal to the estimated distance and<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>(2) the index returns the tuples in order of increasing estimated<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>distance. Imagine that the estimated distances are 0, 1, 2, 3... and<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>the real distances are 2,3,4,5... When it sees the<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>estimated-distance-0 tuple it computes that the actual distance is 2,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>but it doesn't know whether there's going to be a tuple later with an<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>actual distance between 0 and 2, so it buffers the tuple. When it sees<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>the estimated-distance-1 tuple it computes that the actual distance is<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>2, and now it knows there won't be any more estimated or actual<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>distances between 0 and 1, but there could still be a tuple with an<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>estimated distance of 1 and 2 whose actual distance is also between 1<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>and 2, so it buffers the second tuple as well. When it sees the third<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>tuple, with estimated distance 2, it now knows that there won't be any<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>further tuples whose estimated or actual distance is less than 2. So<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>now it can emit the first tuple that it saw, because that had an<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>actual distance of 2 and from this point forward the index will never<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>return anything with a smaller estimated or actual distance. The<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>estimated-distance-1 tuple still has to stay in the buffer, though,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>until we see a tuple whose estimated distance is greater than that<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>tuple's actual distance (3).<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><div><div style='border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in'><p class=MsoNormal style='margin-left:.5in'><b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>From:</span></b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> Regina Obe [mailto:lr@pcorp.us] <br><b>Sent:</b> Tuesday, January 03, 2017 1:53 PM<br><b>To:</b> 'PostGIS Development Discussion' <postgis-devel@lists.osgeo.org><br><b>Subject:</b> RE: [postgis-devel] Recheck on Points broken<o:p></o:p></span></p></div></div><p class=MsoNormal style='margin-left:.5in'><o:p> </o:p></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Nope not 100% sure was just a guess based on what Robert Haas said and my assumption that we don't generate boxes for points? <o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>I thought we don't cause it's just baggage, which means we are using the point where as in other cases it is a box distance.<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>I did try to put a sniffer on where it's measuring distance adist[i], bdist[i] around 396 but always got a backend crash.<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><a href="https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/backend/executor/nodeIndexscan.c;h=3143bd94ec4499fba94b41693538b785c4b32e6c;hb=HEAD#l396">https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/backend/executor/nodeIndexscan.c;h=3143bd94ec4499fba94b41693538b785c4b32e6c;hb=HEAD#l396</a><o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>372 static int<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>373 cmp_orderbyvals(const Datum *adist, const bool *anulls,<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>374 const Datum *bdist, const bool *bnulls,<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>375 IndexScanState *node)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>376 {<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>377 int i;<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>378 int result;<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>379 <o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> 380 for (i = 0; i < node->iss_NumOrderByKeys; i++)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>381 {<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>382 SortSupport ssup = &node->iss_SortSupport[i];<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>383 <o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> 384 /*<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>385 * Handle nulls. We only need to support NULLS LAST ordering, because<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>386 * match_pathkeys_to_index() doesn't consider indexorderby<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>387 * implementation otherwise.<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>388 */<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>389 if (anulls[i] && !bnulls[i])<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>390 return 1;<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>391 else if (!anulls[i] && bnulls[i])<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>392 return -1;<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>393 else if (anulls[i] && bnulls[i])<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>394 return 0;<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>395 <o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> 396 result = ssup->comparator(adist[i], bdist[i], ssup);<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>397 if (result != 0)<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>398 return result;<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>399 }<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>400 <o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> 401 return 0;<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>402 }<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>You will probably have much better luck since I was just fumbling my way thru the code.<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Thanks,<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Regina<o:p></o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:.5in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:1.0in'><b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>From:</span></b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> postgis-devel [<a href="mailto:postgis-devel-bounces@lists.osgeo.org">mailto:postgis-devel-bounces@lists.osgeo.org</a>] <b>On Behalf Of </b>Paul Ramsey<br><b>Sent:</b> Tuesday, January 03, 2017 10:00 AM<br><b>To:</b> PostGIS Development Discussion <<a href="mailto:postgis-devel@lists.osgeo.org">postgis-devel@lists.osgeo.org</a>><br><b>Subject:</b> Re: [postgis-devel] Recheck on Points broken<o:p></o:p></span></p><p class=MsoNormal style='margin-left:1.0in'><o:p> </o:p></p><div><p class=MsoNormal style='margin-left:1.0in'>Are we 100% sure this is a float/double issue? The distance between two float boxes should always be *smaller* than the actual distance between two objects, since the float box extrema are always moved *away* from the original object when the float boxes are created. So from a "theoretical mechanics" perspective this shouldn't actually be the source of the problem.<o:p></o:p></p><div><p class=MsoNormal style='margin-left:1.0in'><o:p> </o:p></p></div><div><p class=MsoNormal style='margin-left:1.0in'>From a real world point-of-view, how could it still be the problem?<o:p></o:p></p></div><div><p class=MsoNormal style='margin-left:1.0in'>- maybe the box generation code has a short circuit for points which doesn't do the correct thing? Pretty sure it doesn't, but.<o:p></o:p></p></div><div><p class=MsoNormal style='mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:1.0in'>- something else?<br><br>P<o:p></o:p></p></div></div><div><p class=MsoNormal style='margin-left:1.0in'><o:p> </o:p></p><div><p class=MsoNormal style='margin-left:1.0in'>On Tue, Jan 3, 2017 at 4:54 AM, Regina Obe <<a href="mailto:lr@pcorp.us" target="_blank">lr@pcorp.us</a>> wrote:<o:p></o:p></p><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt'><p class=MsoNormal style='margin-left:1.0in'><br>>> Anyrate if there is nothing that can be done about ensuring index<br>>> distance is always less or equal to actual distance<br><br>> I remember we were all happy about having *real* distance with a more recent PostgreSQL. If that's not the case (as the user reports) we should try to find a way to provide both mechanisms.<br>> Two different operators, maybe ?<br>> --strk;<br><br>We've already got two different operators. We have <#> which doesn't use recheck and that's what I told the user to use, until we resolve this.<br><br>The thing is the <-> I think pretty much for all reasonable purposes returns the right order for points (and in fact in this case yields the same value and <-> I think in all cases it will).<br><br>So it's just the float4/float8 mess why it screws up and it Errors noisily in PostgreSQL land where we cannot control.<br><br>I hate telling people to if you have point / point use <#> and if you have others you can safely use <->. That's sooo unfriendly.<br><br>I think the best thing is just to not have point-point checks use recheck. Can we do that easily? That's what PostgreSQL point/point does.<br>That way we don't fall into the PostgreSQL box trap of<br><br>"Hey -- how come your index distance is bigger than your computed distance. What kind of monster are you? Screw you!"<br><br>Thanks,<br>Regina<o:p></o:p></p><div><div><p class=MsoNormal style='margin-left:1.0in'><br>_______________________________________________<br>postgis-devel mailing list<br><a href="mailto:postgis-devel@lists.osgeo.org">postgis-devel@lists.osgeo.org</a><br><a href="http://lists.osgeo.org/mailman/listinfo/postgis-devel" target="_blank">http://lists.osgeo.org/mailman/listinfo/postgis-devel</a><o:p></o:p></p></div></div></blockquote></div><p class=MsoNormal style='margin-left:1.0in'><o:p> </o:p></p></div></div></body></html>