The first solution that comes to mind is to make the penalty and picksplit functions forcibly segregate empty ranges from others, that is a split will never put empty ranges together with non-empty ones. Then, we can assume that a non-empty internal node doesn't represent any empty leaf entries, and avoid descending to it when it doesn't overlap the target range. Then the equality-search case could be improved too.
Thoughts, better ideas?
Have you seen my patch about GiST for range types?
There mentioned problem is solved by introduction of RANGE_CONTAIN_EMPTY bit in range flags. This bit is only used in GiST index and means that there are underlying empty ranges.
