Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1Uci6a-0003cj-JJ for pgsql-performance@arkaria.postgresql.org; Wed, 15 May 2013 20:15:20 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.72) (envelope-from ) id 1Uci6a-0000d5-3S for pgsql-performance@arkaria.postgresql.org; Wed, 15 May 2013 20:15:20 +0000 Received: from makus.postgresql.org ([2001:4800:7903:4::125]) by malur.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1Uci6Z-0000d0-6W for pgsql-performance@postgresql.org; Wed, 15 May 2013 20:15:19 +0000 Received: from mbx.knossos.net.nz ([202.160.48.10]) by makus.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1Uci6U-0002eu-0t for pgsql-performance@postgresql.org; Wed, 15 May 2013 20:15:18 +0000 Received: from [10.1.1.3] (60-234-150-59.bitstream.orcon.net.nz [60.234.150.59]) (authenticated bits=0) by mbx.knossos.net.nz (8.14.4/8.14.4) with ESMTP id r4FKF2VV010025 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Thu, 16 May 2013 08:15:03 +1200 Message-ID: <5193ECC6.4080901@archidevsys.co.nz> Date: Thu, 16 May 2013 08:15:02 +1200 From: Gavin Flower Organization: ArchiDevSys User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130509 Thunderbird/17.0.6 MIME-Version: 1.0 To: Craig James CC: sthomas@optionshouse.com, "pgsql-performance@postgresql.org" Subject: Re: Thinking About Correlated Columns (again) References: <5193AA62.2040700@optionshouse.com> In-Reply-To: Content-Type: multipart/alternative; boundary="------------020206030002080405020004" X-Pg-Spam-Score: 0.8 (/) List-Archive: List-Help: List-ID: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: X-Mailing-List: pgsql-performance Precedence: bulk Sender: pgsql-performance-owner@postgresql.org This is a multi-part message in MIME format. --------------020206030002080405020004 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit On 16/05/13 04:23, Craig James wrote: > On Wed, May 15, 2013 at 8:31 AM, Shaun Thomas > > wrote: > > [Inefficient plans for correlated columns] has been a pain point > for quite a while. While we've had several discussions in the > area, it always seems to just kinda trail off and eventually > vanish every time it comes up. > [...] > > It's a very hard problem. There's no way you can keep statistics > about all possible correlations since the number of possibilities is > O(N^2) with the number of columns. Actually far worse: N!/(N - K)!K! summed over K=1...N, assuming the order of columns in the correlation is unimportant (otherwise it is N factorial) - based on my hazy recollection of the relevant maths... [...] Cheers, Gavin --------------020206030002080405020004 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit
On 16/05/13 04:23, Craig James wrote:
On Wed, May 15, 2013 at 8:31 AM, Shaun Thomas <sthomas@optionshouse.com> wrote:
[Inefficient plans for correlated columns] has been a pain point for quite a while. While we've had several discussions in the area, it always seems to just kinda trail off and eventually vanish every time it comes up.

[...]

It's a very hard problem.  There's no way you can keep statistics about all possible correlations since the number of possibilities is O(N^2) with the number of columns.
Actually far worse: N!/(N - K)!K! summed over K=1...N, assuming the order of columns in the correlation is unimportant (otherwise it is N factorial) - based on my hazy recollection of the relevant maths...

[...]

Cheers,
Gavin

--------------020206030002080405020004--