Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1ovNcr-0007EK-1e for pgsql-committers@arkaria.postgresql.org; Wed, 16 Nov 2022 18:59:09 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1ovNcp-0006tw-3I for pgsql-committers@arkaria.postgresql.org; Wed, 16 Nov 2022 18:59:07 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1ovNco-0006tH-SN for pgsql-committers@lists.postgresql.org; Wed, 16 Nov 2022 18:59:06 +0000 Received: from mahout.postgresql.org ([2001:4800:3e1:1::227]) by makus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1ovNcm-00067V-9L for pgsql-committers@lists.postgresql.org; Wed, 16 Nov 2022 18:59:05 +0000 Received: from gemulon.postgresql.org ([2001:4800:3e1:1::198]) by mahout.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1ovNcl-0006ta-Ui for pgsql-committers@lists.postgresql.org; Wed, 16 Nov 2022 18:59:03 +0000 Received: from localhost ([127.0.0.1] helo=gemulon.postgresql.org) by gemulon.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1ovNck-000UYW-On for pgsql-committers@lists.postgresql.org; Wed, 16 Nov 2022 18:59:03 +0000 Content-Type: multipart/mixed; boundary="===============1493815644718986496==" MIME-Version: 1.0 From: Tom Lane To: pgsql-committers@lists.postgresql.org Subject: pgsql: Invent "multibitmapsets", and use them to speed up antijoin dete X-Auto-Response-Suppress: All Auto-Submitted: auto-generated Message-Id: Date: Wed, 16 Nov 2022 18:59:03 +0000 List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --===============1493815644718986496== Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: base64 SW52ZW50ICJtdWx0aWJpdG1hcHNldHMiLCBhbmQgdXNlIHRoZW0gdG8gc3BlZWQgdXAgYW50aWpv aW4gZGV0ZWN0aW9uLgoKSW1wbGVtZW50IGEgZGF0YSBzdHJ1Y3R1cmUgdGhhdCBpcyBhIExpc3Qg b2YgQml0bWFwc2V0cywgd2hpY2ggaXMKZXNzZW50aWFsbHkgYSAyLUQgYm9vbGVhbiBhcnJheSBl eGNlcHQgdGhhdCB0aGUgcm93cyBuZWVkIG5vdCBhbGwKYmUgdGhlIHNhbWUgd2lkdGguICBPcGVy YXRpb25zIHN1Y2ggYXMgdW5pb24gYW5kIGludGVyc2VjdGlvbiBhcmUKbWVhbmluZ2Z1bCBmb3Ig dGhlc2UsIGp1c3QgYXMgdGhleSBhcmUgZm9yIEJpdG1hcHNldHMuICBFdmVudHVhbGx5CndlIG1p Z2h0IGJ1aWxkIG1hbnkgb2YgdGhlIHNhbWUgb3BlcmF0aW9ucyB0aGF0IHdlIGhhdmUgd3JpdHRl biBmb3IKQml0bWFwc2V0cywgYnV0IGZvciB0aGUgZmlyc3QgdXNlLWNhc2Ugd2UganVzdCBuZWVk IGEgZmV3LgoKVGhhdCBmaXJzdCB1c2UtY2FzZSBpcyBmb3IgYW50aWpvaW4gZGV0ZWN0aW9uOiBy ZWR1Y2Vfb3V0ZXJfam9pbnMKbmVlZHMgdG8gZmluZCB0aGUgc2V0IG9mIFZhcnMgdGhhdCBhcmUg Y2VydGFpbiB0byBiZSBub24tbnVsbCBpbiBhCnN1Y2Nlc3NmdWxseSBqb2luZWQgKG5vdCBudWxs LWV4dGVuZGVkKSBsZWZ0IGpvaW4gcm93LCBhbmQgYWxzbwpmaW5kIHRoZSBzZXQgb2YgVmFycyBz dWJqZWN0IHRvIGhpZ2hlci1sZXZlbCBJUyBOVUxMIGNvbnN0cmFpbnRzLAphbmQgaW50ZXJzZWN0 IHRoZW0uICBXZSBoYWQgYmVlbiBkb2luZyB0aGlzIGJ5IG1ha2luZyBMaXN0cyBvZgp0aGUgVmFy IG5vZGVzIGFuZCB0aGVuIHVzaW5nIGxpc3RfaW50ZXJzZWN0LCB3aGljaCB3b3JrcyBidXQgaXMK cHJldHR5IGluZWZmaWNpZW50IGNvbXBhcmVkIHRvIGEgYml0bWFwc2V0LWxpa2UgaW50ZXJzZWN0 aW9uLgpQb3RlbnRpYWxseSBpdCdzIE8oTl4yKSBpZiB0aGVyZSBhcmUgYSBsb3Qgb2YgVmFycyBp bnZvbHZlZCwKd2hpY2ggZm9ydHVuYXRlbHkgdGhlcmUgZ2VuZXJhbGx5IGFyZW4ndDsgc3RpbGwg aXQncyBub3QgZ3JlYXQuCk1vcmVvdmVyLCB0aGF0IG1ldGhvZCByZXF1aXJlcyB0aGUgVmFycyBv ZiBpbnRlcmVzdCB0byBiZSBleGFjdGx5CmVxdWFsKCkgaW4gdGhlIGpvaW4gY29uZGl0aW9uIGFu ZCB0aGUgdXBwZXIgSVMgTlVMTCBjb25kaXRpb24sCndoaWNoIGlzIHByb2JsZW1hdGljIGZvciBt eSBXSVAgcGF0Y2ggdGhhdCBsYWJlbHMgVmFycyBhY2NvcmRpbmcKdG8gd2hpY2ggb3V0ZXIgam9p bnMgaGF2ZSBwb3NzaWJseSBudWxsZWQgdGhlbS4KCkRpc2N1c3Npb246IGh0dHBzOi8vcG9zdGdy LmVzL20vODkyMjI4LjE2Njg0Mzc4MzhAc3NzLnBnaC5wYS51cwpEaXNjdXNzaW9uOiBodHRwczov L3Bvc3Rnci5lcy9tL0NBTWJXczQtbXZQUENKMVc2aUs2ZEQ1SGlOd29KZGk2bVpwPS03bUU4TjlT aCtjZDB0UUBtYWlsLmdtYWlsLmNvbQoKQnJhbmNoCi0tLS0tLQptYXN0ZXIKCkRldGFpbHMKLS0t LS0tLQpodHRwczovL2dpdC5wb3N0Z3Jlc3FsLm9yZy9wZy9jb21taXRkaWZmL2U5ZTI2YjVlNzE2 NmU2ZjE4NzNlZmQ1OGYzZDVhNGJhMjJjYzNkOGYKCk1vZGlmaWVkIEZpbGVzCi0tLS0tLS0tLS0t LS0tCnNyYy9iYWNrZW5kL25vZGVzL01ha2VmaWxlICAgICAgICAgICAgICAgIHwgICAxICsKc3Jj L2JhY2tlbmQvbm9kZXMvUkVBRE1FICAgICAgICAgICAgICAgICAgfCAgIDEgKwpzcmMvYmFja2Vu ZC9ub2Rlcy9tZXNvbi5idWlsZCAgICAgICAgICAgICB8ICAgMSArCnNyYy9iYWNrZW5kL25vZGVz L211bHRpYml0bWFwc2V0LmMgICAgICAgIHwgMTYyICsrKysrKysrKysrKysrKysrKysrKysrKysr KysrKwpzcmMvYmFja2VuZC9vcHRpbWl6ZXIvcHJlcC9wcmVwam9pbnRyZWUuYyB8ICAyMCArKy0t CnNyYy9iYWNrZW5kL29wdGltaXplci91dGlsL2NsYXVzZXMuYyAgICAgIHwgIDM5ICsrKystLS0K c3JjL2luY2x1ZGUvbm9kZXMvbXVsdGliaXRtYXBzZXQuaCAgICAgICAgfCAgMzkgKysrKysrKwo3 IGZpbGVzIGNoYW5nZWQsIDIzOCBpbnNlcnRpb25zKCspLCAyNSBkZWxldGlvbnMoLSkKCg== --===============1493815644718986496==--