We have implemented multi-key index support for GiST. Patch is available from http://www.sai.msu.su/~megera/postgres/gist/code/7.1.2/patch_multikeygist.7.1.2.gz The patch could be applied for postgresql version 7.1.2 and current sources 7.2 1. initdb is required. But, it's possible just to execute update update pg_am set amstrategies = 12 where amname = 'gist'; 2. You have to recompile all gist_*_ops functions 3. multi-key indexes works only for для gist__int_ops and gist__intbig_ops (from contrib/intarray), because they have support for NULLs. As a bonus we fixed several memory leaks in old GiST code. Example: create index mgix on tabletest using gist (b gist_int_ops, a gist__intbig_ops ) with ( islossy ); select * from tabletest where b @ '{1,2,3}' and a && '{4,5}';