CREATE TABLE orders (
  id int(11) NOT NULL AUTO_INCREMENT,
  created datetime NOT NULL,
  payment_received datetime NOT NULL DEFAULT '0000-00-00 00:00:00',
  settled datetime NOT NULL DEFAULT '0000-00-00 00:00:00',
  dispatched datetime NOT NULL,
  email varchar(100) NOT NULL,
  first_name tinytext NOT NULL,
  last_name tinytext NOT NULL,
  address_line_1 tinytext NOT NULL,
  address_line_2 tinytext NOT NULL,
  address_line_3 tinytext NOT NULL,
  address_city tinytext NOT NULL,
  address_post_code tinytext NOT NULL,
  address_country tinytext NOT NULL,
  address_telephone tinytext NOT NULL,
  address_mobile tinytext NOT NULL,
  cancelled datetime NOT NULL,
  cache_keyword text NOT NULL,
  PRIMARY KEY (id),
  KEY email (email),
  KEY settled (settled),
  FULLTEXT KEY cache_keyword (cache_keyword)
);

CREATE TABLE orders (
  id int(11) NOT NULL AUTO_INCREMENT,
  created datetime NOT NULL,
  payment_received datetime NOT NULL DEFAULT '0000-00-00 00:00:00',
  settled datetime NOT NULL DEFAULT '0000-00-00 00:00:00',
  dispatched datetime NOT NULL,
  email varchar(100) NOT NULL,
  first_name tinytext NOT NULL,
  last_name tinytext NOT NULL,
  address_line_1 tinytext NOT NULL,
  address_line_2 tinytext NOT NULL,
  address_line_3 tinytext NOT NULL,
  address_city tinytext NOT NULL,
  address_post_code tinytext NOT NULL,
  address_country tinytext NOT NULL,
  address_telephone tinytext NOT NULL,
  address_mobile tinytext NOT NULL,
  cancelled datetime NOT NULL,
  cache_keyword text NOT NULL,
  PRIMARY KEY (id),
  KEY email (email),
  KEY settled (settled),
  KEY payment_received (payment_received,cancelled),
  FULLTEXT KEY cache_keyword (cache_keyword)
);

The ANALYZE for this query is predictably boring, but I do occasionally see it using the payment_received index (presumably for the ORDER BY).

While I believe this is a general question (how to search several text fields in a big table); for some more specific details, the SQL would be something like:

SELECT
    o.id,
    o.created,
    o.payment_received,
    o.settled,
    o.dispatched,
    o.first_name,
    o.last_name,
    o.email
FROM
    orders AS o
WHERE
    o.first_name LIKE "%Craig%" AND
    o.last_name LIKE "%Francis%" AND
    o.address_post_code LIKE "%10%" AND
    o.cancelled = "0000-00-00 00:00:00"
ORDER BY
    payment_received DESC
LIMIT
    0, 50;

The fields searched will depend on what the admin has provided.

And if 50 results are returned, then it will also run:

SELECT
    COUNT(o.id) AS c
FROM
    orders AS o
WHERE
    o.first_name LIKE "%Craig%" AND
    o.last_name LIKE "%Francis%" AND
    o.address_post_code LIKE "%10%" AND
    o.cancelled = "0000-00-00 00:00:00";

The table structure uses tinytext fields for these searchable fields.

It does have 77 columns, but most are unrelated for this (e.g. vat, discounts, tracking information), so I'll abbreviate it to the following:

CREATE TABLE orders (
  id int(11) NOT NULL AUTO_INCREMENT,
  created datetime NOT NULL,
  payment_received datetime NOT NULL DEFAULT '0000-00-00 00:00:00',
  settled datetime NOT NULL DEFAULT '0000-00-00 00:00:00',
  dispatched datetime NOT NULL,
  email varchar(100) NOT NULL,
  first_name tinytext NOT NULL,
  last_name tinytext NOT NULL,
  address_line_1 tinytext NOT NULL,
  address_line_2 tinytext NOT NULL,
  address_line_3 tinytext NOT NULL,
  address_city tinytext NOT NULL,
  address_post_code tinytext NOT NULL,
  address_country tinytext NOT NULL,
  address_telephone tinytext NOT NULL,
  address_mobile tinytext NOT NULL,
  cancelled datetime NOT NULL,
  cache_keyword text NOT NULL,
  PRIMARY KEY (id),
  KEY email (email),
  KEY settled (settled),
  FULLTEXT KEY cache_keyword (cache_keyword)
);

The cache_keyword is an interesting one, as it gets populated with a CONCAT() of the searchable field values, this works great for the normal search, but does not work in this "advanced search", as the admin are typically searching for partial values.