Thanks Jordan for the insight
I guess case 2 was the cause of the problem
"The distribution of join keys is highly unbalanced. That is, if one LOCATIONID accounts for a large proportion of the rows in table1. Sometimes this might be expected. Sometimes, it is because of default value. For example, if table1 has a lot of rows where the LOCATIONID is not known, so by convention, 0 is used, this would mean that a lot of data gets hashed to the same location."
Most of the values in table1.LOCATIONID were NULL. So even though I had all the table2.LOCATIONID were unique it was failing.
As soon as I joined with column which has 99% of distinct values on both table1 and table2 then it worked like a charm