Subject: Indexes with condition using immutable functions applied to column
	not used
From: Sylvain Rabot <sylvain@abstraction.fr>
Reply-To: sylvain@abstraction.fr
To: pgsql-performance@postgresql.org
Cc: Sylvain Rabot <sylvain@abstraction.fr>
Content-Type: multipart/signed; micalg="pgp-sha1";
	protocol="application/pgp-signature";
	boundary="=-uStmTNpC/bC504EVHdBt"
Date: Tue, 08 Feb 2011 01:14:58 +0100
Message-ID: <1297124098.2549.65.camel@kheops>
Mime-Version: 1.0


--=-uStmTNpC/bC504EVHdBt
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi,

I am trying to understand how indexes works to get the most of them.

First I would like to know if there is more advantage than overhead to
split an index in several ones using conditions e.g. doing :

CREATE INDEX directory_id_user_0_btree_idx ON mike.directory USING btree (i=
d_user) WHERE id_user < 250000;
CREATE INDEX directory_id_user_250000_btree_idx ON mike.directory USING btr=
ee (id_user) WHERE id_user >=3D 250000 AND id_user < 500000;
CREATE INDEX directory_id_user_500000_btree_idx ON mike.directory USING btr=
ee (id_user) WHERE id_user >=3D 500000 AND id_user < 750000;
CREATE INDEX directory_id_user_750000_btree_idx ON mike.directory USING btr=
ee (id_user) WHERE id_user >=3D 750000 AND id_user < 1000000;

instead of having only one index for all the id_user. the forecasts for
the table directory are +500 millions records and something like 1
million distinct id_user.

If there is my idea was to do a repartition in the indexes using a
consistent hash algorithm in order to fill the indexes in parallel
instead of successively :

CREATE OR REPLACE FUNCTION mike.__mod_cons_hash(
    IN  in_dividend     bigint,
    IN  in_divisor      integer,
    OUT remainder       integer
) AS $__$

BEGIN
    SELECT in_dividend % in_divisor INTO remainder;
END;

$__$ LANGUAGE plpgsql IMMUTABLE COST 10;

CREATE INDEX directory_id_user_mod_cons_hash_0_btree_idx ON mike.directory =
USING btree (id_user) WHERE __mod_cons_hash(id_user, 4) =3D 0;
CREATE INDEX directory_id_user_mod_cons_hash_1_btree_idx ON mike.directory =
USING btree (id_user) WHERE __mod_cons_hash(id_user, 4) =3D 1;
CREATE INDEX directory_id_user_mod_cons_hash_2_btree_idx ON mike.directory =
USING btree (id_user) WHERE __mod_cons_hash(id_user, 4) =3D 2;
CREATE INDEX directory_id_user_mod_cons_hash_3_btree_idx ON mike.directory =
USING btree (id_user) WHERE __mod_cons_hash(id_user, 4) =3D 3;

But the thing is the indexes are not used :

mike=3D# SELECT version();
                                                      version              =
                                       =20
---------------------------------------------------------------------------=
----------------------------------------
 PostgreSQL 8.4.7 on i686-pc-linux-gnu, compiled by GCC gcc-4.4.real (Ubunt=
u/Linaro 4.4.4-14ubuntu5) 4.4.5, 32-bit
(1 row)

mike=3D# REINDEX INDEX directory_id_user_mod_cons_hash_0_btree_idx;
LOG:  duration: 14644.160 ms  statement: REINDEX INDEX
directory_id_user_mod_cons_hash_0_btree_idx;
REINDEX
mike=3D# EXPLAIN ANALYZE SELECT * FROM directory WHERE id_user =3D 4;
                                                   QUERY PLAN              =
                                    =20
---------------------------------------------------------------------------=
-------------------------------------
 Seq Scan on directory  (cost=3D0.00..38140.66 rows=3D67 width=3D148) (actu=
al time=3D0.077..348.211 rows=3D10303 loops=3D1)
   Filter: (id_user =3D 4)
 Total runtime: 351.114 ms
