[nierman]

and you probably want to include these indices in any case to enforce that a given (user, movie) pair in the join table is unique (unless you want to track if a rating was changed and when, etc.)

further, you might decide to cluster on the index or partition.

[wiredfool]

Yep. You'd probably wind up wanting two indexes, a unique one on user,movie and then possibly one on movie only, to speed lookups the other way.