Как эффективно получить «самую последнюю соответствующую строку»?

53

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

У меня есть таблица, inventoryскажем, которая представляет инвентарь, который я держу в определенный день.

date       | good | quantity
------------------------------
2013-08-09 | egg  | 5
2013-08-09 | pear | 7
2013-08-02 | egg  | 1
2013-08-02 | pear | 2

и таблица, скажем, «цена», которая содержит цену товара в данный день

date       | good | price
--------------------------
2013-08-07 | egg  | 120
2013-08-06 | pear | 200
2013-08-01 | egg  | 110
2013-07-30 | pear | 220

Как я могу эффективно получить «самую последнюю» цену для каждой строки таблицы инвентаря, т.е.

date       | pricing date | good | quantity | price
----------------------------------------------------
2013-08-09 | 2013-08-07   | egg  | 5        | 120
2013-08-09 | 2013-08-06   | pear | 7        | 200
2013-08-02 | 2013-08-01   | egg  | 1        | 110
2013-08-02 | 2013-07-30   | pear | 2        | 220

Я знаю один способ сделать это:

select inventory.date, max(price.date) as pricing_date, good
from inventory, price
where inventory.date >= price.date
and inventory.good = price.good
group by inventory.date, good

и затем присоедините этот запрос снова к инвентарю. Для больших таблиц даже выполнение первого запроса (без повторного присоединения к инвентарю) выполняется очень медленно. Тем не менее, та же проблема быстро решается, если я просто использую свой язык программирования для выдачи одного max(price.date) ... where price.date <= date_of_interest ... order by price.date desc limit 1запроса на каждый date_of_interestиз таблицы инвентаризации, поэтому я знаю, что нет никаких вычислительных затруднений. Однако я предпочел бы решить всю проблему с помощью одного запроса SQL, поскольку это позволило бы мне выполнить дальнейшую обработку SQL по результату запроса.

Есть ли стандартный способ сделать это эффективно? Такое чувство, что оно должно появляться часто и что должен быть способ написать быстрый запрос.

Я использую Postgres, но был бы признателен общий ответ на SQL.

Том Эллис
источник
3
Голосовали за перенос на DBA.SE, так как это вопрос эффективности. Мы можем написать запрос несколькими различными способами, но это не сделает его намного быстрее.
ypercubeᵀᴹ
5
Вам действительно нужны все товары за все дни из одного запроса? Похоже, маловероятное требование? Чаще всего можно получить цены на конкретную дату или цены для конкретного товара (на определенную дату). Эти альтернативные запросы могли бы намного легче извлечь выгоду из (соответствующих) индексов. Нам также нужно знать: количество элементов (сколько строк в каждой таблице?), Полное определение таблицы, вкл. типы данных, ограничения, индексы, ... (используйте \d tblв psql), ваша версия Postgres и мин. / Макс. количество цен за товар.
Эрвин Брандштеттер,
@ErwinBrandstetter Вы просите меня принять ответ? Я не совсем квалифицирован, чтобы знать, что лучше, хотя, поскольку у вас больше всего голосов, я с радостью приму это.
Том Эллис
Принимайте, только если он отвечает на ваш вопрос или работает на вас. Вы можете даже оставить комментарий о том, как поступили, если это может помочь в связанных случаях. Если вы чувствуете, что на ваш вопрос нет ответа, сообщите нам.
Эрвин Брандштеттер,
1
Тогда я должен извиниться, потому что, хотя я получил, как мне кажется, отличные ответы, я больше не работаю над проблемой, которая спровоцировала вопрос, поэтому мне некуда судить, какой ответ является лучшим, или, если действительно, любой из них действительно подходят для моего случая использования (как это было). Если есть какой-то этикет DBA.Stackexchange, которому я должен следовать в этом случае, пожалуйста, дайте мне знать.
Том Эллис

Ответы:

42

Это очень зависит от обстоятельств и точных требований. Рассмотрим мой комментарий к вопросу .

Простое решение

С DISTINCT ONв Postgres:

SELECT DISTINCT ON (i.good, i.the_date)
       i.the_date, p.the_date AS pricing_date, i.good, p.price
FROM   inventory  i
LEFT   JOIN price p ON i.good = p.good AND i.the_date >= p.the_date
ORDER  BY i.good, i.the_date, p.the_date DESC;

Заказанный результат.

Или NOT EXISTSв стандартном SQL (работает с каждой знакомой мне СУБД):

