<div dir="ltr"><div dir="ltr"><div>Hi Rajat, </div><div><br></div><div>I made some updates to the report. And I publish here for backup.</div><div><br></div><div><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px"><strong>Abstract</strong></p><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px">GiST(Generalized Search Tree) is a generalization data structure of a variety of disk-based height-balanced search trees. Under the high-level API of GiST, structures like b-tree, r-tree can be implemented for data management. PostgreSQL defines a set of process function APIs for elements of the GiST index. Only with these function implementations can a data type be indexed and managed by a GiST structure. In large data scenarios, pre-sorting a batch of data fetched in memory may be a local approximation to the global sorting method. Recent PostgreSQL patch shows that it should speed up the build of a GiST index after some pre-sorting of the data which needs to be indexed. In one fork, the author replaces the GIST_OPTIONS_PROC with GIST_ORDER_PROC to try to define an order for data fetched in memory to sort in order to speed up the subsequent index building process. And I implemented pre-sorting methods in z-order pattern and Hilbert order pattern, Alos tested and compared pre-sorting methods on various data.</p><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px"><strong>The state of the art BEFORE your GSoC</strong></p><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px">The index building process does not change the tuple order in the page and runs at a slow speed</p><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px"><strong>The addition value</strong> </p><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px">With the pre-sorting index, the time of building index reduce to the to one-third to one-fifth of the original</p><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px"><strong>Links</strong></p><ul style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px"><li>Code Base: <a class="ext-link" href="https://github.com/postgis/postgis/pull/619" style="text-decoration-line:none;color:rgb(187,0,0);border-bottom:1px dotted rgb(187,187,187)"><span class="gmail-icon" style="background:url("../extlink.gif") 0% 50% no-repeat;padding-left:15px"></span>https://github.com/postgis/postgis/pull/619</a></li><li>Wiki: <a class="ext-link" href="https://trac.osgeo.org/postgis/wiki/ImplementSortingMethodsBeforeGistIndexBuilding" style="text-decoration-line:none;color:rgb(187,0,0);border-bottom:1px dotted rgb(187,187,187)"><span class="gmail-icon" style="background:url("../extlink.gif") 0% 50% no-repeat;padding-left:15px"></span>https://trac.osgeo.org/postgis/wiki/ImplementSortingMethodsBeforeGistIndexBuilding</a></li><li>Test Results and Performance Comparison: <a class="ext-link" href="https://docs.google.com/document/d/1_mY_F2hPDk3vmXH5PPp2z9BuQWt-ZMORk6KxtdVQ3HY/edit?usp=sharing" style="text-decoration-line:none;color:rgb(187,0,0);border-bottom:1px dotted rgb(187,187,187)"><span class="gmail-icon" style="background:url("../extlink.gif") 0% 50% no-repeat;padding-left:15px"></span>https://docs.google.com/document/d/1_mY_F2hPDk3vmXH5PPp2z9BuQWt-ZMORk6KxtdVQ3HY/edit?usp=sharing</a></li></ul><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px"><strong>Conclusion</strong></p><ul style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px"><li>The Morton/Hilbert hash function for pre-sorting can accelerate the process of index building process and reduce the time-consuming to one-third to one-fifth of the original</li><li>The query operation for different data in the same area demonstrates more stable performance</li><li>The query performance of pre-sorting is about 30% slower than the original</li></ul><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px"><strong>Future Work</strong></p><ul style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px"><li>Try to figure out the reason for the slowness of the pre-sorting index</li><li>Implement a fast Morton/Hilbert hash function for n-dimension geometry objects</li></ul><img src="cid:ii_ksop7hww1" alt="pre-sort-gist.png" width="474" height="172"><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px">                        The flow chart of pre-sort gist index</p><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px">Thanks for your excellent work and assistance!</p><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px">Best regards,</p><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px">Han</p><p style="color:rgb(0,0,0);font-family:Verdana,Arial,"Bitstream Vera Sans",Helvetica,sans-serif;font-size:13px"><br></p></div></div></div>