Test run with a Columnstore index, the duration got a lot larger
Unfortunately the duration jumped from 934 seconds to 7749 seconds.
Can I assuse columnstore index may not be a good option for a query of this kind?
Your query reads every row from the large table, performs a number of moderately complex computations, filters a relatively small percentage using string comparisons, and then performs most of its work in the hash join probe residual.
It might be possible to rework the design to be more CS-friendly, but it would require a fair bit of analysis and redesign. If you decide to go this route, be sure to read the TechNet article, "SQL Server Columnstore Performance Tuning".