Как оптимизировать внутреннее самостоятельное соединение? - PullRequest
Новая
       9

Как оптимизировать внутреннее самостоятельное соединение?

0 голосов
/ 02 июня 2019

У меня 1 миллион ведер шариков.Каждый шар имеет ряд атрибутов (и не все атрибуты имеют смысл для каждого мяча - например, мяч для гольфа нельзя надуть / сдуть).

buckets and balls visualization

Пользователи ищут ведра и шары в зависимости от конкретных требований к мячу.Например, пользователь может спросить, какие корзины содержат golf ball, red ball и red soccer ball?В этом примере ведро с мячом для гольфа и одним красным футбольным мячом, но никакие другие красные шары не удовлетворяют запросу (нам нужен по крайней мере еще один красный шар; два красных футбольных мяча сделали бы это. Другими словами, один мячне может одновременно удовлетворить несколько частей запроса).Таким образом, запрос будет выглядеть примерно так: 

[{
    ball_type: "golf"
},{
    color: "red"
},{
    color: "red",
    ball_type: "soccer"
}]

Приложение возвращает как bucket ids, так и ball ids, которые удовлетворяют требованиям в каждом сегменте (предпочтительно таким образом, чтобы сопоставить соответствующий идентификатор шара сзапрос соответствует).Например, возможный возврат будет выглядеть следующим образом: 

[{
    bucket_id: 1,
    ball_ids: [{
        query: “golf ball”,
        ball_id: 1,
    },{
        query: “red ball”,
        ball_id: 6,
    },{
        query: “red soccer ball”,
        ball_id: 14,
    }]
},
 ... other matches ...
]

Но это будет так же хорошо: 

    bucket_id: 1,
    ball_ids: {
        query0_ball_id: 1,
        query1_ball_id: 6,
        query2_ball_id: 14
    }

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

Мое текущее решение состоит в том, чтобы использовать таблицу, которая выглядит следующим образом: 

ball_id | ball_type | color | weight | is_inflated | bucket_id
--------------------------------------------------------------
0       | cricket   | red   | 157    | NULL        | 1
1       | golf      | green | 45.93  | NULL        | 1
[etc.]

Запросы, а затем полагаются на собственные внутренние объединения (FROM balls as b0 INNER JOIN balls as b1), где b0.bucket_id = b1.bucket_id.Примерно так: 

SELECT
    b0.bucket_id AS bucket_id,
    b0.ball_id AS ball_0,
    b1.ball_id AS ball_1,
    b2.ball_id AS ball_2
FROM balls AS b0
INNER JOIN balls AS b1 ON
    b0.bucket_id = b1.bucket_id
INNER JOIN balls AS b2 ON
    b0.bucket_id = b2.bucket_id
WHERE
        -- each ball must be unique
        b0.ball_id != b1.ball_id AND b0.ball_id != b2.ball_id AND b1.ball_id != b2.ball_id

    -- match balls to requirements
    AND
        b0.ball_type = 'golf'
    AND
        b1.color = 'red'
    AND
        b2.color = 'red' AND b2.ball_type = 'soccer'

Это довольно эффективно, когда я ищу только ведра, в которых есть два типа шариков.Также хорошо, когда я ищу несколько шаров, которые в целом редки.

Проблема в том, что, когда я ищу три шара, которые встречаются 10000 раз, соединения становятся невероятно дорогими, даже если результат составляет всего 30 корзин.Таким образом, запросы, которые я хочу выполнить менее 100 мс, занимают более 5000 мс (и, очевидно, добавление еще одного общего шарика к запросу умножит проблему).Примечание. Самая дорогая часть моего (postgres) запроса - «Параллельное сканирование кучи растровых изображений», значение которого я еще не до конца понимаю.

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

Я открыт для альтернативных структур данных, но я думаю, что это заставляет этот вопросслишком открытоЯ хочу придерживаться моего postgres db и структуры, которую я описываю выше, если это не ужасная идея по какой-то причине, потому что: (1) это облегчает концептуально другим разработчикам вход в этот проект, (2) это требует меньше времениот меня, чтобы узнать основную технологию (этот материал - только хобби).

...