Robustness of PostgreSQL Query Optimization Under Stale Statistics, Data Drift, and Distribution Skew: A Depth-and-Breadth Study

Introduction

Before an SQL statement is executed, the query optimizer selects a physical execution plan from alternative access paths, join orders, and physical operators. Cost-based optimizers compare these alternatives using estimated execution costs, an approach established by the System R optimizer . Cardinality estimates for intermediate results are an important input to these cost calculations . When an intermediate cardinality is estimated incorrectly, the error can propagate to later joins that depend on that result . The resulting estimates can change the relative costs assigned to candidate plans and, consequently, the plan selected for execution. Such errors can change the relative costs assigned to candidate plans and, consequently, the plan selected for execution.

PostgreSQL stores planner statistics in its system catalog and uses them when estimating query cardinalities. The command samples table contents and refreshes these statistics for subsequent query planning . The command samples table contents and updates the planner statistics used during query optimization . These statistics describe the data at the time they are collected. They can therefore become inaccurate after the underlying values change. A bulk update, data migration, ingestion batch, or a concentrated change in a categorical value may alter the current distribution while the planner continues to use statistics collected from the earlier state. PostgreSQL documentation identifies inaccurate planner statistics as one possible cause of poor plan selection and provides automatic and manual analysis for refreshing them .

Research on query optimization has examined cardinality estimation, join ordering, cost models, and the runtime effect of different optimizer components. The Join Order Benchmark (JOB) was introduced with multi-join queries over IMDb data containing correlations that are difficult for conventional optimizers . A later JOB study further examined the effect of correlations that cross join boundaries . These studies provide evidence that estimation errors can affect the plans selected by an optimizer. The setting considered in this paper is more specific. We keep PostgreSQL and the SQL workload unchanged, modify the data distribution, and then examine what happens when the planner statistics still describe the data before that modification.

The effect of such a mismatch can depend on the query. If the stale estimates do not change the selected access path or join strategy, the execution may remain close to the result obtained with refreshed statistics. For another query, the same type of distribution change can alter the estimated cost of competing plans and lead to a different join order or physical operator. We therefore examine query-level runtimes rather than relying only on a single workload average or median. This is especially useful for identifying a small number of queries whose behavior differs substantially from the rest of the workload.

In this paper, we study stale planner statistics by creating paired PostgreSQL database copies from the same analyzed database. Both copies receive the same deterministic modifications to non-key attributes and contain the same current data when the queries are executed. The difference is that the stale copy keeps the statistics collected before the update, whereas the fresh copy runs after receiving the same update. Primary and foreign keys are not modified, so the join relationships remain unchanged. We record execution time, node-level cardinality error, join and scan operators, planning time, coarse plan topology, and the duration of . Buffer counters are also retained in the experimental output. Their node-wise sums are not used as quantitative I/O evidence because the captured PostgreSQL counters can be cumulative across plan nodes.

The evaluation is carried out in two phases. The first is a depth experiment with five representative TPC-H SF1 query forms and eight JOB queries. These queries are executed at 20%, 50%, and 80% targeted distribution drift, using two warm-up executions and seven measured executions for each successful condition. This phase is used to follow the same queries as the amount of drift changes and to inspect their PostgreSQL plans in detail. The second phase evaluates all 113 canonical JOB queries at 80% drift, using one warm-up and three measured executions. Before inspecting the complete 113-query outcome, we fixed the query population, repetition count, timeout treatment, slowdown thresholds, and statistical tests for this phase. The protocol was fixed internally for the experiment and was not externally preregistered.

The breadth experiment shows that the effect is not uniform across JOB. For the 106 uncensored stale/fresh query pairs, the median runtime ratio is 1.006×, with a bootstrap 95% confidence interval of 0.992-1.044. At the query level, 31 of 113 queries are at least 2× slower with stale statistics. Fourteen are at least 10× slower, and three are at least 100× slower. Seven stale query conditions exceed the 180 s statement cap, whereas every corresponding fresh condition completes within the cap. JOB 2c gives the largest exact ratio at 3660×. The depth experiment also shows increasing sensitivity in the same JOB family as the targeted drift is increased from 20% to 80%.

The work provides an empirical characterization of this behavior in PostgreSQL rather than a new optimizer or cardinality estimator. The paired databases allow statistics freshness to change while the current data and SQL remain fixed. Repeated measurements in the depth phase are used to examine how individual plans change with drift, while the complete JOB breadth phase measures the frequency of large slowdowns at the severe drift setting. We also retain the PostgreSQL JSON plans for the largest regressions. These plans are used to compare estimated and actual rows and to examine the join operators selected under stale and fresh statistics.

Complete Article

The complete article, including all figures, tables, equations and algorithms, is available in the official publication PDF.

View Full PDF

Conclusion

We evaluated PostgreSQL 16.4 after controlled changes to the database value distribution while keeping the current data and SQL identical between paired stale and freshly analyzed copies. In the depth experiment, JOB queries 2a-2c become progressively slower relative to their fresh-statistics executions as the targeted drift increases. Query 2c changes from 861.8× at 20% drift to 3491.0× at 80%. The separate breadth experiment repeats the 80% condition over all 113 canonical JOB queries.

The breadth measurements show that the slowdown is concentrated in part of the workload. The uncensored median stale/fresh ratio is 1.006×, while 31 queries are at least 2× slower, 14 are at least 10× slower, and three are at least 100× slower. Seven stale query-conditions exceed the 180 s statement limit, whereas every fresh condition completes. In the plan cases examined in detail, large runtime regressions coincide with substantial cardinality underestimation and changes in join topology. Query 2c provides the largest exact breadth ratio at 3660.16×.

