SQL Server 2014: ada penjelasan untuk perkiraan kardinalitas bergabung mandiri yang tidak konsisten?

Pertimbangkan paket kueri berikut di SQL Server 2014:

Dalam rencana kueri, bergabung sendiri ar.fId = ar.fIdmenghasilkan perkiraan 1 baris. Namun, ini adalah perkiraan yang tidak konsisten secara logis: armemiliki 20,608baris dan hanya satu nilai berbeda fId(yang secara akurat tercermin dalam statistik). Oleh karena itu, gabungan ini menghasilkan produk silang lengkap baris ( ~424MMbaris), menyebabkan kueri berjalan selama beberapa jam.

Saya mengalami kesulitan memahami mengapa SQL Server akan datang dengan perkiraan yang dapat dengan mudah terbukti tidak konsisten dengan statistik. Ada ide?

Investigasi awal dan detail tambahan

Berdasarkan jawaban Paul di sini , sepertinya heuristik SQL 2012 dan SQL 2014 untuk memperkirakan bergabung dengan kardinalitas harus dengan mudah menangani situasi di mana dua histogram identik perlu dibandingkan.

Saya mulai dengan output dari jejak flag 2363, tetapi tidak dapat memahaminya dengan mudah. Apakah potongan berikut ini berarti bahwa SQL Server membandingkan histogram untuk fIddan bIduntuk memperkirakan selektivitas gabungan yang hanya menggunakan fId? Jika demikian, itu jelas tidak benar. Atau apakah saya salah membaca keluaran jejak bendera?

Plan for computation:
  CSelCalcExpressionComparedToExpression( QCOL: [ar].fId x_cmpEq QCOL: [ar].fId )
Loaded histogram for column QCOL: [ar].bId from stats with id 3
Loaded histogram for column QCOL: [ar].fId from stats with id 1
Selectivity: 0

Perhatikan bahwa saya telah menemukan beberapa solusi, yang termasuk dalam skrip repro lengkap dan membawa kueri ini ke milidetik. Pertanyaan ini difokuskan pada pemahaman perilaku, bagaimana menghindarinya dalam pertanyaan di masa mendatang, dan menentukan apakah itu bug yang harus diarsipkan dengan Microsoft.

Berikut ini adalah skrip repro lengkap , berikut ini adalah output lengkap dari jejak flag 2363 , dan berikut adalah definisi kueri dan tabel jika Anda ingin melihatnya dengan cepat tanpa membuka skrip lengkap:

WITH cte AS (
    SELECT ar.fId, 
        ar.bId,
        MIN(CONVERT(INT, ar.isT)) AS isT,
        MAX(CONVERT(INT, tcr.isS)) AS isS
    FROM  #SQL2014MinMaxAggregateCardinalityBug_ar ar 
    LEFT OUTER JOIN #SQL2014MinMaxAggregateCardinalityBug_tcr tcr
        ON tcr.rId = 508
        AND tcr.fId = ar.fId
        AND tcr.bId = ar.bId
    GROUP BY ar.fId, ar.bId
)
SELECT s.fId, s.bId, s.isS, t.isS
FROM cte s 
JOIN cte t 
    ON t.fId = s.fId 
    AND t.isT = 1

---

CREATE TABLE #SQL2014MinMaxAggregateCardinalityBug_ar (
    fId INT NOT NULL,
    bId INT NOT NULL,
    isT BIT NOT NULL
    PRIMARY KEY (fId, bId)
)

CREATE TABLE #SQL2014MinMaxAggregateCardinalityBug_tcr (
    rId INT NOT NULL,
    fId INT NOT NULL,
    bId INT NOT NULL,
    isS BIT NOT NULL
    PRIMARY KEY (rId, fId, bId, isS)
)

Saya mengalami kesulitan memahami mengapa SQL Server akan datang dengan perkiraan yang dapat dengan mudah terbukti tidak konsisten dengan statistik.

Konsistensi

Tidak ada jaminan umum akan konsistensi. Perkiraan dapat dihitung pada subtree yang berbeda (tapi secara logis setara) pada waktu yang berbeda, menggunakan metode statistik yang berbeda.

Tidak ada yang salah dengan logika yang mengatakan bergabung dengan dua subtree identik harus menghasilkan produk silang, tetapi tidak ada yang sama mengatakan bahwa pilihan penalaran lebih sehat daripada yang lain.

Estimasi awal

