Thread: Index condition in a Nested Loop

Index condition in a Nested Loop

From
Mark Hills
Date:
I found in a production system that mostly the performance is being
crippled by the handling of one particular case.

I hope I've reduced this to a minimal example, below.

Summary: when more than one key is given (or the data is sourced from a
table) the planner is forced to a join of the whole data set.

The query aggregates a small amount of the data in a large data set. It
looks like lookups via a Nested Loop would be considerably quicker. I did
this explicitly in the UNION query.

What is that prevents the index condition from being used in earlier parts
of the query? Only where a single condition is present is it be used below
the final join.

Is it that a Nested Loop cannot make several independent lookups via an
index?

Is my input preventing the planner doing this, or would it need to be
smarter about something?

It seems interesting that it is able to do this successfully in the third
plan: "As above but without the join to the job table".

Thanks

--
Mark


--
-- Create schema:  job -E task -E resource
--

CREATE TABLE job (
    jid integer PRIMARY KEY
);

CREATE TABLE task (
    jid integer REFERENCES job (jid),
    tid integer PRIMARY KEY
);

CREATE TABLE resource (
    tid integer REFERENCES task (tid),
    name text
);

CREATE INDEX idx_task ON task (jid, tid);
CREATE INDEX idx_resource_tid ON resource (tid, name);
CREATE INDEX idx_resource_name ON resource (name, tid);

--
-- Populate with data:
--     10000 jobs,
--     1000 tasks per job,
--     0-4 resources per task
--

CREATE OR REPLACE FUNCTION
populate()
RETURNS VOID
AS $$
DECLARE
    t integer;
BEGIN
    FOR t IN 0..10000 LOOP
        INSERT INTO job VALUES (t);
    END LOOP;

    FOR t IN 0..10000000 LOOP
        INSERT INTO task VALUES (random() * 10000, t);

        IF random() > 0.1 THEN
            INSERT INTO resource VALUES (t, 'wallace');
            INSERT INTO resource VALUES (t, 'gromit');
        END IF;

        IF random() > 0.9 THEN
            INSERT INTO resource VALUES (t, 'shaun');
        END IF;

        IF random() > 0.6 THEN
            INSERT INTO resource VALUES (t, 'wendolene');
        END IF;
    END LOOP;
END
$$ LANGUAGE plpgsql;

SELECT populate();
VACUUM ANALYZE;

-- Define some simple aggregation with a left join

CREATE VIEW middle AS
    SELECT task.jid,
        task.tid,
        COUNT(resource.name) AS nresource
    FROM task
        LEFT JOIN resource ON task.tid = resource.tid
    GROUP BY task.jid,
        task.tid;

-- Aggregate again for a single key: fast
-- "Nested Loop" is used

SELECT job.jid,
    sum(nresource)
FROM job
    INNER JOIN middle ON job.jid = middle.jid
WHERE job.jid IN (1234)
GROUP BY job.jid;

--  GroupAggregate  (cost=0.00..35026.04 rows=1 width=12)
--    ->  Nested Loop  (cost=0.00..35021.13 rows=980 width=12)
--          ->  Index Only Scan using job_pkey on job  (cost=0.00..4.28 rows=1 width=4)
--                Index Cond: (jid = 1234)
--          ->  GroupAggregate  (cost=0.00..34997.25 rows=980 width=15)
--                ->  Nested Loop Left Join  (cost=0.00..34970.55 rows=2254 width=15)
--                      ->  Index Only Scan using idx_task on task  (cost=0.00..55.98 rows=980 width=8)
--                            Index Cond: (jid = 1234)
--                      ->  Index Only Scan using idx_resource_tid on resource  (cost=0.00..35.54 rows=7 width=11)
--                            Index Cond: (tid = task.tid)
-- (10 rows)

-- As above, but with two keys: slow
-- "Merge Join" is attempted; this is the 'bad' case

EXPLAIN
SELECT job.jid,
    sum(nresource)