SELECT i.the_date, p.the_date AS pricing_date, i.good, i.quantity, p.price
FROM   inventory  i
LEFT   JOIN price p ON p.good = i.good AND p.the_date <= i.the_date
WHERE  NOT EXISTS (
   SELECT 1 FROM price p1
   WHERE  p1.good = p.good
   AND p1.the_date <= i.the_date
   AND p1.the_date >  p.the_date
   );

Тот же результат, но с произвольным порядком сортировки - если только вы не добавите ORDER BY.
В зависимости от распределения данных, точных требований и показателей любой из них может быть быстрее.
Как правило, DISTINCT ONэто победитель, и вы получаете отсортированный результат поверх него. Но в некоторых случаях другие методы запросов (намного) еще быстрее. Смотри ниже.

Решения с подзапросами для вычисления максимальных / минимальных значений обычно медленнее. Варианты с CTE, как правило, медленнее, но все же.

Простые представления (например, предложенные в другом ответе) совсем не помогают производительности в Postgres.

SQL Fiddle.


Правильное решение

Строки и сопоставление

Прежде всего, вы страдаете от неоптимального расположения таблицы. Это может показаться тривиальным, но нормализация вашей схемы может иметь большое значение.

Сортировка по типам символов ( text, varchar, ...) должно быть сделано в соответствии с локалью - в COLLATION в частности. Скорее всего, ваша БД использует некоторый локальный набор правил (например, в моем случае:) de_AT.UTF-8. Узнайте с помощью:

SHOW lc_collate;

Это замедляет сортировку и поиск по индексу . Чем дольше ваши строки (названия товаров), тем хуже. Если вы на самом деле не заботитесь о правилах сортировки в выходных данных (или о порядке сортировки вообще), это может быть быстрее, если вы добавите COLLATE "C":

SELECT DISTINCT ON (i.good COLLATE "C", i.the_date)
       i.the_date, p.the_date AS pricing_date, i.good, p.price
FROM   inventory  i
LEFT   JOIN price p ON i.good = p.good AND i.the_date >= p.the_date
ORDER  BY i.good COLLATE "C", i.the_date, p.the_date DESC;

Обратите внимание, как я добавил сопоставление в двух местах.
В два раза быстрее в моем тесте с 20 тыс. Строк в каждой и очень простыми именами ('good123').

Индекс

Если ваш запрос должен использовать индекс, столбцы с символьными данными должны использовать сопоставление ( goodв примере):

CREATE INDEX inventory_good_date_desc_collate_c_idx
ON price(good COLLATE "C", the_date DESC);

Обязательно прочитайте последние две главы этого связанного ответа на SO:

Вы можете даже иметь несколько индексов с разными параметрами сортировки в одних и тех же столбцах - если вам также нужны товары, отсортированные согласно другому (или стандартному) параметру сортировки в других запросах.

Нормализовать

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

CREATE TABLE good (
  good_id serial PRIMARY KEY
, good    text   NOT NULL
);

CREATE TABLE inventory (
  good_id  int  REFERENCES good (good_id)
, the_date date NOT NULL
, quantity int  NOT NULL
, PRIMARY KEY(good_id, the_date)
);

CREATE TABLE price (
  good_id  int     REFERENCES good (good_id)
, the_date date    NOT NULL
, price    numeric NOT NULL
, PRIMARY KEY(good_id, the_date));

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

CREATE INDEX price_good_date_desc_idx ON price(good, the_date DESC);

Опять же, сопоставление должно соответствовать вашему запросу (см. Выше).

В Postgres 9.2 или более поздних версиях «индексы покрытия» для сканирования только по индексу могут помочь еще больше - особенно если в ваших таблицах содержатся дополнительные столбцы, что делает таблицу значительно больше, чем индекс покрытия.

Эти результирующие запросы выполняются намного быстрее:

НЕ СУЩЕСТВУЕТ

SELECT i.the_date, p.the_date AS pricing_date, g.good, i.quantity, p.price
FROM   inventory  i
JOIN   good       g USING (good_id)
LEFT   JOIN price p ON p.good_id = i.good_id AND p.the_date <= i.the_date
AND    NOT EXISTS (
   SELECT 1 FROM price p1
   WHERE  p1.good_id = p.good_id
   AND    p1.the_date <= i.the_date
   AND    p1.the_date >  p.the_date
   );

ОТЛИЧАЕТСЯ НА

SELECT DISTINCT ON (i.the_date)
       i.the_date, p.the_date AS pricing_date, g.good, i.quantity, p.price
