Re: Secondary index access optimizations

On 14.08.2017 19:33, Konstantin Knizhnik wrote:
>
>
> On 14.08.2017 12:37, Konstantin Knizhnik wrote:
>> Hi hackers,
>>
>> I am trying to compare different ways of optimizing work with huge
>> append-only tables in PostgreSQL where primary key is something like
>> timestamp and queries are usually accessing most recent data using
>> some secondary keys. Size of secondary index is one of the most
>> critical factors limiting insert/search performance. As far as data
>> is inserted in timestamp ascending order, access to primary key is
>> well localized and accessed tables are present in memory. But if we
>> create secondary key for the whole table, then access to it will
>> require random reads from the disk and significantly decrease
>> performance.
>>
>> There are two well known solutions of the problem:
>> 1. Table partitioning
>> 2. Partial indexes
>>
>> This approaches I want to compare. First of all I want to check if
>> optimizer is able to generate efficient query execution plan covering
>> different time intervals.
>> Unfortunately in both cases generated plan is not optimal.
>>
>> 1. Table partitioning:
>>
>> create table base (k integer primary key, v integer);
>> create table part1 (check (k between 1 and 10000)) inherits (base);
>> create table part2 (check (k between 10001 and 20000)) inherits (base);
>> create index pi1 on part1(v);
>> create index pi2 on part2(v);
>> insert int part1 values (generate series(1,10000), random());
>> insert into part2 values (generate_series(10001,20000), random());
>> explain select * from base where k between 1 and 20000 and v = 100;
>> QUERY PLAN
>> -----------------------------------------------------------------------
>> Append (cost=0.00..15.65 rows=3 width=8)
>> -> Seq Scan on base (cost=0.00..0.00 rows=1 width=8)
>> Filter: ((k >= 1) AND (k <= 20000) AND (v = 100))
>> -> Index Scan using pi1 on part1 (cost=0.29..8.31 rows=1 width=8)
>> Index Cond: (v = 100)
>> Filter: ((k >= 1) AND (k <= 20000))
>> -> Index Scan using pi2 on part2 (cost=0.29..7.34 rows=1 width=8)
>> Index Cond: (v = 100)
>> Filter: ((k >= 1) AND (k <= 20000))
>>
>> Questions:
>> - Is there some way to avoid sequential scan of parent table? Yes, it
>> is empty and so sequential scan will not take much time, but ... it
>> still requires some additional actions and so increasing query
>> execution time.
>> - Why index scan of partition indexes includes filter condition if it
>> is guaranteed by check constraint that all records of this partition
>> match search predicate?
>>
>>
>> 2. Partial indexes:
>>
>> create table t (k integer primary key, v integer);
>> insert into t values (generate_series(1,20000),random());
>> create index i1 on t(v) where k between 1 and 10000;
>> create index i2 on t(v) where k between 10001 and 20000;
>> postgres=# explain select * from t where k between 1 and 10000 and v
>> = 100;
>> QUERY PLAN
>> ------------------------------------------------------------
>> Index Scan using i1 on t (cost=0.29..7.28 rows=1 width=8)
>> Index Cond: (v = 100)
>> (2 rows)
>>
>>
>> Here we get perfect plan. Let's try to extend search interval:
>>
>>
>> postgres=# explain select * from t where k between 1 and 20000 and v
>> = 100;
>> QUERY PLAN
>> ------------------------------------------------------------------
>> Index Scan using t_pkey on t (cost=0.29..760.43 rows=1 width=8)
>> Index Cond: ((k >= 1) AND (k <= 20000))
>> Filter: (v = 100)
>> (3 rows)
>>
>> Unfortunately in this case Postgres is not able to apply partial
>> indexes.
>> And this is what I expected to get:
>>
>> postgres=# explain select * from t where k between 1 and 10000 and v
>> = 100 union all select * from t where k between 10001 and 20000 and v
>> = 100;
>> QUERY PLAN
>> ----------------------------------------------------------------------
>> Append (cost=0.29..14.58 rows=2 width=8)
>> -> Index Scan using i1 on t (cost=0.29..7.28 rows=1 width=8)
>> Index Cond: (v = 100)
>> -> Index Scan using i2 on t t_1 (cost=0.29..7.28 rows=1 width=8)
>> Index Cond: (v = 100)
>>
>>
>> I wonder if there are some principle problems in supporting this two
>> things in optimizer:
>> 1. Remove search condition for primary key if it is fully satisfied
>> by derived table check constraint.
>> 2. Append index scans of several partial indexes if specified
>> interval is covered by their conditions.
>>
>> I wonder if someone is familiar with this part of optimizer ad can
>> easily fix it.
>> Otherwise I am going to spend some time on solving this problems (if
>> community think that such optimizations will be useful).
>>
>
> Replying to myself: the following small patch removes redundant checks
> from index scans for derived tables:
>
>
> diff --git a/src/backend/optimizer/util/plancat.c
> b/src/backend/optimizer/util/plancat.c
> index 939045d..1f7c9cf 100644
> --- a/src/backend/optimizer/util/plancat.c
> +++ b/src/backend/optimizer/util/plancat.c
> @@ -1441,6 +1441,20 @@ relation_excluded_by_constraints(PlannerInfo
> *root,
> if (predicate_refuted_by(safe_constraints,
> rel->baserestrictinfo, false))
> return true;
>
> + /*
> + * Remove from restriction list items implied by table
> constraints
> + */
> + safe_restrictions = NULL;
> + foreach(lc, rel->baserestrictinfo)
> + {
> + RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
> + if (!predicate_implied_by(list_make1(rinfo->clause),
> safe_constraints, false)) {
> + safe_restrictions = lappend(safe_restrictions,
> rinfo);
> + }
> + }
> + rel->baserestrictinfo = safe_restrictions;
> +
> +
> return false;
> }
>
> =================================================
>
> I am not sure if this is the right place of adjusting restriction list
> and is such transformation always correct.
> But for the queries I have tested produced plans are correct:
>
>
> postgres=# explain select * from base where k between 1 and 20000 and
> v = 100;
> QUERY PLAN
> -----------------------------------------------------------------------
> Append (cost=0.00..15.64 rows=3 width=8)
> -> Seq Scan on base (cost=0.00..0.00 rows=1 width=8)
> Filter: ((k >= 1) AND (k <= 20000) AND (v = 100))
> -> Index Scan using pi1 on part1 (cost=0.29..8.30 rows=1 width=8)
> Index Cond: (v = 100)
> -> Index Scan using pi2 on part2 (cost=0.29..7.34 rows=1 width=8)
> Index Cond: (v = 100)
> (7 rows)
>
> postgres=# explain select * from base where k between 1 and 15000 and
> v = 100;
> QUERY PLAN
> -----------------------------------------------------------------------
> Append (cost=0.00..15.64 rows=3 width=8)
> -> Seq Scan on base (cost=0.00..0.00 rows=1 width=8)
> Filter: ((k >= 1) AND (k <= 15000) AND (v = 100))
> -> Index Scan using pi1 on part1 (cost=0.29..8.30 rows=1 width=8)
> Index Cond: (v = 100)
> -> Index Scan using pi2 on part2 (cost=0.29..7.34 rows=1 width=8)
> Index Cond: (v = 100)
> Filter: (k <= 15000)
> (8 rows)
>