FROM job
    INNER JOIN middle ON job.jid = middle.jid
WHERE job.jid IN (1234, 5678)
GROUP BY job.jid;

--  GroupAggregate  (cost=5636130.95..6091189.12 rows=2 width=12)
--    ->  Merge Join  (cost=5636130.95..6091179.10 rows=2000 width=12)
--          Merge Cond: (task.jid = job.jid)
--          ->  GroupAggregate  (cost=5636130.95..5966140.73 rows=9999986 width=15)
--                ->  Sort  (cost=5636130.95..5693633.43 rows=23000992 width=15)
--                      Sort Key: task.jid, task.tid
--                      ->  Merge Left Join  (cost=0.00..1251322.49 rows=23000992 width=15)
--                            Merge Cond: (task.tid = resource.tid)
--                            ->  Index Scan using task_pkey on task  (cost=0.00..281847.80 rows=9999986 width=8)
--                            ->  Index Only Scan using idx_resource_tid on resource  (cost=0.00..656962.32
rows=23000992width=11) 
--          ->  Materialize  (cost=0.00..8.55 rows=2 width=4)
--                ->  Index Only Scan using job_pkey on job  (cost=0.00..8.54 rows=2 width=4)
--                      Index Cond: (jid = ANY ('{1234,5678}'::integer[]))
-- (13 rows)

-- As above but without the join to the job table: fast

SELECT jid,
    sum(nresource)
FROM middle
WHERE jid IN (1234, 5678)
GROUP BY jid;

--  GroupAggregate  (cost=0.00..69995.03 rows=200 width=12)
--    ->  GroupAggregate  (cost=0.00..69963.62 rows=1961 width=15)
--          ->  Nested Loop Left Join  (cost=0.00..69910.18 rows=4511 width=15)
--                ->  Index Only Scan using idx_task on task  (cost=0.00..93.39 rows=1961 width=8)
--                      Index Cond: (jid = ANY ('{1234,5678}'::integer[]))
--                ->  Index Only Scan using idx_resource_tid on resource  (cost=0.00..35.52 rows=7 width=11)
--                      Index Cond: (tid = task.tid)
-- (7 rows)

-- Kludge to lookup two keys: fast (cost 70052)

    SELECT job.jid,
        sum(nresource)
    FROM job
        INNER JOIN middle ON job.jid = middle.jid
    WHERE job.jid IN (1234)
    GROUP BY job.jid
UNION
    SELECT job.jid,
        sum(nresource)
    FROM job
        INNER JOIN middle ON job.jid = middle.jid
    WHERE job.jid IN (5678)
    GROUP BY job.jid;

--
-- Repeat with job keys from a table instead of 'IN' clause.
--

CREATE TABLE one_job (
    jid integer PRIMARY KEY
);

CREATE TABLE two_jobs (
    jid integer PRIMARY KEY
);

INSERT INTO one_job VALUES (1234);
INSERT INTO two_jobs VALUES (1234), (5678);

ANALYZE one_job;
ANALYZE two_jobs;

-- Joining against one row: slow (cost 5636131.97..6092141.59)
-- "Merge Join" is attempted

EXPLAIN
SELECT job.jid,
    sum(nresource)
FROM one_job job
    INNER JOIN middle ON job.jid = middle.jid
GROUP BY job.jid;

-- Joining against two rows: slow (cost 5636131.98..6093141.60)
-- "Merge Join" is attempted

EXPLAIN
SELECT job.jid,
    sum(nresource)
FROM two_jobs job
    INNER JOIN middle ON job.jid = middle.jid
GROUP BY job.jid;


Re: Index condition in a Nested Loop

From
Tom Lane
Date:
Mark Hills <mark@pogo.org.uk> writes:
> What is that prevents the index condition from being used in earlier parts
> of the query? Only where a single condition is present is it be used below
> the final join.

