Thread: Puzzling table scan in a CTE

Puzzling table scan in a CTE

From
Date:

Good day,

 

I have a recursive CTE where a table scan occurs, even though there doesn't seem to be a good reason for it.

It seems the planner came to the conclusion that columns that are not actually used in the output, joins or a where clause are a part of the output.

It's not a performance problem now and the query runs quickly (which is why I haven't posted it on the performance mailing list). What bothers me is that the scan seems to be there without being really necessary and I would like to avoid any extra I/O. I would expect the plan to be close the simplified query without CTE posted after the CTE query below.

I'm also worried that this could get worse over time and that it might influence the query's performance.

 

The question:

Am I missing something and the table scan is necessary?

If not, is there a way to avoid it?

 

This is the query:

WITH RECURSIVE user_subordinates 

AS 

(

SELECT

ur1."id" AS var_id,

ur1.id_user_parent AS var_id_user_parent,

ur1.login AS var_login,

ur1_1.login AS var_login_parent,

1::smallint AS var_sort_order

FROM

"user" ur1

JOIN

"user" ur1_1

ON(ur1.id_user_parent=ur1_1."id")

WHERE

ur1.id = 3970

AND ur1.disabled=false

UNION ALL

SELECT

ur2."id" AS var_id,

ur2.id_user_parent AS var_id_user_parent,

ur2.login AS var_login,

ups1.var_login AS var_login_parent,

(ups1.var_sort_order + 1)::smallint AS var_sort_order

FROM

user_subordinates ups1

JOIN

"user" ur2

ON( ups1.var_id = ur2.id_user_parent

AND ups1.var_id <> ur2.id

)

)

SELECT

var_id,

var_id_user_parent,

var_login,

var_login_parent,

var_sort_order

FROM

user_subordinates

ORDER BY

var_sort_order,       

var_id,             

var_id_user_parent

;

This is its execution plan:

http://explain.depesz.com/s/4hY

 

This is a simplified version of the query without CTE:

SELECT

ur2."id" AS var_id,

ur2.id_user_parent AS var_id_user_parent,

ur2.login AS var_login,

ups1.var_login AS var_login_parent,

(ups1.var_sort_order + 1)::smallint AS var_sort_order

FROM

(

SELECT

ur1."id" AS var_id,

ur1.id_user_parent AS var_id_user_parent,

ur1.login AS var_login,

ur1_1.login AS var_login_parent,

1::smallint AS var_sort_order

FROM

"user" ur1

JOIN

"user" ur1_1

ON(ur1.id_user_parent=ur1_1."id")

WHERE

ur1.id = 3970

AND ur1.disabled=false

) ups1

JOIN

"user" ur2

ON( ups1.var_id = ur2.id_user_parent

AND ups1.var_id <> ur2.id

)

;

 

Its plan is here:

http://explain.depesz.com/s/Ak3

 

Here's the table's DDL:

CREATE TABLE "user"

(

id bigserial NOT NULL, -- Unique row identifier

id_user_parent bigint NOT NULL DEFAULT 3, -- Identifier of user's parent user

id_address bigint NOT NULL,

login character varying NOT NULL, -- Login name of a user

password character varying NOT NULL, -- Login password of a user

date_created timestamp without time zone NOT NULL DEFAULT now(), -- Date and time at which the record was created

id_user_created bigint NOT NULL, -- Identifier of a user who created the row

date_modified timestamp without time zone, -- Date and time at which the record was modified

id_user_modified bigint, -- Identifier of a user who modified the row

disabled boolean NOT NULL DEFAULT true, -- Its value is set to true when user account is disabled, false when enabled.

activation_hash character varying NOT NULL, -- Activation hash that a hashed string sent to the user matches against during activation.

invoiced boolean NOT NULL DEFAULT false, -- True is user wishes to be invoiced, false otherwise.

CONSTRAINT user_pkey PRIMARY KEY (id),

CONSTRAINT user_id_address_fkey FOREIGN KEY (id_address) REFERENCES address (id),

CONSTRAINT user_id_user_created_fkey FOREIGN KEY (id_user_created) REFERENCES "user" (id),

CONSTRAINT user_id_user_modified_fkey FOREIGN KEY (id_user_modified) REFERENCES "user" (id),

CONSTRAINT u_login UNIQUE (login)

);

CREATE INDEX fki_user_id_address_fkey ON "user" USING btree(id_address);

CREATE INDEX ix__user__id_user_parent ON "user" USING btree(id_user_parent);

CREATE UNIQUE INDEX ix__user__login ON "user" USING btree (lower(login::text) COLLATE pg_catalog."default");

