X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (unknown [200.46.204.2]) by svr1.postgresql.org (Postfix) with ESMTP id 35FBFD1B4E4 for ; Fri, 14 Nov 2003 22:13:05 +0000 (GMT) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (neptune.hub.org [200.46.204.2]) (amavisd-new, port 10024) with ESMTP id 81185-01 for ; Fri, 14 Nov 2003 18:12:36 -0400 (AST) Received: from sss.pgh.pa.us (unknown [192.204.191.242]) by svr1.postgresql.org (Postfix) with ESMTP id 7233FD1B561 for ; Fri, 14 Nov 2003 18:12:33 -0400 (AST) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.12.10/8.12.10) with ESMTP id hAEMCS19005810; Fri, 14 Nov 2003 17:12:28 -0500 (EST) To: nickf@ontko.com Cc: "Pgsql-Performance@Postgresql. Org" , "Ray Ontko" Subject: Re: n_distinct way off, but following a pattern. In-reply-to: References: Comments: In-reply-to "Nick Fankhauser" message dated "Fri, 14 Nov 2003 16:27:16 -0500" Date: Fri, 14 Nov 2003 17:12:27 -0500 Message-ID: <5809.1068847947@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: by amavisd-new at postgresql.org X-Archive-Number: 200311/125 X-Sequence-Number: 4685 "Nick Fankhauser" writes: > I'm seeing estimates for n_distinct that are way off for a large table Estimating n_distinct from a small sample is inherently a hard problem. I'm not surprised that the estimates would get better as the sample size increases. But maybe we can do better. The method we are currently using is this: /*---------- * Estimate the number of distinct values using the estimator * proposed by Haas and Stokes in IBM Research Report RJ 10025: * n*d / (n - f1 + f1*n/N) * where f1 is the number of distinct values that occurred * exactly once in our sample of n rows (from a total of N), * and d is the total number of distinct values in the sample. * This is their Duj1 estimator; the other estimators they * recommend are considerably more complex, and are numerically * very unstable when n is much smaller than N. It would be interesting to see exactly what inputs are going into this equation. Do you feel like adding some debug printouts into this code? Or just looking at the variables with a debugger? In 7.3 it's about line 1060 in src/backend/commands/analyze.c. BTW, this is already our second try at this problem, the original 7.2 equation didn't last long at all ... regards, tom lane