Indexing for OR statement
The best approach is &quot;normalize your data&quot;.

If you cannot or don't want by some reason then try to use 4 separate queries and combine their outputs using UNION:
    select id 
    from table 
    where  p1_user_id='username' 
      and turn=0 
      and timestamp &gt; 20200101
UNION 
    select id 
    from table 
    where  p2_user_id='username' 
      and turn=0 
      and timestamp &gt; 20200101
UNION 
    select id 
    from table 
    where  p3_user_id='username' 
      and turn=0 
      and timestamp &gt; 20200101
UNION 
    select id 
    from table 
    where  p4_user_id='username' 
      and turn=0 
      and timestamp &gt; 20200101

Each separate query can use index ((pX_user_id, turn, timestamp) or (turn, pX_user_id, timestamp) are the most suitable), i.e. for total improvement you need to create 4 separate indices. Of course final UNION  will cause filesort, but, if the final amount of output rows is not too huge then you may have an improvement totally (but may not - be ready).


When this query runs, it doesn't use the indexes. Using explain, it shows the possible indexes, but then doesn't select one.

Server can use the index only as compact table version, not as an index - but for this the index must be covering, i.e. it must look similar to (turn, timestamp, p1_user_id, p2_user_id, p3_user_id, p4_user_id, id) - but I doubt that this is reasonable.