CREATE UNIQUE INDEX ix__user__login__varchar_pattern_ops ON "user" USING btree (lower(login::text) COLLATE pg_catalog."default" varchar_pattern_ops);

 

Environment: Windows 7 Professional x64, PostgreSQL 9.3.1. The table has been analysed before executing the query and getting the explain result. It's on my workstation and nobody else uses the database but me.

 

Any thought on this are appreciated.

 

Thank you.

 

Peter Slapansky

 

Re: Puzzling table scan in a CTE

From
Elliot
Date:
On 2013-11-22 11:54, slapo@centrum.sk wrote:

Good day,

 

I have a recursive CTE where a table scan occurs, even though there doesn't seem to be a good reason for it.

It seems the planner came to the conclusion that columns that are not actually used in the output, joins or a where clause are a part of the output.

It's not a performance problem now and the query runs quickly (which is why I haven't posted it on the performance mailing list). What bothers me is that the scan seems to be there without being really necessary and I would like to avoid any extra I/O. I would expect the plan to be close the simplified query without CTE posted after the CTE query below.

I'm also worried that this could get worse over time and that it might influence the query's performance.

 

The question:

Am I missing something and the table scan is necessary?

If not, is there a way to avoid it?

 

This is the query:

WITH RECURSIVE user_subordinates 

AS 

(

SELECT

ur1."id" AS var_id,

ur1.id_user_parent AS var_id_user_parent,

ur1.login AS var_login,

ur1_1.login AS var_login_parent,

1::smallint AS var_sort_order

FROM

"user" ur1

JOIN

"user" ur1_1

ON(ur1.id_user_parent=ur1_1."id")

WHERE

ur1.id = 3970

AND ur1.disabled=false

UNION ALL

SELECT

ur2."id" AS var_id,

ur2.id_user_parent AS var_id_user_parent,

ur2.login AS var_login,

ups1.var_login AS var_login_parent,

(ups1.var_sort_order + 1)::smallint AS var_sort_order

FROM

user_subordinates ups1

JOIN

"user" ur2

ON( ups1.var_id = ur2.id_user_parent

AND ups1.var_id <> ur2.id

)

)

SELECT

var_id,

var_id_user_parent,

var_login,

var_login_parent,

var_sort_order

FROM

user_subordinates

ORDER BY

var_sort_order,       

var_id,             

var_id_user_parent

;

This is its execution plan:

http://explain.depesz.com/s/4hY

 

This is a simplified version of the query without CTE:

SELECT

ur2."id" AS var_id,

ur2.id_user_parent AS var_id_user_parent,

ur2.login AS var_login,

ups1.var_login AS var_login_parent,

(ups1.var_sort_order + 1)::smallint AS var_sort_order

FROM

(

SELECT

ur1."id" AS var_id,

ur1.id_user_parent AS var_id_user_parent,

ur1.login AS var_login,

ur1_1.login AS var_login_parent,

1::smallint AS var_sort_order

FROM

"user" ur1

JOIN

"user" ur1_1

ON(ur1.id_user_parent=ur1_1."id")

WHERE

ur1.id = 3970

AND ur1.disabled=false

) ups1

JOIN

"user" ur2

ON( ups1.var_id = ur2.id_user_parent

AND ups1.var_id <> ur2.id

)

;

 

Its plan is here:

http://explain.depesz.com/s/Ak3

 

Here's the table's DDL:

CREATE TABLE "user"

(

id bigserial NOT NULL, -- Unique row identifier

id_user_parent bigint NOT NULL DEFAULT 3, -- Identifier of user's parent user

id_address bigint NOT NULL,

login character varying NOT NULL, -- Login name of a user

password character varying NOT NULL, -- Login password of a user

date_created timestamp without time zone NOT NULL DEFAULT now(), -- Date and time at which the record was created

id_user_created bigint NOT NULL, -- Identifier of a user who created the row

date_modified timestamp without time zone, -- Date and time at which the record was modified

id_user_modified bigint, -- Identifier of a user who modified the row

disabled boolean NOT NULL DEFAULT true, -- Its value is set to true when user account is disabled, false when enabled.

activation_hash character varying NOT NULL, -- Activation hash that a hashed string sent to the user matches against during activation.

invoiced boolean NOT NULL DEFAULT false, -- True is user wishes to be invoiced, false otherwise.

CONSTRAINT user_pkey PRIMARY KEY (id),

CONSTRAINT user_id_address_fkey FOREIGN KEY (id_address) REFERENCES address (id),

CONSTRAINT user_id_user_created_fkey FOREIGN KEY (id_user_created) REFERENCES "user" (id),

CONSTRAINT user_id_user_modified_fkey FOREIGN KEY (id_user_modified) REFERENCES "user" (id),

CONSTRAINT u_login UNIQUE (login)

);

