Which database to use when you have a 6 billion of rows inside and need to query rows with from list of IDs?
My assumption here is using FLOAT in place of the actual composite key is slowing the query engine's ability to create the proper estimates.
So instead of using the &quot;clever&quot; column, just use a composite primary key:
CREATE TABLE Country
(
  CountryCd  CHAR(3)      NOT NULL  --ISO Country Code
 ,Name       VARCHAR(50)  NOT NULL
 ,CONSTRAINT PK_Country PRIMARY KEY (CountryCd)
 ,CONSTRAINT AK_Country UNIQUE (Name)
)
;
CREATE TABLE Subdivision  --State/province/region/county etc.
(
  CountryCd      CHAR(3)      NOT NULL
 ,SubdivisionCd  CHAR(3)      NOT NULL  --ISO subdivision code
 ,Name           VARCHAR(50)  NOT NULL
 ,CONSTRAINT FK_Subdivision_Division_Of_Country FOREIGN KEY (CountryCd) REFERENCES Country (CountryCd)
 ,CONSTRAINT PK_Subdivision PRIMARY KEY (CountryCd, SubdivisionCd)
 ,CONSTRAINT AK_Subdivision UNIQUE (CountryCd, Name)
)
;
CREATE TABLE City
(
  CityId         INT          NOT NULL
 ,CountryCd      CHAR(3)      NOT NULL
 ,SubdivisionCd  CHAR(3)      NOT NULL
 ,Name           VARCHAR(50)  NOT NULL
 ,CONSTRAINT FK_City_Located_In_Subdivision FOREIGN KEY (CountryCd, SubdivisionCd) REFERENCES Subdivision (CountryCd, SubdivisionCd)
 ,CONSTRAINT PK_City PRIMARY KEY (CityId)
 ,CONSTRAINT AK_City UNIQUE (CountryCd, SubdivisionCd, Name)
)
;
CREATE TABLE CityRoadDistance
(
  SourceCityId       INT  NOT NULL
 ,DestinationCityId  INT  NOT NULL
 ,RoadDistance       INT  NOT NULL
 ,CONSTRAINT FK_CityDistance_From_City FOREIGN KEY (SourceCityId) REFERENCES City (CityId)
 ,CONSTRAINT FK_CityDistance_To_City FOREIGN KEY (DestinationCityId) REFERENCES City (CityId)
 ,CONSTRAINT PK_CityDistance PRIMARY KEY (SourceCityId, DestinationCityId)
 ,CONSTRAINT CK_CityDistance_SourceCityId_LT_DestinationCityId CHECK (SourceCityId &lt; DestinationCityId) --Enforces only one record per city pair
)
;

Easy enough to find the single distance:
SELECT
  RoadDistance
FROM
  CityDistance
WHERE
  SourceCityId = 7 
    AND DestinationCityId = 235

But as you said the secondary requirement is to return 1,000 in less than 50 ms.
You won't be able to use IN, so you will need to build a list for the WHERE clause (e.g. (SourceCityId = 7 AND DestinationCityId = 235) OR (SourceCityId = 1345 AND DestinationCityId = 2934)...).
This should allow the query engine to look at things and say: &quot;Oh, I only need to perform 1,000 seeks&quot; and return your data relatively quickly.  However for 50 ms or less you're going to need some very fast SSDs or the pages already cached in memory.
Alternatives would be something like an in-memory key-value store.  This would cut down on compilation and seek time somewhat, but I'd try using an actual composite key and seeing what happens.