• -- The query requires a scan of the whole 100M rows to evaluate the ORDER BY.

    -- An index with Destination, Origin, Airline and Tax will help.

    -- You *probably* don't need to join the lookups until after the aggregate -

    -- this help will speed up the query.

    ;WITH Preaggregate AS (

    SELECT TOP 10

    FAF.Destination,

    [CountDestCityCode] = Count(FAF.Destination),

    FAF.Origin,

    FAF.Airline

    FROM dbo.FactFares AS FAF

    WHERE (FAF.Tax >= 0)

    GROUP BY FAF.Destination, FAF.Origin, FAF.Airline

    ORDER BY Count(FAF.Destination) DESC

    )

    SELECT

    DLDest.CityCode AS [DestCityCode],

    FAF.[CountDestCityCode],

    DL.CityCode AS [OriginCityCode],

    DA.AirlineName AS [AirlineName]

    FROM Preaggregate FAF

    LEFT OUTER JOIN DimLocation AS DLDest ON FAF.Destination = DLDest.Location_Key

    LEFT OUTER JOIN DimLocation AS DL ON FAF.Origin = DL.Location_Key

    LEFT OUTER JOIN DimAirlines AS DA ON FAF.Airline = DA.AirlineCode

    “Write the query the simplest way. If through testing it becomes clear that the performance is inadequate, consider alternative query forms.” - Gail Shaw

    For fast, accurate and documented assistance in answering your questions, please read this article.
    Understanding and using APPLY, (I) and (II) Paul White
    Hidden RBAR: Triangular Joins / The "Numbers" or "Tally" Table: What it is and how it replaces a loop Jeff Moden