Opened 13 years ago

Last modified 7 years ago

#1024 new enhancement

Change 3D relationship functions to use &&& in addition to &&

Reported by: robe Owned by: pramsey
Priority: medium Milestone: PostGIS Fund Me
Component: postgis Version: master
Keywords: Cc:

Description (last modified by nicklas)

Now that we have the new &&& nd interacts operator in place, we can change all the 3D aware functions to use that short-circuit instead of &&.

So

ST_3DIntersects, ST_3DDWithin, ST_3DFullyWithin

Nicklas — you want to tackle this one since these are your babies :)

Attachments (1)

index_compare.sql (3.4 KB ) - added by nicklas 12 years ago.
to compare 2d and 3d index

Download all attachments as: .zip

Change History (23)

comment:1 by robe, 13 years ago

On second thought as Paul pointed out — what if they didn't build a 3D index on their 3D geometries.

We might want to do instead

&& AND &&& AND _ST_3D

That will catch both indexes and choose the cheapest one to test first

comment:2 by robe, 12 years ago

Has anyone thought about this more? I want to make this change now and close this out. Speak now or forever hold your peace. I'm going to make this change tomorrow if there are no objections and check and compare to make sure with a 3D index it is indeed faster than the old function.

comment:3 by nicklas, 12 years ago

Sorry Regina, I have missed this one.

Of course we should do it.

If you have time do do it please do.

Otherwise I will do it in i few days.

Thanks

Nicklas

comment:4 by nicklas, 12 years ago

Hmm,

"&& AND &&& AND _ST_3D That will catch both indexes and choose the cheapest one to test first"

Does that mean it will use the cheapest to test or the one giving less job for the recheck?

I mean I guess && is cheaper do do but it will sort away fewer records and send more of them for recheck. How smart is the planner?

/Nicklas

comment:5 by robe, 12 years ago

Hmm good question. I forgot that a 3D index would satisfy both && and &&&, though that is my assumption. Paul — correct me if I am mistaken.

So actually the order should be &&& AND &&.

The way PostgreSQL works — it will first process the one that can take advantage of an index all else being equal (not sure how it compares index costs). If both can utilize an index (it can't tell which is more costly), then it will process in order.

So my thinking is if a user has a 2D index, then && will be checked first and then &&& would provide additional filtering before the more costly _ST_3D regardless of if we do &&& and && or && and &&&.

If they have a 3D index, then &&& will be used first only if we put it in front (assuming that both && and &&& can take advantage of the index), followed by && which in theory would be a pointless check but shouldn't add too much overhead. This is just following precedence of operation when costs are considered even.

comment:6 by nicklas, 12 years ago

Description: modified (diff)

comment:7 by nicklas, 12 years ago

As seen in the attached .sql the planner didn't react as I had hoped.

It looks at the &&& operator and judge it as more expensive than && operator.

Is there a "cost" somewhere? I didn't see it.

In the example in the file with 100000 records the planner chooses a heap bit scan if it is forced to use &&& operator. If it can chose it uses an index scan on the && operator and ignores the &&& operator.

Interesting is that if I increase the number of records to 1000000, then it uses a hep bit scan also with && operator but still chooses && over &&& operator.

I really hope there is a cost somewhere to tweak. Or is it just doing those decisions from statistics?

/Nicklas

by nicklas, 12 years ago

Attachment: index_compare.sql added

to compare 2d and 3d index

comment:8 by pramsey, 12 years ago

Milestone: PostGIS 2.0.0PostGIS 2.1.0

I think this should be shelved until later. The 3D index doesn't have a real selectivity estimator, so any attempt to cross your fingers and expect the planner to do right is misplaced.

comment:9 by robe, 11 years ago

You think we can visit this now that you have your selectivity in place or you still want to wait.

I think we'd need to still have && for those who chose a 2D index.

So more like &&& and &&

comment:10 by pramsey, 11 years ago

Yeah, it can be done, but it's dicey. Once you start mixing 2d and 3d operands, the results might become "unexpected", since 2d operands are treated as if they exist entirely on the z=0 plane. Not sure if it violates the "principle of least surprise"

comment:11 by robe, 11 years ago

Milestone: PostGIS 2.1.0PostGIS Future

why would it matter for 3D geometries. We only use ST_3DIntersects for 3D so I would expect the answer to be the same regardless since the final determinator is the _ST_3DIntersects. Or are you thinking aobut when people intersct 2D geometries with 3D geometries. Again if they use a 3D op when they want a 2D op, they deserve to be surprised.

Anyway this is not a rush — can wait till 2.2.

comment:12 by strk, 9 years ago

Beware that &&& is N-dimensional while 3D relationship functions are 3D only. Please make sure they are consistent. See also #3045, that's changing the threatment of 2d-3d operands from "exist entirely on the z=0 plane" to "exist on every z plane"

comment:13 by robe, 9 years ago

Milestone: PostGIS FuturePostGIS 2.1.6

comment:14 by robe, 9 years ago

Milestone: PostGIS 2.1.6PostGIS 2.2.0

comment:15 by robe, 9 years ago

Priority: mediumhigh
Type: taskenhancement

Okay we really need this. If I have a nd_index, by ST_3DIntersects does not use an index.

I had to change to

CREATE OR REPLACE FUNCTION st_3dintersects(
    geom1 geometry,
    geom2 geometry)
  RETURNS boolean AS
'SELECT $1 &&& $2 AND $1 && $2 AND _ST_3DIntersects($1, $2)'
  LANGUAGE sql IMMUTABLE
  COST 100;

rather than instead of, I think we need both. I had thought that && would use the 3D index but it doesn't. So we need both in case someone has only a 2D index in place so that the function can use a 3D or 2D index.

comment:16 by robe, 9 years ago

Summary: Change 3D relationship functions to use &&& instead of &&Change 3D relationship functions to use &&& in addition to &&

comment:17 by strk, 9 years ago

WARNING: remember that &&& is N-dimensional, while ST_3DIntersecs is 3-dimensional. Using &&& might exclude including candidates only because the M ranges of the operands do not overlap

comment:18 by robe, 9 years ago

Yah was thinking about that. Well it sucks that if I have a 3D index this function won't use an index. So to take full advantage of 3D I'd have to have both a 3D index and a 2D index, which seems pretty stupid to me.

comment:19 by strk, 9 years ago

The problem is really that we don't have 3D operators. Either 2D or ND. You could use the ND index for ND operations, but for 3D operations, can't use an index.

comment:20 by strk, 9 years ago

Actually, I think there's a way. You could drop the M from the non-indexed operand (ST_Force3DZ if 4D or ST_Force2D for 3DM). Doing that (with my recent fix in the &&& operator) the M value of the indexed column would always be found as overlapping the other (3DZ only) operand.

comment:21 by robe, 9 years ago

Milestone: PostGIS 2.2.0PostGIS Future
Priority: highmedium

seems like too complicated to drag into 2.2 sadly. So I guess I'll just have to live with the fact I can't use an nd spatial index (cause I don't want to have 2 spatial indexes). a pitty.

comment:22 by robe, 7 years ago

Milestone: PostGIS FuturePostGIS Fund Me

Milestone renamed

Note: See TracTickets for help on using tickets.