Dalam kasus spesifik Anda, estimasi kardinalitas awal untuk gabungan tidak dilakukan pada dua subtree identik . Bentuk pohon pada saat itu adalah:

  LogOp_Join
     LogOp_GbAgg
        LogOp_LeftOuterJoin
           LogOp_Dapatkan TBL: ar
           LogOp_Select
              LogOp_Dapatkan TBL: tcr
              ScaOp_Comp x_cmpEq
                 ScaOp_Identifier [tcr] .rId
                 Nilai ScaOp_Const = 508
           ScaOp_Logical x_lopAnd
              ScaOp_Comp x_cmpEq
                 ScaOp_Identifier [ar] .fId
                 ScaOp_Identifier [tcr] .fId
              ScaOp_Comp x_cmpEq
                 ScaOp_Identifier [ar] .bId
                 ScaOp_Identifier [tcr] .bId
        AncOp_PrjList 
           AncOp_PrjEl Expr1003 
              StopMax ScaOp_AggFunc
                 ScaOp_Convert int
                    ScaOp_Identifier [tcr] .isS
     LogOp_Select
        LogOp_GbAgg
           LogOp_LeftOuterJoin
              LogOp_Dapatkan TBL: ar
              LogOp_Select
                 LogOp_Dapatkan TBL: tcr
                 ScaOp_Comp x_cmpEq
                    ScaOp_Identifier [tcr] .rId
                    Nilai ScaOp_Const = 508
              ScaOp_Logical x_lopAnd
                 ScaOp_Comp x_cmpEq
                    ScaOp_Identifier [ar] .fId
                    ScaOp_Identifier [tcr] .fId
                 ScaOp_Comp x_cmpEq
                    ScaOp_Identifier [ar] .bId
                    ScaOp_Identifier [tcr] .bId
           AncOp_PrjList 
              AncOp_PrjEl Expr1006 
                 StopMin ScaOp_AggFunc
                    ScaOp_Convert int
                       ScaOp_Identifier [ar] .isT
              AncOp_PrjEl Expr1007 
                 StopMax ScaOp_AggFunc
                    ScaOp_Convert int
                       ScaOp_Identifier [tcr] .isS
        ScaOp_Comp x_cmpEq
           ScaOp_Identifier Expr1006 
           Nilai ScaOp_Const = 1
     ScaOp_Comp x_cmpEq
        ScaOp_Identifier QCOL: [ar] .fId
        ScaOp_Identifier QCOL: [ar] .fId

Input gabungan pertama memiliki agregat yang tidak diproyeksikan disederhanakan, dan input gabungan kedua memiliki predikat yang t.isT = 1didorong di bawahnya, di mana t.isTberada MIN(CONVERT(INT, ar.isT)). Meskipun demikian, perhitungan selektivitas untuk isTpredikat dapat digunakan CSelCalcColumnInIntervalpada histogram:

  CSelCalcColumnInInvalval
      Kolom: COL: Expr1006 

Memuat histogram untuk kolom QCOL: [ar] .isT dari statistik dengan id 3

Selektivitas: 4.85248e-005

Koleksi statistik yang dihasilkan: 
  CStCollFilter (ID = 11, CARD = 1)
      CStCollGroupBy (ID = 10, CARD = 20608)
          CStCollOuterJoin (ID = 9, CARD = 20608 x_jtLeftOuter)
              CStCollBaseTable (ID = 3, CARD = 20608 TBL: ar)
              CStCollFilter (ID = 8, CARD = 1)
                  CStCollBaseTable (ID = 4, CARD = 28 TBL: tcr)

Harapan (benar) adalah untuk 20.608 baris dikurangi menjadi 1 baris dengan predikat ini.

Gabung estimasi

Pertanyaannya sekarang adalah bagaimana 20.608 baris dari input gabungan lainnya akan cocok dengan satu baris ini:

  LogOp_Join
      CStCollGroupBy (ID = 7, CARD = 20608)
          CStCollOuterJoin (ID = 6, CARD = 20608 x_jtLeftOuter)
              ...

      CStCollFilter (ID = 11, CARD = 1)
          CStCollGroupBy (ID = 10, CARD = 20608)
              ...

      ScaOp_Comp x_cmpEq
          ScaOp_Identifier QCOL: [ar] .fId
          ScaOp_Identifier QCOL: [ar] .fId

Ada beberapa cara berbeda untuk memperkirakan bergabung secara umum. Kita bisa, misalnya:

• Turunkan histogram baru di setiap operator paket di setiap subtree, sejajarkan di join (interpolasi nilai langkah yang diperlukan), dan lihat bagaimana mereka cocok; atau
• Lakukan penyelarasan 'histogram' yang lebih sederhana dari histogram (menggunakan nilai minimum dan maksimum, bukan langkah-demi-langkah); atau
• Hitung selektivitas terpisah untuk kolom gabungan saja (dari tabel dasar, dan tanpa pemfilteran apa pun), lalu tambahkan efek selektivitas predikat tidak-bergabung.
• ...

