Bagaimana cara efisien saya mendapatkan "baris terkait terbaru"?

53

Saya memiliki pola kueri yang harus sangat umum, tetapi saya tidak tahu cara menulis kueri yang efisien untuknya. Saya ingin mencari baris tabel yang sesuai dengan "tanggal terbaru bukan setelah" baris tabel lain.

Saya punya meja, inventorykatakanlah, yang mewakili inventaris yang saya pegang pada hari tertentu.

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

dan sebuah meja, "harga" katakan, yang menyimpan harga suatu barang pada hari tertentu

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

Bagaimana saya bisa mendapatkan harga "terbaru" secara efisien untuk setiap baris tabel inventaris, yaitu

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

Saya tahu satu cara untuk melakukan ini:

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

dan kemudian gabungkan permintaan ini lagi ke inventaris. Untuk tabel besar bahkan melakukan kueri pertama (tanpa bergabung lagi dengan inventaris) sangat lambat. Namun, masalah yang sama dengan cepat diselesaikan jika saya cukup menggunakan bahasa pemrograman saya untuk mengeluarkan satu max(price.date) ... where price.date <= date_of_interest ... order by price.date desc limit 1permintaan untuk masing-masing date_of_interestdari tabel persediaan, jadi saya tahu tidak ada hambatan komputasi. Saya akan, bagaimanapun, lebih suka untuk menyelesaikan seluruh masalah dengan satu query SQL, karena itu akan memungkinkan saya untuk melakukan pemrosesan SQL lebih lanjut pada hasil query.

Apakah ada cara standar untuk melakukan ini secara efisien? Rasanya seperti itu harus sering muncul dan harus ada cara untuk menulis permintaan cepat untuk itu.

Saya menggunakan Postgres, tetapi jawaban SQL-generik akan dihargai.

Tom Ellis
sumber
3
Memilih untuk dimigrasi ke DBA.SE karena ini merupakan pertanyaan efisiensi. Kami dapat menulis kueri dalam beberapa cara berbeda tetapi itu tidak akan membuatnya lebih cepat.
ypercubeᵀᴹ
5
Apakah Anda benar-benar membutuhkan semua barang untuk semua hari dari satu permintaan? Sepertinya persyaratan yang tidak mungkin? Lebih umum seseorang akan mengambil harga untuk tanggal tertentu atau harga untuk barang tertentu (pada tanggal tertentu). Pertanyaan-pertanyaan alternatif itu bisa jauh lebih mudah mendapat manfaat dari indeks yang sesuai. Kita juga perlu tahu: kardinalitas (berapa baris di setiap tabel?), Termasuk definisi tabel lengkap . tipe data, batasan, indeks, ... (digunakan \d tbldalam psql), versi Postgres dan min. / maks. jumlah harga per barang.
Erwin Brandstetter
@ ErwinBrandstetter Apakah Anda meminta saya untuk menerima jawaban? Saya tidak benar-benar memenuhi syarat untuk mengetahui mana yang terbaik, meskipun karena milik Anda memiliki banyak dukungan, saya senang menerimanya.
Tom Ellis
Hanya terima jika itu menjawab pertanyaan Anda atau cocok untuk Anda. Anda bahkan dapat meninggalkan komentar bagaimana Anda melanjutkan jika itu dapat membantu kasus terkait. Jika Anda merasa pertanyaan Anda belum terjawab, beri tahu kami.
Erwin Brandstetter
1
Saya harus minta maaf, karena walaupun saya telah menerima apa yang tampaknya merupakan jawaban yang sangat baik, saya tidak lagi mengerjakan masalah yang memancing pertanyaan, jadi saya tidak dapat menilai mana yang merupakan jawaban terbaik, atau jika memang ada di antara mereka sangat cocok untuk use case saya (seperti dulu). Jika ada beberapa ettiquette DBA.Stackexchange saya harus mengikuti dalam hal ini tolong beri tahu saya.
Tom Ellis

Jawaban:

42

Itu sangat tergantung pada keadaan dan persyaratan yang tepat. Pertimbangkan komentar saya untuk pertanyaan itu .

