<div dir="ltr">Hi Han,<div><br></div><div>Thank you for the detailed information. The presorting function in PostgreSQL considers as well just the first 32 bits of Morton hashing, so they are probably affected by the same issue as well. I didn't find any study in this sense, like you did here in order to understand the drop in performance in using the index once it's built. Of course, you are focusing on the lack of performance, which is ~0.03ms vs ~0.05ms. I think that even the difference in hitting few additional pages can bring to this lack, which looks big with this sub-ms query but maybe it's more contained for larger source datasets. What is important to see is that the index ensures high performance if compared to the execution without any index (~13ms), so a factor ~1/500 is possible considering both GiST indexes with or without any pre-sorting. On the other hand, pre-sorting allows build time for the index which is ~1/3 of the case without the presorting!</div><div><br></div><div>Anyway, if you have time it's worth trying a full 32-bit hashing for the presorting. Keep us updated! It's sad to know that the next will be your last week for this GSoC - which doesn't mean you are allowed to disappear from the community! ;)</div><div><br></div><div>Thank you Han for the fantastic job you are doing!</div><div><br></div><div>Giuseppe.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Il giorno mar 17 ago 2021 alle ore 18:04 Han Wang <<a href="mailto:hanwgeek@gmail.com">hanwgeek@gmail.com</a>> ha scritto:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div></div><div><h3 id="gmail-m_8173830140312830512m_2761007492899234331gmail-CodingWeek109thAugust-15thAugust" style="font-family:Arial,Verdana,"Bitstream Vera Sans",Helvetica,sans-serif;letter-spacing:-0.018em;break-after:avoid;font-size:14px;border-bottom:1px dashed rgb(221,221,221);padding:0.2em 0.3em 0.1em;color:rgb(0,0,0)"><div style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif;font-size:small;font-weight:400;letter-spacing:normal">Hi all,</div><div style="color:rgb(34,34,34);font-family:Arial,Helvetica,sans-serif;font-size:small;font-weight:400;letter-spacing:normal">I am here to share with you my Week 10 report. You can also find it at [1]</div></h3><h3 id="gmail-m_8173830140312830512m_2761007492899234331gmail-CodingWeek109thAugust-15thAugust" style="font-family:Arial,Verdana,"Bitstream Vera Sans",Helvetica,sans-serif;letter-spacing:-0.018em;break-after:avoid;font-size:14px;border-bottom:1px dashed rgb(221,221,221);padding:0.2em 0.3em 0.1em;color:rgb(0,0,0)">Coding Week 10 (9th August - 15th August)<a href="https://trac.osgeo.org/postgis/wiki/ImplementSortingMethodsBeforeGistIndexBuilding#CodingWeek109thAugust-15thAugust" title="链接到这一节" style="text-decoration-line:none;color:rgb(215,215,215);border:none;font-size:0.8em;vertical-align:text-top" target="_blank"></a></h3><h3 id="gmail-m_8173830140312830512m_2761007492899234331gmail-m_-8639790829994434745gmail-CodingWeek92ndAugust-8stAugust" style="font-family:Arial,Verdana,"Bitstream Vera Sans",Helvetica,sans-serif;letter-spacing:-0.018em;break-after:avoid;font-size:14px;border-bottom:1px dashed rgb(221,221,221);padding:0.2em 0.3em 0.1em;color:rgb(0,0,0)"><p style="font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px;font-weight:400;letter-spacing:normal"><strong>Coding Phase </strong>:</p><ul style="font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px;font-weight:400;letter-spacing:normal"><li>Do more traversal tests</li><li>Fix the issue of <code style="color:rgb(102,0,0);border:1px solid rgb(238,221,204);border-radius:0.25em;padding:0px 0.3em;background:rgb(250,250,250)">gist_page_items</code></li></ul><p style="font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px;font-weight:400;letter-spacing:normal"><strong>Plans for next week</strong>:</p><ul style="font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px;font-weight:400;letter-spacing:normal"><li>Submit the final evaluation</li><li>Plan for a 32 bit hash function</li><li>Finish the documents</li></ul></h3></div><div>I have updated the document[2] for more tests. The pre-sort function works normally. But from this test, I think the current implementation of the fast index building method with pre-sorting may cause a loss of performance. </div><div>The pre-sorting function entry in Postgres does not check the leaf elements of a GiST index. And the first 32-bit of a 64bit Morton/Hilbert hash code as a datum key may reduce the precision significantly. </div><div>From my perspective, a 32 bit hash function may be necessary next. If you have any questions or suggestions, please let me know! You can reach me at the #postgis channel in matrix.</div><div><div><br></div><div>[1] <a href="https://trac.osgeo.org/postgis/wiki/ImplementSortingMethodsBeforeGistIndexBuilding" target="_blank">https://trac.osgeo.org/postgis/wiki/ImplementSortingMethodsBeforeGistIndexBuilding</a><br></div><div>[2] <a href="https://docs.google.com/document/d/1m4oxBAsKCyjAnYmkCmQ0X_ltiid5tliFwF3rtdzlKsc/edit?usp=sharing" target="_blank">https://docs.google.com/document/d/1m4oxBAsKCyjAnYmkCmQ0X_ltiid5tliFwF3rtdzlKsc/edit?usp=sharing</a></div><div><br></div><div>Best regards,</div><div>Han</div></div></div>
_______________________________________________<br>
postgis-devel mailing list<br>
<a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a><br>
</blockquote></div>