Как равномерно выбрать N значений из БД?

#mysql #алгоритм

В прошлом вопросе нужно было выводить значений Как равномерно выбрать N значений
из массива?

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

+++++++++++++++++++++++
| id | value | device |
+++++++++++++++++++++++
| 10 | 1020  | 5      |
+++++++++++++++++++++++
| 11 | 1030  | 5      |
+++++++++++++++++++++++
| 20 | 1040  | 5      |
+++++++++++++++++++++++
| 30 | 1050  | 5      |
+++++++++++++++++++++++
| 33 | 1000  | 6      |
+++++++++++++++++++++++
| 47 | 9050  | 6      |
+++++++++++++++++++++++
| 50 | 5020  | 6      |
+++++++++++++++++++++++
.....


Т.е. что получается: в таблице есть список записей, например у устройства 5 записей
140, у устройства 6 записей 500.

Можно ли сделать такой запрос, который для каждого устройства равномерно выберет
100 записей?

upd уточнения

Версия mysql 5.5.55.
    

Ответы

Ответ 1

Для того чтобы выбрать N записей из каждой группы с равными интервалами, нам нужно
из каждой группы выбрать записи с порядковыми номерами, кратными T / N, где T - это
количество записей в группе. Да это же работа для оконных функций count(*) over (partition
by device) и row_number() over (partition by device order by id)... Стоп, их нет в
MySQL. Ооооокей, достанем с балкона велосипед и попробуем их эмулировать.

count(*) over (partition by device) эмулируется легко и непринуждённо:

select d.id, d.value, d.device, cnt.records_in_group
from data d
inner join (
    select device, count(*) records_in_group
    from data
    group by device
) cnt on cnt.device = d.device;


row_number() over (partition by device order by id) эмулируется чуть сложнее:

select d.id, d.value, d.device, rn.row_number
from data d
inner join (
    select d1.id, count(*) row_number
    from data d1
    left outer join data d2 on d1.device = d2.device and d2.id <= d1.id
    group by d1.id, d1.value, d1.device
) rn on d.id = rn.id;


По сути, для каждой записи в группе мы считаем количество записей с id меньшим, чем
id текущей записи, и получаем её порядковый номер.

Соединяем, вводим поле factor, которое показывает, с каким шагом нужно брать записи
из группы:

select d.id, d.value, d.device,
       cnt.records_in_group,
       rn.row_number,
       cnt.records_in_group / 100 factor
from data d
inner join (
    select device, count(*) records_in_group
    from data
    group by device
) cnt on cnt.device = d.device
inner join (
    select d1.id, count(*) row_number
    from data d1
    left outer join data d2 on d1.device = d2.device and d2.id <= d1.id
    group by d1.id, d1.value, d1.device
) rn on d.id = rn.id;


Теперь умножим factor на числа от 1 до T и получим индексы записей в группах, которые
нужно выбрать. Сначала сгенерируем все пары (device, index), где index = [1, T]:

select d.device, irn.idx
from data d
inner join (
    select d1.id, count(*) as idx
    from data d1
    left outer join data as d2 on d1.device = d2.device and d2.id <= d1.id
    group by d1.id, d1.value, d1.device
) irn on irn.id = d.id;


А теперь при помощи найдём все записи, индекс которых в группе кратен factor:

select d.id, d.value, d.device
from data d
inner join (    -- наша эмуляция count(*) over(...)
    select device, count(*) records_in_group
    from data
    group by device
) cnt on cnt.device = d.device
inner join (    -- наша эмуляция row_number(*) over(...)
    select d1.id, count(*) row_number
    from data d1
    left outer join data d2 on d1.device = d2.device and d2.id <= d1.id
    group by d1.id, d1.value, d1.device
) rn on d.id = rn.id
cross join (    -- все пары (device, index)
    select d.device, irn.idx
    from data d
    inner join (
        select d1.id, count(*) as idx
        from data d1
        left outer join data as d2 on d1.device = d2.device and d2.id <= d1.id
        group by d1.id, d1.value, d1.device
    ) irn on irn.id = d.id
) drn
where drn.device = d.device
  and rn.row_number = floor(drn.idx * cnt.records_in_group / 100) -- factor спрятался тут
order by d.device, d.id;


Несложно заметить, что подзапросы rn и irn идентичны. Немного сократим код, вынеся
их в CTE... Стоп, CTE завезли только в 8 версии MySQL. Что ж, смиряемся с этим и принимаем
запрос в текущем виде за финальный результат.

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


Ответ 2

Попробовал решить задачу через увеличение выбираемых записей для каждого устройства
, если записей больше N то переводим позицию в 0 и берем следующие устройство. 
Для чистоты симулирую твои данные нагенерив тестовый контент:

#таблица
CREATE TABLE `devices` (
    `id` INT(11) NOT NULL AUTO_INCREMENT,
    `value` INT(11) NULL DEFAULT NULL,
    `device` INT(11) NULL DEFAULT NULL,
    PRIMARY KEY (`id`),
    INDEX `device` (`device`)
)
ENGINE=InnoDB;

#процедура генерации тестовых данных
#вставим 100к записей для 6 устройств
DELIMITER $$
CREATE PROCEDURE test_prepare_data()
    BEGIN
        DECLARE i INT DEFAULT 100;
        WHILE i < 100000 DO
            INSERT INTO devices ( value , device) VALUES ( (rand() * 3333) , (ROUND((RAND()
* (6-1))+1)) );
            SET i = i + 1;
        END WHILE;
END$$
DELIMITER;

#заполняю таблицу тестовыми данными
CALL test_prepare_data(); 


Тестовые данные готовы , реализую запрос согласно условию , получаю для каждого устройства
по 100 записей фильтруя их id , value , device по возрастанию:

    SELECT
        id, value , device ,n
    FROM
      ( SELECT  @prev := '', @n := 0 ) init
    JOIN
      ( SELECT  @n := if(device != @prev, 1, @n + 1) AS n,
                @prev := device,
                id, value, device
            FROM  devices
            ORDER BY
                device , value , id ASC
      ) x
    WHERE  n <= 100
    ORDER BY  device , value, id , n;


Запрос работает, выбирает и фильтрует значения согласно условию


Тестово дергаю значение по ID SELECT * FROM devices WHERE id = 68676 , ответ совпадает
с результатом в выборке. 

http://sqlfiddle.com/#!9/24ad24/2