Solusi sederhana

Dengan DISTINCT ONdi 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;

Memesan hasil.

Atau dengan NOT EXISTSdalam SQL standar (berfungsi dengan setiap RDBMS yang saya tahu):

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

Hasil yang sama, tetapi dengan urutan sortir yang sewenang-wenang - kecuali jika Anda menambahkan ORDER BY.
Bergantung pada distribusi data, persyaratan dan indeks yang tepat, salah satu dari ini mungkin lebih cepat.
Secara umum, DISTINCT ONadalah pemenang dan Anda mendapatkan hasil yang diurutkan di atasnya. Tetapi untuk kasus-kasus tertentu teknik kueri lainnya (jauh) lebih cepat. Lihat di bawah.

Solusi dengan subqueries untuk menghitung nilai max / min umumnya lebih lambat. Varian dengan CTE pada umumnya lebih lambat.

Pandangan polos (seperti yang diajukan oleh jawaban lain) tidak membantu kinerja sama sekali di Postgres.

SQL Fiddle.


Solusi yang tepat

String dan collation

Pertama-tama, Anda menderita tata letak tabel yang kurang optimal. Ini mungkin tampak sepele, tetapi menormalkan skema Anda bisa sangat membantu.

Penyortiran berdasarkan tipe karakter ( text,, varchar...) harus dilakukan sesuai dengan lokal - KOLASI khususnya. Kemungkinan besar DB Anda menggunakan beberapa aturan lokal (seperti, dalam kasus saya:) de_AT.UTF-8. Cari tahu dengan:

SHOW lc_collate;

Ini membuat pengurutan dan pencarian indeks lebih lambat . Semakin lama string Anda (nama barang) semakin buruk. Jika Anda sebenarnya tidak peduli dengan aturan pengumpulan di output Anda (atau urutan pengurutan sama sekali), ini bisa lebih cepat jika Anda menambahkan 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;

Perhatikan bagaimana saya menambahkan collation di dua tempat.
Dua kali lebih cepat dalam pengujian saya dengan masing-masing 20k baris dan nama yang sangat mendasar ('good123').

Indeks

Jika kueri Anda seharusnya menggunakan indeks, kolom dengan data karakter harus menggunakan goodsusunan yang cocok ( dalam contoh):

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

Pastikan untuk membaca dua bab terakhir dari jawaban terkait ini di SO:

Anda bahkan dapat memiliki beberapa indeks dengan susunan berbeda pada kolom yang sama - jika Anda juga membutuhkan barang yang diurutkan menurut susunan lain (atau bawaan) dalam kueri lain.

Normalisasi

String berlebihan (nama yang baik) juga mengasapi tabel dan indeks Anda, yang membuat semuanya lebih lambat. Dengan tata letak tabel yang tepat Anda bisa menghindari sebagian besar masalah untuk memulai. Bisa terlihat seperti ini:

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

Kunci utama secara otomatis menyediakan (hampir) semua indeks yang kita butuhkan.
Bergantung pada detail yang hilang, indeks multikolom aktif pricedengan urutan menurun pada kolom kedua dapat meningkatkan kinerja:

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

Sekali lagi, pemeriksaan harus sesuai dengan query Anda (lihat di atas).

Dalam Postgres 9.2 atau lebih baru "indeks penutup" untuk pindaian indeks saja bisa membantu lebih - terutama jika tabel Anda memiliki kolom tambahan, membuat tabel secara substansial lebih besar dari indeks penutup.

Kueri yang dihasilkan ini jauh lebih cepat:

TIDAK ADA

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

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

SQL Fiddle.


Solusi lebih cepat

Jika itu masih belum cukup cepat, mungkin ada solusi yang lebih cepat.

CTE rekursif / JOIN LATERAL/ subquery berkorelasi

Khusus untuk distribusi data dengan banyak harga per barang :

Tampilan terwujud

Jika Anda perlu menjalankan ini sering dan cepat, saya sarankan Anda membuat tampilan terwujud. Saya pikir aman untuk mengasumsikan, bahwa harga dan inventaris untuk tanggal yang lalu jarang berubah. Hitung hasilnya sekali dan simpan snapshot sebagai tampilan terwujud.

