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 1rIHYT-007XEv-1g for pgsql-hackers@arkaria.postgresql.org; Wed, 27 Dec 2023 00:13:49 +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 1rIHYQ-00H8AM-FJ for pgsql-hackers@arkaria.postgresql.org; Wed, 27 Dec 2023 00:13:46 +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 1rIHYQ-00H8AE-2v for pgsql-hackers@lists.postgresql.org; Wed, 27 Dec 2023 00:13:46 +0000 Received: from mail-qv1-xf2f.google.com ([2607:f8b0:4864:20::f2f]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1rIHYJ-00E3l1-46 for pgsql-hackers@postgresql.org; Wed, 27 Dec 2023 00:13:45 +0000 Received: by mail-qv1-xf2f.google.com with SMTP id 6a1803df08f44-67f9f6caabcso35759906d6.3 for ; Tue, 26 Dec 2023 16:13:38 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1703636016; x=1704240816; darn=postgresql.org; h=to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=hsFJUH43usDDYsIuShIdkskpsuTEBn4JaeskPzAcHmo=; b=k/vvzDJ2vr8AOCNpRPHqqDSarM4j/2T4eWwoXhAreSsT52/77uPUEYIcNDaBt34kTT hy4aIUmFQ+y77rS+Vm+ZU6DQn/WzJesz3dkJ4ETkA6QOsMPvTCpVubgULYz7aov0H293 7pPjErLuB1GBOJ1IdIuFIuqQRt7S0lJIVoQWjziM0AHkNXyYxbtJrwYaQtSKg+LsmvzH F57gM2slauEeFoOjDaaxUXscX/BfeirHa7kKOidlXNXjr/DUsdbf/38xxrPbO+CuHuz/ msfUhjfb5D+mUHpAiumeBykUg7iGYpf678CG3RqttGKHMaJoAF27fXSQqeVf6K3dvWLO tCbQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1703636016; x=1704240816; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=hsFJUH43usDDYsIuShIdkskpsuTEBn4JaeskPzAcHmo=; b=N5AuhinEfJ/BUODRxXar1O+m0oQAvix7+9e9bC9a99aHqfugY+U2sRVyBpLS9Ohygr Fqe3IiBUS0sXWI2xPVzrKUf6pT5bReaTxzkhZUDomp76+zWX7i5uxENJ/nEdMdcbznne 0GZ+OJUHkFD8nxge+LMMFCO8UO88EybGy61WHqxvsevtzqx7GL46/QAdeiLR6ygMjCWi b7l2GRgt+ShpYtaypO4Fntr0RnEL40M9mCT9WoqqTLh50Z71je2RDb8DJkdsn7nBOP7z IOhaMY1Rsd3GeL4ZY8A2TBGRW5SipuKgxA+otcVDGkcYvXVHx9DEpkI81WJRI/7oKSC5 8dJg== X-Gm-Message-State: AOJu0YyQyWYVSYbX9hF/8jFjD9UffqgXPsr7cp1mThsITwcoptA8fEuJ 2TRD5KfN6B/mmM77+bqA9DL5I6yPDxzCGlONRf+MNA5QtV0= X-Google-Smtp-Source: AGHT+IHjDwp/MqXDXyimWnp8oIPHTkptc6Ukn5bZZhpCwWc78DNJJKMk37ddrY+jwhc1//5Me/eYgOL8jOwtg/UN0Rc= X-Received: by 2002:ad4:5ba8:0:b0:67f:5b3d:5f19 with SMTP id 8-20020ad45ba8000000b0067f5b3d5f19mr14520386qvq.57.1703636016489; Tue, 26 Dec 2023 16:13:36 -0800 (PST) MIME-Version: 1.0 From: Alexander Cheshev Date: Wed, 27 Dec 2023 01:13:25 +0100 Message-ID: Subject: Multidimensional Histograms To: pgsql-hackers@postgresql.org Content-Type: text/plain; charset="UTF-8" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk Hello Hackers, To improve selectivities of queries I suggest to add support of multidimensional histograms as described in paper [1]. To query multidimensional histograms efficiently we can use H-trees as described in paper [2]. Postgres has limited support of multivariate statistics: * MCV only useful for columns with small number of distinct values; * functional dependencies only reflect dependencies among columns (not column values). [1] http://www.cs.cmu.edu/~rcarlson/docs/RyanCarlson_databases.pdf [2] https://dl.acm.org/doi/pdf/10.1145/50202.50205 -- Regards, Alexander Cheshev