X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (unknown [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id 7C84E534BC for ; Wed, 6 Apr 2005 19:35:59 +0100 (BST) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 52558-06 for ; Wed, 6 Apr 2005 18:35:54 +0000 (GMT) Received: from priv-edtnes27.telusplanet.net (outbound04.telus.net [199.185.220.223]) by svr1.postgresql.org (Postfix) with ESMTP id 1CF5153498 for ; Wed, 6 Apr 2005 19:35:53 +0100 (BST) Received: from localhost ([199.185.220.240]) by priv-edtnes27.telusplanet.net (InterMail vM.6.01.04.00 201-2131-118-20041027) with ESMTP id <20050406183553.LSIR6807.priv-edtnes27.telusplanet.net@localhost>; Wed, 6 Apr 2005 12:35:53 -0600 Received: from 209.17.183.249 ( [209.17.183.249]) as user a3a18850@204.209.205.53 by webmail.telus.net with HTTP; Wed, 6 Apr 2005 11:35:53 -0700 Message-ID: <1112812553.42542c091d8ce@webmail.telus.net> Date: Wed, 6 Apr 2005 11:35:53 -0700 From: Mischa To: Arjen van der Meijden Cc: performance pgsql Subject: Re: Plan for relatively simple query seems to be very inefficient References: <425413D3.5030304@vulcanus.its.tudelft.nl> In-Reply-To: <425413D3.5030304@vulcanus.its.tudelft.nl> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: Internet Messaging Program (IMP) 3.1-cvs X-Originating-IP: 209.17.183.249 X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=1.082 tagged_above=0 required=5 tests=AWL, DNS_FROM_RFC_POST, FORGED_RCVD_HELO X-Spam-Level: * X-Archive-Number: 200504/116 X-Sequence-Number: 11513 Quoting Arjen van der Meijden : > Hi list, > > I noticed on a forum a query taking a surprisingly large amount of time > in MySQL. Of course I wanted to prove PostgreSQL 8.0.1 could do it much > better. To my surprise PostgreSQL was ten times worse on the same > machine! And I don't understand why. > > I don't really need this query to be fast since I don't use it, but the > range-thing is not really an uncommon query I suppose. So I'm wondering > why it is so slow and this may point to a wrong plan being chosen or > generated. > > Here are table definitions: > > Table "public.postcodes" > Column | Type | Modifiers > -------------+---------------+----------- > postcode_id | smallint | not null > range_from | smallint | > range_till | smallint | > Indexes: > "postcodes_pkey" PRIMARY KEY, btree (postcode_id) > "range" UNIQUE, btree (range_from, range_till) > > Table "public.data_main" > Column | Type | Modifiers > --------+----------+----------- > userid | integer | not null > range | smallint | > Indexes: > "data_main_pkey" PRIMARY KEY, btree (userid) > > And here's the query I ran: > > SELECT COUNT(*) FROM > data_main AS dm, > postcodes AS p > WHERE dm.range BETWEEN p.range_from AND p.range_till I just posted an answer to this (via webcafe webmail; can't recall which pg-list), that might interest you. BTree indexes as they stand (multi-column, ...) answer what most people need for queries. Unfortunately, out-of-the-box, they have no good way of handling range queries. To compensate, you can use a small amount of kinky SQL. This is in the same line as the tricks used to implement hierarchic queries in relational SQL. [1] Create a table "widths"(wid int) of powers of 2, up to what will just cover max(range_till-range_from). Since your "range" column is a smallint, this table can have no more than 15 rows. You can get as fussy as you want about keeping this table to a minimum. [2] Change postcodes: ALTER TABLE postcodes ADD wid INT USING 2 ^ CEIL(LOG(range_from - range_till,2)); ALTER TABLE postcodes ADD start INT USING range_from - (range_from % wid); CREATE INDEX postcodes_wid_start_index ON (wid, start); ANALYZE postcodes; [4] Write your query as: SELECT COUNT(*) FROM data_main AS dm CROSS JOIN widths -- yes, CROSS JOIN. For once, it HELPS performance. JOIN postcodes AS p ON dm.wid = widths.wid AND dm.start = p.range - p.range % widths.wid WHERE dm.range BETWEEN p.range_from AND p.range_till This uses BTREE exact-match to make a tight restriction on which rows to check. YMMV, but this has worked even for multi-M table joins. -- "Dreams come true, not free."