Thank you, that's exactly the kind of overview I was looking for.
> It shows that there is a lot of methods based on building temporaty > indexes. It might mean that building of temporary GiST index is not a > bad idea.
That had occurred to me, but I was hesitant to only use temp indexes. It still doesn't really offer a good solution when both sides of the join are relatively large (because of random I/O). Also the build speed of the index would be more important than it is now.
Note, that amount of random I/O during GiST index build significanlty dicreased after my GSoC project for buffering GiST index build. However, GiST index build is still quite CPU-expensive. This problem could be evaded by support of another methods of index build (another than producing a lot of penalty and picksplit calls). Hilbert curve and similar methods could help here. Implementation of such methods would require extension of GiST interface.