Коллеги, приветствую!

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

Итак, требуется хранить в базе (PostgreSQL) набор прямоугольников на плоскости. Прямоугольники могут накладываться друг на друга, поэтому чтобы избежать случайности в наложении каждому прямоугольнику присвоено весовое значение:

TABLE data(
id integer PRIMARY KEY; -- идентификатор
mybox box; -- прямоугольник, далее - бокс
weight float8; -- вес
);

Задача состоит в том, чтобы осуществлять выборку самых лёгких боксов внутри определённой области прямоугольной формы (далее будем называть её "мегаплиткой") так, чтобы плотность боксов (количество боксов на единицу площади) не превышала бы определённого порогового значения в N штук на площадь. Если мы назовём "плиткой" прямоугольник со стороной в 1/8 стороны мегаплитки, т.е. разобьём мегаплитку на 256 равных плиток, то требование плотности удовлетворительно упрощается до "не более N боксов на одну плитку".
Есть еще требование на размер прямоугольника относительно размера мегаплитки, однако им для рассмотрения можно пренебречь, но стоит помнить, что в выборках оно так же учитывается.

У меня уже почти есть лобовое решение задачи (оно ещё не полностью реализовано, но всё понятно, как делать):

1) написана SQL-функция, состоящая из одного SELECT, выполняющего выборку N самых лёгких боксов внутри плитки (при этом, пользуемся встроенной в постгрес поддержкой геометрических фигур для определения размера бокса и пересечения плитки с боксом). Функция возвращает массив идентификаторов подходящих боксов. Выглядит она так (условие размера на бокс удалено за несущественностью):
CREATE OR REPLACE FUNCTION get_boxes_tile(tile box) RETURNS integer[] AS
$$
SELECT ARRAY( SELECT id FROM data WHERE mybox && $1 ORDER BY weight DESC LIMIT N );
$$ LANGUAGE sql STRICT STABLE;

2) внутри plpgsql-функции создаём разбиение мегаплитки на плитки, и для каждой из 8*8==256 плиток вычисляем с помощью get_boxes_tile() входящие в них боксы. Затем сливаем массивы в единый список, для которого уже извлекаем из базы значения самих боксов и возвращаем их вызывающему.

Теперь собственно вопрос: а как бы это оптимизировать? Ведь фактически получается, что для каждой выборки на одну мегаплитку база будет выполнять 256 проходов по таблице data и хорошо, но нереально, если там 100 строк. Но 10 000 или 100 000 - куда более реальное значение и база будет обсчитывать один запрос очень долго.
Можно ли как-то составить запрос в функции get_boxes_tile() таким образом, чтобы он за один проход по базе вычислял бы боксы для нескольких плиток? (добавить в WHERE AND "пересечение бокса с соседней плиткой" не пойдёт, т.к. при этом нарушится условие плотности - LIMIT будет считаться для двух плиток, а не одной).

Спасибо.

miksoft,

> 1) а почему нельзя одним запросом получить все боксы, находящиеся внутри мегаплитки, и этот список разбирать уже процедурно?

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


> 2) PostgreSQL умеет для выборки боксов применять какие-либо индексы? Если да, то откуда "256 проходов по таблице data" ?

Честно говоря, у меня нет никаких значимых знаний на эту тему, поэтому и спрашиваю.

miksoftВот с этого и начните чтение документации. Даже при беглом просмотре вижу, что актуальны разделы 9.11. Geometric Functions and Operators и 11.2. Index Types . В т.ч. обратите внимание на ключевое слово GiST.

Спасибо, вы уже здорово мне помогли :)
Геометрические операторы я уже, наверное, наизусть помню, а за GiST спасибо, не знал. Это кое-что облегчит.
Но правильно ли я понимаю, что GiST облегчит базе только проход по таблице при обработке одного SELECT ? И если (как я описывал в "лобовом" алгоритме) выполнять отдельный вызов функции get_boxes_tile() для обработки каждой из 256 плиток, то всё равно будет 256 обращений к таблице (пусть благодаря GiST и не полных проходов по ней). А можно ли как-нить сократить число обращений?

miksoftВы бы спрашивали хотя бы в профильном подфоруме...
Да я ещё толком не понял даже, насколько это постгрессо-специфичный вопрос ;)
Сейчас выложу там ссылку сюда, спасибо за идею.

