Q:

MYSQL - Select query with multiple OR conditions is Slow

I have a table of over 2 million rows and i need to rapidly do select queries on it in a loop.
SELECT ID,WebSite FROM `CompanyData` WHERE A1='data1' OR A2='data2' OR A3='data3'

It's taking 300 milli-seconds. I feel it shouldn't take this much time. Here is the EXPLAIN from that query:
--------+---------------------------------------------------------------------------------------------------------------------------+
| id | select_type | table    | type  | possible_keys  | key      |  key_len    | ref  | rows  | Extra                              |
+----+-------------+----------+-------+---------------+------+---------+------+---------+-------------------------------------------+
|  1 | SIMPLE     | CompanyData | index | A1,A2,A3     | A1,A2,A3 | 153,153,153 | NULL | 3     | Using union(A1,A2,A3); Using where |
+----+-------------+----------+-------+---------------+------+---------+------+---------+-------------------------------------------+

Here is the table structure:
CREATE TABLE `CompanyData` (
  `ID` int(11) NOT NULL AUTO_INCREMENT,
  `WebSite` varchar(150) DEFAULT NULL,
  `CompanyName` varchar(200) DEFAULT NULL,
  `A1` varchar(150) DEFAULT NULL,
  `A2` varchar(150) DEFAULT NULL,
  `A3` varchar(150) DEFAULT NULL,
  PRIMARY KEY (`ID`),
  UNIQUE KEY `WebSite` (`WebSite`,`CompanyName`),
  KEY `CompanyName` (`CompanyName`),
  KEY `A1` (`A1`),
  KEY `A2` (`A2`),
  KEY `A3` (`A3`)
) ENGINE=InnoDB AUTO_INCREMENT=3931223 DEFAULT CHARSET=latin1

Recently i have inserted another 10 million records to the table. Then the same 
Query is taking around 3 Seconds.
Please suggest a way to improve the Select query lookup. Even I am ready to restructure the table.
Thanks

A:

It is difficult for MySQL to optimize conditions with an OR.  You might be better trying:
SELECT ID, WebSite
FROM `CompanyData`
WHERE A1 = 'data1'
UNION
SELECT ID, WebSite
FROM `CompanyData`
WHERE A2 = 'data2' 
UNION
SELECT ID, WebSite
FROM `CompanyData`
WHERE A3 = 'data3';

Note that this uses UNION instead of UNION ALL.  An alternative version with UNION ALL looks like this (assuming the values are never NULL):
SELECT ID, WebSite
FROM `CompanyData`
WHERE A1 = 'data1'
UNION ALL
SELECT ID, WebSite
FROM `CompanyData`
WHERE A2 = 'data2' AND A1 <> 'data1'
UNION ALL
SELECT ID, WebSite
FROM `CompanyData`
WHERE A3 = 'data3' AND A1 <> 'data1' AND A2 <> 'data2';

For this query, the best indexes are composite indexes:  (A1, ID, WebSite), (A2, A1, ID, Website), and (A3, A1, A2, ID, WebSite).

