<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>Hi Darafei,</p>
<p>How does this relate to e.g. PostGIS with polygon or line data? <br>
</p>
<p>Faster indexing for point data only is only of limited value,
there are already reasonable alternatives for point type data,
e.g. BRIN indexes. However, for polygon and line data, GiST does
still appear to be the most efficient index for accessing the data
in spatial lookups, and tools like e.g. osm2pgsql default to them.</p>
<p>Is this commit just the "groundwork" layed out to implement
something like this in PostGIS, or does it require more work on
the PostgreSQL side itself before that is even conceivable?</p>
<p>Marco<br>
</p>
<div class="moz-cite-prefix">Op 23-1-2021 om 11:30 schreef Darafei
"Komяpa" Praliaskouski:<br>
</div>
<blockquote type="cite"
cite="mid:CAC8Q8t+YGtnabnTaG_wXgD9wmYHdtT_gQDPYaOLqiGmjGO29GQ@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="ltr">Hi,
<div><br>
</div>
<div>Here it is, committed to PG14. Works for Postgres's
internal `point` type now as far as I know. No PostGIS support
yet since that's gonna be in almost a year and committed just
a week ago.<br>
<a href="https://commitfest.postgresql.org/29/2276/"
moz-do-not-send="true">https://commitfest.postgresql.org/29/2276/</a></div>
<div><br>
</div>
<div>There is no parallel sort there though so you're welcome to
improve that too.<br>
<br>
You're welcome to test and report your findings.</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Sat, Jan 23, 2021 at 1:25
PM Marco Boeringa <<a href="mailto:marco@boeringa.demon.nl"
moz-do-not-send="true">marco@boeringa.demon.nl</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi
all,<br>
<br>
A couple of months ago, I asked a question about GiST spatial
indexing <br>
speed for (PostGIS) geometries, and the fact that the current
<br>
implementation is slow and not capable of parallel indexing.
GiST <br>
indexing is currently one of the major bottlenecks when
dealing with <br>
massive spatial datasets like e.g. OpenStreetMap.<br>
<br>
Back then, a couple of posters indicated there was ongoing
work to <br>
improve this, and that there might be improvements coming up
for a <br>
future release of PostgreSQL, e.g. see the remarks of
Alexander below as <br>
one example.<br>
<br>
Does anyone know what is the current status of all of this
work? Is <br>
there any realistic chance of an implementation in the
upcoming <br>
PostgreSQL 14? This GiST indexing performance issue appears to
have a <br>
long history, but with the ever growing OpenStreetMap
database, is <br>
becoming an increasing problem for PostGIS users. I think
improvements <br>
in PG14 would be really welcomed by the PostGIS community.<br>
<br>
Marco Boeringa<br>
<br>
> Op 21-9-2020 om 18:39 schreef Peter Geoghegan:<br>
>> On Wed, Sep 16, 2020 at 3:17 PM Alexander Korotkov <br>
>> <<a href="mailto:aekorotkov@gmail.com"
target="_blank" moz-do-not-send="true">aekorotkov@gmail.com</a>>
wrote:<br>
>>> In fact, GiST indexes are inferior to B-tree
indexes for many reasons.<br>
>>> For instance, B-tree implements disk-ordered scan
during VACUUM, while<br>
>>> GiST doesn't. B-tree could implement retail
index tuple delete (which<br>
>>> will be very useful for pluggable table AMs), but
for GiST retail<br>
>>> delete is problematic, because its performance is
not guaranteed to be<br>
>>> log(N). B-tree implements deduplication, but
GiST doesn't. And so<br>
>>> on. So, most of advances are applied to B-tree,
while GiST is<br>
>>> retarded. That makes me think it's a good idea
to reimplement GiST on<br>
>>> top of B-tree.<br>
>> A standard B-Tree with Z ordering is sometimes called
a UB-Tree. This<br>
>> is described in "Modern B-Tree techniques", which
promotes UB-Trees as<br>
>> having all of the advantages you list here. Though
the book also says<br>
>> that it probably has somewhat inferior read
performance to<br>
>> "specialized structures" (which probably refers to
loosely ordered<br>
>> tree structures like GiST). This matches my own high
level intuitions<br>
>> about it.<br>
>><br>
>>> In short, my idea is to add to the B-tree ability
to maintain "union<br>
>>> key" (MBR for spatial) in pivot tuple (including
leftmost pivot<br>
>>> tuple), while navigation of insertions will
remain comparison-based<br>
>>> (Z-ordered for spatial). Once we have union keys
correctly<br>
>>> maintained, we can implement a special "union
key" scan for B-tree,<br>
>>> which would work similar to the GiST scan.
Maintaining union keys<br>
>>> could be tricky, because we will have to make
sure no concurrent split<br>
>>> ruined our work on extension of parent union key
before we've extended<br>
>>> the child union key. But nevertheless, I think
it's solvable.<br>
>> That sounds hard. It sounds like you more or less
want to make the<br>
>> structure a true UB-Tree for inserts -- a structure
where you cannot<br>
>> allow there to be more than one place for any
possible key in the<br>
>> index. But you also want to maintain a union key for
selects, in order<br>
>> to make it possible to have a choice of subtree to
insert into, just<br>
>> like GiST. Is it really possible to do both at the
same time? It feels<br>
>> like a fundamental trade-off.<br>
>><br>
>> I suspect that it would be helpful (if you just did a
traditional<br>
>> UB-Tree, without the union key stuff) to add
specialized suffix<br>
>> truncation logic, that picked a split point according
to special<br>
>> criteria for the conditioned Z-order keys. That might
limit the extent<br>
>> of the performance hit for reads, without the added
complexity of the<br>
>> union key thing. This is just a guess.<br>
>><br>
>> I don't have a particularly good sense of the costs
here. It's obvious<br>
>> that the benefits would be very significant, but you
don't need me to<br>
>> say that. The hard parts are 1.) determining the
costs, and 2.)<br>
>> determining if the benefits are worth it.<br>
>><br>
>><br>
>> -- <br>
>> Peter Geoghegan<br>
> _______________________________________________<br>
> postgis-users mailing list<br>
> <a href="mailto:postgis-users@lists.osgeo.org"
target="_blank" moz-do-not-send="true">postgis-users@lists.osgeo.org</a><br>
> <a
href="https://lists.osgeo.org/mailman/listinfo/postgis-users"
rel="noreferrer" target="_blank" moz-do-not-send="true">https://lists.osgeo.org/mailman/listinfo/postgis-users</a><br>
_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org" target="_blank"
moz-do-not-send="true">postgis-users@lists.osgeo.org</a><br>
<a
href="https://lists.osgeo.org/mailman/listinfo/postgis-users"
rel="noreferrer" target="_blank" moz-do-not-send="true">https://lists.osgeo.org/mailman/listinfo/postgis-users</a><br>
</blockquote>
</div>
<br clear="all">
<div><br>
</div>
-- <br>
<div dir="ltr" class="gmail_signature">
<div dir="ltr">Darafei "Komяpa" Praliaskouski<br>
OSM BY Team - <a href="http://openstreetmap.by/"
target="_blank" moz-do-not-send="true">http://openstreetmap.by/</a><br>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
postgis-users mailing list
<a class="moz-txt-link-abbreviated" href="mailto:postgis-users@lists.osgeo.org">postgis-users@lists.osgeo.org</a>
<a class="moz-txt-link-freetext" href="https://lists.osgeo.org/mailman/listinfo/postgis-users">https://lists.osgeo.org/mailman/listinfo/postgis-users</a>
</pre>
</blockquote>
</body>
</html>