Subject: Problem with Postgres finding intersection of lists

From: Dale Arntson <[email-masked]>
Date: Mon, 7 Feb 1994 12:56:41 -0600

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
[email-masked]      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.

---

From: [email-masked] (Paul M. Aoki)
Date: Mon, 07 Feb 1994 14:36:55 -0800

> i3.wd = "mathematica" and

i executed this as-is and it blows out the query optimizer (it runs
out of memory -- it uses a variant of the exponential-complexity 
optimization algorithm from IBM's System R and, because it was
originally written in lisp, leaks memory like a sieve).

on a wild guess, i then re-ran it on our development system using 
chained join clauses, i.e.,

i1.rn = i2.rn and
i2.rn = i3.rn and
i3.rn = i4.rn and
i4.rn = i5.rn and
c.rn = i1.rn

and the query completed relatively quickly.  (i also made your keyword 
table bigger and threw an index over the columns so that the cost-based
optimizer would be *sure* to use the index.. scans of base tables are
*very* slow.  where they can be used, indices are always always always 
a good idea.)

the optimizer is not super-smart and doesn't compute all of the possible
join clauses it could invent based on the closure of these clauses 
(i1=i2,i1=i3...i3=i4,i3=i5,...).  writing the query this way basically
forces a particular join order, which is ok in this particular case 
because they're all on the same table anyway.  but the original query 
has too many join order possibilities for the optimizer to handle.. it 
got to 140MB on our alpha server before dying..
--
  Paul M. Aoki  |  CS Div., Dept. of EECS, UCB  |  [email-masked]
                |  Berkeley, CA 94720           |  ...!uunet!ucbvax!aoki