Optimization problem: compound clustered keys, flag conditions and index-merge

Three tables:

product: with columns: ( a, g, ...a_lot_more... )

a: PK, clustered
g: bit-column

main: with columns: ( c, f, a, b, ...a_lot_more... )

c: PK, clustered
f: bit-column
(a, b): UQ

lookup with columns: ( a, b, c, i )

(a, b): PK, clustered
a: FK to product(a)
c: UQ, FK to main(c)
i: bit-column

I can't find good indexes for the join:

FROM  
    product
  JOIN 
    lookup
      ON  lookup.a = product.a  
  JOIN
    main
      ON  main.c = lookup.c 
WHERE 
      product.g = 1
  AND
      main.f = 1
  AND 
      lookup.i = 1
  AND lookup.b = 17

I tried a covering index on product (g, a, ...) and it's used but not with spectacular results.

Some combinations of indexes on the lookup table produce execution plans with index-merge, with slight efficiency gain over the previous plan.

Is there some obvious combination that I am missing?

Could a re-design of the structure help?

The DBMS is MySQL 5.5 and all tables are using InnoDB.

Table sizes:

product: 67K   ,  g applied:    64K 

main:   420K   ,  f applied:   190K

lookup:  12M   ,  b,i applied:  67K

This pains me...

I've had to use temp tables with InnoDB before. Load them with filters, create an index, join these temp table.

The problem as I reckon is if that InnoDB only has Nested Join algorithm: the grown-up RDBMS query optimisers have more to use. This is based on trying to run Data Warehouse type loads on InnoDB.

Temp tables drags the overall complexity down the MySQL query optimiser's level...

StackExchange Database Administrators Q#21953, answer score: 3