4 ms·
> Some clever abuse of the query planner output quickly gives us an estimate. Tldr: They estimate counts by parsing it out of the query plan but get an exact c
by kjeetgill 5y ago
> Some clever abuse of the query planner output quickly gives us an estimate.
Tldr: They estimate counts by parsing it out of the query plan but get an exact count if the estimate is under a threshold.
Clever! But it makes me nervous. I was expecting it to involve HLL or CountMinSketch or something.
- twoodfin 5y agoIndeed, this is relying on the optimizer’s cardinality estimates from previously collected statistics. These are notoriously inaccurate across all DBMS’s in even marginally complex queries[1]. They’re obviously better than nothing when making planning decisions—correctly estimating A > B is useful enough even if both are off by large factors—and maybe for this application it’s effective enough. For the DBMS I work on, an alternative solution would involve bitmap indexes for each possible filter field. These are compact and can be logically combined and counted at rates of billions/second via SIMD, even without HLL or other estimators. [1] https://www.vldb.org/pvldb/vol9/p204-leis.pdf https://www.vldb.org/pvldb/vol9/p204-leis.pdf
- code_biologist 5y agoCurious how you'd do bitmap indexes at a user level in postgres? An extension like pg_roaringbitmap [1] or am I missing something native? [1] https://pgxn.org/dist/pg_roaringbitmap/ https://pgxn.org/dist/pg_roaringbitmap/
- twoodfin 5y agoAFAICT bitmaps as a persistent index structure aren’t supported. They’re only used in-memory at query runtime for combining results from multiple index scans.
- hansvm 5y agoI've hacked together something nearly equivalent to roaring bitmaps with varbits and a bit of extra metadata. Caveat emptor, but it was good enough for the problem at hand.