simple SELECT EXISTS takes about two hours to execute
I think the problem stems from the one and only nullable: PRODUCT_QUANTITY. Why ?

Look at your query

SELECT EXISTS (SELECT * FROM ORDERS
WHERE USER_ID='c85bc9f7-704f-418e-98af-a1528622dd42'
AND   PLACE_ID='2'
AND   PRODUCT_ID='2bc7277f-c7c3-43bf-9598-9466c96a8f12');


The subquery has SELECT * and the ORDERS table has 4 columns


3 with NOT NULL
1 with DEFAULT NULL


Based on the MySQL Documentation on Subquery Optimization, the MySQL Query Optimizer performs subquery optimization by means of converting a subquery as follows:


  The MySQL query optimizer has different strategies available to
  evaluate subqueries. For IN (or =ANY) subqueries, the optimizer has
  these choices:
  
  
  Semi-join
  Materialization
  EXISTS strategy
  
  
  For NOT IN (or &lt;>ALL) subqueries, the optimizer has these choices:
  
  
  Materialization
  EXISTS strategy
  


In your particular case, you explicitly wrote the SELECT EXISTS (SELECT * ...). So, you are more responsible to optimize the subquery. Consequently, you should expect the MySQL Query Optimizer to start messing with you since it did not participate in the construction of the EXISTS strategy.

From the MySQL Documentation on Optimizing Subqueries with EXISTS Strategy, this is how checks on done for your SELECT:


  Becomes:

EXISTS (SELECT 1 FROM ... WHERE subquery_where
                      AND oe_1 = ie_1
                      AND ...
                      AND oe_N = ie_N) The following discussion assumes a single pair of outer and inner expression values for simplicity.

  
  The conversion just described has its limitations. It is valid only if
  we ignore possible NULL values. That is, the “pushdown” strategy works
  as long as both of these two conditions are true:
  
  
  outer_expr and inner_expr cannot be NULL.
  You do not need to distinguish NULL from FALSE subquery results. (If the subquery is a part of an OR or AND expression in the WHERE clause,
  MySQL assumes that you do not care.)
  


The bulletpoint that says outer_expr and inner_expr cannot be NULL might be the problem. The inner_expr could present possible rows with a NULL in one of the columns in spite of all the data being non-null. To me, such a check is unnecessary. 

The same document says the following in the evaluation process:


  For proper evaluation, it is necessary to be able to check whether the SELECT has produced any rows at all, so outer_expr = inner_expr cannot be pushed down into the subquery. This is a problem, because many real world subqueries become very slow unless the equality can be pushed down.


To make a long story short, slowness is being imposed because your SELECT EXISTS (SELECT * ...) is not optimal and the MySQL Query Optimizer is still abiding by its preset rules. There are checks being done on possible null results from the subquery even though you know there will be a non-null result.

SUGGESTION

Rather that doing a deeper dive into what makes your query's execution slow, I would rewrite the query as follows:

SELECT COUNT(1) FROM ORDERS
WHERE USER_ID='c85bc9f7-704f-418e-98af-a1528622dd42'
AND   PLACE_ID='2'
AND   PRODUCT_ID='2bc7277f-c7c3-43bf-9598-9466c96a8f12');


What are the advantages of rewriting the query this way ?


Subquery evaluation is completely eliminated
Return value is always non-null, either 0 or 1
Checking for 0/1 should be just as good as checking forTRUE/FALSE


GIVE IT A TRY !!!