There is one more problem with predicate_implied_by function and
standard Postgres partitions.
Right now it specifies constrains for partitions using intervals with
open high boundary:

postgres=# create table bt (k integer, v integer) partition by range (k);
postgres=# create table dt1 partition of bt for values from (1) to (10001);
postgres=# create table dt2 partition of bt for values from (10001) to
(20001);
postgres=# create index dti1 on dt1(v);
postgres=# create index dti2 on dt2(v);
postgres=# insert into bt values (generate_series(1,20000), random());

postgres=# \d+ dt2
Table "public.dt2"
Column | Type | Collation | Nullable | Default | Storage | Stats
target | De
scription
--------+---------+-----------+----------+---------+---------+--------------+---
----------
k | integer | | | | plain
| |
v | integer | | | | plain
| |
Partition of: bt FOR VALUES FROM (10001) TO (20001)
Partition constraint: ((k IS NOT NULL) AND (k >= 10001) AND (k < 20001))
Indexes:
"dti2" btree (v)

If now I run the query with predicate "between 1 and 20000", I still see
extra check in the plan:

postgres=# explain select * from bt where k between 1 and 20000 and v = 100;
QUERY PLAN
----------------------------------------------------------------------
Append (cost=0.29..15.63 rows=2 width=8)
-> Index Scan using dti1 on dt1 (cost=0.29..8.30 rows=1 width=8)
Index Cond: (v = 100)
-> Index Scan using dti2 on dt2 (cost=0.29..7.33 rows=1 width=8)
Index Cond: (v = 100)
Filter: (k <= 20000)
(6 rows)