FROM   inventory  i
JOIN   good       g USING (good_id)
LEFT   JOIN price p ON p.good_id = i.good_id AND p.the_date <= i.the_date
ORDER  BY i.the_date, p.the_date DESC;

SQL Fiddle.


Более быстрые решения

Если это все еще не достаточно быстро, могут быть более быстрые решения.

Рекурсивный CTE / JOIN LATERAL/ коррелированный подзапрос

Специально для распространения данных со многими ценами за товар :

Материализованный вид

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

Postgres 9.3+ имеет автоматическую поддержку материализованных представлений. Вы можете легко реализовать базовую версию в более старых версиях.

Эрвин Брандштеттер
источник
3
price_good_date_desc_idxИндекс вы рекомендуете значительно улучшили производительность аналогичного запроса шахты. Мой план запроса изменился от стоимости 42374.01..42374.86до 0.00..37.12!
Цимманон
@ cimmanon: Отлично! Какова ваша основная функция запроса? НЕ СУЩЕСТВУЕТ? ОТЛИЧАЕТСЯ НА? ГРУППА ПО?
Эрвин Брандштеттер
Использование DISTINCT ON
cimmanon
6

К вашему сведению, я использовал mssql 2008, поэтому у Postgres не будет индекса «включить». Однако использование базовой индексации, показанной ниже, изменится с хеш-соединений на слияния в Postgres: http://explain.depesz.com/s/eF6 (без индекса) http://explain.depesz.com/s/j9x ( с индексом по критериям объединения)

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

create view mostrecent_pricing_dates_per_good as
select i.good,i.date i_date,max(p.date)p_date
  from inventory i
  join price p on i.good = p.good and i.date >= p.date
 group by i.good,i.date;

Тогда ваш запрос может стать более простым и легким для манипулирования другими видами, если запрос (например, использование левых соединений для поиска ресурсов без последних ценовых дат):

select i.good
       ,i.date inventory_date
       ,i.quantity
       ,p.date pricing_date
       ,p.price       
  from inventory i
  join price p on i.good = p.good
  join mostrecent_pricing_dates_per_good x 
    on i.good = x.good 
   and p.date = x.p_date
   and i.date = x.i_date

Это дает следующий план выполнения: http://sqlfiddle.com/#!3/24f23/1 нет индексации

... Все сканы с полной сортировкой. Обратите внимание, что затраты производительности на хеш-совпадения занимают большую часть общей стоимости ... и мы знаем, что сканирование и сортировка таблицы выполняются медленно (по сравнению с целью: поиск индекса).

Теперь добавьте базовые индексы, чтобы помочь критериям, используемым в вашем объединении (я не утверждаю, что это оптимальные индексы, но они иллюстрируют суть): http://sqlfiddle.com/#!3/5ec75/1 с базовой индексацией

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

Последняя итерация использует «include» в индексах, чтобы план мог легко скользить и получать дополнительно запрашиваемые данные прямо из самого индекса. Итак, поиск пропал: http://sqlfiddle.com/#!3/5f143/1 введите описание изображения здесь

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

  1. Он создает понятные структуры данных в вашей базе данных, которые легче составлять и повторно использовать в других областях приложения.
  2. Все самые дорогостоящие операторы запросов были исключены из плана запросов с использованием некоторой базовой индексации.
cocogorilla
источник
3
Это хорошо (для SQL-сервера), но оптимизирует для разных СУБД, хотя и имеет сходства, но и с серьезными различиями.
ypercubeᵀᴹ
@ypercube это правда. Я добавил некоторые уточнения о Postgres. Мое намерение состояло в том, что большая часть мыслительного процесса, показанного здесь, будет применяться независимо от специфических особенностей СУБД.
Кокогорилла
Ответ очень глубокий, поэтому мне понадобится некоторое время, чтобы опробовать его. Я дам вам знать, как у меня дела.
Том Эллис
5

Если у вас есть PostgreSQL 9.3 (выпущен сегодня), то вы можете использовать LATERAL JOIN.

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

SELECT  Inventory.Date,
        Inventory.Good,
        Inventory.Quantity,
        Price.Date,
        Price.Price
FROM    Inventory
        LATERAL
        (   SELECT  Date, Price
            FROM    Price
            WHERE   Price.Good = Inventory.Good
            AND     Price.Date <= Inventory.Date
            ORDER BY Price.Date DESC
            LIMIT 1
        ) p;

Это в основном эквивалентно приложению SQL-Server APPLY , и для демонстрационных целей есть работающий пример этого на SQL-Fiddle .

