Comment obtenir efficacement «la rangée la plus récente correspondante»?

J'ai un modèle de requête qui doit être très courant, mais je ne sais pas comment écrire une requête efficace pour celui-ci. Je veux rechercher les lignes d'une table qui correspondent à "la date la plus récente pas après" les lignes d'une autre table.

J'ai un tableau, par inventoryexemple, qui représente l'inventaire que je tiens un jour donné.

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

et une table, "prix" par exemple, qui contient le prix d'un bien un jour donné

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

Comment puis-je obtenir efficacement le prix "le plus récent" pour chaque ligne du tableau d'inventaire, c'est-à-dire

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

Je connais un moyen de faire cela:

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

et rejoignez à nouveau cette requête pour inventorier. Pour les grandes tables, même faire la première requête (sans rejoindre à nouveau l' inventaire) est très lente. Cependant, le même problème est rapidement résolu si j'utilise simplement mon langage de programmation pour émettre une max(price.date) ... where price.date <= date_of_interest ... order by price.date desc limit 1requête pour chaque requête à date_of_interestpartir de la table d'inventaire. Je sais donc qu'il n'y a pas de problème de calcul. Toutefois, je préférerais résoudre le problème dans son intégralité avec une requête SQL unique, car cela me permettrait de poursuivre le traitement SQL sur le résultat de la requête.

Existe-t-il un moyen standard de le faire efficacement? Il me semble que cela doit souvent arriver et qu'il devrait y avoir un moyen d'écrire une requête rapide pour cela.

J'utilise Postgres, mais une réponse générique SQL serait appréciée.

Cela dépend beaucoup des circonstances et des exigences exactes. Considérez mon commentaire à la question .

Solution simple

Avec DISTINCT ONdans 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;

Résultat commandé.

Ou avec NOT EXISTSen SQL standard (fonctionne avec tous les SGBDR que je connais):

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
   );

Même résultat, mais avec un ordre de tri arbitraire - sauf si vous ajoutez ORDER BY.
En fonction de la distribution des données, des exigences exactes et des index, l'un ou l'autre peut être plus rapide.
En général, DISTINCT ONc'est le vainqueur et vous obtenez un résultat trié en plus. Mais dans certains cas, d’autres techniques d’interrogation sont (beaucoup) plus rapides, pour le moment. Voir ci-dessous.

Les solutions avec sous-requêtes pour calculer les valeurs max / min sont généralement plus lentes. Les variantes avec CTE sont généralement plus lentes encore.

Les vues claires (comme celles proposées par une autre réponse) n’aident pas du tout les performances dans Postgres.

Fiddle SQL.

Bonne solution

Cordes et collation

Tout d'abord, vous souffrez d'une disposition de table sous-optimale. Cela peut sembler trivial, mais normaliser votre schéma peut aller très loin.

Tri par types de caractères ( text, varchar...) doit être fait selon les paramètres locaux - le COLLATIONNEMENT en particulier. Il est fort probable que votre base de données utilise un ensemble de règles locales (comme dans mon cas:) de_AT.UTF-8. Découvrez avec:

SHOW lc_collate;

Cela rend le tri et l' index look-ups plus lent . Plus vos ficelles (noms de marchandises) sont longues, plus les choses vont mal. Si vous ne vous souciez pas réellement des règles de classement dans votre sortie (ou de l'ordre du tri), cela peut être plus rapide si vous ajoutez 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;

Notez comment j'ai ajouté le classement à deux endroits.
Deux fois plus vite dans mon test avec 20k lignes chacune et des noms très basiques ('good123').

Indice

Si votre requête est supposée utiliser un index, les colonnes contenant des données de type caractères doivent utiliser un classement correspondant ( gooddans l'exemple):

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

Assurez-vous de lire les deux derniers chapitres de cette réponse sur SO:

• Sélectionnez la première ligne de chaque groupe GROUP BY?

Vous pouvez même avoir plusieurs index avec des classements différents sur les mêmes colonnes - si vous avez également besoin de marchandises triées selon un autre classement (ou le classement par défaut) dans d'autres requêtes.

Normaliser

Les chaînes redondantes (nom du bien) gonflent également vos tables et index, ce qui ralentit encore le processus. Avec une bonne disposition de la table, vous pourriez éviter la plupart des problèmes. Pourrait ressembler à ceci:

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));

Les clés primaires fournissent automatiquement (presque) tous les index dont nous avons besoin.
Selon les éléments manquants, un indice de multicolumn sur priceavec ordre décroissant sur la deuxième colonne peut améliorer les performances:

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

