Slow Query Log shows "Full_join: Yes" some of the time?

There is a stored procedure that executes a few times a second and normally runs for anywhere between few hundred milliseconds to just over 1 second. When running over 1 second I see the query in my slow query log and it shows “Full_join: No”

However, once in a while the query will take 10s of minutes to run and the slow query log will ultimately show “Full_join: Yes” and I am trying to understand under what circumstances that will occur.

Strangely, if I then take the query from the slow query log and run it directly it again runs in a few hundred milliseconds and the EXPLAIN looks totally normal.

I know that I have not provided specific details on the query, but I am ultimately just trying to understand why the execution plan will occasionally do a full join even though neither the database structure nor stored procedure has changed.