I don't think lack of parallelism is a concern. I think the nested
loop is more of concern. Ideally, the execution plan should show only
"index seeks" meaning MSSQL will perform a single pass on an index.
The nested loop means it will procedurally loop over something (look
for number of executes to see how many times it loops). I would run
DBCC SHOWCONTIG to see if your indexes are fragmented, assuming you
have indexes on that machine. I would also try running SP_UPDATESTATS
before executing the query.