Mengapa perkiraan gabungan kardinalitas ini begitu besar?

Saya mengalami apa yang saya pikir adalah perkiraan kardinalitas yang sangat tinggi untuk pertanyaan berikut:

SELECT dm.PRIMARY_ID
FROM
(
    SELECT COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID) PRIMARY_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID
    LEFT OUTER JOIN X_DETAIL_2 d2 ON dt.ID = d2.ID
    LEFT OUTER JOIN X_DETAIL_3 d3 ON dt.ID = d3.ID
) dm
INNER JOIN X_LAST_TABLE lst ON dm.PRIMARY_ID = lst.JOIN_ID;

Perkiraan rencana ada di sini . Saya sedang mengerjakan salinan statistik dari tabel sehingga saya tidak dapat memasukkan rencana aktual. Namun, saya tidak berpikir itu sangat relevan untuk masalah ini.

SQL Server memperkirakan bahwa 481577 baris akan dikembalikan dari tabel turunan "dm". Itu kemudian memperkirakan bahwa 4528030000 baris akan dikembalikan setelah bergabung ke X_LAST_TABLE dilakukan, tetapi JOIN_ID adalah kunci utama X_LAST_TIME. Saya mengharapkan perkiraan kardinalitas gabungan antara 0 dan 481577 baris. Alih-alih, estimasi baris nampaknya 10% dari jumlah baris yang akan saya dapatkan ketika cross bergabung dengan tabel luar dan dalam. Matematika untuk ini berhasil dengan pembulatan: 481577 * 94025 * 0,1 = 45280277425 yang dibulatkan menjadi 4528030000.

Saya terutama mencari akar penyebab perilaku ini. Saya tertarik pada solusi sederhana juga, tapi tolong jangan menyarankan mengubah model data atau menggunakan tabel temp. Permintaan ini adalah penyederhanaan logika dalam tampilan. Saya tahu bahwa melakukan COALESCE pada beberapa kolom dan bergabung dengannya bukanlah praktik yang baik. Bagian dari tujuan pertanyaan ini adalah untuk mengetahui apakah saya perlu merekomendasikan agar model data didesain ulang.

Saya menguji pada Microsoft SQL Server 2014 dengan penaksir kardinalitas lama diaktifkan. TF 4199 dan yang lainnya aktif. Saya bisa memberikan daftar lengkap tanda jejak jika itu akhirnya relevan.

Berikut adalah definisi tabel yang paling relevan:

CREATE TABLE X_LAST_TABLE (
JOIN_ID NUMERIC(18, 0) NOT NULL
    CONSTRAINT PK_X_LAST_TABLE PRIMARY KEY CLUSTERED (JOIN_ID ASC)
);

Saya juga mencoret semua skrip pembuatan tabel bersama dengan statistik mereka jika ada yang ingin mereproduksi masalah di salah satu server mereka.

Untuk menambahkan beberapa pengamatan saya, menggunakan TF 2312 memperbaiki perkiraan, tapi itu bukan pilihan bagi saya. TF 2301 tidak memperbaiki estimasi. Menghapus salah satu tabel memperbaiki taksiran. Anehnya, mengubah urutan bergabung X_DETAIL_LINK juga memperbaiki perkiraan. Dengan mengubah urutan bergabung, maksud saya menulis ulang kueri dan tidak memaksa urutan bergabung dengan sebuah petunjuk. Berikut adalah perkiraan rencana kueri saat hanya mengubah urutan gabungan.

Saya tahu bahwa melakukan COALESCEpada beberapa kolom dan bergabung dengannya bukanlah praktik yang baik.

Menghasilkan kardinalitas dan estimasi distribusi yang baik cukup sulit ketika skema adalah 3NF + (dengan kunci dan kendala) dan kueri bersifat relasional dan terutama SPJG (seleksi-proyeksi-gabung-grup oleh). Model CE dibangun berdasarkan prinsip-prinsip tersebut. Fitur yang lebih tidak biasa atau non-relasional ada dalam kueri, semakin dekat satu dengan batas-batas apa kardinalitas dan kerangka kerja selektivitas dapat menangani. Pergi terlalu jauh dan CE akan menyerah dan menebak .

Sebagian besar contoh MCVE adalah SPJ sederhana (tanpa G), meskipun dengan equijoins luar yang lebih dominan (dimodelkan sebagai gabungan dalam ditambah anti-semijoin) daripada equijoin dalam yang lebih sederhana (atau semijoin). Semua relasi memiliki kunci, meskipun tidak ada kunci asing atau kendala lainnya. Semua kecuali satu dari gabungan adalah satu-ke-banyak, yang bagus.

