За последние 24 часа нас посетили 21056 программистов и 1110 роботов. Сейчас ищет 391 программист ...

Запрос с приоритетом

Тема в разделе "PostgreSQL", создана пользователем Chushkin, 29 дек 2019.

  1. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    В PG есть возможность запросов с приоритетом?
    Например:
    - есть список (1,2,3)
    - найти и вернуть запись со значением = 1
    - Если =1 нет, то вернуть =2
    - Если =2 нет, то вернуть =3 и т.д.
    Интересует наличие встроенной оптимизированной возможности.
    Ибо подзапросы и прочая хрень слишком медленно.

    п.с. В MySQL такой возможности нет и это проблема. Таких запросов будет много, - хотелось бы оптимальный движок под это.
     
  2. Sail

    Sail Старожил

    С нами с:
    1 ноя 2016
    Сообщения:
    1.591
    Симпатии:
    360
    @Chushkin, сортировка по условию и ограничение количества строк в выдаче.
     
    artoodetoo нравится это.
  3. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    11.068
    Симпатии:
    1.231
    Адрес:
    там-сям
    @Chushkin ты про сортировку по релевантности типа как в fulltext search ?
    --- Добавлено ---
    Или тебя интересует нечеткий (fuzzy) поиск?
     
  4. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Стандартные варианты не подходят - слишком медленно.
    Нужна встроенная оптимизированная возможность.
     
  5. Sail

    Sail Старожил

    С нами с:
    1 ноя 2016
    Сообщения:
    1.591
    Симпатии:
    360
    На всякий случай уточню. :rolleyes:
    Речь о том, что не нужен "запрос с приоритетом". Этот приоритет обеспечивается сортировкой.
    То есть, не надо выполнять последовательность:
    "- найти и вернуть запись со значением = 1
    - Если =1 нет, то вернуть =2
    - Если =2 нет, то вернуть =3 и т.д."
     
  6. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Ни то ни другое. Поиск должен быть чётким, однозначным.
    Примерно так.
    Представь, что есть 1 млн. сущностей, у каждой 100 разных значений. Т.е. всего 100 млн.записей.
    И есть список из 100 значений в заданном порядке.
    Нужно выбрать одну запись из 100 млн., у которой значение равно значению из заданного списка, но с учётом приоритета/порядка в списке. Т.е. первую подходящую из списка ("выборка с приоритетом").
    Задачу можно решить разными способами, - join, with и т.п. Но всё это медленно, - в среднем это 2.5 миллиарда подзапросов (жуть).
    Можно уменьшить число подзапросов и использовать упорядочение, но это ещё хуже/медленнее (двойная жуть).
    Отсюда интерес к поиску движка, где это оптимизировано.
    И отсюда вопрос: Есть ли такое в PG, оптимизированное под задачу "выборка с приоритетом"?
     
  7. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    11.068
    Симпатии:
    1.231
    Адрес:
    там-сям
    Честно говоря, не понимаю такое описание проблемы. Ты выбираешь из миллиона записей 100 подходящих по некоторым критериям. Среди этих 100 могут быть значения более подходящие и менее подходящие. Ты можешь их отсортировать соответственно от "лучшей" к "худшей". Уже не миллион тасуешь, а только 100.

    Я знаю что постгрес умеет всякие хитрые штуки не совсем SQL, но что именно тебя не устроило в данном случае как-то неочевидно.
    --- Добавлено ---
    Не получается подтолкнуть построитель запросов к эффективному плану?
    --- Добавлено ---
    Откуда взялись 2.5 млрд подзапросов? Ты думаешь что движок бд подзапросы буквально как вложенные циклы просчитывает? :) Нет.
     
    runcore нравится это.
  8. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Господа-товарищи, я задал вопрос, чтобы получить ответ, а не для того, чтобы потрепаться о сферическом коне. :) О нём мы потреплемся в другой теме.
    И конечно я проверил все стандартные варианты, прежде чем задать вопрос. Как любой нормальный разраб.
    И меня это не устроило. Почему - сказал.
    Если знаете как это сделать правильно - подскажите. Или укажите на особенность PG, которая позволит сделать это.
    Нужна скорость выборки максимум 0.1 сек. для 100 возвращаемых записей по условиям, указанным выше (100 млн.записей и т.д. и т.п.).
     
  9. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    11.068
    Симпатии:
    1.231
    Адрес:
    там-сям
    okay :) удачи!
     
    Valick нравится это.
  10. runcore

    runcore Старожил

    С нами с:
    12 окт 2012
    Сообщения:
    3.625
    Симпатии:
    158
    Поддерживаю @artoodetoo
    1) сначала уменьшаем кол-во элементов множества.те Выбираем ВСЕ варианты для данной сущности. их всего 100, по твоим словам.
    2) полученные сортируем с необходимым нам приоритетом. берем первую. Бинго.

    т.е. либо я неправильно понял задачу, либо ты усложняешь - простую задачу.
    Есть ссылки на подобный функционал в других БД(Oracle, MSSQL..)? дай ссылку, чтоб понять что именно ты имеешь в виду
     
  11. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    В теории всё отлично.
    Попробуй это сделать на 100 млн. И выбрать 100 записей таким способом (1 страница).
    Потом поделишься, чем отличается теория от практики.

    Не знаю. :(
    С Oracle никогда не работал, а с MSSQL не работал очень давно - забыл уже всё.
     
  12. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Попробую описать задачу более приземлённо.
    - Есть 1 млн. товаров.
    - У каждого товара есть 100 оттенков цветов.
    - Есть некий список приоритетов по оттенкам, размером 100 оттенков. (неважно откуда и как, просто "есть")
    Нужно показать посетителю товары с учётом списка приоритетов.
    Например, если в списке "зелёный, синий, чёрный,...", то посетителю нужно показать товар с зелёным оттенком, если есть. Если нет, то показать с синим. Если нет с синим, то с чёрным и т.д. Таким образом ему нужно выдать 1 страницу товаров (100 штук).
    Допустимое время выборки 100 товаров 0.1 секунды (фактически, время генерации страницы, +/-).

    п.с. Только не думайте, что в реальной задаче список товаров. :) Товары - для наглядности.
     
  13. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    11.068
    Симпатии:
    1.231
    Адрес:
    там-сям
    @Chushkin Я уже боюсь высказывать своё мнение. Именно потому, что задача кажется мне обычной. Я обычный программист, а не божественный, извини. Я таки попробую вывести разговор на конкретные примеры.

    Если мы таки будем считать, что речь о товарах, то у них может быть "модель" и несколько дополнительных признаков, в т.ч. цвет. При выдаче можно указать фильтры и сортировку, где один из параметров будет цвет или некая функция от цвета - по предпочтениям. Если к примеру пользователем выбрана сортировка по цене, но мы также знаем его цветовые предпочтения, то запрос может выглядеть так:

    Код (SQL):
    1. SELECT a,b,c,d,e,f,g,h
    2. FROM products
    3. WHERE условия_фильтра_которые_желательно_оптимизировать
    4. ORDER BY
    5.   price ASC, -- наивысший приоритет сортировки
    6.   FIELD(color, 'black', 'blue', 'green') DESC -- внутри одной цены в первую очередь будет показан зелёный товар
    https://www.db-fiddle.com/f/7s9gJQh2rZDd6ePpNwbRGg/1

    Сама по себе сортировка по выражению не использует индексы, но если индексы работают в фильтре и приоритетной сортировке, то это не большая проблема.
    --- Добавлено ---
    Мой FIELD() можно назвать "приоритетом"? Если нет, то покажи что надо изменить чтобы выразить приоритет по твоему.
     
    #13 artoodetoo, 31 дек 2019
    Последнее редактирование: 31 дек 2019
  14. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    "Раз пошла такая пьянка" или "Дело было вечером, делать было нечего".

    Упростим таблицы до предела, на примере для MySQL:
    PHP:
    1. CREATE TABLE `tProducts` (
    2.   `productID` int NOT NULL PRIMARY KEY
    3. );
    4. CREATE TABLE `tProductsColors` (
    5.   `productID` int NOT NULL,
    6.   `colorID` int NOT NULL,
    7.   PRIMARY KEY (`productID`,`colorID`)
    8. )
    В tProductsColors 28 млн.записей (всего!). В tProducts 0.5 млн.
    Классический вариант запроса на выборку с использованием упорядочивания (т.е. left join возвращает/находит первый подходящий из заданного списка):
    PHP:
    1. select p.*, pc.colorID
    2. from tProducts p
    3. left join tProductsColors pc on pc.productID = p.productID and colorID = (
    4.     select colorID
    5.     from tProductsColors
    6.     where productID = p.productID and colorID in (
    7.         68,73,45,35,5,58,40,7,98,59,31,1,89,39,17,88,51,52,69,54,
    8.         99,91,27,78,81,12,56,34,94,28,36,90,57,24,85,15,92,4,67,72,
    9.         95,32,64,11,30,80,8,96,100,10,48,37,16,41,76,3,2,79,33,43,
    10.         74,75,55,20,26,19,47,49,42,62,70,66,50,71,29,22,82,14,9,84,
    11.         23,44,53,87,21,63,46,61,18,77,38,86,6,93,13,65,97,83,25,60)
    12.     order by field(colorID,
    13.         68,73,45,35,5,58,40,7,98,59,31,1,89,39,17,88,51,52,69,54,
    14.         99,91,27,78,81,12,56,34,94,28,36,90,57,24,85,15,92,4,67,72,
    15.         95,32,64,11,30,80,8,96,100,10,48,37,16,41,76,3,2,79,33,43,
    16.         74,75,55,20,26,19,47,49,42,62,70,66,50,71,29,22,82,14,9,84,
    17.         23,44,53,87,21,63,46,61,18,77,38,86,6,93,13,65,97,83,25,60)
    18.     limit 1)
    19. limit 0, 100
    Некоторые параметры выборки:
    0, 100:
    Total Time: 0.017 sec, Innodb_rows_read# 16910 (хорошо)
    1000, 100 (это всего 11-я страница, 1100 строк):
    Total Time: 0.183 sec, Innodb_rows_read# 190087 (за гранью)
    10000, 100:
    Total Time: 1.678 sec, Innodb_rows_read# 1739161 (недопустимо)
    100000, 100:
    Total Time: 16.529 sec, Innodb_rows_read# 17233738 (жуть)
    499900, 100:
    Total Time: 1 m 23 sec, Innodb_rows_read# 86088721 (жуть в квадрате)
    где,
    Innodb_rows_read - The number of rows read from Innodb tables

    В принципе, можно избавится от упорядочивания и ускорить выборку в ~2 раза. Но это не решает проблему.
    Хотелось бы внутридвижковую, оптимизированную хрень, которая выполняет эту задачу на пару порядков быстрее.
    Я так понимаю, что в PG такой особенности нет. Или сильно засекречена и о ней никто не знает. :)

    Было бы любопытно узнать, а как PG справится с таким запросом на таких данных?
     
  15. romach

    romach Старожил

    С нами с:
    26 окт 2013
    Сообщения:
    2.904
    Симпатии:
    719
    @Chushkin отпишись, если таки решишь таск в один запрос.
     
  16. romach

    romach Старожил

    С нами с:
    26 окт 2013
    Сообщения:
    2.904
    Симпатии:
    719
    А ты его пробовал запускать? Мне кажется что он вернет не то что нужно, а что попалось первым в where in
     
  17. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    А как ты думаешь, "Некоторые параметры выборки" я от балды написал? ;)
    Вернёт то, что нужно, - для этого там "order by ... limit 1".
    "in" просто ограничивает выборку действительными для field() значениями, чтобы она не возвращала "0".
    Можно избавиться от IN, если использовать обратное упорядочивание (desc), соотвественно и сам список д.б. в обратном порядке "первый по приоритету - последний в списке". Но это частный случай, а в общем случае IN должен быть.
    --- Добавлено ---
    В MySQL не решаемо возможностями движка, однозначно.
    В PG, судя по этой теме, тоже не решаемо.
     
  18. romach

    romach Старожил

    С нами с:
    26 окт 2013
    Сообщения:
    2.904
    Симпатии:
    719
    но не должен, потому что порядок здесь не гарантируется ни разу: в IN может попасться первым любое color_id, которое удовлетворит всем условиям и отсортируется. Я уже молчу про то в каком порядке будет происходить join. Правильные результаты тут скорее везение, типа как с group by или select limit offset без сортировки. Стандарт позволяет отдавать всё что угодно (буквально, limit 100 offset 100 может вернуть те же строки, что и limit 100) и то что mysql при этом возвращает похожий на правду результат - это проблемы исключительно того, кто этому доверится. Как-то так )
    --- Добавлено ---
    Ну, я не думаю, сегодня 2 января так то ) Я просто указал на бд-специфичный момент и жду от кого-нибудь решения. Таск то интересный )
     
    artoodetoo нравится это.
  19. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Ты немного неправильно понимаешь работу запроса.
    По классике примерно так, последовательно:
    - Запрос выбирает все значения, согласно фильтру в WHERE
    - Упорядочивает согласно ORDER BY
    - Выбирает/возвращает первую запись согласно LIMIT

    Другое дело, что оптимизатор может улучшить алгоритм (что в реальности и происходит).
    Но результат выборки при этом не меняется.
    Вот если без order by, тогда да, результат не предсказуем по sql-стандарту.
     
  20. runcore

    runcore Старожил

    С нами с:
    12 окт 2012
    Сообщения:
    3.625
    Симпатии:
    158
    а сколько у тебя занимает времени запрос ?:
    Код (Text):
    1. select p.*
    2. from tProducts p
    3. limit 499900, 100;
     
  21. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Total Time: 0.062 sec, Innodb_rows_read# 500000
     
  22. Sail

    Sail Старожил

    С нами с:
    1 ноя 2016
    Сообщения:
    1.591
    Симпатии:
    360
    Получается "масло масляное" :)
    Однако, надо подзапрос использовать не для сранения (что инициирует его выполнение при поиске каждой строки итоговой выборки), а в качестве второй таблицы.
    "Классичкеская" задача выборки top-n из подгруппы. В данном случае - по паре (productID, colorID).
    В случае PostgreSQL, присмотритесь, например, к функции rank(), или другим "оконным функциям"
    --- Добавлено ---
    Ещё одно описание, на всякий случай :)
     
    romach нравится это.
  23. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Покажи как, - напиши запрос.
     
  24. Sail

    Sail Старожил

    С нами с:
    1 ноя 2016
    Сообщения:
    1.591
    Симпатии:
    360
    Для начала:
    Код (Text):
    1. select p.*, pc.colorID
    2. from tProducts p
    3. left join (
    4.     select productID, colorID
    5.     from tProductsColors
    6.     where colorID in (
    7.         68,73,45,35,5,58,40,7,98,59,31,1,89,39,17,88,51,52,69,54,
    8.         99,91,27,78,81,12,56,34,94,28,36,90,57,24,85,15,92,4,67,72,
    9.         95,32,64,11,30,80,8,96,100,10,48,37,16,41,76,3,2,79,33,43,
    10.         74,75,55,20,26,19,47,49,42,62,70,66,50,71,29,22,82,14,9,84,
    11.         23,44,53,87,21,63,46,61,18,77,38,86,6,93,13,65,97,83,25,60)
    12.     order by field(colorID,
    13.         68,73,45,35,5,58,40,7,98,59,31,1,89,39,17,88,51,52,69,54,
    14.         99,91,27,78,81,12,56,34,94,28,36,90,57,24,85,15,92,4,67,72,
    15.         95,32,64,11,30,80,8,96,100,10,48,37,16,41,76,3,2,79,33,43,
    16.         74,75,55,20,26,19,47,49,42,62,70,66,50,71,29,22,82,14,9,84,
    17.         23,44,53,87,21,63,46,61,18,77,38,86,6,93,13,65,97,83,25,60)
    18.     ) as pc on pc.productID = p.productID
    19. limit 0, 100
    (без группировки по productID и colorID, раз уж PRIMARY KEY (`productID`,`colorID`))
    Остаётся решить задачку "top-1" для подзапроса... :cool:
     
  25. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Не "Для начала:", а рабочий запрос. (написать что-то от балды каждый сможет)
    п.с. Результат выборки должен быть тот же, что в классическом варианте.