Re: [HACKERS] [GENERAL] Question about partial functional indexes and the query planner

2014-06-12 Thread Keith Fiske
On Wed, Jun 11, 2014 at 7:24 PM, Tom Lane t...@sss.pgh.pa.us wrote:

 Robert Haas robertmh...@gmail.com writes:
  On Tue, Jun 10, 2014 at 7:19 PM, Tom Lane t...@sss.pgh.pa.us wrote:
  Given the lack of previous complaints, I'm not sure this amounts to
  a back-patchable bug, but it does seem like something worth fixing
  going forward.

  Agreed, although I'd be willing to see us slip it into 9.4.  It's
  doubtful that anyone will get upset if their query plans change
  between beta1 and beta2, but the same cannot be said for released
  branches.

 After further thought about this I realized that there's another category
 of proof possibilities that is pretty simple to add while we're at it.
 Namely, once we've found that both subexpressions of the two operator
 clauses are equal(), we can use btree opclass relationships to prove that,
 say, x  y implies x = y or x  y refutes x  y, independently of
 just what x and y are.  (Well, they have to be immutable expressions, but
 we'd not get this far if they're not.)  We already had pretty nearly all
 of the machinery for that, but again it was only used for proving cases
 involving comparisons to constants.

 A little bit of refactoring later, I offer the attached draft patch.
 I'm thinking this is probably more than we want to slip into 9.4
 at this point, but I'll commit it to HEAD soon if there are not
 objections.

 regards, tom lane



 --
 Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
 To make changes to your subscription:
 http://www.postgresql.org/mailpref/pgsql-hackers


I applied Tom's patch to the latest HEAD
(e04a9ccd2ccd6e31cc4af6b08257a0a186d0fce8) and showed it to Brian. Looks to
solve the problem he originally reported

$ patch -p1 -i ../better-predicate-proofs-1.patch
(Stripping trailing CRs from patch.)
patching file src/backend/optimizer/util/predtest.c


$ /opt/pgsql_patch_review/bin/psql postgres
Timing is on.
Null display (null) is ┬źNULL┬╗.
Expanded display (expanded) is used automatically.
psql (9.5devel)
Type help for help.

postgres=# CREATE OR REPLACE FUNCTION public.return_if_even(v_id integer)
returns integer
postgres-# LANGUAGE sql AS
postgres-# $$
postgres$# SELECT case when v_id % 2 = 1 then 0 else v_id end;
postgres$# $$;
CREATE FUNCTION
Time: 44.669 ms

postgres=# create table public.partial_functional_index_test as
postgres-# select id from generate_series(1,100) AS s(id);
SELECT 100
Time: 1037.993 ms

postgres=# create index partial_functional_idx ON
public.partial_functional_index_test
postgres-# USING btree ( public.return_if_even(id) )
postgres-# WHERE public.return_if_even(id) = id;
LOG:  sending cancel to blocking autovacuum PID 12521
DETAIL:  Process 12424 waits for ShareLock on relation 16385 of database
12217.
STATEMENT:  create index partial_functional_idx ON
public.partial_functional_index_test
USING btree ( public.return_if_even(id) )
WHERE public.return_if_even(id) = id;
ERROR:  canceling autovacuum task
CONTEXT:  automatic analyze of table
postgres.public.partial_functional_index_test
CREATE INDEX
Time: 1658.245 ms

postgres=# explain analyze select count(1) from
public.partial_functional_index_test where public.return_if_even(id) = id;
 QUERY
PLAN
-
 Aggregate  (cost=4818.05..4818.06 rows=1 width=0) (actual
time=2503.851..2503.854 rows=1 loops=1)
   -  Bitmap Heap Scan on partial_functional_index_test
(cost=82.67..4805.55 rows=5000 width=0) (actual time=43.724..1309.309
rows=50 loops=1)
 Recheck Cond: (CASE WHEN ((id % 2) = 1) THEN 0 ELSE id END = id)
 Heap Blocks: exact=4425
 -  Bitmap Index Scan on partial_functional_idx  (cost=0.00..81.42
rows=5000 width=0) (actual time=42.961..42.961 rows=50 loops=1)
 Planning time: 4.245 ms
 Execution time: 2505.281 ms
(7 rows)

Time: 2515.344 ms
postgres=# explain analyze select count(1) from
public.partial_functional_index_test where id = public.return_if_even(id);
 QUERY
