Thread: partial index

partial index

From
Bruce Momjian
Date:
What is a partial index?  I have never known.

--
Bruce Momjian                          |  830 Blythe Avenue
maillist@candle.pha.pa.us              |  Drexel Hill, Pennsylvania 19026
  +  If your life is a hard drive,     |  (610) 353-9879(w)
  +  Christ can be your backup.        |  (610) 853-3000(h)

Re: partial index

From
aoki@CS.Berkeley.EDU (Paul M. Aoki)
Date:
Bruce Momjian <maillist@candle.pha.pa.us> writes:
> What is a partial index?  I have never known.

it's an index built over a subset of a table; the subset is defined by
a predicate.  postgres supported partial indices with arbitrary
predicates.  i believe ibm's db2 for as/400 supports partial indices
using single-clause predicates.

the main motivation is: if all of the queries you ask that can
profitably use an index fall into a certain range, why build an index
over the whole table and suffer the associated space/time costs?
(there are other reasons; see the first paper referenced below.)

the machinery to build, update and query partial indices isn't too
bad.  the hairy parts are index selection (which indices do i build)
and query optimization (which indices do i use) -- i.e., the parts
that involve deciding what predicate(s) match the workload/query in
some useful way.  for those who are into database theory, the problems
are basically analogous to the corresponding materialized view
problems, albeit with different cost parameters and formulae.  these
are, in the general case, hard problems for the standard ordinal sql
types; they're super-hard problems with black-box extension types,
because the selectivity estimation technology is so crude.

1. Stonebraker, M.
     The case for partial indexes (DBMS).
   SIGMOD Record, Dec. 1989, vol.18, (no.4):4-11.
http://s2k-ftp.CS.Berkeley.EDU:8000/postgres/papers/ERL-M89-17.pdf

2. Olson, Nels Edward.
     Partial indexing in POSTGRES : research project / by Nels Edward Olson.
   1993.
       UCB   Engin     T7.49.1993 O676

1. CONFERENCE PAPER
   Seshadri, P.; Swami, A.
     Generalized partial indexes.
   IN:  Proceedings of the Eleventh International Conference on Data
   Engineering (Cat. No.95CH35724). (Proceedings of the Eleventh International
   Conference on Data Engineering (Cat. No.95CH35724)Proceedings of the
   Eleventh International Conference on Data Engineering, Taipei, Taiwan, 6-10
   March 1995). Edited by: Yu, P.S.; Chen, A.L.P. Los Alamitos, CA, USA: IEEE
   Comput. Soc. Press, 1995. p. 420-7.
http://simon.cs.cornell.edu/home/praveen/papers/partindex.de95.ps.Z
--
  Paul M. Aoki         | University of California at Berkeley
  aoki@CS.Berkeley.EDU | Dept. of EECS, Computer Science Division #1776
                       | Berkeley, CA 94720-1776

Re: [HACKERS] Re: partial index

From
Bruce Momjian
Date:
> Bruce Momjian <maillist@candle.pha.pa.us> writes:
> > What is a partial index?  I have never known.
>
> it's an index built over a subset of a table; the subset is defined by
> a predicate.  postgres supported partial indices with arbitrary
> predicates.  i believe ibm's db2 for as/400 supports partial indices
> using single-clause predicates.
>
> the main motivation is: if all of the queries you ask that can
> profitably use an index fall into a certain range, why build an index
> over the whole table and suffer the associated space/time costs?
> (there are other reasons; see the first paper referenced below.)

I had suspected that's what they were, but never really was sure.  Now
the next question, "Should we rip them out?"   No one uses them, and
they seem to be of very limited usefulness.

I am inclinded to keep them, but I am not sure.


>
> the machinery to build, update and query partial indices isn't too
> bad.  the hairy parts are index selection (which indices do i build)
> and query optimization (which indices do i use) -- i.e., the parts
> that involve deciding what predicate(s) match the workload/query in
> some useful way.  for those who are into database theory, the problems
> are basically analogous to the corresponding materialized view
> problems, albeit with different cost parameters and formulae.  these
> are, in the general case, hard problems for the standard ordinal sql
> types; they're super-hard problems with black-box extension types,
> because the selectivity estimation technology is so crude.
>
> 1. Stonebraker, M.
>      The case for partial indexes (DBMS).
>    SIGMOD Record, Dec. 1989, vol.18, (no.4):4-11.
> http://s2k-ftp.CS.Berkeley.EDU:8000/postgres/papers/ERL-M89-17.pdf
>
> 2. Olson, Nels Edward.
>      Partial indexing in POSTGRES : research project / by Nels Edward Olson.
>    1993.
>        UCB   Engin     T7.49.1993 O676
>
> 1. CONFERENCE PAPER
>    Seshadri, P.; Swami, A.
>      Generalized partial indexes.
>    IN:  Proceedings of the Eleventh International Conference on Data
>    Engineering (Cat. No.95CH35724). (Proceedings of the Eleventh International
>    Conference on Data Engineering (Cat. No.95CH35724)Proceedings of the
>    Eleventh International Conference on Data Engineering, Taipei, Taiwan, 6-10
>    March 1995). Edited by: Yu, P.S.; Chen, A.L.P. Los Alamitos, CA, USA: IEEE
>    Comput. Soc. Press, 1995. p. 420-7.
> http://simon.cs.cornell.edu/home/praveen/papers/partindex.de95.ps.Z
> --
>   Paul M. Aoki         | University of California at Berkeley
>   aoki@CS.Berkeley.EDU | Dept. of EECS, Computer Science Division #1776
>                        | Berkeley, CA 94720-1776
>
>


--
Bruce Momjian                          |  830 Blythe Avenue
maillist@candle.pha.pa.us              |  Drexel Hill, Pennsylvania 19026
  +  If your life is a hard drive,     |  (610) 353-9879(w)
  +  Christ can be your backup.        |  (610) 853-3000(h)