It is because operator_predicate_proof is not able to understand that k
< 20001 and k <= 20000 are equivalent for integer type.
If I rewrite query as (k >= 1 and k < 20001) then plan is optimal:

postgres=# explain select * from bt where k >= 1 and k < 20001 and v = 100;
QUERY PLAN
----------------------------------------------------------------------
Append (cost=0.29..15.63 rows=2 width=8)
-> Index Scan using dti1 on dt1 (cost=0.29..8.30 rows=1 width=8)
Index Cond: (v = 100)
-> Index Scan using dti2 on dt2 (cost=0.29..7.33 rows=1 width=8)
Index Cond: (v = 100)
(5 rows)

It is fixed by one more patch of predtest.c:

diff --git a/src/backend/optimizer/util/predtest.c
b/src/backend/optimizer/util
index 06fce84..c318d00 100644
--- a/src/backend/optimizer/util/predtest.c
+++ b/src/backend/optimizer/util/predtest.c
@@ -17,6 +17,7 @@

#include "catalog/pg_proc.h"
#include "catalog/pg_type.h"
+#include "catalog/pg_operator.h"
#include "executor/executor.h"
#include "miscadmin.h"
#include "nodes/nodeFuncs.h"
@@ -1407,6 +1408,11 @@ static const StrategyNumber BT_refute_table[6][6] = {
{none, none, BTEQ, none, none, none} /* NE */
};

+#define Int2LessOperator 95
+#define Int2LessOrEqualOperator 522
+#define Int4LessOrEqualOperator 523
+#define Int8LessOrEqualOperator 414
+

/*
* operator_predicate_proof
if (clause_const->constisnull)
return false;

+ if (!refute_it
+ && ((pred_op == Int4LessOrEqualOperator && clause_op ==
Int4LessOperator)
+ || (pred_op == Int8LessOrEqualOperator && clause_op ==
Int8LessOperator)
+ || (pred_op == Int2LessOrEqualOperator && clause_op ==
Int2LessOperator))
+ && pred_const->constbyval && clause_const->constbyval
+ && pred_const->constvalue + 1 == clause_const->constvalue)
+ {
+ return true;
+ }
+
/*
* Lookup the constant-comparison operator using the system
catalogs and
* the operator implication tables.
===============================

Now plan is perfect once again:

postgres=# explain select * from bt where k between 1 and 20000 and v = 100;
QUERY PLAN
----------------------------------------------------------------------
Append (cost=0.29..15.63 rows=2 width=8)
-> Index Scan using dti1 on dt1 (cost=0.29..8.30 rows=1 width=8)
Index Cond: (v = 100)
-> Index Scan using dti2 on dt2 (cost=0.29..7.33 rows=1 width=8)
Index Cond: (v = 100)
(5 rows)

postgres=# explain select * from bt where k between 1 and 15000 and v = 100;
QUERY PLAN
----------------------------------------------------------------------
Append (cost=0.29..15.63 rows=2 width=8)
-> Index Scan using dti1 on dt1 (cost=0.29..8.30 rows=1 width=8)
Index Cond: (v = 100)
-> Index Scan using dti2 on dt2 (cost=0.29..7.33 rows=1 width=8)
Index Cond: (v = 100)
Filter: (k <= 15000)
(6 rows)

I am not sure that proposed approach is general enough, but I do not
know how to implement in more elegant way.
Composed patch is attached to this mail.

--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company