Postgres 9.3+ memiliki dukungan otomatis untuk pandangan terwujud. Anda dapat dengan mudah mengimplementasikan versi dasar di versi yang lebih lama.

Erwin Brandstetter
sumber
3
The price_good_date_desc_idxIndeks Anda merekomendasikan secara dramatis meningkatkan kinerja untuk query yang sama saya. Paket permintaan saya berubah dari biaya 42374.01..42374.86menjadi 0.00..37.12!
cimmanon
@cimmanon: Bagus! Apa fitur permintaan inti Anda? TIDAK ADA? DISTINCT ON? GROUP BY?
Erwin Brandstetter
Menggunakan DISTINCT ON
cimmanon
6

FYI, saya menggunakan mssql 2008, jadi Postgres tidak akan memiliki indeks "include". Namun, menggunakan pengindeksan dasar yang ditunjukkan di bawah ini akan berubah dari hash joins untuk menggabungkan joins di Postgres: http://explain.depesz.com/s/eF6 (tanpa indeks) http://explain.depesz.com/s/j9x ( dengan indeks pada kriteria bergabung)

Saya mengusulkan memecah permintaan Anda menjadi dua bagian. Pertama, pandangan (tidak dimaksudkan untuk meningkatkan kinerja) yang dapat digunakan dalam berbagai konteks lain yang mewakili hubungan tanggal inventaris dan tanggal penetapan harga.

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;

Maka kueri Anda dapat menjadi lebih mudah dan lebih mudah untuk memanipulasi untuk jenis lain jika penyelidikan (seperti menggunakan gabungan kiri untuk menemukan inventaris tanpa tanggal penetapan harga terkini):

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

Ini menghasilkan rencana eksekusi berikut: http://sqlfiddle.com/#!3/24f23/1 tidak ada pengindeksan

... Semua pindaian dengan semacam penuh. Perhatikan biaya kinerja pencocokan hash mengambil sebagian besar biaya total ... dan kami tahu bahwa pemindaian dan pengurutan tabel lambat (dibandingkan dengan tujuan: indeks mencari).

Sekarang, tambahkan indeks dasar untuk membantu kriteria yang digunakan dalam bergabung Anda (saya tidak membuat klaim ini adalah indeks optimal, tetapi mereka menggambarkan intinya): http://sqlfiddle.com/#!3/5ec75/1 dengan pengindeksan dasar

Ini menunjukkan peningkatan. Operasi loop bersarang (inner join) tidak lagi mengambil biaya total yang relevan untuk kueri. Sisa biaya sekarang tersebar di antara pencarian indeks (pemindaian untuk inventaris karena kami menarik setiap baris inventaris). Tetapi kita bisa melakukan lebih baik lagi karena kueri menarik jumlah dan harga. Untuk mendapatkan data itu, setelah mengevaluasi kriteria gabungan, pencarian harus dilakukan.

Iterasi akhir menggunakan "termasuk" pada indeks untuk membuatnya mudah bagi rencana untuk meluncur dan mendapatkan data tambahan yang diminta langsung dari indeks itu sendiri. Jadi pencarian hilang: http://sqlfiddle.com/#!3/5f143/1 masukkan deskripsi gambar di sini

Sekarang kami memiliki rencana kueri di mana total biaya kueri tersebar secara merata di antara operasi pencarian indeks yang sangat cepat. Ini akan mendekati sama baiknya dengan yang didapatnya. Tentunya para ahli lain dapat meningkatkan ini lebih lanjut, tetapi solusinya membersihkan beberapa masalah utama:

  1. Ini menciptakan struktur data yang dapat dipahami dalam database Anda yang lebih mudah untuk menyusun dan menggunakan kembali di area lain dari suatu aplikasi.
  2. Semua operator permintaan yang paling mahal telah difaktorkan keluar dari rencana permintaan menggunakan beberapa pengindeksan dasar.