These measurements show why the median alone is insufficient to describe this workload under the tested drift intervention. Many JOB queries remain close to their fresh-statistics runtime, while a smaller group accounts for the large slowdowns and timeouts. Future experiments should randomize stale/fresh execution order and apply the complete JOB workload at lower drift levels. Further evaluation on additional PostgreSQL versions and other DBMSs is also needed. A separate maintenance study could then test targeted statistics refresh and distribution-aware refresh triggers under less severe and more production-like update patterns.

Data Availability

The study uses the public Join Order Benchmark SQL and May-2013 IMDb snapshot and TPC-H-derived synthetic data as described in the manuscript.

References

1. P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price, “Access path selection in a relational database management system, ” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 1979, pp. 23-34, doi: 10.1145/582095.582099
2. S. Chaudhuri, “An overview of query optimization in relational systems, ” in Proc. 17th ACM SIGACT-SIGMOD-SIGART Symp. Principles Database Systems, 1998, pp. 34-43, doi: 10.1145/275487.275492
3. Y. E. Ioannidis and S. Christodoulakis, “On the propagation of errors in the size of join results, ” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 1991, pp. 268-277, doi: 10.1145/115790.115835
4. PostgreSQL Global Development Group, “ANALYZE, ” PostgreSQL 16 Documentation. [Online]. Available: https://www.postgresql.org/docs/16/sql-analyze.html
5. PostgreSQL Global Development Group, “Updating planner statistics, ” PostgreSQL 16 Documentation, Sec. 25.1.3. [Online]. Available: https://www.postgresql.org/docs/16/routine-vacuuming.html
6. V. Leis, A. Gubichev, A. Mirchev, P. Boncz, A. Kemper, and T. Neumann, “How good are query optimizers, really?” Proc. VLDB Endowment, vol. 9, no. 3, pp. 204-215, 2015, doi: 10.14778/2850583.2850594
7. V. Leis, B. Radke, A. Gubichev, A. Mirchev, P. A. Boncz, A. Kemper, and T. Neumann, “Query optimization through the looking glass, and what we found running the Join Order Benchmark, ” VLDB J., vol. 27, no. 5, pp. 643-668, 2018, doi: 10.1007/s00778-017-0480-7
8. M. Stillger, G. M. Lohman, V. Markl, and M. Kandil, “LEO - DB2's LEarning optimizer, ” in Proc. 27th Int. Conf. Very Large Data Bases, 2001, pp. 19-28.
9. V. Markl, V. Raman, D. E. Simmen, G. M. Lohman, H. Pirahesh, and M. Cilimdzic, “Robust query processing through progressive optimization, ” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2004, pp. 659-670, doi: 10.1145/1007568.1007642
10. V. Leis, B. Radke, A. Gubichev, A. Kemper, and T. Neumann, “Cardinality estimation done right: Index-based join sampling, ” in Proc. 8th Biennial Conf. Innovative Data Systems Research, 2017.
11. A. Kipf, T. Kipf, B. Radke, V. Leis, P. Boncz, and A. Kemper, “Learned cardinalities: Estimating correlated joins with deep learning, ” in Proc. 9th Biennial Conf. Innovative Data Systems Research, 2019.
12. Z. Yang, E. Liang, A. Kamsetty, C. Wu, Y. Duan, X. Chen, P. Abbeel, J. M. Hellerstein, S. Krishnan, and I. Stoica, “Deep unsupervised cardinality estimation, ” Proc. VLDB Endowment, vol. 13, no. 3, pp. 279-292, 2019, doi: 10.14778/3368289.3368294
13. B. Hilprecht, A. Schmidt, M. Kulessa, A. Molina, K. Kersting, and C. Binnig, “DeepDB: Learn from data, not from queries!” Proc. VLDB Endowment, vol. 13, no. 7, pp. 992-1005, 2020, doi: 10.14778/3384345.3384349
14. PostgreSQL Global Development Group, “CREATE STATISTICS, ” PostgreSQL 16 Documentation. [Online]. Available: https://www.postgresql.org/docs/16/sql-createstatistics.html
15. S. Zeighami and C. Shahabi, “Theoretical analysis of learned database operations under distribution shift through distribution learnability, ” in Proc. 41st Int. Conf. Machine Learning, PMLR, vol. 235, 2024, pp. 58283-58305.
16. A. Kamali, V. Kantere, C. Zuzarte, and V. Corvinelli, “Roq: Robust query optimization based on a risk-aware learned cost model, ” arXiv preprint arXiv:2401.15210, 2024.
17. P. Negi, R. Marcus, A. Kipf, H. Mao, N. Tatbul, T. Kraska, and M. Alizadeh, “Flow-Loss: Learning cardinality estimates that matter, ” Proc. VLDB Endowment, vol. 14, no. 11, pp. 2019-2032, 2021, doi: 10.14778/3476249.3476259
18. Y. Han, Z. Wu, P. Wu, R. Zhu, J. Yang, L. W. Tan, K. Zeng, G. Cong, Y. Qin, A. Pfadler, Z. Qian, J. Zhou, J. Li, and B. Cui, “Cardinality estimation in DBMS: A comprehensive benchmark evaluation, ” Proc. VLDB Endowment, vol. 15, no. 4, pp. 752-765, 2021, doi: 10.14778/3503585.3503586
19. PostgreSQL Global Development Group, “PostgreSQL 16.4 release notes, ” Aug. 8, 2024. [Online]. Available: https://www.postgresql.org/docs/release/16.4/
20. Transaction Processing Performance Council, TPC Benchmark H (TPC-H) Standard Specification, Revision 3.0.1, 2022.