Bergantung pada penaksir kardinalitas yang digunakan, dan beberapa heuristik, semua itu (atau variasi) dapat digunakan. Lihat Buku Putih Microsoft Mengoptimalkan Rencana Kueri Anda dengan SQL Server 2014 Cardinality Estimator untuk lebih lanjut.

Bug?

Sekarang, seperti yang disebutkan dalam pertanyaan, dalam hal ini gabungan kolom tunggal 'sederhana' (aktif fId) menggunakan CSelCalcExpressionComparedToExpressionkalkulator:

Rencanakan perhitungan:

  CSelCalcExpressionComparedToExpression [ar] .fId x_cmpEq [ar] .fId

Memuat histogram untuk kolom QCOL: [ar] .bId dari statistik dengan id 2
Memuat histogram untuk kolom QCOL: [ar] .fId dari statistik dengan id 1

Selektivitas: 0

Perhitungan ini menilai bahwa bergabung dengan 20.608 baris dengan 1 baris yang difilter akan memiliki selektivitas nol: tidak ada baris yang cocok (dilaporkan sebagai satu baris dalam rencana akhir). Apakah ini salah? Ya, mungkin ada bug di CE baru di sini. Orang bisa berpendapat bahwa 1 baris akan cocok dengan semua baris atau tidak sama sekali, sehingga hasilnya mungkin masuk akal, tetapi ada alasan untuk meyakini sebaliknya.

Rinciannya sebenarnya agak rumit, tetapi harapan untuk perkiraan didasarkan pada fIdhistogram tanpa filter , dimodifikasi oleh selektivitas filter, memberikan 20608 * 20608 * 4.85248e-005 = 20608baris sangat masuk akal.

Mengikuti perhitungan ini berarti menggunakan kalkulator CSelCalcSimpleJoinWithDistinctCountsalih-alih CSelCalcExpressionComparedToExpression. Tidak ada cara yang terdokumentasi untuk melakukan ini, tetapi jika Anda penasaran, Anda dapat mengaktifkan tanda jejak tidak berdokumen 9479:

Perhatikan bahwa sambungan akhir menghasilkan 20.608 baris dari dua input baris tunggal, tetapi itu tidak mengejutkan. Ini adalah paket yang sama yang diproduksi oleh CE asli di bawah TF 9481.

Saya menyebutkan rinciannya rumit (dan memakan waktu untuk menyelidiki), tetapi sejauh yang saya tahu, akar penyebab masalah terkait dengan predikat rId = 508, dengan selektivitas nol. Estimasi nol ini dinaikkan ke satu baris dengan cara normal, yang tampaknya berkontribusi pada estimasi selektivitas nol pada gabungan yang dipertanyakan ketika menghitung predikat yang lebih rendah di pohon input (karenanya memuat statistik untuk bId).

Mengizinkan sambungan luar untuk membuat estimasi sisi dalam nol-baris (alih-alih naik ke satu baris) (sehingga semua baris luar memenuhi syarat) memberikan estimasi gabungan 'bebas bug' dengan salah satu kalkulator. Jika Anda tertarik untuk menjelajahi ini, tanda jejak tidak berdokumen adalah 9473 (sendirian):

Perilaku estimasi kardinalitas gabungan dengan CSelCalcExpressionComparedToExpressionjuga dapat dimodifikasi untuk tidak memperhitungkan `` bId` dengan flag variasi lain yang tidak terdokumentasi (9494). Saya menyebutkan semua ini karena saya tahu Anda tertarik pada hal-hal seperti itu; bukan karena mereka menawarkan solusi. Sampai Anda melaporkan masalah tersebut ke Microsoft, dan mereka mengatasinya (atau tidak), mengungkapkan kueri secara berbeda mungkin merupakan cara terbaik untuk maju. Terlepas dari apakah perilaku itu disengaja atau tidak, mereka harus tertarik untuk mendengar tentang regresi.

Akhirnya, untuk merapikan satu hal lain yang disebutkan dalam naskah reproduksi: posisi akhir Filter dalam rencana pertanyaan adalah hasil dari eksplorasi berbasis biaya yang GbAggAfterJoinSelmemindahkan agregat dan filter di atas gabungan, karena output gabungan memiliki sedemikian kecil jumlah baris. Filter pada awalnya di bawah gabungan, seperti yang Anda harapkan.