"WHERE job.jid IN (1234)" is simplified to "WHERE job.jid = 1234", and
that in combination with "JOIN ON job.jid = middle.jid" allows deduction
of "middle.jid = 1234" a/k/a "task.jid = 1234", leading to the
recognition that only one row from "task" is needed.  There is no such
transitive propagation of general IN clauses.  The problem with your
slower queries is not that they're using merge joins, it's that there's
no scan-level restriction on the task table so that whole table has to
be scanned.

Another thing that's biting you is that the GROUP BY in the view acts as
a partial optimization fence: there's only a limited amount of stuff
that can get pushed down through that.  You might consider rewriting the
view to avoid that, along the lines of

create view middle2 as
  SELECT task.jid, task.tid,
    (select count(resource.name) from resource where task.tid = resource.tid) AS nresource
  FROM task;

This is not perfect: this formulation forces the system into essentially
a nestloop join between task and resource.  In cases where you actually
want results for a lot of task rows, that's going to lose badly.  But in
the examples you're showing here, it's going to work better.

            regards, tom lane

Re: Index condition in a Nested Loop

From
Mark Hills
Date:
On Sun, 26 Feb 2012, Tom Lane wrote:

> Mark Hills <mark@pogo.org.uk> writes:
> > What is that prevents the index condition from being used in earlier parts
> > of the query? Only where a single condition is present is it be used below
> > the final join.
>
> "WHERE job.jid IN (1234)" is simplified to "WHERE job.jid = 1234", and
> that in combination with "JOIN ON job.jid = middle.jid" allows deduction
> of "middle.jid = 1234" a/k/a "task.jid = 1234", leading to the
> recognition that only one row from "task" is needed.  There is no such
> transitive propagation of general IN clauses.  The problem with your
> slower queries is not that they're using merge joins, it's that there's
> no scan-level restriction on the task table so that whole table has to
> be scanned.
>
> Another thing that's biting you is that the GROUP BY in the view acts as
> a partial optimization fence: there's only a limited amount of stuff
> that can get pushed down through that.  You might consider rewriting the
> view to avoid that, along the lines of
>
> create view middle2 as
>   SELECT task.jid, task.tid,
>     (select count(resource.name) from resource where task.tid = resource.tid) AS nresource
>   FROM task;
>
> This is not perfect: this formulation forces the system into essentially
> a nestloop join between task and resource.  In cases where you actually
> want results for a lot of task rows, that's going to lose badly.  But in
> the examples you're showing here, it's going to work better.

Thanks for this. Indeed it does work better, and it's exactly the method I
was hoping the planner could use to execute the query.

I modified the report on the previous week's data, and it now runs 6x
faster (in a database containing approx. 2 years of data). There are
several similar reports. Some queries work on only a hanful of jobs and
this change ensures they are instant.

I hadn't realised that sub-queries restrict the planner so much. Although
at some point I've picked up a habit of avoiding them, presumably for this
reason.

If you have time to explain, I'd be interested in a suggestion for any
change to the planner that could make a small contribution towards
improving this. eg. a small project that could get me into the planner
code.

Many thanks for your help,

--
Mark

Re: Index condition in a Nested Loop

From
Tom Lane
Date:
Mark Hills <mark@pogo.org.uk> writes:
> I hadn't realised that sub-queries restrict the planner so much. Although
> at some point I've picked up a habit of avoiding them, presumably for this
> reason.

> If you have time to explain, I'd be interested in a suggestion for any
> change to the planner that could make a small contribution towards
> improving this. eg. a small project that could get me into the planner
> code.

Well, if it were easy to do, we'd probably have done it already ...

Plain subqueries might perhaps be turned into joins (with special join
types no doubt), but I'm not sure what we'd do about subqueries with
grouping or aggregation, as your examples had.  There was some talk a
month or three back about allowing such subqueries to have parameterized
paths a la the recently-added parameterized path mechanism, but it
didn't get further than idle speculation.

            regards, tom lane