Optimize UNION query in MYSQL

I have a problem with a UNION query in MySQL. We have 10 millions players on our website and we would like to select players with a multi-criterias system. For exemple, selecting US people, men, > 35 yo.

We are using "vertical partionning" : 1 table per criter. For exemple :

* user_country
- id_user
- id_country

We would like to do this kind of query :

SELECT id_inscri FROM userdata_langue 
WHERE id_langue='43' 
  UNION 
SELECT id_inscri FROM userdata_sexe 
WHERE sexe='2' 
  UNION 
SELECT id_inscri FROM userdata_nb_jour 
WHERE nb_jour>='31' 
  UNION 
SELECT id_inscri FROM userdata_last 
WHERE last<='2013-04-07' 
  AND last>='2013-04-03' ;

Do you have any idea on how to optimize that ?

Thanks !

François

----- More details Explain of the query :

id  select_type table   type    possible_keys   key key_len ref rows    Extra
1   PRIMARY userdata_langue ref id_langue   id_langue   1   const       398846  Using index
2   UNION   userdata_sexe   ref sexe    sexe    1   const   1667137 Using index
3   UNION   userdata_nb_jour    range   nb_jour nb_jour 2   NULL    5830    Using where; Using index
4   UNION   userdata_last   range   last    last    3   NULL    371614  Using where; Using index
NULL    UNION RESULT    <union1,2,3,4>  ALL NULL    NULL    NULL    NULL    NULL

SHOW CREATE TABLE

Table   Create Table
userdata_langue CREATE TABLE `userdata_langue` (
 `id_inscri` bigint(20) NOT NULL,
 `id_langue` tinyint(3) unsigned NOT NULL,
 PRIMARY KEY (`id_inscri`),
 KEY `id_langue` (`id_langue`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1