выборка из трёх таблиц с GROUP BY и ORDER BY

Боюсь без магии с переменными тут не обойтись. Нам надо санчала получить полную перемноженную выборку всех товаров во всех группах, отсортировать ее по популярности. Далее, по ходу строк помечать первый товар в группе, в случае если он не встречался ранее и запоминать в текстовой переменной, что такой товар уже был использован:

select cat_id, cat_name, item_id, item_name
  from (
    select y.*,
           @cgrp,
           @first:=if(@cgrp!=cat_id and find_in_set(item_id,@used)=0,1,0) first,
           @used:=concat(@used,if(@first,concat(',',item_id),'')),
           @cgrp:=if(@first,cat_id,@cgrp)
      from (
        select c.id cat_id,c.name cat_name, c.popularity cat_p, i.id item_id, i.name item_name, i.popularity item_p
          from cats c, items i, cats2items ci, (select @cgrp:=0,@used:='',@first:=0) x
         where ci.cat_id=c.id and ci.item_id=i.id
         order by c.popularity desc, c.id, i.popularity desc
      ) y
  ) z
 where first=1
 order by cat_p desc, item_p desc

Пример на sqlfiddle.com. Обратите внимание, в категории 4 запрос не вывел ни одной строки, так как оба товара, которые есть в этой категории, ранее уже были выведены в других категориях. И это не лечится при данной постановке задачи, категории в которых мало товаров могут этим страдать.