Postgresql – Inefficient execution plan selected by PostgreSQL

execution-planperformancepostgresqlpostgresql-9.5

I have the following SQL query

explain analyze
select    CERTIFICATE_ID,
   SERIAL_NUMBER,
   SUBJECT_DISTINGUISHED_NAME,
   NOT_BEFORE,
   NOT_AFTER,
   FIRST_SEEN,
   REVOKED,
   LINT_ERRORS  from (

select
         C.ID CERTIFICATE_ID,
         X509_SERIALNUMBER(C.CERTIFICATE) SERIAL_NUMBER,
         X509_SUBJECTNAME(C.CERTIFICATE) SUBJECT_DISTINGUISHED_NAME,
         X509_NOTBEFORE(C.CERTIFICATE) NOT_BEFORE,
         X509_NOTAFTER(C.CERTIFICATE) NOT_AFTER,
         (
            select
               min(CLE.ENTRY_TIMESTAMP) 
            from
               CT_LOG_ENTRY CLE 
            where
               CLE.CERTIFICATE_ID = C.ID 
         )
         FIRST_SEEN,
         (
            select
               count(CRL.CA_ID) 
            from
               CRL_REVOKED CRL 
            where
               CRL.CA_ID = 52410 
               and CRL.SERIAL_NUMBER = X509_SERIALNUMBER(C.CERTIFICATE) 
         )
         REVOKED,
         (
            select
               count(LCI.CERTIFICATE_ID) 
            from
               LINT_CERT_ISSUE LCI 
            where
               LCI.CERTIFICATE_ID = C.ID 
         )
         LINT_ERRORS 
      from
         CERTIFICATE C 
      where
         C.ISSUER_CA_ID = 52410
    ) as all_certs
    
    where REVOKED = 0 and LINT_ERRORS > 0 AND NOT_AFTER > '2018-06-05'::TIMESTAMP AND FIRST_SEEN > '2018-05-29'::TIMESTAMP

which gets executed against a database with this schema https://github.com/crtsh/certwatch_db/blob/master/create_schema.sql available under crt.sh with the user Guest (in case you want to try it).

If I execute it with the where clause NOT_AFTER > '2018-06-05'::TIMESTAMP AND FIRST_SEEN > '2018-05-29'::TIMESTAMP it is very slow:

Index Scan using c_notafter_ica on certificate c  (cost=0.57..8292463.66 rows=25 width=1383) (actual time=202744.665..202744.665 rows=0 loops=1)
  Index Cond: ((x509_notafter(certificate) > '2018-06-05 00:00:00'::timestamp without time zone) AND (issuer_ca_id = 52410))
  Filter: (((SubPlan 4) = 0) AND ((SubPlan 5) > 0) AND ((SubPlan 6) > '2018-05-29 00:00:00'::timestamp without time zone))
  Rows Removed by Filter: 4079
  SubPlan 1
    ->  Aggregate  (cost=31.08..31.09 rows=1 width=8) (never executed)
          ->  Index Scan using ctle_pk on ct_log_entry cle  (cost=0.58..31.05 rows=13 width=8) (never executed)
                Index Cond: (certificate_id = c.id)
  SubPlan 2
    ->  Aggregate  (cost=8.60..8.61 rows=1 width=4) (never executed)
          ->  Index Only Scan using crlr_pk on crl_revoked crl  (cost=0.57..8.59 rows=1 width=4) (never executed)
                Index Cond: ((ca_id = 52410) AND (serial_number = x509_serialnumber(c.certificate)))
                Heap Fetches: 0
  SubPlan 3
    ->  Aggregate  (cost=8.69..8.70 rows=1 width=8) (never executed)
          ->  Index Only Scan using lci_c on lint_cert_issue lci  (cost=0.57..8.68 rows=6 width=8) (never executed)
                Index Cond: (certificate_id = c.id)
                Heap Fetches: 0
  SubPlan 4
    ->  Aggregate  (cost=8.60..8.61 rows=1 width=4) (actual time=0.397..0.398 rows=1 loops=4079)
          ->  Index Only Scan using crlr_pk on crl_revoked crl_1  (cost=0.57..8.59 rows=1 width=4) (actual time=0.016..0.016 rows=0 loops=4079)
                Index Cond: ((ca_id = 52410) AND (serial_number = x509_serialnumber(c.certificate)))
                Heap Fetches: 561
  SubPlan 5
    ->  Aggregate  (cost=8.69..8.70 rows=1 width=8) (actual time=0.149..0.150 rows=1 loops=3603)
          ->  Index Only Scan using lci_c on lint_cert_issue lci_1  (cost=0.57..8.68 rows=6 width=8) (actual time=0.147..0.147 rows=0 loops=3603)
                Index Cond: (certificate_id = c.id)
                Heap Fetches: 0
  SubPlan 6
    ->  Aggregate  (cost=31.08..31.09 rows=1 width=8) (actual time=1.329..1.330 rows=1 loops=6)
          ->  Index Scan using ctle_pk on ct_log_entry cle_1  (cost=0.58..31.05 rows=13 width=8) (actual time=1.010..1.321 rows=2 loops=6)
                Index Cond: (certificate_id = c.id)