GarethD
источник
5

Как отмечали Эрвин и другие, эффективный запрос зависит от множества переменных, и PostgreSQL очень старается оптимизировать выполнение запроса на основе этих переменных. Как правило, сначала вы хотите написать для ясности, а затем изменить производительность после выявления узких мест.

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

Первое, что нужно попробовать, это просто сделать вид и присоединиться к нему:

CREATE VIEW most_recent_rows AS
SELECT good, max(date) as max_date
FROM inventory
GROUP BY good;

Это должно хорошо работать при выполнении чего-то вроде:

SELECT price 
  FROM inventory i
  JOIN goods g ON i.goods = g.description
  JOIN most_recent_rows r ON i.goods = r.goods
 WHERE g.id = 123;

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

Второе, что вы можете сделать, это добавить в таблицу инвентаризации столбец most_recent bool и

create unique index on inventory (good) where most_recent;

Затем вы захотите использовать триггеры, чтобы установить значение Most_recent равным false, когда была вставлена ​​новая строка для товара. Это добавляет больше сложности и больше шансов для ошибок, но это полезно.

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

Обновите комментарий Эрвина ниже, похоже, я неправильно это понял. Перечитывая вопрос, я совсем не уверен, что задают. Я хочу упомянуть в обновлении, что является потенциальной проблемой, которую я вижу, и почему это оставляет неясным.

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

Вы не можете предполагать, что одна дата указывает цену на данный товар. Цены в любом бизнесе могут быть согласованы на контрагента и даже иногда на транзакцию. По этой причине вы действительно должны хранить цену в таблице, которая фактически обрабатывает входящий или исходящий инвентарь (таблица инвентаризации). В таком случае ваша таблица дат / товаров / цен просто указывает базовую цену, которая может быть изменена на основе переговоров. В таком случае эта проблема переходит от проблемы отчетности к проблеме, которая является транзакционной и работает по одной строке из каждой таблицы за раз. Например, вы можете посмотреть цену по умолчанию для данного товара в данный день как:

 SELECT price 
   FROM prices p
   JOIN goods g ON p.good = g.good
  WHERE g.id = 123 AND p."date" >= '2013-03-01'
  ORDER BY p."date" ASC LIMIT 1;

С индексом цен (товар, дата) это будет хорошо работать.

Если это надуманный пример, возможно, что-то более близкое к тому, над чем вы работаете, поможет.

Крис Траверс
источник
most_recentПодход должен хорошо работать на самую последнюю цену абсолютно . Казалось бы, ОП требует самой последней цены относительно каждой даты инвентаризации.
Эрвин Брандштеттер,
Хорошая точка зрения. Перечитывая, я замечаю некоторые реальные практические недостатки предлагаемых данных, но не могу сказать, является ли это лишь надуманным примером. В качестве надуманного примера я не могу сказать, чего не хватает. Может быть, обновление, чтобы указать это было бы в порядке тоже.
Крис Треверс
@ChrisTravers: это надуманный пример, но я не вправе публиковать фактическую схему, с которой я работаю. Возможно, вы могли бы немного рассказать о том, какие практические недостатки вы заметили.
Том Эллис
Я не думаю, что это должно быть точным, но беспокоюсь о проблеме, потерянной в аллегории. Что-то немного ближе было бы полезно. Проблема заключается в том, что при ценообразовании цена в определенный день, вероятно, будет по умолчанию, и, следовательно, вы не будете использовать ее для отчетов только в качестве значения по умолчанию для ввода транзакции, поэтому ваши интересные запросы обычно представляют собой всего несколько строк в время.
Крис Треверс
3

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

with cte as (
  select
    good,
    price,
    date,
    coalesce(lead(date) over(partition by good order by date) - 1
            ,Now()::date) as ndate
  from
    price
)

select * from inventory i join cte on
  (i.good = cte.good and i.date between cte.date and cte.ndate)

SqlFiddle

Томас Грайф
источник
1

Используйте объединение из инвентаря в цену с условиями соединения, которые ограничивают записи из таблицы цен только теми, которые находятся на или до даты инвентаризации, затем извлекают максимальную дату, и где дата является самой высокой датой из этого подмножества

Итак, для вашей инвентарной цены:

 Select i.date, p.Date pricingDate,
    i.good, quantity, price        
 from inventory I join price p 
    on p.good = i.good
        And p.Date = 
           (Select Max(Date from price
            where good = i.good
               and date <= i.Date)

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


источник
К сожалению, не ускоряет процесс.