cocogorilla
sumber
3
Ini baik-baik saja (untuk SQL-Server) tetapi mengoptimalkan untuk DBMS berbeda sementara ia memiliki kesamaan, ia memiliki perbedaan yang serius juga.
ypercubeᵀᴹ
@ ypercube itu benar. Saya menambahkan beberapa kualifikasi tentang Postgres. Maksud saya adalah bahwa sebagian besar proses pemikiran yang diilustrasikan di sini akan berlaku terlepas dari fitur spesifik DBMS.
cocogorilla
Jawabannya sangat mendalam, jadi saya perlu waktu untuk mencobanya. Saya akan memberi tahu Anda bagaimana caranya.
Tom Ellis
5

Jika Anda memiliki PostgreSQL 9.3 (dirilis hari ini) maka Anda dapat menggunakan LATERAL JOIN.

Saya tidak memiliki cara untuk menguji ini, dan belum pernah menggunakannya sebelumnya, tetapi dari apa yang dapat saya katakan dari dokumentasi sintaksinya akan menjadi seperti:

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;

Ini pada dasarnya setara dengan SQL-Server BERLAKU , dan ada contoh yang berfungsi pada SQL-Fiddle untuk tujuan demo.

GarethD
sumber
5

Seperti yang dicatat oleh Erwin dan yang lainnya, permintaan yang efisien tergantung pada banyak variabel dan PostgreSQL berusaha sangat keras untuk mengoptimalkan eksekusi permintaan berdasarkan variabel-variabel tersebut. Secara umum Anda ingin menulis untuk kejelasan terlebih dahulu dan kemudian memodifikasi untuk kinerja setelah Anda mengidentifikasi kemacetan.

Selain itu PostgreSQL memiliki banyak trik yang dapat Anda gunakan untuk membuat hal-hal yang sedikit lebih efisien (indeks parsial untuk satu) jadi tergantung pada beban baca / tulis Anda, Anda mungkin dapat mengoptimalkan ini sangat jauh dengan melihat pengindeksan yang cermat.

Hal pertama yang harus dicoba adalah hanya melihat dan bergabung:

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

Ini harus berkinerja baik ketika melakukan sesuatu seperti:

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;

Maka Anda dapat bergabung itu. Kueri akan berakhir dengan bergabung dengan tampilan terhadap tabel yang mendasarinya, tetapi dengan asumsi Anda memiliki indeks unik pada (tanggal, bagus dalam urutan itu ), Anda harus baik-baik saja (karena ini akan menjadi pencarian cache sederhana). Ini akan bekerja dengan sangat baik dengan beberapa baris memandang ke atas tetapi akan sangat tidak efisien jika Anda mencoba untuk mencerna jutaan harga barang.

Hal kedua yang bisa Anda lakukan adalah menambahkan ke tabel inventaris kolom bool most_recent dan

create unique index on inventory (good) where most_recent;

Anda kemudian ingin menggunakan pemicu untuk menetapkan most_recent menjadi false ketika baris baru untuk barang dimasukkan. Ini menambahkan lebih banyak kerumitan dan peluang lebih besar untuk bug tetapi sangat membantu.

Sekali lagi banyak ini tergantung pada indeks yang tepat berada di tempatnya. Untuk sebagian besar kueri tanggal terbaru, Anda mungkin harus memiliki indeks pada tanggal, dan mungkin satu multi-kolom yang dimulai dengan tanggal dan termasuk kriteria bergabung Anda.

Perbarui komentar Per Erwin di bawah ini, sepertinya saya salah paham. Membaca ulang pertanyaan saya sama sekali tidak yakin apa yang ditanyakan. Saya ingin menyebutkan dalam pembaruan apa potensi masalah yang saya lihat dan mengapa hal ini tidak jelas.

