Return-Path: owner-postman Received: from localhost (localhost [127.0.0.1]) by nobozo.CS.Berkeley.EDU (8.6.4/8.6.3) with SMTP id KAA10431 for postgres-dist; Mon, 7 Feb 1994 10:54:43 -0800 Resent-From: POSTGRES mailing list Resent-Message-Id: <199402071854.KAA10431@nobozo.CS.Berkeley.EDU> X-Authentication-Warning: nobozo.CS.Berkeley.EDU: Host localhost didn't use HELO protocol Sender: owner-postman@postgres.Berkeley.EDU X-Return-Path: owner-postman Received: from hush.lib.uchicago.edu (dale@hush.lib.uchicago.edu [128.135.53.4]) by nobozo.CS.Berkeley.EDU (8.6.4/8.6.3) with ESMTP id KAA10422 for ; Mon, 7 Feb 1994 10:54:41 -0800 Received: from localhost (dale@localhost) by hush.lib.uchicago.edu (8.6.4/8.6.4) id MAA28137 for postgres@nobozo.CS.Berkeley.EDU; Mon, 7 Feb 1994 12:56:41 -0600 Date: Mon, 7 Feb 1994 12:56:41 -0600 From: Dale Arntson Message-Id: <199402071856.MAA28137@hush.lib.uchicago.edu> To: postgres@postgres.Berkeley.EDU Subject: Problem with Postgres finding intersection of lists Resent-To: postgres-dist@postgres.Berkeley.EDU Resent-Date: Mon, 07 Feb 94 10:54:43 -0800 Resent-XMts: smtp Hello Postgres users! I'm trying to build a bibliographic retrieval system for a library reserve department using Postgres 4.1 on a Sparcstation 2. I am using your standard inverted list to provide access points to these bibliographic records. The problem is that Postgres does not seem to be able find the intersection of the lists generated from a query on the inversion table when the words that are queried reach even a trivial number. To illustrate the problem I have constructed a sample database that contains a table of just two citations and a table that inverts their text (see below). The execution time of queries submitted against these tables increases more than geometrically with every word added to the query. Here is a sample query and the execution times of similar queries using varying numbers of words. retrieve unique (c.txt) from c in cite, i1 in invert, i2 in invert, i3 in invert, i4 in invert, i5 in invert where i1.wd = "russell" and i2.wd = "principia" and i3.wd = "mathematica" and i4.wd = "cambridge" and i5.wd = "press" and i1.rn = i2.rn and i1.rn = i3.rn and i1.rn = i4.rn and i1.rn = i5.rn and c.rn = i1.rn No. of Words Execution time ------------------------------ 2 words 3 secs. 3 words 4.5 secs. 4 words 9 secs. 5 words 60 secs. 6 words (quit monitoring after 20 mins.) Indexing the relevant columns only increases the execution time. Also, I have more than the recommended resources allocated for memory. I am I doing something wrong here or is there a problem with Postgres? Any and all help will be appreciated. - dale ____________________________________________________________ Dale Arntson University of Chicago 312-702-8463 1100 E. 57th St. Rm. 210 dale@stax.lib.uchicago.edu Chicago, IL 60637 ____________________________________________________________ P.S. Enclosed below for completeness is a listing of the sample tables. * retrieve (invert.all)\g Query sent to backend is "retrieve (invert.all)" ----------------------------- | rn | wd | ----------------------------- | 101 | 101 | ----------------------------- | 101 | russell | ----------------------------- | 101 | whitehead | ----------------------------- | 101 | alfred | ----------------------------- | 101 | north | ----------------------------- | 101 | bertrand | ----------------------------- | 101 | principia | ----------------------------- | 101 | mathematica | ----------------------------- | 101 | cambridge | ----------------------------- | 101 | university | ----------------------------- | 101 | of | ----------------------------- | 101 | cambridge | ----------------------------- | 101 | press | ----------------------------- | 101 | 1950 | ----------------------------- | 102 | 102 | ----------------------------- | 102 | faulkner | ----------------------------- | 102 | william | ----------------------------- | 102 | go | ----------------------------- | 102 | down | ----------------------------- | 102 | moses | ----------------------------- | 102 | new | ----------------------------- | 102 | york | ----------------------------- | 102 | vintage | ----------------------------- | 102 | press | ----------------------------- | 102 | 1950 | ----------------------------- Go * retrieve (cite.all)\g Query sent to backend is "retrieve (cite.all)" ----------------------------- | rn | txt | ----------------------------- | 101 | Russell, Bertrand & Alfred North Whitehead, Principia Mathematica, University of Cambridge Press, 1950| ----------------------------- | 102 | Faulkner, William, Go Down Moses, New York, Vintage Press, 1950| ----------------------------- Go * \q I live to serve you.