X-Antony
А у самого какие соображения по этому поводу?

Лучшее что я придумал - обьединить все в одну таблицу вида

id | name | params
1 | вася | (10)(11)
2 | петя | (10)(11)
3 | коля | (10)(25)

и делать выборку, используя условие "params LIKE '%(10)%' AND params LIKE '%(11)%'", но я не уверен что это будет оптимальным вариантом.

Оставь как было изначально и тут есть варианты

SELECT * FROM `users` AS `u` WHERE `u`.`id` IN (SELECT `up`.`user` FROM `user2param` AS `up` WHERE `up`.`param` IN (10, 11))

SELECT `u`.* FROM `users` AS `u`
LEFT JOIN `user2param` AS `up` ON `up`.`param` IN (10, 11)
WHERE `u`.`id` = `up`.`user`

SELECT `u`.* FROM `users` AS `u`
LEFT JOIN `params` AS `p` ON `p`.`id` IN (10, 11)
LEFT JOIN `user2param` AS `up` ON `up`.`param` = `p`.`id`
WHERE `u`.`id` = `up`.`user`

короче, вариантов масса

linker

В том то и сложность, что все не так просто

Каждый из этих запросов выберет всех трех юзеров, но в том то и дело, что поиск у меня должен работать по обязательному наличию обоих этих параметров, поэтому, как я и написал выше, должен выбрать только васю и петю (но никак не колю).

Еще немного помучавшись, написал такой запрос:

SELECT u.*
FROM users u
LEFT JOIN user2param up1 ON up1.param = 10
LEFT JOIN user2param up2 ON up2.param = 11
WHERE u.id = up1.user AND u.id = up2.user

Он работает как надо, но опять таки, не уверен в его оптимальности, особенно, учитывая, что входных параметров может быть и больше.
Может быть есть еще какие-то варианты?

Как вариант:

SELECT `u`.`name`, COUNT(`p`.`user`) AS `cnt`
  FROM `params` AS `p`
  LEFT JOIN `users` AS `u` ON `p`.`user` = `u`.`id`
    WHERE `p`.`param` IN(10,11)
      GROUP BY `p`.`user`
        HAVING `cnt` = 2

Где `cnt` = 2 - количество параметров, которые обязательно должны совпасть. (10,11 - 2 параметра, 10,11,25 - меняем на тройку итд).

kirik, спасибо, работает.

Еще вопрос по теме...

Если я, допустим, отображаю результаты поиска постранично... как сделать лучше?

1) Выбирать из таблицы только нужные записи, используя LIMIT.
Например если посетитель запросил страницу 5 и количество результатов на странице - 10, в запросе будет присутствовать выражение "LIMIT (5-1)*10, 10".

Однако чтоб делать такой запрос нужно предварительно знать количество страниц, для чего соответственно нужно подсчитать общее количество результатов поиска (чтоб OFFSET случайно не привысил количество выбранных строк). Тоесть необходимо два запроса...

2) Выбирать из таблицы все результаты, после чего средствами PHP обрезать массив результатов (например с помощью array_slice()) и выводить нужные.

Или же может есть еще более разумный способ?

Второй вариант никогда не используйте.
По первому варианту: вам чтобы нарисовать список страниц и так придётся получить общее количество записей. Можете это делать в одном запросе при помощи calc_found_rows. Если оффсет будет выбран несуществующий, то ничего и не выводите, ведь это пользователь попадёт на такую страницу не через элементы навигации, а сам подставив значение, то его проблемы, что он ничего не увидит.

Nikitian, спасибо за разьяснение.
Сделал так, как вы посоветовали.