From: | Jeff Davis <pgsql(at)j-davis(dot)com> |
---|---|
To: | pgsql-hackers(at)postgresql(dot)org |
Cc: | Heikki Linnakangas <hlinnakangas(at)vmware(dot)com>, Alexander Korotkov <aekorotkov(at)gmail(dot)com> |
Subject: | rangetypes spgist questions/refactoring |
Date: | 2014-05-20 16:52:45 |
Message-ID: | 1400604765.3741.28.camel@jdavis-laptop |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
I am trying to understand the rangetypes spgist code and its interaction
with empty ranges. (Slightly embarrassing, because I reviewed the code.)
I see an old email here:
http://www.postgresql.org/message-id/50145A9C.7080400@enterprisedb.com
But still don't have a clear picture.
What I don't understand is:
1. Under what conditions might a tuple have no prefix (centroid), yet
also *not* be allTheSame?
2. Why would any tuple have 2 nodes? If there are some non-empty ranges,
why not make a centroid and have 4 or 5 nodes?
I added a bunch of assertions that seem reasonable to me based on my
understanding of the structure, and I attached them as a patch. They all
pass regression, which has a non-trivial set of input ranges, so there
is a reasonable chance the assertions are generally true. But if they
are true, some refactoring is in order.
It seems like the structure should be something like:
* Empty and non-empty ranges are only mixed in the root (level == 0).
* If a tuple has any non-empty ranges, there's a prefix (centroid).
AllTheSame may or may not be set (ordinarily not).
* If a tuple has only empty ranges, there's no prefix, and allTheSame is
set.
* The root tuple may have 5 nodes if there are any non-empty ranges,
otherwise 1 node (and allTheSame is set).
* Inner tuples may have either:
- one node if it contains only empty ranges, in which case it is
allTheSame, and must be in the 5th node (quadrant) of the root node, and
be at level 1
- four nodes if there are any non-empty ranges, in which case it has
*no* empty ranges
Note: I am using "allTheSame" in the logical sense; perhaps the flag is
an internal optimization that we can't rely on.
Regards,
Jeff Davis
Attachment | Content-Type | Size |
---|---|---|
range_spgist.diff | text/x-patch | 2.8 KB |
From | Date | Subject | |
---|---|---|---|
Next Message | Alvaro Herrera | 2014-05-20 17:32:38 | Re: I thought we were changing the name of recvlogical? |
Previous Message | Josh Berkus | 2014-05-20 16:43:04 | Re: I thought we were changing the name of recvlogical? |