It's no coincidence that GIN indexes (which have some of the same issues) only support lossy index scans.
AFAIK Gin is lossy for phrase queries as we don't store word position in the posting list. For purely logical queries, where position doesn't matter, it's not lossy.
One more consideration against the proposal is that if we want to select with more than one "suffix" columns in the WHERE clause, effectively we will have a join of two separate index scans. And as we consider suffix columns to be highly selective, and prefix columns are weakly selective, then it could be very slow.
Just some ideas on the topic which may not be connected to OP proposal (Not sure whether should we implement them as a part of nbtree) :
1. If prefix columns have low selectivity it may be good if we have some attribute-level deduplication only for prefix columns.
2. If we have several suffix columns, it might be a good idea is to treat them as an n-dimensional space and define some R-tree or Quad-tree on top of them (using GiST, SpGIST).
