Query Time is doubled because of a column in select
The time difference is probably due to:


The larger amount of data that needs to be returned to the client; and
The FORMAT function is relatively slow


You may be able to avoid using FORMAT by using a T-SQL expression instead, for example:

REPLACE(CONVERT(char(11), dtutcDateTime, 106), SPACE(1), '-') + 
SPACE(1) + 
CONVERT(char(8), @dt, 108);

-- Returns 25-Mar-2016 23:45:19


See:


FORMAT() is nice and all, but… by Aaron Bertrand
CAST and CONVERT (Transact-SQL) in the product documentation


You should also avoid scalar T-SQL functions in general, for performance reasons. Both plans use a UDF called xPT_ConvertTimeToDDHHMMSS. Scalar T-SQL functions are executed per row, with an overhead similar to that of running a complete query (each time). With 121,861 function calls, that overhead will be adding up. Use an in-line function or T-SQL intrinsics instead.

Also check that the variable @sUrlHeader is not a LOB type (e.g. varchar(max)) if it does not need to be. Using varchar(8000) or below may be significantly faster.

You can check the raw performance of the query (discounting the effect of a client that is slow to accept the results) by running it in SSMS with the Discard Results option set:



...or by selecting the query into a temporary table:

SELECT
  OverspeedReportId = ol.iVehicleMonitoringId,
  AssetId = iAssetId,
  Registration = sReference,
  CategoryId = iCategoryId,
  CategoryName = sCategoryName,
  SiteId = iSiteId,
  SiteName = sSiteName,
  OverspeedDate = FORMAT(dtutcDateTime, 'dd-MMM-yyyy HH:mm:ss'),
  DistanceTraveledSinceLastOverSpeed = DistanceCoveredKM,
  TimeDifferenceDDDHHMMSS = SUBSTRING(dbo.xPT_ConvertTimeToDDHHMMSS(DiffSeconds,'s'),1,12),
  SpeedKM = fSpeed,
  [Address] = sState +', '+ sDistrict +', ' +sPoi +', ' + sRoad +', '+sPoi,
  MapUrl = @sUrlHeader+'/Report/ReportOnMap/?id='
      +CONVERT(VARCHAR(10), @iCompanyId)+'&amp;ReportName=OverspeedReport'
      +'&amp;AssetId='+ CONVERT(VARCHAR(10), iAssetId)
      +'&amp;MaxSpeed='+ CONVERT(VARCHAR(10), fSpeed)      
      +'&amp;OverspeedingDate=' + FORMAT(dtutcDateTime, 'dd-MMM-yyyy HH:mm:ss')
      +'&amp;VehicleMonitoringLogId='+ CONVERT(VARCHAR, ol.iVehicleMonitoringId),
  [Locate] = 'Locate'
INTO #Results -- NEW!
FROM #overspeedLogs ol
LEFT JOIN VehicleGISAddressLog gis
    ON gis.iVehicleMonitoringId = ol.iVehicleMonitoringId
ORDER BY
    ol.iAssetId, 
    ol.dtUtcDateTime;


For the most comprehensive collection of performance data, run the queries directly from SQL Sentry Plan Explorer. Click the "Post to SQLPerformance.com" toolbar button to upload the complete session for expert analysis on that site.

If you are unable to do that, consider adding STATISTICS IO output to your question, at least.