It's becoming clear that merge trees and compaction need to be addressed next, after delete vectors brought them onstage.
Vertica will actually look up the equality keys in a relevant projection if it exists, and then use the column values in the matching rows to equality-delete from the other projections; it's fairly good at avoiding table scans.