CREATE INDEX fki_user_id_address_fkey ON "user" USING btree(id_address);

CREATE INDEX ix__user__id_user_parent ON "user" USING btree(id_user_parent);

CREATE UNIQUE INDEX ix__user__login ON "user" USING btree (lower(login::text) COLLATE pg_catalog."default");

CREATE UNIQUE INDEX ix__user__login__varchar_pattern_ops ON "user" USING btree (lower(login::text) COLLATE pg_catalog."default" varchar_pattern_ops);

 

Environment: Windows 7 Professional x64, PostgreSQL 9.3.1. The table has been analysed before executing the query and getting the explain result. It's on my workstation and nobody else uses the database but me.

 

Any thought on this are appreciated.

 

Thank you.

 

Peter Slapansky

 

You can "set enable_seqscan = off" to see what the planner thinks of using the index on id_user_parent.
Does every user have a parent? Or a child? Those will affect how many matches you'll find, and if it's a lot then it'll be faster doing the table scan.
Also, have you changed any configuration settings? random_page_cost might need some tuning.


Re: [GENERAL] Puzzling table scan in a CTE

From
Date:

Thanks for the suggestion.

I've tried it with seqscan set to off, but there's still a bitmap heap scan going on:

http://explain.depesz.com/s/zIJl

 

I have random_page_cost set to 1.5 at the moment, as the database is on a solid state disk.

 

Every user has a parent, but not every parent has a child.

The number of rows returned by the query is 17 at the moment.

It would be even less for a child tree of other users, usually 0 to 3, and the plan remains the same in those cases.

The table itself has only slightly below 5000 rows right now. It's not a lot, but it seems too many to go for a table scan for just 17 rows.

Could it be that the planner cannot estimate the possible match count because of the CTE?

 

If I remove the recursion, the plan is still nearly the same: http://explain.depesz.com/s/NAu

 

WITH RECURSIVE user_subordinates 

AS 

(

SELECT

ur1."id" AS var_id,

ur1.id_user_parent AS var_id_user_parent,

ur1.login AS var_login,

ur1_1.login AS var_login_parent,

1::smallint AS var_sort_order

FROM

"user" ur1

JOIN

"user" ur1_1

ON(ur1.id_user_parent=ur1_1."id")

WHERE

ur1.id = 3984

AND ur1.disabled=false

),

user_subordinates_united

AS

(

SELECT

ur2."id" AS var_id,

ur2.id_user_parent AS var_id_user_parent,

ur2.login AS var_login,

ups1.var_login AS var_login_parent,

(ups1.var_sort_order + 1)::smallint AS var_sort_order

FROM

user_subordinates ups1

JOIN

"user" ur2

ON( ups1.var_id = ur2.id_user_parent

AND ups1.var_id <> ur2.id

)

)

SELECT

var_id,

var_id_user_parent,

var_login,

var_login_parent,

var_sort_order

FROM

user_subordinates_united

ORDER BY

var_sort_order,       

var_id,             

var_id_user_parent

;

 

______________________________________________________________
> Od: Elliot <yields.falsehood@gmail.com>
> Komu: <slapo@centrum.sk>, <pgsql-general@postgresql.org>
> Dátum: 22.11.2013 18:06
> Predmet: Re: [GENERAL] Puzzling table scan in a CTE
>

 

You can "set enable_seqscan = off" to see what the planner thinks of using the index on id_user_parent.
Does every user have a parent? Or a child? Those will affect how many matches you'll find, and if it's a lot then it'll be faster doing the table scan.
Also, have you changed any configuration settings? random_page_cost might need some tuning.

 

On 2013-11-22 11:54, slapo@centrum.sk wrote:

Good day,

 

I have a recursive CTE where a table scan occurs, even though there doesn't seem to be a good reason for it.

It seems the planner came to the conclusion that columns that are not actually used in the output, joins or a where clause are a part of the output.

It's not a performance problem now and the query runs quickly (which is why I haven't posted it on the performance mailing list). What bothers me is that the scan seems to be there without being really necessary and I would like to avoid any extra I/O. I would expect the plan to be close the simplified query without CTE posted after the CTE query below.

I'm also worried that this could get worse over time and that it might influence the query's performance.

 

The question:

Am I missing something and the table scan is necessary?

If not, is there a way to avoid it?

 

This is the query:

WITH RECURSIVE user_subordinates 

AS 

(

SELECT

ur1."id" AS var_id,

ur1.id_user_parent AS var_id_user_parent,

ur1.login AS var_login,

ur1_1.login AS var_login_parent,

1::smallint AS var_sort_order

FROM

"user" ur1

JOIN

"user" ur1_1

ON(ur1.id_user_parent=ur1_1."id")

WHERE

ur1.id = 3970

AND ur1.disabled=false

UNION ALL

SELECT

ur2."id" AS var_id,

ur2.id_user_parent AS var_id_user_parent,

ur2.login AS var_login,

ups1.var_login AS var_login_parent,

(ups1.var_sort_order + 1)::smallint AS var_sort_order

FROM

user_subordinates ups1

JOIN

"user" ur2

ON( ups1.var_id = ur2.id_user_parent

AND ups1.var_id <> ur2.id

)

)

SELECT

var_id,

var_id_user_parent,

var_login,

var_login_parent,

var_sort_order

FROM

user_subordinates

ORDER BY

var_sort_order,       

var_id,             

var_id_user_parent

;

This is its execution plan:

http://explain.depesz.com/s/4hY

 

This is a simplified version of the query without CTE:

SELECT

ur2."id" AS var_id,

ur2.id_user_parent AS var_id_user_parent,

ur2.login AS var_login,

ups1.var_login AS var_login_parent,

(ups1.var_sort_order + 1)::smallint AS var_sort_order

FROM

(

SELECT

ur1."id" AS var_id,

ur1.id_user_parent AS var_id_user_parent,

ur1.login AS var_login,

ur1_1.login AS var_login_parent,

1::smallint AS var_sort_order

FROM

"user" ur1

JOIN

"user" ur1_1

ON(ur1.id_user_parent=ur1_1."id")

WHERE

ur1.id = 3970

AND ur1.disabled=false

) ups1

JOIN

"user" ur2

ON( ups1.var_id = ur2.id_user_parent

AND ups1.var_id <> ur2.id

)

;

 

Its plan is here:

http://explain.depesz.com/s/Ak3

 

Here's the table's DDL:

CREATE TABLE "user"

(

id bigserial NOT NULL, -- Unique row identifier

id_user_parent bigint NOT NULL DEFAULT 3, -- Identifier of user's parent user

id_address bigint NOT NULL,

login character varying NOT NULL, -- Login name of a user

password character varying NOT NULL, -- Login password of a user

date_created timestamp without time zone NOT NULL DEFAULT now(), -- Date and time at which the record was created

id_user_created bigint NOT NULL, -- Identifier of a user who created the row

date_modified timestamp without time zone, -- Date and time at which the record was modified

id_user_modified bigint, -- Identifier of a user who modified the row

disabled boolean NOT NULL DEFAULT true, -- Its value is set to true when user account is disabled, false when enabled.

activation_hash character varying NOT NULL, -- Activation hash that a hashed string sent to the user matches against during activation.

invoiced boolean NOT NULL DEFAULT false, -- True is user wishes to be invoiced, false otherwise.

CONSTRAINT user_pkey PRIMARY KEY (id),

CONSTRAINT user_id_address_fkey FOREIGN KEY (id_address) REFERENCES address (id),

CONSTRAINT user_id_user_created_fkey FOREIGN KEY (id_user_created) REFERENCES "user" (id),

CONSTRAINT user_id_user_modified_fkey FOREIGN KEY (id_user_modified) REFERENCES "user" (id),

CONSTRAINT u_login UNIQUE (login)

);

CREATE INDEX fki_user_id_address_fkey ON "user" USING btree(id_address);

CREATE INDEX ix__user__id_user_parent ON "user" USING btree(id_user_parent);

CREATE UNIQUE INDEX ix__user__login ON "user" USING btree (lower(login::text) COLLATE pg_catalog."default");

CREATE UNIQUE INDEX ix__user__login__varchar_pattern_ops ON "user" USING btree (lower(login::text) COLLATE pg_catalog."default" varchar_pattern_ops);

 

Environment: Windows 7 Professional x64, PostgreSQL 9.3.1. The table has been analysed before executing the query and getting the explain result. It's on my workstation and nobody else uses the database but me.

 

Any thought on this are appreciated.

 

Thank you.

 

Peter Slapansky

 

Re: Puzzling table scan in a CTE

From
Elliot
Date:
On 2013-11-22 12:49, slapo@centrum.sk wrote:

Thanks for the suggestion.

I've tried it with seqscan set to off, but there's still a bitmap heap scan going on:

http://explain.depesz.com/s/zIJl

 

I have random_page_cost set to 1.5 at the moment, as the database is on a solid state disk.

 

Every user has a parent, but not every parent has a child.

The number of rows returned by the query is 17 at the moment.

It would be even less for a child tree of other users, usually 0 to 3, and the plan remains the same in those cases.

The table itself has only slightly below 5000 rows right now. It's not a lot, but it seems too many to go for a table scan for just 17 rows.

Could it be that the planner cannot estimate the possible match count because of the CTE?

Can you do "explain (analyze, buffers)"? I'm wondering if your entire table is in a very small number of pages, possibly all on just one page, in which case a table scan makes sense. The plan with seqscan off has just a tiny bit higher estimated cost, and it ran 1.5ms slower - that difference could be noise, but I'm thinking that all it's doing is an extra index page read without eliminating any table data page reads (under the assumption that the table is all in a single page).

Re: Puzzling table scan in a CTE

From
Kevin Grittner
Date:
"slapo@centrum.sk" <slapo@centrum.sk> wrote:

> I have a recursive CTE where a table scan occurs, even though
> there doesn't seem to be a good reason for it.

Do you have effective_cache_size set to 50% to 75% of machine RAM?
Do you have cpu_tuple_cost set to between 0.03 and 0.05?  If not,
do changes to these settings help?

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


Re: [GENERAL] Puzzling table scan in a CTE

From
Date:

Sorry for the delay, but I didn't have access to the database during the weekend.

 

Here's the output of "explain (analyze, buffers)":

http://explain.depesz.com/s/scC

 

I'm also curious why it actually seems to touch the table assuming there are output columns which I haven't defined anywhere (see previously posted plan).

 

Cheers. :-)

 

Peter Slapansky

 

______________________________________________________________
> Od: Elliot <yields.falsehood@gmail.com>
> Komu: <slapo@centrum.sk>, <pgsql-general@postgresql.org>
> Dátum: 22.11.2013 19:58
> Predmet: Re: [GENERAL] Puzzling table scan in a CTE
>

> CC: "Elliot"

On 2013-11-22 12:49, slapo@centrum.sk wrote:

Thanks for the suggestion.

I've tried it with seqscan set to off, but there's still a bitmap heap scan going on:

http://explain.depesz.com/s/zIJl

 

I have random_page_cost set to 1.5 at the moment, as the database is on a solid state disk.

 

Every user has a parent, but not every parent has a child.

The number of rows returned by the query is 17 at the moment.

It would be even less for a child tree of other users, usually 0 to 3, and the plan remains the same in those cases.

The table itself has only slightly below 5000 rows right now. It's not a lot, but it seems too many to go for a table scan for just 17 rows.

Could it be that the planner cannot estimate the possible match count because of the CTE?

Can you do "explain (analyze, buffers)"? I'm wondering if your entire table is in a very small number of pages, possibly all on just one page, in which case a table scan makes sense. The plan with seqscan off has just a tiny bit higher estimated cost, and it ran 1.5ms slower - that difference could be noise, but I'm thinking that all it's doing is an extra index page read without eliminating any table data page reads (under the assumption that the table is all in a single page).

Re: [GENERAL] Puzzling table scan in a CTE

From
Date:

I apologise for the late response.

 

I've increased "effective_cache_size" to 50% and tried again - no change.

Afterwards, I've increased "cpu_tuple_cost" from 0.02 to 0.05 and tried again - no change.

 

What is most curious to me is that I think the initial result set is very small, so any JOINs on it should be pretty selective and the number of results should be pretty small with each scan: 1 to 10 from about 4000 rows. I might be missing something, but the row estimates are accurate.

The actual number of loops should be between 1 and 3 right now, as the tree doesn't go any deeper - a user has at most two parents right now, although that might change later.

 

Thank you. :-)

 

Peter Slapansky

 

______________________________________________________________
> Od: Kevin Grittner <kgrittn@ymail.com>
> Komu: "slapo@centrum.sk" <slapo@centrum.sk>, "pgsql-general@postgresql.org" <pgsql-general@postgresql.org>
> Dátum: 22.11.2013 20:25
> Predmet: Re: [GENERAL] Puzzling table scan in a CTE
>

"slapo@centrum.sk" <slapo@centrum.sk> wrote:

> I have a recursive CTE where a table scan occurs, even though
> there doesn't seem to be a good reason for it.

Do you have effective_cache_size set to 50% to 75% of machine RAM?
Do you have cpu_tuple_cost set to between 0.03 and 0.05?  If not,
do changes to these settings help?

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company