Desain database yang ditawarkan tidak memiliki IME penggunaan nyata dengan ERP dan sistem akuntansi. Ini akan bekerja dalam model penetapan harga hipotetis sempurna di mana segala sesuatu yang dijual pada hari tertentu dari produk tertentu memiliki harga yang sama. Namun ini tidak selalu terjadi. Bahkan tidak berlaku untuk hal-hal seperti pertukaran mata uang (meskipun beberapa model berpura-pura bahwa itu terjadi). Jika ini adalah contoh yang dibuat-buat, tidak jelas. Jika ini adalah contoh nyata, ada masalah yang lebih besar dengan desain pada tingkat data. Saya akan berasumsi di sini bahwa ini adalah contoh nyata.

Anda tidak dapat mengasumsikan bahwa tanggal saja menentukan harga untuk barang tertentu. Harga dalam bisnis apa pun dapat dinegosiasikan per pihak lawan dan bahkan terkadang per transaksi. Untuk alasan ini Anda benar-benar harus menyimpan harga di tabel yang benar-benar menangani inventaris masuk atau keluar (tabel inventaris). Dalam kasus seperti itu, tanggal / barang / tabel harga Anda hanya menentukan harga dasar yang dapat berubah berdasarkan negosiasi. Dalam kasus seperti ini, masalah ini berubah dari masalah pelaporan menjadi masalah yang bersifat transaksional dan beroperasi pada satu baris dari setiap tabel pada satu waktu. Misalnya, Anda kemudian dapat mencari harga default untuk produk yang diberikan pada hari tertentu sebagai:

 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;

Dengan indeks harga (baik, tanggal) ini akan berkinerja baik.

Saya ini adalah contoh yang dibuat-buat, mungkin sesuatu yang lebih dekat dengan apa yang Anda kerjakan akan membantu.

Chris Travers
sumber
The most_recentPendekatan harus bekerja dengan baik untuk harga terbaru benar-benar . Sepertinya OP membutuhkan harga terbaru relatif terhadap setiap tanggal inventaris.
Erwin Brandstetter
Poin bagus. Membaca ulang meskipun saya melihat beberapa kekurangan praktis nyata dengan data yang diusulkan tetapi saya tidak tahu apakah itu hanya contoh yang dibuat-buat. Sebagai contoh buat-buat, saya tidak tahu apa yang hilang. Mungkin pembaruan untuk menunjukkan ini juga akan beres.
Chris Travers
@ ChrisTravers: Ini adalah contoh yang dibuat-buat, tapi saya tidak berhak memposting skema aktual yang sedang saya kerjakan. Mungkin Anda bisa mengatakan sedikit tentang kekurangan praktis apa yang Anda lihat.
Tom Ellis
Saya tidak berpikir itu harus tepat, tetapi khawatir tentang masalah yang hilang dalam perumpamaan. Sesuatu yang sedikit lebih dekat akan sangat membantu. Masalahnya adalah bahwa dengan penetapan harga, harga pada hari tertentu cenderung menjadi default, dan akibatnya Anda tidak akan menggunakannya untuk pelaporan hanya sebagai default untuk entri transaksi, sehingga permintaan menarik Anda biasanya hanya beberapa baris pada sebuah waktu.
Chris Travers
3

Cara lain adalah dengan menggunakan fungsi jendela lead()untuk mendapatkan rentang tanggal untuk setiap baris dalam harga tabel dan kemudian digunakan betweensaat bergabung dengan inventaris. Saya sebenarnya menggunakan ini dalam kehidupan nyata, tetapi terutama karena ini adalah ide pertama saya bagaimana menyelesaikan ini.

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

Tomas Greif
sumber
1

Gunakan gabungan dari inventaris ke harga dengan ketentuan gabungan yang membatasi rec rec dari daftar harga hanya pada yang ada pada atau sebelum tanggal inventaris, kemudian ekstrak tanggal maksimum, dan di mana tanggal tersebut adalah tanggal tertinggi dari subset tersebut

Jadi untuk harga inventaris Anda:

 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)

Jika harga untuk barang tertentu berubah lebih dari satu kali pada hari yang sama, dan Anda benar-benar hanya memiliki tanggal dan tidak ada kali dalam kolom ini, Anda mungkin perlu menerapkan lebih banyak pembatasan pada gabungan untuk memilih hanya satu dari catatan perubahan harga.


sumber
Sayangnya, sepertinya tidak mempercepat.