X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (neptune.hub.org [200.46.204.2]) by svr1.postgresql.org (Postfix) with ESMTP id 5E617D1B8C8 for ; Tue, 30 Dec 2003 16:33:38 +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 21075-05 for ; Tue, 30 Dec 2003 12:32:48 -0400 (AST) Received: from mail4.speakeasy.net (mail4.speakeasy.net [216.254.0.204]) by svr1.postgresql.org (Postfix) with ESMTP id 7AA26D1B468 for ; Tue, 30 Dec 2003 12:32:47 -0400 (AST) Received: (qmail 25116 invoked from network); 30 Dec 2003 16:32:46 -0000 Received: from atlas.jonathangardner.net (HELO jonathangardner.net) (jgardn@[66.92.192.166]) (envelope-sender ) by mail4.speakeasy.net (qmail-ldap-1.03) with RC4-MD5 encrypted SMTP for ; 30 Dec 2003 16:32:46 -0000 From: Jonathan Gardner To: pgsql-performance@postgresql.org Subject: DELETE ... WHERE ctid IN (...) vs. Iteration Date: Tue, 30 Dec 2003 08:32:38 -0800 User-Agent: KMail/1.5.94 MIME-Version: 1.0 Content-Disposition: inline Content-Type: Text/Plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Message-Id: <200312300832.44945.jgardner@jonathangardner.net> X-Virus-Scanned: by amavisd-new at postgresql.org X-Archive-Number: 200312/314 X-Sequence-Number: 5174 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I guess this may have come up before, but now that 7.4 has the IN with=20 improved performance, it may be time to revisit this topic. Compare these two algorithms (in plpgsql): (a) DELETE FROM foo WHERE ctid IN ( SELECT foo.ctid FROM ... WHERE ... ); (b) FOR result IN SELECT foo.ctid FROM ... WHERE ... LOOP DELETE FROM foo WHERE ctid =3D result; END LOOP; My poor understanding of how the IN operator works leaves me to believe=20 that for a large set of data in the IN group, a hash is used and a=20 tablescan done on foo. However, for a small set of data in the IN group,= =20 no tablescan is performed. I assume that (a) works at O(ln(N)) for large N, and O(N) for small N,=20 while (b) works at O(N) universally. Therefore, (a) is the superior=20 algorithm. I welcome criticism and correction. - --=20 Jonathan Gardner jgardner@jonathangardner.net Live Free, Use Linux! -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.2 (GNU/Linux) iD8DBQE/8aipWgwF3QvpWNwRAk8GAJoDWISjxG7LMB1FdCFmwlOafsmZTwCePx18 lyHLNBJ8nP0RHzv6WfRzQ+M=3D =3DFPdW -----END PGP SIGNATURE-----