Encore une fois, le classement doit correspondre à votre requête (voir ci-dessus).

Dans Postgres 9.2 ou version ultérieure, des "indices de couverture" pour les analyses d'index pourraient en aider davantage, en particulier si vos tables contiennent des colonnes supplémentaires, ce qui la rend nettement plus grande que l'indice de couverture.

Ces requêtes résultantes sont beaucoup plus rapides:

N'EXISTE PAS

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
   );

DISTINCT ON

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;

Fiddle SQL.

Des solutions plus rapides

Si cela n’est toujours pas assez rapide, il pourrait y avoir des solutions plus rapides.

CTE récursif / JOIN LATERAL/ sous-requête corrélée

Surtout pour les distributions de données avec beaucoup de prix par bien :

• Optimiser la requête GROUP BY pour récupérer le dernier enregistrement par utilisateur

Vue matérialisée

Si vous devez exécuter cela souvent et rapidement, je vous suggère de créer une vue matérialisée. Je pense qu'il est prudent de supposer que les prix et les stocks pour les dates antérieures changent rarement. Calculez le résultat une fois et stockez un instantané sous forme de vue matérialisée.

Postgres 9.3+ prend en charge automatiquement les vues matérialisées. Vous pouvez facilement implémenter une version de base dans les anciennes versions.

Pour votre information, j'ai utilisé mssql 2008, donc Postgres n'aura pas l'index "include". Cependant, l’utilisation de l’indexation de base illustrée ci-dessous changera de jointure par hachage à une fusion dans Postgres: http://explain.depesz.com/s/eF6 (pas d’index) http://explain.depesz.com/s/j9x ( avec index sur critères de jointure)

Je propose de diviser votre requête en deux parties. Tout d'abord, une vue (non destinée à améliorer les performances) pouvant être utilisée dans une variété d'autres contextes représentant la relation entre les dates d'inventaire et les dates d'établissement des prix.

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;

Ensuite, votre requête peut devenir plus simple et plus facile à manipuler pour d'autres types si interrogation (par exemple, utiliser des jointures à gauche pour trouver un stock sans dates de tarification récentes):

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

Cela donne le plan d'exécution suivant: http://sqlfiddle.com/#!3/24f23/1

... Tous les scans avec un tri complet. Notez que le coût de performance des correspondances de hachage représente la majeure partie du coût total ... et nous savons que les analyses et le tri des tableaux sont lents (par rapport à l'objectif: la recherche d'index).

Maintenant, ajoutez des index de base pour aider les critères utilisés dans votre jointure (je ne prétends pas que ce sont des index optimaux, mais ils illustrent bien ce point): http://sqlfiddle.com/#!3/5ec75/1

Cela montre une amélioration. Les opérations de boucle imbriquée (jointure interne) ne prennent plus aucun coût total pertinent pour la requête. Le reste du coût est maintenant réparti entre les recherches d'index (analyse de l'inventaire, car nous extrayons toutes les lignes de l'inventaire). Mais nous pouvons faire encore mieux parce que la requête tire la quantité et le prix. Pour obtenir ces données, après avoir évalué les critères de jointure, des recherches doivent être effectuées.

La dernière itération utilise "include" sur les index pour faciliter le glissement du plan et obtenir les données supplémentaires demandées directement de l'index lui-même. Les recherches ont donc disparu: http://sqlfiddle.com/#!3/5f143/1

Nous avons maintenant un plan de requête dans lequel le coût total de la requête est réparti uniformément entre les opérations de recherche d'index très rapides. Ce sera proche de ce qui est bon. D’autres experts peuvent certes améliorer encore cette situation, mais la solution élimine deux préoccupations majeures:

1. Il crée des structures de données intelligibles dans votre base de données, faciles à composer et à réutiliser dans d'autres zones d'une application.
2. Tous les opérateurs de requête les plus coûteux ont été exclus du plan de requête à l'aide d'une indexation de base.