Planning time: 0.594 ms
Execution time: 202744.792 ms

But if I change the filter criteria to NOT_AFTER > '2017-07-01'::TIMESTAMP AND FIRST_SEEN > '2018-05-29'::TIMESTAMP the execution plan changes and it get's pretty fast (by the order of two magnitudes):

Index Scan using c_ica_typecanissue on certificate c  (cost=0.57..9012341.59 rows=1 width=1383) (actual time=0.684..2606.056 rows=4713 loops=1)
  Index Cond: (issuer_ca_id = 52410)
  Filter: ((x509_notafter(certificate) > '2017-07-01 00:00:00'::timestamp without time zone) AND ((SubPlan 4) = 0) AND ((SubPlan 5) = 0) AND ((SubPlan 6) > '2017-07-01 00:00:00'::timestamp without time zone))
  Rows Removed by Filter: 652
  SubPlan 1
    ->  Aggregate  (cost=31.08..31.09 rows=1 width=8) (actual time=0.013..0.014 rows=1 loops=4713)
          ->  Index Scan using ctle_pk on ct_log_entry cle  (cost=0.58..31.05 rows=13 width=8) (actual time=0.005..0.008 rows=3 loops=4713)
                Index Cond: (certificate_id = c.id)
  SubPlan 2
    ->  Aggregate  (cost=8.60..8.61 rows=1 width=4) (actual time=0.071..0.072 rows=1 loops=4713)
          ->  Index Only Scan using crlr_pk on crl_revoked crl  (cost=0.57..8.59 rows=1 width=4) (actual time=0.005..0.005 rows=0 loops=4713)
                Index Cond: ((ca_id = 52410) AND (serial_number = x509_serialnumber(c.certificate)))
                Heap Fetches: 0
  SubPlan 3
    ->  Aggregate  (cost=8.69..8.70 rows=1 width=8) (actual time=0.006..0.007 rows=1 loops=4713)
          ->  Index Only Scan using lci_c on lint_cert_issue lci  (cost=0.57..8.68 rows=6 width=8) (actual time=0.004..0.004 rows=0 loops=4713)
                Index Cond: (certificate_id = c.id)
                Heap Fetches: 0
  SubPlan 4
    ->  Aggregate  (cost=8.60..8.61 rows=1 width=4) (actual time=0.072..0.073 rows=1 loops=5365)
          ->  Index Only Scan using crlr_pk on crl_revoked crl_1  (cost=0.57..8.59 rows=1 width=4) (actual time=0.005..0.005 rows=0 loops=5365)
                Index Cond: ((ca_id = 52410) AND (serial_number = x509_serialnumber(c.certificate)))
                Heap Fetches: 680
  SubPlan 5
    ->  Aggregate  (cost=8.69..8.70 rows=1 width=8) (actual time=0.007..0.007 rows=1 loops=4726)
          ->  Index Only Scan using lci_c on lint_cert_issue lci_1  (cost=0.57..8.68 rows=6 width=8) (actual time=0.005..0.005 rows=0 loops=4726)
                Index Cond: (certificate_id = c.id)
                Heap Fetches: 0
  SubPlan 6
    ->  Aggregate  (cost=31.08..31.09 rows=1 width=8) (actual time=0.015..0.016 rows=1 loops=4713)
          ->  Index Scan using ctle_pk on ct_log_entry cle_1  (cost=0.58..31.05 rows=13 width=8) (actual time=0.006..0.010 rows=3 loops=4713)
                Index Cond: (certificate_id = c.id)
Planning time: 0.664 ms
Execution time: 2610.109 ms

