- Add an index on top of the whole PK - Add indexes onto other columns trying to help the JOIN - Add additional statistics on two related columns
Another idea I had was to make use of generated columns and hash the PKs together to an BIGINT and solely use this for the JOIN. However, this would not work when not all columns of the PK are used for the JOIN.
Can you expand on the additional statistics you created? Why was it on only two columns? Did you include MCVs type of extended stats?