Pengecualian adalah banyak-ke-banyak gabungan luar antara X_DETAIL_1dan X_DETAIL_LINK. Satu-satunya fungsi gabungan ini di MCVE adalah berpotensi menduplikasi baris X_DETAIL_1. Ini adalah hal yang tidak biasa .

Predikat kesetaraan sederhana (pilihan) dan operator skalar juga lebih baik. Sebagai contoh, atribut bandingkan-sama / konstan biasanya berfungsi dengan baik dalam model. Relatif "mudah" untuk memodifikasi histogram dan statistik frekuensi untuk mencerminkan penerapan predikat tersebut.

COALESCEdibangun CASE, yang pada gilirannya diimplementasikan secara internal sebagai IIF(dan ini benar sebelum IIFmuncul dalam bahasa Transact-SQL). Model CE IIFsebagai UNIONdengan dua anak yang saling eksklusif, masing-masing terdiri dari proyek pada seleksi pada relasi input. Masing-masing komponen yang tercantum memiliki dukungan model, sehingga menggabungkannya relatif mudah. Meski begitu, semakin banyak satu lapisan abstraksi, semakin tidak akurat hasil akhirnya - alasan mengapa rencana pelaksanaan yang lebih besar cenderung kurang stabil dan dapat diandalkan.

ISNULL, di sisi lain, intrinsik ke mesin. Itu tidak dibangun menggunakan komponen yang lebih mendasar. Menerapkan efek ISNULLke histogram, misalnya, semudah mengganti langkah untuk NULLnilai (dan memadatkan sesuai kebutuhan). Masih relatif buram, karena operator skalar pergi, dan sebaiknya dihindari jika memungkinkan. Namun demikian, secara umum ini lebih ramah-pengoptimal (kurang pengoptimal-tidak ramah) daripada CASEalternatif berbasis.

CE (70 dan 120+) sangat kompleks, bahkan oleh standar SQL Server. Ini bukan kasus menerapkan logika sederhana (dengan formula rahasia) untuk setiap operator. CE tahu tentang kunci dan dependensi fungsional; ia tahu cara memperkirakan menggunakan frekuensi, statistik multivarian, dan histogram; dan ada banyak sekali kasus khusus, penyempurnaan, check & balance, dan struktur pendukung. Ini sering memperkirakan misalnya bergabung dalam berbagai cara (frekuensi, histogram) dan memutuskan hasil atau penyesuaian berdasarkan perbedaan antara keduanya.

Satu hal dasar terakhir yang harus dicakup: Estimasi kardinalitas awal berjalan untuk setiap operasi di pohon kueri, dari bawah ke atas. Selektivitas dan kardinalitas diturunkan untuk operator daun terlebih dahulu (hubungan dasar). Informasi histogram dan kepadatan / frekuensi yang dimodifikasi diturunkan untuk operator induk. Semakin jauh kita melanjutkan, semakin rendah kualitas estimasi cenderung karena kesalahan cenderung menumpuk.

Estimasi komprehensif awal tunggal ini memberikan titik awal, dan terjadi jauh sebelum pertimbangan diberikan pada rencana eksekusi akhir (ini terjadi jauh sebelum tahap kompilasi rencana sepele). Pohon kueri pada titik ini cenderung mencerminkan bentuk kueri tertulis dengan cukup dekat (meskipun dengan subqueries dihapus, dan penyederhanaan diterapkan dll.)

Segera setelah estimasi awal, SQL Server melakukan heuristic join reordering, yang secara longgar mencoba menyusun ulang pohon untuk menempatkan tabel yang lebih kecil dan selektivitas tinggi bergabung terlebih dahulu. Ini juga mencoba untuk memposisikan sambungan dalam sebelum sambungan luar dan produk silang. Kemampuannya tidak luas; upayanya tidak lengkap; dan tidak mempertimbangkan biaya fisik (karena belum ada - hanya informasi statistik dan informasi metadata yang ada). Menyusun ulang heuristik paling berhasil pada pohon equijoin batin sederhana. Itu ada untuk memberikan titik awal yang "lebih baik" untuk optimasi berbasis biaya.

Mengapa perkiraan gabungan kardinalitas ini begitu besar?