(3 rows)

So I also did this test :

mike=3D# CREATE INDEX directory_id_user_4_btree_idx ON mike.directory USING=
 btree (id_user) WHERE id_user > 3 and id_user < 5;
CREATE INDEX
mike=3D# EXPLAIN ANALYZE select * from directory where id_user =3D 4;
                                                                   QUERY PL=
AN                                                                   =20
---------------------------------------------------------------------------=
----------------------------------------------------------------------
 Index Scan using directory_id_user_4_btree_idx on directory  (cost=3D0.00.=
.10.58 rows=3D67 width=3D148) (actual time=3D0.169..7.753 rows=3D10303 loop=
s=3D1)
   Index Cond: (id_user =3D 4)
 Total runtime: 10.973 ms
(3 rows)

mike=3D# DROP INDEX directory_id_user_4_btree_idx;
DROP INDEX
mike=3D# CREATE INDEX directory_id_user_4_btree_idx ON mike.directory USING=
 btree (id_user) WHERE id_user - 1 > 2 and id_user + 1 < 6;
CREATE INDEX
mike=3D# EXPLAIN ANALYZE select * from directory where id_user =3D 4;
                                                   QUERY PLAN              =
                                    =20
---------------------------------------------------------------------------=
-------------------------------------
 Seq Scan on directory  (cost=3D0.00..38140.66 rows=3D67 width=3D148) (actu=
al time=3D0.153..360.020 rows=3D10303 loops=3D1)
   Filter: (id_user =3D 4)
 Total runtime: 363.106 ms
(3 rows)

mike=3D# DROP INDEX directory_id_user_4_btree_idx;
DROP INDEX
mike=3D# CREATE INDEX directory_id_user_4_btree_idx ON mike.directory USING=
 btree (id_user) WHERE id_user > 2 + 1 and id_user < 6 - 1;
CREATE INDEX
mike=3D# EXPLAIN ANALYZE select * from directory where id_user =3D 4;
                                                                   QUERY PL=
AN                                                                   =20
---------------------------------------------------------------------------=
----------------------------------------------------------------------
 Index Scan using directory_id_user_4_btree_idx on directory  (cost=3D0.00.=
.10.58 rows=3D67 width=3D148) (actual time=3D0.245..8.262 rows=3D10303 loop=
s=3D1)
   Index Cond: (id_user =3D 4)
 Total runtime: 11.110 ms
(3 rows)

As you see the index condition although, differently written, is the
same but the second index is not used apparently because the immutable
function is applied on the column.

So do you know the reason why the planner is not able to use indexes
which have immutable functions applied to the column in their
condition ?

Regards.

--=20
Sylvain Rabot <sylvain@abstraction.fr>

--=-uStmTNpC/bC504EVHdBt
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)

iQEcBAABAgAGBQJNUIsCAAoJECLlHVUnhaoW368H/jTBe0JDKsaRZy50MxTXDM/+
X7PoaSaIE5RdmkdteAh0PjxAp2lFpd2j6sfR/lxca4kAfhfcBSwcXhoq7yU+su6+
WvLshXhL/fPYZf+l+luZRLRS+Hma3us54CHNCA6zMK1h2u/aEHPCCIzBQKs5zmpb
JosUCjktPASLa7tz0LU5y3FG0NrSpFCWxdSO8afPKwK9urdoEI8VwXxeYolfk05Q
2SjezR7X2Pe5VrqKzyhxoMkWBWWkgGnpZGvjQeNL7tKi0oynQmQlpBaqyyEYeuVI
Uyk7harrUgppW56Ahus1+0EN4wIPZBpjXY+ljwyfAKx9W5HV2D9ksVD4tmxFINw=
=uHkF
-----END PGP SIGNATURE-----

--=-uStmTNpC/bC504EVHdBt--