Сортировка сущностей с seed

[Redjik]

Алгоритм необходим для нескольких проектов.
Уже несколько недель ломаем голову =).

Задача:
Имеется несколько "очередей", для вывода сущностей (+ пагинатор), вывод в таком порядке
1) Вип места - несколько сущностей могут принадлежать одному месту, выводится только одна в зависимости от seed, остальные, относящиейся к этому месту выводятся в других очередях.
2) Оплаченные с фотографиями - выводятся рандомно в зависимсти от seed
3) Оплаченные без фото.
4) Бесплатные c фото, вывод по дате, update_date DESC
5) Бесплатные без фото, вывод по дате, update_date DESC

Проблема в том, что есть фильтр и пагинатор - порядок не должен меняться.

Рассмотренные варианты:
1) Таблица-помощник: id сущности, timestamp (seed), order (порядок вывода).
Берем эту таблиу, джойним таблицу сущностей и делаем выборку по значениям фильтра.
Минус: синхронизация данных и добавление.удаление записей сразу из двух таблиц - денормализация

2) Таблица-помощник берется из кеша запроса или создается на лету.

SELECT * FROM (SELECT id as entity_id FROM entity ORDER BY RAND(seed)) as helper
INNER JOIN entity as e ON (entity_id=e.id)
WHERE ...

Проблема: mysql не поддерживает кеш для subquery, не очень хочется переходить на mariaDb + не известно будет ли кешироваться запрос если будет order by rand(seed), в mysql точно не кешируется.

3) Сортировка id на php - результат вставляем в ORDER BY FIELD()
Один из самых медленных вариантов, чем больше записей - тем хуже рабоатет.

ЗЫ. postgreSQL не предлагать, я его не знаю, слишком дорого будет для компании, если я буду на проекте еще и postgreSQL учить, резибрать, дебажить...

 

[Вурдалак]

А как 3-й вариант зависит от кол-ва записей? Вам же нужно доставать только объекты, которые укладываются в страницу. Сами списки id-шников можно генерить где-нибудь в фоне.

А, фильтрация еще. Ну и пофиг, можно просто для полученного полного (без применения фильтров) списка id-шников сделать в том же фоне списки по различным характеристикам. Если юзер применяет фильтр, то через http://php.net/array_intersect_key находите пересечение. И потом делаете пагинацию по этому массиву id-шников.

 

[Redjik]

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

 

[grigori]

не верю, что тягать список через драйвер, преобразование в типы php и array_intersect_key в скриптовом движке быстрее, чем join по индексам

 

[Вурдалак]

grigori, через какой драйвер, какое преобразование типов? Да и bottleneck у вас — сортировка, а тут она будет в фоне.

 

[grigori]

Вурдалак, memcached + десериализация - подготовка одного списка, результат фильтрации будет проходить через mysqlnd - для второго списка, затем списки умножатся в array_intersect,
imho это будет дольше, чем умножение 2х индексов в mysql, limit по ним, и передача результата в php

 

[Вурдалак]

<?php

$a = range(0, 100000);
shuffle($a);

$b = range(0, 100000);
shuffle($b);
$b = array_slice($b, 0, 50000);

$c = range(0, 100000);
shuffle($c);
$c = array_slice($c, 0, 50000);

$a = serialize(array_flip($a));
$b = serialize(array_flip($b));
$c = serialize(array_flip($c));

$t = microtime(1);

$a = unserialize($a);
$b = unserialize($b);
$c = unserialize($c);

var_dump(count(array_intersect_key($a, $b, $c)));
var_dump(microtime(1) - $t);

$ php bench.php
int(24857)
float(0.047413110733032)

 

[grigori]

а какое отношение имеет к задаче скорость работы shuffle, range, array_slice, array_flip и serialize?
надо замерять Memcache::get и PDOStatement::fetchAll

в принцпе, 0.05 сек - примерно сопоставимо со временем исполнения нескольких sql-запросов

 

[Вурдалак]

grigori, если ты посмотришь внимательнее, все эти функции не участвуют в бенчмарке. Во-первых, это фиксированное время. Тот же список в ORDER BY FIELD() будет увеличивать время сортировки нелинейно. Во-вторых, это на моём ноуте, надо смотреть на реальных данных. Здесь 100000 значений, по 50K в каждом из фильтров. У вас пагиниция по 100K сущностей?

 

[Вурдалак]

надо замерять Memcache::get и PDOStatement::fetchAll

Замеряй.

 

[grigori]

да, мой вопрос некорректен, ты меряешь скорость 3х вызовов unserialize и 1го array_intersect_key для 50к случайных int в ключах массивов.
с учетом отсутствия фреймворка, шаблонов и хранилища данных, 0.04 секунды - не очень большое, но заметное время, однако, я не понимаю смысл этого числа

да я-то замерю, куда я денусь,
а какие выводы-то делать из твоих измерений? я ж понять пытаюсь

 

[Вурдалак]

99% времени тут занимает unserialize, это значит, что всё время работы зависит от максимального количества элементов в списке. Если у тебя 10K — это будет работать за 0.001, если у тебя 100K и 0.03 тебя не устраивает — тогда закажи на аутсорсе демона на плюсах, который будет держать в памяти эти списки id и будет отдавать сразу нужный page id-шников (нет bottleneck'а в виде unserialize'а). Я не понимаю в чём твои проблемы.

Кстати, не путай array_intersect и array_intersect_key, у них принципиально разный порядок по скорости.

 

[grigori]

пока проблемы в гражданской войне и в том, чтобы понять этот прошлый пост

 

[Вурдалак]

Вурдалак, memcached + десериализация - подготовка одного списка, результат фильтрации будет проходить через mysqlnd - для второго списка, затем списки умножатся в array_intersect

Вот здесь что-то не то, я предлагал так:

$list = Memcache->get(normalizeSeed($seed));

foreach ($filters as $filter) { // $filter = new Filter(Memcache->get($filter->getName().'_'.normalizeSeed($seed)));
    $list = $filter->apply($list); // array_key_intersect
}

$idList = Paginator->get($list, $page, $limit); // array_slice($list, $page * $limit, $limit)

$db->query('SELECT ... FROM entity WHERE id IN (?a) ORDER BY FIELD(id, ?a)', [$idList, $idList]);

 

[grigori]

Вурдалак, sorry что поздно отвечаю, но я не понимаю твой алгоритм:
что делает функция normalizeSeed()?
откуда взялся массив $filters и что в объекте $filter?

 

[Вурдалак]

normalizeSeed() в моём представлении — это типа $timestamp % 1000, потому что честно строить списки для каждого $timestamp может быть overkilling.
filters взялся от пользователя. Каждый фильтр содержит какой-то массив id-шников под каждый критерий. А сами id-шники, конечно, берутся из какого-то хранилища.
Ну а пересечение всех списков даст искомое упорядоченное множество id-шников, по которому можно делать пагинацию.

Но всё it depends, если у вас куча критериев, как на Яндекс.Маркет, то такая затея сомнительна: будет очень много списков.

 

[Redjik]

Но всё it depends, если у вас куча критериев, как на Яндекс.Маркет, то такая затея сомнительна: будет очень много списков.

Да, мой случай, у Григория меньше...

 

[fixxxer]

1) какая частота обновлений данных? Если не очень часто, то имеет смысл попробовать sphinx + expession ranker. Ну или какой-нибудь хипстерский еластик =)

2) сколько данных? Влезут ли они все сразу в память?