Received: from maia.hub.org (maia-3.hub.org [200.46.204.243]) by mail.postgresql.org (Postfix) with ESMTP id 0E73CB61FE5 for ; Wed, 1 Jun 2011 17:31:44 -0300 (ADT) Received: from mail.postgresql.org ([200.46.204.86]) by maia.hub.org (mx1.hub.org [200.46.204.243]) (amavisd-maia, port 10024) with ESMTP id 40089-05-2 for ; Wed, 1 Jun 2011 20:31:36 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-pz0-f46.google.com (mail-pz0-f46.google.com [209.85.210.46]) by mail.postgresql.org (Postfix) with ESMTP id 856B3B61FDD for ; Wed, 1 Jun 2011 17:31:36 -0300 (ADT) Received: by pzk9 with SMTP id 9so79727pzk.19 for ; Wed, 01 Jun 2011 13:31:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=AjpQdlDUC7QZ6kU+BUn8K3m8/sYdvlFu+bXg0GpHujM=; b=HWLl2dfRlzS1hXnz94ymWtzErGrwLSlK+uCXDcr5Ra1VcSxvXzMNHtN3SU62mDHuGI UgfrCK1Y/EHpknQZ8HwvLUSLC5qjdErXdGMlwkKwL+CifefZgos6Waji9VAe6fTwDRuN kPspRMloJXDUd0aBDnXKP2CzxhwudKCzlDuBA= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; b=ilYiFFJa2bnCEl5S7OTAKuaAMFacSmQqZskgJgRM8N6Z2YrVrzuRSyAYYbhUgq92oL kCd9qkDtlEVwYBlhxqIuvWbi4QCVxaM3+8vXpjN/Q2T2zEEeEt6gNWCxE9bdu7fcktVj wfq05rjZ5OdrZDUp+3VnPG/CU3uhwySGRpLlA= MIME-Version: 1.0 Received: by 10.68.34.72 with SMTP id x8mr3039979pbi.312.1306960294828; Wed, 01 Jun 2011 13:31:34 -0700 (PDT) Received: by 10.68.56.70 with HTTP; Wed, 1 Jun 2011 13:31:34 -0700 (PDT) In-Reply-To: <24247.1306959956@sss.pgh.pa.us> References: <1306210464806-4420974.post@n5.nabble.com> <4DDB47BC.8030504@postnewspapers.com.au> <1306247697267-4422247.post@n5.nabble.com> <4DDC6109.7060708@postnewspapers.com.au> <1306341749094-4425890.post@n5.nabble.com> <4DDDBD96.4010809@postnewspapers.com.au> <1306413217406-4428435.post@n5.nabble.com> <7913.1306900062@sss.pgh.pa.us> <24247.1306959956@sss.pgh.pa.us> Date: Wed, 1 Jun 2011 16:31:34 -0400 Message-ID: Subject: Re: [PERFORM] Hash Anti Join performance degradation From: Robert Haas To: Tom Lane Cc: =?ISO-8859-1?Q?C=E9dric_Villemain?= , panam , PostgreSQL-development Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=-1.898 tagged_above=-5 required=5 tests=BAYES_00=-1.9, FREEMAIL_FROM=0.001, RFC_ABUSE_POST=0.001 X-Spam-Level: X-Archive-Number: 201106/52 X-Sequence-Number: 188765 On Wed, Jun 1, 2011 at 4:25 PM, Tom Lane wrote: > Because of the way that a bitmap heap scan works, the rows are > guaranteed to be loaded into the hash table in physical order, which > means (in the fast case) that the row with the largest "id" value gets > loaded last. =A0And because ExecHashTableInsert pushes each row onto the > front of its hash chain, that row ends up at the front of the hash > chain. =A0Net result: for all the outer rows that aren't the one with > maximum id, we get a joinqual match at the very first entry in the hash > chain. =A0Since it's an antijoin, we then reject that outer row and go > on to the next. =A0The join thus ends up costing us only O(N) time. Ah! Make sense. If I'm reading your explanation right, this means that we could have hit a similar pathological case on a nestloop as well, just with a data ordering that is the reverse of what we have here? --=20 Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company