Why did ranges perform badly during the initial test? Because GIST/GIN indexes were used? Is it possible to use btree indexes with them, and would it make a difference? Construct a similar test dataset (similar size, but random content) and investigate.