PLAN
-
 Aggregate  (cost=4818.05..4818.06 rows=1 width=0) (actual
time=2483.862..2483.866 rows=1 loops=1)
   -  Bitmap Heap Scan on partial_functional_index_test
(cost=82.67..4805.55 rows=5000 width=0) (actual time=40.704..1282.955
rows=50 loops=1)
 Recheck Cond: (CASE WHEN ((id % 2) = 1) THEN 0 ELSE id END = id)
 Heap Blocks: exact=4425
 -  Bitmap Index Scan on partial_functional_idx  (cost=0.00..81.42
rows=5000 width=0) (actual time=39.657..39.657 rows=50 loops=1)
 Planning time: 0.127 ms
 Execution time: 2483.979 ms
(7 rows)


--
Keith Fiske
Database 

Re: [HACKERS] [GENERAL] Question about partial functional indexes and the query planner

2014-06-11 Thread Robert Haas
On Tue, Jun 10, 2014 at 7:19 PM, Tom Lane t...@sss.pgh.pa.us wrote:
 Given the lack of previous complaints, I'm not sure this amounts to
 a back-patchable bug, but it does seem like something worth fixing
 going forward.

Agreed, although I'd be willing to see us slip it into 9.4.  It's
doubtful that anyone will get upset if their query plans change
between beta1 and beta2, but the same cannot be said for released
branches.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] [GENERAL] Question about partial functional indexes and the query planner

2014-06-11 Thread Tom Lane
Robert Haas robertmh...@gmail.com writes:
 On Tue, Jun 10, 2014 at 7:19 PM, Tom Lane t...@sss.pgh.pa.us wrote:
 Given the lack of previous complaints, I'm not sure this amounts to
 a back-patchable bug, but it does seem like something worth fixing
 going forward.

 Agreed, although I'd be willing to see us slip it into 9.4.  It's
 doubtful that anyone will get upset if their query plans change
 between beta1 and beta2, but the same cannot be said for released
 branches.

After further thought about this I realized that there's another category
of proof possibilities that is pretty simple to add while we're at it.
Namely, once we've found that both subexpressions of the two operator
clauses are equal(), we can use btree opclass relationships to prove that,
say, x  y implies x = y or x  y refutes x  y, independently of
just what x and y are.  (Well, they have to be immutable expressions, but
we'd not get this far if they're not.)  We already had pretty nearly all
of the machinery for that, but again it was only used for proving cases
involving comparisons to constants.

A little bit of refactoring later, I offer the attached draft patch.
I'm thinking this is probably more than we want to slip into 9.4
at this point, but I'll commit it to HEAD soon if there are not
objections.

regards, tom lane

diff --git a/src/backend/optimizer/util/predtest.c b/src/backend/optimizer/util/predtest.c
index 9d61a4d..039221f 100644
*** a/src/backend/optimizer/util/predtest.c
--- b/src/backend/optimizer/util/predtest.c
*** static bool predicate_refuted_by_simple_
*** 95,102 
  static Node *extract_not_arg(Node *clause);
  static Node *extract_strong_not_arg(Node *clause);
  static bool list_member_strip(List *list, Expr *datum);
! static bool btree_predicate_proof(Expr *predicate, Node *clause,
! 	  bool refute_it);
  static Oid	get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it);
  static void InvalidateOprProofCacheCallBack(Datum arg, int cacheid, uint32 hashvalue);
  
--- 95,106 
  static Node *extract_not_arg(Node *clause);
  static Node *extract_strong_not_arg(Node *clause);
  static bool list_member_strip(List *list, Expr *datum);
! static bool operator_predicate_proof(Expr *predicate, Node *clause,
! 		 bool refute_it);
! static bool operator_same_subexprs_proof(Oid pred_op, Oid clause_op,
! 			 bool refute_it);
! static bool operator_same_subexprs_lookup(Oid pred_op, Oid clause_op,
! 			  bool refute_it);
  static Oid	get_btree_test_op(Oid pred_op, Oid clause_op, bool refute_it);
  static void InvalidateOprProofCacheCallBack(Datum arg, int cacheid, uint32 hashvalue);
  