MCVE memiliki " banyak-ke-banyak bergabung " tidak biasa "sebagian besar , dan equi bergabung dengan COALESCEpredikat. Pohon operator juga memiliki sambungan dalam yang terakhir , yang disusun ulang dengan heuristik tidak dapat memindahkan pohon ke posisi yang lebih disukai. Mengesampingkan semua skalar dan proyeksi, pohon gabungan adalah:

LogOp_Join [ Card=4.52803e+009 ]
    LogOp_LeftOuterJoin [ Card=481577 ]
        LogOp_LeftOuterJoin [ Card=481577 ]
            LogOp_LeftOuterJoin [ Card=481577 ]
                LogOp_LeftOuterJoin [ Card=481577 ]
                LogOp_Get TBL: X_DRIVING_TABLE(alias TBL: dt) [ Card=481577 ]
                LogOp_Get TBL: X_DETAIL_1(alias TBL: d1) [ Card=70 ]
                LogOp_Get TBL: X_DETAIL_LINK(alias TBL: lnk) [ Card=47 ]
            LogOp_Get TBL: X_DETAIL_2(alias TBL: d2) X_DETAIL_2 [ Card=119 ]
        LogOp_Get TBL: X_DETAIL_3(alias TBL: d3) X_DETAIL_3 [ Card=281 ]
    LogOp_Get TBL: X_LAST_TABLE(alias TBL: lst) X_LAST_TABLE [ Card=94025 ]

Perhatikan perkiraan akhir yang salah sudah ada. Ini dicetak sebagai Card=4.52803e+009dan disimpan secara internal sebagai nilai floating point presisi ganda 4,5280277425e + 9 (4528027742.5 dalam desimal).

Tabel turunan dalam kueri asli telah dihapus, dan proyeksi dinormalisasi. Representasi SQL dari pohon tempat kardinalitas awal dan estimasi selektivitas dilakukan adalah:

SELECT 
    PRIMARY_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)
FROM X_DRIVING_TABLE dt
LEFT OUTER JOIN X_DETAIL_1 d1
    ON dt.ID = d1.ID
LEFT OUTER JOIN X_DETAIL_LINK lnk 
    ON d1.LINK_ID = lnk.LINK_ID
LEFT OUTER JOIN X_DETAIL_2 d2 
    ON dt.ID = d2.ID
LEFT OUTER JOIN X_DETAIL_3 d3 
    ON dt.ID = d3.ID
INNER JOIN X_LAST_TABLE lst 
    ON lst.JOIN_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)

(Sebagai tambahan, yang diulang COALESCEjuga hadir dalam rencana akhir - sekali dalam Skalarat Hitung terakhir, dan sekali di sisi bagian dalam gabungan bagian dalam).

Perhatikan akhir bergabung. Gabungan dalam ini adalah (menurut definisi) produk kartesius X_LAST_TABLEdan hasil gabungan sebelumnya, dengan pilihan (gabungan predikat) dari yang lst.JOIN_ID = COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)diterapkan. Kardinalitas produk kartesius hanyalah 481577 * 94025 = 45280277425.

Untuk itu, kita perlu menentukan dan menerapkan selektivitas predikat. Kombinasi COALESCEpohon yang diperluas buram (dalam hal UNIONdan IIF, ingat) bersama-sama dengan dampak pada informasi utama, histogram turunan dan frekuensi dari gabungan luar-ke-luar yang "tidak biasa" sebagian besar-banyak-banyak-banyak yang dikombinasikan, berarti CE tidak mampu memperoleh estimasi yang dapat diterima dengan salah satu cara normal.

Akibatnya, ia memasuki Logika Tebak. Logika tebakan cukup kompleks, dengan lapisan tebakan "dididik" dan algoritme tebak "tidak-terdidik" dicoba. Jika tidak ada dasar yang lebih baik untuk tebakan ditemukan, model menggunakan tebakan terakhir, yang untuk perbandingan kesetaraan adalah: sqllang!x_Selectivity_Equal= selektivitas tetap 0,1 (tebakan 10%):