Si vous possédez PostgreSQL 9.3 (publié aujourd'hui), vous pouvez utiliser un LATERAL JOIN.

Je n'ai aucun moyen de tester cela et je ne l'ai jamais utilisé auparavant, mais d'après ce que je peux dire de la documentation, la syntaxe ressemblerait à quelque chose comme:

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;

Ceci est fondamentalement équivalent à APPLY de SQL-Server , et il existe un exemple fonctionnel de ceci sur SQL-Fiddle à des fins de démonstration.

Comme Erwin et d'autres l'ont noté, une requête efficace dépend d'un grand nombre de variables et PostgreSQL essaye très fort d'optimiser l'exécution de la requête en fonction de ces variables. En général, vous souhaitez écrire d' abord pour plus de clarté , puis pour améliorer les performances après avoir identifié les goulots d'étranglement.

De plus, PostgreSQL propose de nombreuses astuces pour rendre les choses beaucoup plus efficaces (index partiels pour un). Ainsi, en fonction de votre charge de lecture / écriture, vous pourrez peut-être optimiser ceci en recherchant une indexation soigneuse.

La première chose à faire est de créer une vue et de la rejoindre:

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

Cela devrait bien fonctionner lorsque vous faites quelque chose comme:

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;

Ensuite, vous pouvez rejoindre cela. La requête finira par rejoindre la vue par rapport à la table sous-jacente, mais en supposant que vous ayez un index unique (date, bon dans cet ordre ), vous devriez pouvoir y aller (puisqu'il s'agira d'une simple recherche dans le cache). Cela fonctionnera très bien avec quelques rangées recherchées mais sera très inefficace si vous essayez de digérer des millions de prix de biens.

La deuxième chose à faire est d’ajouter à la table d’inventaire une colonne most_recent bool et

create unique index on inventory (good) where most_recent;

Vous voudriez alors utiliser les déclencheurs pour définir most_recent sur false lors de l'insertion d'une nouvelle ligne pour un produit. Cela ajoute plus de complexité et de plus grandes chances pour les bogues mais c'est utile.

Encore une fois, cela dépend en grande partie de la mise en place des index appropriés. Pour les requêtes de date les plus récentes, vous devriez probablement avoir un index sur la date, et éventuellement un multi-colonne commençant par la date et incluant vos critères de jointure.

Mettez à jour le commentaire de Per Erwin ci-dessous, il semble que j'ai mal compris cela. Relisant la question, je ne suis pas du tout sûr de ce qui est demandé. Je veux mentionner dans la mise à jour quel est le problème potentiel que je vois et pourquoi cela laisse cette question incertaine.

La conception de la base de données proposée n'a pas d'utilisation réelle d'IME avec les systèmes ERP et de comptabilité. Cela fonctionnerait dans un modèle de prix parfait hypothétique où tout ce qui est vendu un jour donné d'un produit donné a le même prix. Par contre, ce n'est pas toujours le cas. Ce n'est même pas le cas pour des choses comme les échanges de devises (bien que certains modèles prétendent que ce soit le cas). S'il s'agit d'un exemple artificiel, ce n'est pas clair. S'il s'agit d'un exemple réel, la conception au niveau des données pose des problèmes plus importants. Je vais supposer ici qu'il s'agit d'un exemple réel.

Vous ne pouvez pas supposer que la seule date spécifie le prix d'un bien donné. Les prix dans toute entreprise peuvent être négociés par contrepartie et parfois même par transaction. Pour cette raison, vous devez vraiment stocker le prix dans la table qui gère réellement l'inventaire entrant ou sortant (la table d'inventaire). Dans un tel cas, votre tableau de dates / biens / prix spécifie simplement un prix de base qui peut être sujet à changement en fonction de la négociation. Dans un tel cas, le problème de rapportage devient un problème transactionnel opérant sur une ligne à la fois de chaque table. Par exemple, vous pouvez alors rechercher le prix par défaut pour un produit donné un jour donné, comme suit:

 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;

Avec un indice sur les prix (bon, date), cela fonctionnera bien.

Si ceci est un exemple artificiel, peut-être que quelque chose de plus proche de ce sur quoi vous travaillez pourrait vous aider.

Une autre solution consisterait à utiliser la fonction window lead()pour obtenir une plage de dates pour chaque ligne du prix du tableau, puis à utiliser betweenpour rejoindre l'inventaire. J'ai effectivement utilisé cela dans la vie réelle, mais principalement parce que c'était ma première idée de comment résoudre ce problème.

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

Utilisez une jointure d'un inventaire à un prix avec des conditions de jonction qui limitent les ordres de la table des prix à ceux qui sont à la date d'inventaire ou avant la date d'inventaire, puis extrayez la date maximale et où la date est la date la plus haute de ce sous-ensemble.

Donc pour votre prix d'inventaire:

 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)

Si le prix d'un bien spécifié a changé plusieurs fois le même jour et que vous ne disposez réellement que de dates et pas d'heures, vous devrez peut-être appliquer davantage de restrictions aux jointures pour ne sélectionner qu'un seul des enregistrements de modification de prix.