*** arrayexpr_cleanup_fn(PredIterInfo info)
*** 1025,1032 
   * we are within an AND/OR subtree of a WHERE clause.  (Again, foo is
   * already known immutable, so the clause will certainly always fail.)
   *
!  * Finally, we may be able to deduce something using knowledge about btree
!  * operator families; this is encapsulated in btree_predicate_proof().
   *--
   */
  static bool
--- 1029,1037 
   * we are within an AND/OR subtree of a WHERE clause.  (Again, foo is
   * already known immutable, so the clause will certainly always fail.)
   *
!  * Finally, if both clauses are binary operator expressions, we may be able
!  * to prove something using the system's knowledge about operators; those
!  * proof rules are encapsulated in operator_predicate_proof().
   *--
   */
  static bool
*** predicate_implied_by_simple_clause(Expr 
*** 1060,1067 
  		return false;			/* we can't succeed below... */
  	}
  
! 	/* Else try btree operator knowledge */
! 	return btree_predicate_proof(predicate, clause, false);
  }
  
  /*--
--- 1065,1072 
  		return false;			/* we can't succeed below... */
  	}
  
! 	/* Else try operator-related knowledge */
! 	return operator_predicate_proof(predicate, clause, false);
  }
  
  /*--
*** predicate_implied_by_simple_clause(Expr 
*** 1083,1090 
   * these cases is to support using IS NULL/IS NOT NULL as partition-defining
   * constraints.)
   *
!  * Finally, we may be able to deduce something using knowledge about btree
!  * operator families; this is encapsulated in btree_predicate_proof().
   *--
   */
  static bool
--- 1088,1096 
   * these cases is to support using IS NULL/IS NOT NULL as partition-defining
   * constraints.)
   *
!  * Finally, if both clauses are binary operator expressions, we may be able
!  * to prove something using the system's knowledge about operators; those
!  * proof rules are encapsulated in operator_predicate_proof().
   *--
   */
  static bool
*** predicate_refuted_by_simple_clause(Expr 
*** 1148,1155 
  		return false;			/* we can't succeed below... */
  	}
  
! 	/* Else try btree operator knowledge */
! 	return btree_predicate_proof(predicate, clause, true);
  }
  
  
--- 1154,1161 
  		return false;	

Re: [HACKERS] [GENERAL] Question about partial functional indexes and the query planner

2014-06-10 Thread Tom Lane
Brian Dunavant br...@omniti.com writes:
 I am using a partial functional index on a table where F(a) = a.  Querying
 whre F(a) = a hits the index as expected.  However the reverse statement a
 = F(a) does not.  I have verified this in 9.3.4.
 Is this a deficiency with the query planner, or are these not actually
 equivalent?  I've been stumped on it.

Interesting.  The reason this doesn't work is that predicate_implied_by()
fails to prove a = b given b = a, at least in the general case.
It will figure that out if either a or b is a constant, but not if
neither one is.  The fact that it works with constants might explain
the lack of previous complaints, but this is still pretty surprising
given the amount of knowledge about equality that the system evinces
otherwise.  (I'm also wondering whether the EquivalenceClass logic
might not sometimes rewrite a = b into b = a, causing a failure
of this sort even when the user *had* phrased his query consistently.)

It would be fairly straightforward to add a proof rule along the lines of
if both expressions are binary opclauses, and the left input expression
of each one is equal() to the right input of the other, and the operators
are each other's commutators, then the implication holds.

An objection might be made that this would add noticeably to the cost of
failing proofs, but I think it wouldn't be that bad, especially if we did
the syscache lookup for the commutator check last.  In most scenarios the
equal() checks would fail pretty quickly when the proof rule doesn't
apply.  Also, I believe that in the case where a or b is a constant,
even though we can make the proof already, this approach would succeed
noticeably more quickly than btree_predicate_proof() can.  (Worth noting
also is that predicate_implied_by() isn't even used unless you have
things like partial indexes involved, so that its cost is not especially
relevant to simple queries.)

I'd be inclined to add some similar proof rules to predicate_refuted_by,
along the lines of a op1 b refutes a op2 b if op1 is op2's negator and
a op1 b refutes b op2 a if op1 is the negator of op2's commutator.
Again, the code is currently unable to make such deductions unless a or b
is a constant.

Given the lack of previous complaints, I'm not sure this amounts to
a back-patchable bug, but it does seem like something worth fixing
going forward.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers