Re: Broken selectivity with special inet operators

Summary: special inet operators ( << >> <<= =>> ) are
up to 1000000X off in estimating rowcounts
Type: performance
Severity: normal
Tested on: 9.1.0
Description:

We've been noticing that row estimates for queries which use the =>> and
<<= operators for inet data were way, way off. We finally narrowed the
problem down to a simple test:

===========
USING <<= :
===========

explain analyze
SELECT count(*)
FROM partition1 lh
WHERE lh.ip <<= '1.2.3'::cidr;

QUERY PLAN
.....
-> Index Scan using partition1_ip on partition1 lh
(cost=0.00..10.21 rows=6956732 width=0)
(actual time=0.016..0.016 rows=0 loops=1)
Index Cond: ((ip >= '1.2.3.0/24'::inet) AND (ip <=
'1.2.3.255'::inet))
Filter: (ip <<= '1.2.3.0/24'::inet)
.....

explain analyze
SELECT count(*)
FROM partition2 WHERE 1=1 AND ip <<= '87.178.193.0/24'::inet;

QUERY PLAN
Aggregate (cost=18296.78..18296.79 rows=1 width=0) (actual
time=0.037..0.038 rows=1 loops=1)
-> Index Scan using partition2_ip on partition2 (cost=0.00..38.36
rows=7303365 width=0) (actual ti
me=0.022..0.031 rows=5 loops=1)
Index Cond: ((ip >= '87.178.193.0/24'::inet) AND (ip <=
'87.178.193.255'::inet))
Filter: (ip <<= '87.178.193.0/24'::inet)
Total runtime: 0.107 ms

============
USING < > :
============

explain analyze
SELECT count(*)
FROM partition1 lh
WHERE lh.ip >= '1.2.3.0/24'::inet and lh.ip <= '1.2.3.255'::inet;

QUERY PLAN
....
-> Index Scan using partition1_ip on partition1 lh
(cost=0.00..10.22 rows=1 width=0)
(actual time=0.016..0.016 rows=0 loops=1)
Index Cond: ((ip >= '1.2.3.0/24'::inet) AND (ip <=
'1.2.3.255'::inet))
....

explain analyze
SELECT count(*)
FROM partition2 WHERE 1=1 AND ip > '87.178.193.0'::inet and ip <=
'87.178.193.255'::inet;

QUERY PLAN

Aggregate (cost=26.34..26.35 rows=1 width=0) (actual time=0.033..0.033
rows=1 loops=1)
-> Index Scan using partition2_ip on partition2 (cost=0.00..26.33
rows=5 width=0) (actual time=0.0
19..0.029 rows=5 loops=1)
Index Cond: ((ip > '87.178.193.0'::inet) AND (ip <=
'87.178.193.255'::inet))
Total runtime: 0.097 ms

====
Note that the mis-estimate of rows returned in each case is almost
exactly 50% of the total rows in the table. That would suggest that
match_special_index_operator is failing, and not recognizing the <<=
operator for estimation purposes and just going with a default estimate
of 0.5.

I've tried to locate the cause of this problem, but the code involved is
rather convoluted and crusty, and I can't follow the logic. Help?

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus <josh(at)agliodbs(dot)com> writes:
> Summary: special inet operators ( << >> <<= =>> ) are
> up to 1000000X off in estimating rowcounts

A look in pg_operator will show you that these operators have no
associated selectivity estimators at all. It's not so much "broken"
as "unimplemented".

regression=# select oid::regoperator,oprcode,oprrest,oprjoin from pg_operator where (oprleft = 869 or oprright = 869) and oprresult = 16;
oid | oprcode | oprrest | oprjoin
----------------+---------------+-------------+-----------------
=(inet,inet) | network_eq | eqsel | eqjoinsel
<>(inet,inet) | network_ne | neqsel | neqjoinsel
<(inet,inet) | network_lt | scalarltsel | scalarltjoinsel
<=(inet,inet) | network_le | scalarltsel | scalarltjoinsel
>(inet,inet) | network_gt | scalargtsel | scalargtjoinsel
>=(inet,inet) | network_ge | scalargtsel | scalargtjoinsel
<<(inet,inet) | network_sub | - | -
<<=(inet,inet) | network_subeq | - | -
>>(inet,inet) | network_sup | - | -
>>=(inet,inet) | network_supeq | - | -
(10 rows)

regards, tom lane

On 9/21/11 1:56 PM, Tom Lane wrote:
> Josh Berkus <josh(at)agliodbs(dot)com> writes:
>> Summary: special inet operators ( << >> <<= =>> ) are
>> up to 1000000X off in estimating rowcounts
>
> A look in pg_operator will show you that these operators have no
> associated selectivity estimators at all. It's not so much "broken"
> as "unimplemented".

Oh! I was assuming that the special case code kicked in regardless.

So we implemented the rewrite to < and > for the actual execution, but
not for cost estimates?

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus <josh(at)agliodbs(dot)com> writes:
> On 9/21/11 1:56 PM, Tom Lane wrote:
>> A look in pg_operator will show you that these operators have no
>> associated selectivity estimators at all. It's not so much "broken"
>> as "unimplemented".

> Oh! I was assuming that the special case code kicked in regardless.

> So we implemented the rewrite to < and > for the actual execution, but
> not for cost estimates?

If you mean the indexscan optimization, we do know how to estimate the
cost of the indexscans, because that depends mostly on the behavior of
the added < or > condition(s). This does not imply knowing how to
estimate the behavior of >>= itself.

regards, tom lane

> If you mean the indexscan optimization, we do know how to estimate the
> cost of the indexscans, because that depends mostly on the behavior of
> the added < or > condition(s). This does not imply knowing how to
> estimate the behavior of >>= itself.

If we can estimate the cost of the indexscan, why can't we estimate the
rowcount? Sorry if I'm being dense here, but I really don't understand
how the special operator code works at all.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus <josh(at)agliodbs(dot)com> writes:
>> If you mean the indexscan optimization, we do know how to estimate the
>> cost of the indexscans, because that depends mostly on the behavior of
>> the added < or > condition(s). This does not imply knowing how to
>> estimate the behavior of >>= itself.

> If we can estimate the cost of the indexscan, why can't we estimate the
> rowcount?

Because the estimated rowcount is derived long before we consider whether
to use an indexscan at all, and indeed must be computable whether the
table has any related index or not. The special-indexscan-qual code is
*not* a substitute for providing a selectivity estimator.

It's possible that we could build simple estimators for these operators
that just turn the problem into a range estimation and then pass it off
to somewhere else, but nobody has tried.

regards, tom lane

> It's possible that we could build simple estimators for these operators
> that just turn the problem into a range estimation and then pass it off
> to somewhere else, but nobody has tried.

Right, that's why I'm asking. I'd like to reuse code ...

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com