miksoftАречИ если (как я описывал в "лобовом" алгоритме) выполнять отдельный вызов функции get_boxes_tile() для обработки каждой из 256 плиток, то всё равно будет 256 обращений к таблице (пусть благодаря GiST и не полных проходов по ней). А можно ли как-нить сократить число обращений?Сократить-то можно..
А как конкретно? Я не понимаю, как составить тогда запрос, чтобы, например, одним селектом для двух плиток проверять плотности и находить N самых лёгких. Два LIMITа получается?.. И как же их вкорячить в один селект?

miksoftАречА как конкретно? Я не понимаю, как составить тогда запрос, чтобы, например, одним селектом для двух плиток проверять плотности и находить N самых лёгких. Два LIMITа получается?.. И как же их вкорячить в один селект?Это тоже постгрессо-специфичный вопрос :)
В MySQL я бы такое сделал при помощи переменных в запросе. PostgreSQL, извините, не знаю.
В крайнем случае LIMIT можно убрать вообще и вычислять его уже процедурно.
О! Кстати, процедурно это может оказаться маза! Попробую и этот вариант, спасибо!!

CVTМожет, у меня плохо с математикой, но почему
авторсоздаём разбиение мегаплитки на плитки, и для каждой из 8*8==256 плиток?
))))))))))))))))))))))))))) да, вы правы)))))))))) недосып начинает сурово сказываться))))
Но всё же сильно на суть это не влияет, мне кажется :)

Kruchinin PahanЕсть специфичная фича в PG. DISTINCT ON (Fld1, Fld2, ... , FldN) ... ORDER BY Fld1, Fld2, ... , FldN, FldN+1, ... , FldN+M

Почитайте внимательно, безотносительно вашей задачи, как раз и дает LIMIT по N значениям.
Большое спасибо, сейчас займусь!

Kruchinin PahanЕсть специфичная фича в PG. DISTINCT ON (Fld1, Fld2, ... , FldN) ... ORDER BY Fld1, Fld2, ... , FldN, FldN+1, ... , FldN+M

Почитайте внимательно, безотносительно вашей задачи, как раз и дает LIMIT по N значениям.

Хм... Честно говоря, не понял.

1) DISTINCT отбирает в результат только те ряды, для которых отличается результат вычисления хоть одного выражения. Правильно? Соответственно DISTINCT ON (Fld1, Fld2, ... , FldN) (с ордером, но не суть) даст только те ряды, в которых (Fld1, Fld2, ... , FldN) различны. Но откуда следует, что это эквивалентно LIMIT N? Количество таких различий зависит и от разнообразия входных данных, а в LIMIT N это не так.
Например, у меня в таблице три поля: Fld1, Fld2, Fld3. Первое константа, второе принимает 3 значение, третье произвольно. Строю SELECT DISTINCT ON (fld1, fld2) * from my_table order by fld1, fld2, fld3; - и в результате получу 3 значения, но никак не 2. Или я что-то не так понимаю?

2) если у меня где-то ошибка в (1), то как мне сформировать условия DISTINCT, чтобы ограничение в N элементов работало бы по одному полю weight? Как??

Спасибо

АречПервое константа, второе принимает 3 значение
Пардон, опечатка, правильно:
Первое константа, второе принимает 3 значени я

Gold_Мне одному задача не понятна? :)
Не исключено :)

> Исходное задание можно увидеть ?
Фактически, описанное и есть исходное задание.
Ещё можно добавить, что все боксы вписаны внутрь одного большого прямоугольника, контейнера. Мегаплитки - это по сути фиксированные варианты разбиения контейнера. Есть вариант, когда мегаплитка представляет собой весь контейнер, на следующем уровне зума сторона контейнера делится пополам и сам контейнера разбивается таким образом на 4 мегаплитки, на следующем - ещё вдвое, всего на 8 мегаплиткок и так далее примерно полтора десятка раз.

> Что такое "весовое значение"?
Возможно, понятие z-order вам ближе?

> Что такое "случайности в наложении"?
Выборка из базы, особенно ограниченная limit, должна быть упорядочена, иначе порядок и в случае с limit вообще сами возвращённые строки, будут произвольными, зависящими от реализации.

> Если только часть бокса внутри мегаплитки он входит в "плотность боксов"?
Да, без сомнения. Он же присутствует в заданной точки плоскости, значит вносит свой вклад в плотность.

> Не понял как разбиение упростило условие?
Ну, по крайней мере хоть стало ясно, как решать задачу плотности. Это, конечно, не dx->0, dy->0 с классическим интегрированием по площади, но всё же вполне достаточно для удовлетворительного результата.

> "Плотность боксов" должна отслеживать база?
Да, конечно. В условиях же написал, что кол-во боксов может быть сотни тысяч и более.