Big IN() clauses etc : feature proposal - Mailing list pgsql-hackers

>>> The moral of the story is that you're probably better off running a
>>> bunch of small selects than in trying to optimize things with one
>>> gargantuan select.
>
>> Ever experiment with loading the parameters into a temp table and
>> joining to that?
>
> Also, it might be worth re-testing that conclusion with PG CVS tip
> (or 8.2 when it comes out).  The reimplementation of IN as = ANY that
> I did a couple months ago might well change the results.

    Long mail, but I think it's interesting...

    I think this is a generic problem, which is often encountered : selecting
a bunch of records based on a list of primary keys (or other indexed,
unique field) ; said list being anything from very short to quite large.
    Here are a few occurences of this need :

    1- The application supplies a list of id's (the case of the OP of this
thread)
    2- A query Q1 yields a list of selected objects , that we wish to use in
several subsequent queries.
    And Q1 is a query we don't wish to do several times, either because it's
slow, complicated (advanced search, for instance), or it acts on a
constantly moving dataset, so the results would be different each time. So
we store the result of Q1 in the application, or in a temp table, or in an
array in a plpgsql variable, whatever, to reuse them.

    Then, for each of these objects, often we will make more queries to
resolve foreign keys (get category name, owner name, from categories and
users tables, etc).

    I have encountered both cases quite often, and they both pose a few
problems. I think it would be a good opportunity for a new feature (see
below).
    A typical use case for point 2 :

    Consider an "objects" table. Each object ...
    - is related to one or several rows from the "categories" table via an
"objects_categories" link table.
    - has an owner_id referencing the "users" table

    I do an "advanced search" query on "objects", which returns a list of
objects. I can join directly to "users" to get the owner's name, but
joining to "categories" is already problematic because of the many-to-many
relationship.

    I wish to do this : fetch all objects matching the search criteria ;
fetch the owner users ; fetch the categories ; build in my application
object space a clean and straightforward data representation for all this.

    Also :
    - I do not wish to complicate the search query.
    - The row estimates for the search query results are likely to be "not so
good" (because it's a complex query) ; so the joins to users and
categories are likely to use suboptimal plans based on "not so good"
estimates.
    - The rows from "objects" are large ; so moving them around through a lot
of small joins hurts performance.

    The obvious solution is this :

BEGIN;
CREATE TEMPORARY TABLE results ON COMMIT DROP AS SELECT * FROM advanced
search query;
ANALYZE results;

-- get the results to the application
SELECT * FROM results;

-- get object owners info
SELECT * FROM users WHERE id IN (SELECT user_id FROM results);

-- get category info
SELECT * FROM categories WHERE id IN (SELECT category_id FROM
objects_to_categories WHERE object_id IN (SELECT id FROM results));

-- get object/category relations (the ORM will use this to link objects in
the application)
SELECT * FROM objects_to_categories WHERE object_id IN (SELECT id FROM
results);
COMMIT;

    You might wonder why I do it this way on the "categories" table.
    This is because I use an Object-Relational mapper which will instantiate
a User or Category class object for each row I fetch from these tables. I
do not want to fetch just the username, using a simple join, but I want
the full object, because :
    - I want to instantiate these objects (they have useful methods to
process rights etc)
    - I do not want to mix columns from "objects" and "users"

    And I do not wish to instantiate each category more than once. This would
waste memory, but more importantly, it is a lot cleaner to have only one
instance per row, because my ORM then translates the foreign key relations
into object relations (pointers). Each instanciated category will contain
a list of Object instances ; each Object instance will contain a list of
the categories it belongs to, and point to its owner user.

    Back to the point : I can't use the temp table method, because temp
tables are too slow.
    Creating a temp table, filling it, analyzing it and then dropping it
takes about 100 ms. The search query, on average, takes 10 ms.

    So I have to move this logic to the application, or to plpgsql, and jump
through hoops and use big IN() clauses ; which has the following drawbacks
:
    - slow
    - ugly
    - very hard for the ORM to auto-generate

*******************************

    Feature proposal :

    A way to store query results in a named buffer and reuse them in the next
queries.
    This should be as fast as possible, store results in RAM if possible, and
be limited to inside a transaction.

    Ways to store results like this already exist in various flavours inside
the postgres engine :
    - Cursors (WITH SCROLL)
    - Arrays (realistically, limited to a list of ids)
    - Executor nodes : Materialize, Hash, Sort, etc

    The simpler to mutate would probably be the cursor.
    Therefore I propose to add the capability to use a CURSOR like a
temporary table, join it to other tables, etc.
    This would be implemented by making FETCH behave just like SELECT and be
usable in subqueries (see example below).

    FETCH can return rows to the application. Why can't it return rows to
postgres itself without using plpgsql tricks ?

    Cursors are already extremely fast.
    If the cursor is declared WITH SCROLL, the result-set is buffered.
Therefore, the rowcount can be computed exactly, and a good plan can be
chosen.
    The important columns could even be ANALYZEd if needed...

    Example :

BEGIN;
DECLARE results SCROLL CURSOR WITHOUT HOLD FOR SELECT * FROM advanced
search query;

-- get the results to the application
FETCH ALL FROM results;

-- get object owners info
MOVE FIRST IN results;
SELECT * FROM users WHERE id IN (FETCH ALL user_id FROM results);

-- buffer object/category relations
MOVE FIRST IN results;
DECLARE cats SCROLL CURSOR WITHOUT HOLD FOR SELECT * FROM
objects_to_categories WHERE object_id IN (FETCH ALL id FROM results);

-- get category info
SELECT * FROM categories WHERE id IN (FETCH ALL category_id FROM cats);

-- get object/category relations
MOVE FIRST IN cats;
FETCH ALL FROM cats;

COMMIT;

    I really like this. It's clean, efficient, and easy to use.

    This would be a lot faster than using temp tables.
    Creating cursors is very fast so we can create two, and avoid doing twice
the same work (ie. hashing the ids from the results to grab categories
only once).

*******************************

    Goodies (utopian derivatives from this feature).

    - Deferred Planning, and on-the-spot function estimates.

    There are no rowcount estimates for set returning functions in postgres.
This is a problem, when postgres thinks the function will return 1000
rows, whereas in reality, it returns 5 rows or 10K rows. Suboptimal plans
are chosen.

SELECT * FROM objects WHERE id IN (SELECT * FROM function( params ));

    This hairy problem can be solved easily with the proposed feature :

DECLARE my_set CURSOR WITHOUT HOLD FOR SELECT * FROM function( params );

    Here, the result set for the function is materialized. Therefore, the
rowcount is known, and the following query can be executed with a very
good plan :

SELECT * FROM objects WHERE id IN (FETCH ALL FROM my_set);

    It will likely be Hash + Nested loop index scan for very few rows, maybe
merge joins for a lot of rows, etc. In both cases the result set from
function() needs to be hashed or sorted, which means buffered in memory or
disk ; the overhead of buffering it in the cursor would have been incurred
anyway, so there is no resource waste.

    Likewise, a hard-to-estimate subquery which breaks the planning of the
outer SELECT could be embedded in a cursor and buffered.

    In a distant future, the planner could chose to automatically do this,
effectively implementing deferred planning.


    Thoughts ?