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 EBC23D1B1B8 for ; Thu, 24 Jun 2004 18:43:30 -0300 (ADT) 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 22303-08 for ; Thu, 24 Jun 2004 21:43:24 +0000 (GMT) Received: from news.hub.org (news.hub.org [200.46.204.72]) by svr1.postgresql.org (Postfix) with ESMTP id 2AC32D1B196 for ; Thu, 24 Jun 2004 18:43:21 -0300 (ADT) Received: from news.hub.org (news.hub.org [200.46.204.72]) by news.hub.org (8.12.9/8.12.9) with ESMTP id i5OLhLQC097201 for ; Thu, 24 Jun 2004 21:43:21 GMT (envelope-from news@news.hub.org) Received: (from news@localhost) by news.hub.org (8.12.9/8.12.9/Submit) id i5OLOtHR092741 for pgsql-performance@postgresql.org; Thu, 24 Jun 2004 21:24:55 GMT From: "Mischa Sandberg" X-Newsgroups: comp.databases.postgresql.performance Subject: Range query optimization Lines: 27 X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2800.1106 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106 Message-ID: Date: Thu, 24 Jun 2004 21:24:58 GMT To: pgsql-performance@postgresql.org X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.8 tagged_above=0.0 required=5.0 tests=PRIORITY_NO_NAME X-Spam-Level: X-Archive-Number: 200406/313 X-Sequence-Number: 7371 I'm trying to make a (qua-technical, qua-business) case for switching from MS SQL, and one of the types of query that really doesn't sit well with MS SQL2K is: -- All fields integers or equivalent. -- Table T(k, x: nonkey fields...) -- Table U(k, a, z: m) -- for each value of (k) a set of non-intersecting ranges [a,z) that map to (m) values. select T.*, U.m from T join U on T.k=U.k and T.x >= U.a and T.x < U.z Typically there are are about 1000-2000 U rows per value of (k), about 100K values of (k) and about 50M values of T. By itself, this type of query grinds the CPU to dust. A clustered index on fields of U (take your pick) barely halves the problem of the loop through 1000-2000 rows of U for each row of T. Hash join likewise. The current workaround is a 'manual' radix index on top of the range table, but it's something of a hack. Would the geometric of extensions handle such queries efficiently? I'm not familiar with applying R-trees to linear range problems. ---- "Dreams come true, not free." -- S.Sondheim