Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1rNaqA-00Df1L-N9 for pgsql-hackers@arkaria.postgresql.org; Wed, 10 Jan 2024 15:50:03 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1rNaq9-005Dx2-ON for pgsql-hackers@arkaria.postgresql.org; Wed, 10 Jan 2024 15:50:01 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1rNaq9-005Dwl-A6 for pgsql-hackers@lists.postgresql.org; Wed, 10 Jan 2024 15:50:01 +0000 Received: from mail.postgrespro.ru ([93.174.131.139]) by magus.postgresql.org with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1rNaq2-000r3k-Ev for pgsql-hackers@postgresql.org; Wed, 10 Jan 2024 15:50:00 +0000 Received: from [192.168.1.34] (cm-27-145-180-125.revip12.asianet.co.th [27.145.180.125]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) (Authenticated sender: a.lepikhov@postgrespro.ru) by mail.postgrespro.ru (Postfix/587) with ESMTPSA id 3E9FBE21040; Wed, 10 Jan 2024 18:49:50 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mx2023; t=1704901792; bh=/yPn68w+F71W18KQjXGujIkslww6yo71S47oPuqvlKU=; h=Message-ID:Date:User-Agent:Subject:To:Cc:References:From: In-Reply-To:From; b=a4TCV3T4A8Hc2HLwpow3Rf+g8R731WYxOTT2rsnpuEtQk7BpYqg4oe+6gvEET6vJc bwnkM7TQjYeJLNzj637glQiVhQvtEC+BCl60UvPH2CRrrOLUyk5KfOhgHOIABlQfGf Es6cdPN/HCIBmFnZtyr4FXZAwhmjBhbaho5weocYBSI2t6+rAnV/nyQbxeDkr8d25Y kzk5X1bOD1rBICYKCK+eg4MvCOE3yMZdnKg/3zDSJLA4ekxQ9liRsOKgoXlJ1+S3YW pTowRXmXXi1OephtK9SVM7ohr+VTmaZr/9VkH/9UO+7Wf2Q1z4jpDYltCD211QieXV nBENLgQJji6MA== Message-ID: <2ba586f7-ae89-4255-bb6e-37af0808b413@postgrespro.ru> Date: Wed, 10 Jan 2024 22:49:48 +0700 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: Multidimensional Histograms Content-Language: en-US To: Alexander Cheshev Cc: Tomas Vondra , pgsql-hackers@postgresql.org, Teodor Sigaev References: <6e92450c-8136-11d4-8f6e-501c693af5c8@enterprisedb.com> <62435ae5-15f3-4485-a8e5-4f50d3bc8c8b@postgrespro.ru> <31d8c6d6-717c-45ae-a8f7-9947eb5e3401@enterprisedb.com> <8af87595-2e6f-43cd-9a20-cc5489c18e49@postgrespro.ru> <6ac2fad9-45e8-4d5a-9de0-a02666bf50d3@enterprisedb.com> From: Andrei Lepikhov Organization: Postgres Professional In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk On 8/1/2024 16:21, Alexander Cheshev wrote: > Hi Andrei, > >> Maybe my wording needed to be more precise. I didn't implement >> multidimensional histograms before, so I don't know how expensive they >> are. I meant that for dependency statistics over about six columns, we >> have a lot of combinations to compute. > > Equi-Depth Histogram in a 6 dimensional case requires 6 times more > iterations. Postgres already uses Equi-Depth Histogram. Even if you > increase the number of buckets from 100 to 1000 then there will be no > overhead as the time complexity of Equi-Depth Histogram has no > dependence on the number of buckets. So, no overhead at all! Maybe. For three columns, we have 9 combinations (passes) for building dependency statistics and 4 combinations for ndistincts; for six columns, we have 186 and 57 combinations correspondingly. Even remembering that dependency is just one number for one combination, building the dependency statistics is still massive work. So, in the multicolumn case, having something like a histogram may be more effective. -- regards, Andrei Lepikhov Postgres Professional