-- the moment of doom
movsd xmm0,mmword ptr [sqllang!x_Selectivity_Equal

Hasilnya adalah selektivitas 0,1 pada produk kartesius: 481577 * 94025 * 0,1 = 4528027742,5 (~ 4,52803e + 009) seperti yang disebutkan sebelumnya.

Menulis ulang

Ketika gabungan yang bermasalah dikomentari , perkiraan yang lebih baik dihasilkan karena selektivitas tetap "tebakan terakhir" dihindari (informasi utama dipertahankan oleh gabungan 1-M). Kualitas taksiran masih rendah, karena COALESCEpredikat gabungan sama sekali tidak ramah CE. Perkiraan yang direvisi setidaknya terlihat lebih masuk akal bagi manusia, saya kira.

Ketika kueri ditulis dengan gabungan luar ke X_DETAIL_LINK ditempatkan terakhir , pemesanan ulang heuristik dapat menukar dengan gabungan akhir batin X_LAST_TABLE. Meletakkan sambungan dalam tepat di sebelah masalah sambungan luar memberikan kemampuan terbatas pada pemesanan ulang awal kesempatan untuk meningkatkan estimasi akhir, karena efek dari sambungan luar banyak-ke-banyak yang "tidak biasa" kebanyakan-ke-banyak yang banyak muncul setelah estimasi selektivitas rumit untuk COALESCE. Sekali lagi, perkiraannya sedikit lebih baik dari perkiraan yang pasti, dan mungkin tidak akan tahan terhadap pemeriksaan silang yang ditentukan di pengadilan.

Menyusun ulang campuran gabungan dalam dan luar adalah sulit dan memakan waktu (bahkan optimisasi penuh tahap 2 hanya mencoba subset terbatas dari gerakan teoritis).

Sarang yang ISNULLdisarankan dalam jawaban Max Vernon berhasil menghindari tebakan tetap bail-out, tetapi estimasi akhir adalah nol baris yang mustahil (terangkat ke satu baris untuk kesopanan). Ini mungkin juga merupakan tebakan tetap 1 baris, untuk semua basis statistik yang dimiliki perhitungan.

Saya mengharapkan perkiraan kardinalitas gabungan antara 0 dan 481577 baris.

Ini adalah ekspektasi yang masuk akal, bahkan jika seseorang menerima bahwa estimasi kardinalitas dapat terjadi pada waktu yang berbeda (selama optimasi berbasis biaya) pada subtree yang secara fisik berbeda, tetapi secara logis dan semantik identik - dengan rencana akhir menjadi semacam yang terbaik yang dijahit bersama. terbaik (per grup memo). Kurangnya jaminan konsistensi seluruh rencana tidak berarti bahwa individu bergabung harus dapat merusak kehormatan, saya mengerti.

Di sisi lain, jika kita berakhir pada tebakan pilihan terakhir , harapan sudah hilang, jadi mengapa repot-repot. Kami mencoba semua trik yang kami tahu, dan menyerah. Jika tidak ada yang lain, estimasi akhir liar adalah tanda peringatan yang bagus bahwa tidak semuanya berjalan dengan baik di dalam CE selama kompilasi dan optimalisasi permintaan ini.

Ketika saya mencoba MCVE, 120+ CE menghasilkan estimasi akhir baris nol (= 1) (seperti yang bersarang ISNULL) untuk kueri asli, yang sama tidak dapat diterima dengan cara berpikir saya.

Solusi nyata mungkin melibatkan perubahan desain, untuk memungkinkan equi-gabung sederhana tanpa COALESCEatau ISNULL, dan idealnya kunci asing & batasan lain yang berguna untuk kompilasi permintaan.

Saya percaya Compute Scalaroperator yang dihasilkan dari COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID)bergabung menjadi X_LAST_TABLE.JOIN_IDpenyebab utama masalah ini. Secara historis, komputasi skalars sulit untuk biaya yang akurat ^{1 , 2} .

Karena Anda telah memberikan contoh yang dapat diverifikasi minimal lengkap (terima kasih!) Dengan statistik yang akurat, saya dapat menulis ulang kueri sehingga bergabung tidak lagi memerlukan CASEfungsionalitas yang COALESCEdiperluas, menghasilkan perkiraan baris yang jauh lebih akurat, dan tampaknya lebih banyak biaya keseluruhan akurat ^{Lihat lampiran di bagian akhir.} :