What can I do to always have it executed quickly?

It is PostgreSQL 9.5.10 on x86_64-pc-linux-gnu, compiled by x86_64-pc-linux-gnu-gcc (Gentoo Hardened 4.9.3 p1.5, pie-0.6.4) 4.9.3, 64-bit

Based on the comment of @ypercube I started to rewrite my query to use LATERAL.

select C.ID CERTIFICATE_ID,
       X509_SERIALNUMBER(C.CERTIFICATE) SERIAL_NUMBER,
       X509_SUBJECTNAME(C.CERTIFICATE) SUBJECT_DISTINGUISHED_NAME,
       X509_NOTBEFORE(C.CERTIFICATE) NOT_BEFORE,
       X509_NOTAFTER(C.CERTIFICATE) NOT_AFTER,
       X.FIRST_SEEN FIRST_SEEN
from CERTIFICATE C
join lateral
  ( select MAX(ENTRY_TIMESTAMP) FIRST_SEEN,
           CERTIFICATE_ID
   from CT_LOG_ENTRY
   group by CERTIFICATE_ID) X on X.CERTIFICATE_ID = C.ID
where C.ISSUER_CA_ID = 52410

Sadly that wasn't successful:

Merge Join  (cost=359447425.76..375740839.22 rows=50631 width=1391)
  Merge Cond: (ct_log_entry.certificate_id = c.id)
  ->  GroupAggregate  (cost=358762818.33..373327199.94 rows=138136176 width=12)
        Group Key: ct_log_entry.certificate_id
        ->  Sort  (cost=358762818.33..363157158.28 rows=1757735980 width=12)
              Sort Key: ct_log_entry.certificate_id
              ->  Seq Scan on ct_log_entry  (cost=0.00..28774171.80 rows=1757735980 width=12)
  ->  Materialize  (cost=684607.44..685485.45 rows=175603 width=1383)
        ->  Sort  (cost=684607.44..685046.44 rows=175603 width=1383)
              Sort Key: c.id
              ->  Index Scan using c_ica_typecanissue on certificate c  (cost=0.57..563673.70 rows=175603 width=1383)
                    Index Cond: (issuer_ca_id = 52410)

Any more ideas?

Best Answer

Thanks to the idea of @ypercubeᵀᴹ I was able to get it working with LATERAL:

select C.ID CERTIFICATE_ID,
       X509_SERIALNUMBER(C.CERTIFICATE) SERIAL_NUMBER,
       X509_SUBJECTNAME(C.CERTIFICATE) SUBJECT_DISTINGUISHED_NAME,
       X509_NOTBEFORE(C.CERTIFICATE) NOT_BEFORE,
       X509_NOTAFTER(C.CERTIFICATE) NOT_AFTER,
       X.FIRST_SEEN FIRST_SEEN,
       Y.REVOKED REVOKED,
       L.LINT_ERRORS LINT_ERRORS
from CERTIFICATE C
join lateral
    (select MIN(CTLE.ENTRY_TIMESTAMP) FIRST_SEEN,
             CTLE.CERTIFICATE_ID
     from CT_LOG_ENTRY CTLE
     where CTLE.CERTIFICATE_ID = C.ID
     group by CTLE.CERTIFICATE_ID ) X on true
left join lateral
    (select COUNT(CRL.CA_ID) REVOKED,
            CRL.SERIAL_NUMBER
     from CRL_REVOKED CRL
     where CRL.CA_ID = C.ISSUER_CA_ID
         and CRL.SERIAL_NUMBER = X509_SERIALNUMBER(C.CERTIFICATE)
     group by CRL.SERIAL_NUMBER) Y on true
left join lateral
    (select COUNT(LCI.CERTIFICATE_ID) LINT_ERRORS,
            LCI.CERTIFICATE_ID
     from LINT_CERT_ISSUE LCI
     where LCI.CERTIFICATE_ID = C.ID
     group by LCI.CERTIFICATE_ID ) L on true
where C.ISSUER_CA_ID = 52410 /*AND L.LINT_ERRORS >= 1*/
    and FIRST_SEEN > NOW() - interval '1 week'
    and X509_NOTAFTER(C.CERTIFICATE) > NOW()
order by CERTIFICATE_ID asc

I wouldn't call the new syntax more readable than the original one, but the query is working very efficient with all kind of combinations of parameter values I've tested.

Related Question