SELECT COALESCE(dm.d1ID, dm.d2ID, dm.d3ID)
FROM
(
    SELECT d1ID = d1.JOIN_ID
        , d2ID = d2.JOIN_ID
        , d3ID = d3.JOIN_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID
    LEFT OUTER JOIN X_DETAIL_2 d2 ON dt.ID = d2.ID
    LEFT OUTER JOIN X_DETAIL_3 d3 ON dt.ID = d3.ID
) dm
INNER JOIN X_LAST_TABLE lst 
    ON (dm.d1ID IS NOT NULL AND dm.d1ID = lst.JOIN_ID)
    OR (dm.d1ID IS NULL AND dm.d2ID IS NOT NULL AND dm.d2ID = lst.JOIN_ID)
    OR (dm.d1ID IS NULL AND dm.d2ID IS NULL AND dm.d3ID IS NOT NULL AND dm.d3ID = lst.JOIN_ID);

Meskipun xID IS NOT NULLsecara teknis tidak diperlukan, karena ID = JOIN_IDtidak akan bergabung dengan nilai nol, saya memasukkannya karena lebih jelas menggambarkan maksudnya.

Paket 1 dan Paket 2

Paket 1:

Paket 2:

Kueri baru mendapat manfaat (?) Dari paralelisasi. Juga dari catatan, permintaan baru memiliki perkiraan jumlah output baris 1, yang mungkin sebenarnya lebih buruk pada akhir hari daripada estimasi 4528030000 untuk permintaan asli. Biaya subtree untuk operator terpilih pada kueri baru masuk pada 243210, sedangkan jam asli masuk pada 536.535, yang jelas lebih murah. Karena itu, saya tidak percaya estimasi pertama mendekati kenyataan.

Adendum 1.

Setelah konsultasi lebih lanjut dengan berbagai orang di The Heap ™ didorong oleh diskusi dengan @Lamak, sepertinya pertanyaan pengamatan saya di atas berkinerja sangat buruk, bahkan dengan paralelisme. Solusi yang memungkinkan perkiraan kinerja dan kardinalitas yang baik terdiri dari mengganti COALESCE(x,y,z)dengan ISNULL(ISNULL(x, y), z), seperti pada:

SELECT dm.PRIMARY_ID
FROM
(
    SELECT ISNULL(ISNULL(d1.JOIN_ID, d2.JOIN_ID), d3.JOIN_ID) PRIMARY_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID
    LEFT OUTER JOIN X_DETAIL_2 d2 ON dt.ID = d2.ID
    LEFT OUTER JOIN X_DETAIL_3 d3 ON dt.ID = d3.ID
) dm
INNER JOIN X_LAST_TABLE lst ON dm.PRIMARY_ID = lst.JOIN_ID;

COALESCEditransformasikan menjadi CASEpernyataan "di bawah selimut" oleh pengoptimal kueri. Dengan demikian, penaksir kardinalitas mengalami kesulitan menemukan statistik yang andal untuk kolom yang terkubur di dalamnya COALESCE. ISNULLmenjadi fungsi intrinsik jauh lebih "terbuka" untuk penaksir kardinalitas. Juga tidak ada nilainya yang ISNULLdapat dioptimalkan jika target diketahui tidak dapat dibatalkan.

Paket ISNULLvarian terlihat seperti:

(Tempel versi Paket di sini ).

FYI, props ke Sentry One untuk Plan Explorer mereka yang hebat, yang saya gunakan untuk menghasilkan rencana grafis di atas.

Sesuai kondisi bergabung Anda, tabel dapat diatur dalam banyak cara, itu "mengubah ke satu cara tertentu" memperbaiki hasilnya.

Misalkan bergabung hanya dengan satu tabel memberi Anda hasil yang benar.

SELECT COALESCE(d1.JOIN_ID, d2.JOIN_ID, d3.JOIN_ID) PRIMARY_ID
    FROM X_DRIVING_TABLE dt
    LEFT OUTER JOIN X_DETAIL_1 d1 ON dt.ID = d1.ID
    LEFT OUTER JOIN X_DETAIL_LINK lnk ON d1.LINK_ID = lnk.LINK_ID

Di sini, di tempat X_DETAIL_1, Anda dapat menggunakan salah satu X_DETAIL_2atau X_DETAIL_3.

Karenanya tujuan istirahat 2 tabel tidak jelas.

Sepertinya Anda telah memecah meja X_DETAIL_1menjadi 2 bagian lagi.

Sebagian besar mungkin " ada kesalahan mana Anda mengisi tabel tersebut. " Idealnya X_DETAIL_1, X_DETAIL_2dan X_DETAIL_3harus berisi jumlah yang sama baris.

Tetapi satu atau lebih tabel berisi jumlah baris yang tidak diinginkan.

Maaf kalau saya salah.