To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: pgsql-sql@postgresql.org
Subject: Re: GiST, Not Using Index
From: Itai Zukerman <zukerman@math-hat.com>
In-Reply-To: <27896.1046379102@sss.pgh.pa.us> (Tom Lane's message of "Thu,
	27 Feb 2003 15:51:42 -0500")
References: <87bs0z1zzs.fsf@matt.w80.math-hat.com>
	<87lm03ghpo.fsf@matt.w80.math-hat.com>
	<87adghtt0h.fsf_-_@pip.dynamiclogic.com>
	<27896.1046379102@sss.pgh.pa.us>
Date: Thu, 27 Feb 2003 16:15:03 -0500
Message-ID: <871y1ttoh4.fsf@pip.dynamiclogic.com>
User-Agent: Gnus/5.090015 (Oort Gnus v0.15) Emacs/21.2
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="=-=-="

--=-=-=

>>   [...some definitions...]
>
> Never leave out the "unimportant" stuff --- that's usually where you
> went wrong ;-)

OK, I've attached below the SQL I use to generate stuff and an
interactive session with the "explain" etc.  The table has 40000 rows,
I do a VACUUM before doing a select, and (what I really don't
understand) the "explain verbose" doesn't mention anything about an index.

> My guess is that you didn't supply a restriction selectivity estimator
> for the ~>= operator.

I'm using contsel and contjoinsel, which I pulled from the rtree_gist
example.

Anyway, hoping you can help...


--=-=-=
Content-Disposition: attachment; filename=sig.sql

-- $Id$

-- I/O functions.

CREATE FUNCTION sig_in(cstring) RETURNS sig
AS '/home/zukerman/d/pg/sig/sig', 'pg_sig_in' LANGUAGE 'C';

CREATE FUNCTION sig_in(int4) RETURNS sig
AS '/home/zukerman/d/pg/sig/sig', 'pg_sig_in_int4' LANGUAGE 'C';

CREATE FUNCTION sig_in(int4[]) RETURNS sig
AS '/home/zukerman/d/pg/sig/sig', 'pg_sig_in_int4arr' LANGUAGE 'C';

CREATE FUNCTION sig_out(sig) RETURNS cstring
AS '/home/zukerman/d/pg/sig/sig', 'pg_sig_out' LANGUAGE 'C';

-- INTERNALLENGTH = 64 bits / 8 = 8 bytes.

CREATE TYPE sig (
  INTERNALLENGTH = 8,
  INPUT = sig_in,
  OUTPUT = sig_out
);

-- Bit functions.

CREATE FUNCTION sig_complement(sig) RETURNS sig
AS '/home/zukerman/d/pg/sig/sig', 'pg_sig_complement' LANGUAGE 'C' STRICT;

CREATE FUNCTION sig_union(sig, sig) RETURNS sig
AS '/home/zukerman/d/pg/sig/sig', 'pg_sig_union' LANGUAGE 'C' STRICT;

CREATE OPERATOR ~ (
  RIGHTARG = sig,
  PROCEDURE = sig_complement
);

CREATE OPERATOR ^ (
  LEFTARG = sig,
  RIGHTARG = sig,
  PROCEDURE = sig_union,
  COMMUTATOR = ^
);

-- Relations.

CREATE FUNCTION sig_equals(sig, sig) RETURNS boolean
AS '/home/zukerman/d/pg/sig/sig', 'pg_sig_equals' LANGUAGE 'C' STRICT;

CREATE FUNCTION sig_subset(sig, sig) RETURNS boolean
AS '/home/zukerman/d/pg/sig/sig', 'pg_sig_subset' LANGUAGE 'C' STRICT;

CREATE FUNCTION sig_superset(sig, sig) RETURNS boolean
AS 'SELECT sig_subset($2,$1);' LANGUAGE 'sql' STRICT;

CREATE OPERATOR ~= (
  LEFTARG = sig,
  RIGHTARG = sig,
  PROCEDURE = sig_equals,
  COMMUTATOR = ~=,
  RESTRICT = eqsel,
  JOIN = eqjoinsel
);

CREATE OPERATOR ~<= (
  LEFTARG = sig,
  RIGHTARG = sig,
  PROCEDURE = sig_subset,
  COMMUTATOR = ~>=,
  RESTRICT = contsel,
  JOIN = contjoinsel
);

CREATE OPERATOR ~>= (
  LEFTARG = sig,
  RIGHTARG = sig,
  PROCEDURE = sig_superset,
  COMMUTATOR = ~<=,
  RESTRICT = contsel,
  JOIN = contjoinsel
);

-- GiST definitions.

CREATE FUNCTION g_sig_consistent(internal, internal, int2) RETURNS bool
AS '/home/zukerman/d/pg/sig/sig' LANGUAGE 'C';

CREATE FUNCTION g_sig_union(bytea, internal) RETURNS internal
AS '/home/zukerman/d/pg/sig/sig' LANGUAGE 'C';

CREATE FUNCTION g_sig_compress(internal) RETURNS internal
AS '/home/zukerman/d/pg/sig/sig' LANGUAGE 'C';

CREATE FUNCTION g_sig_decompress(internal) RETURNS internal
AS '/home/zukerman/d/pg/sig/sig' LANGUAGE 'C';

CREATE FUNCTION g_sig_penalty(internal, internal) RETURNS internal
AS '/home/zukerman/d/pg/sig/sig' LANGUAGE 'C';

CREATE FUNCTION g_sig_picksplit(bytea, internal) RETURNS internal
AS '/home/zukerman/d/pg/sig/sig' LANGUAGE 'C';

CREATE FUNCTION g_sig_same(internal, internal, internal) RETURNS internal
AS '/home/zukerman/d/pg/sig/sig' LANGUAGE 'C';

CREATE OPERATOR CLASS sig_ops
FOR TYPE sig USING gist AS
  OPERATOR 6 ~=,
  OPERATOR 7 ~>=,
  FUNCTION 1 g_sig_consistent (internal, internal, int2),
  FUNCTION 2 g_sig_union (bytea, internal),
  FUNCTION 3 g_sig_compress (internal),
  FUNCTION 4 g_sig_decompress (internal),
  FUNCTION 5 g_sig_penalty (internal, internal),
  FUNCTION 6 g_sig_picksplit (bytea, internal),
  FUNCTION 7 g_sig_same (internal, internal, internal);

--

CREATE TABLE x (y sig);
CREATE INDEX xx ON x USING gist (y sig_ops);

--=-=-=
Content-Disposition: attachment; filename=session.txt

test=# \d x
     Table "public.x"
 Column | Type | Modifiers 
--------+------+-----------
 y      | sig  | 
Indexes: xx gist (y sig_ops)

test=# select count(*) from x;
 count 
-------
 40000
(1 row)

test=# vacuum full analyze x;
VACUUM
test=# select sig_in('{1,2,3,4,5}'::int4[]);
                              sig_in                              
------------------------------------------------------------------
 .*****..........................................................
(1 row)

test=# select * from x where y ~>= sig_in('{1,2,3,4,5}'::int4[]);
                                y                                 
------------------------------------------------------------------
 ******.**.*..*****...***....**.****...*.*.*.....*.**.***..*..*..
 .*****.....*..............**..**......****.*....*..*.*.*.......*
 ******.*..***.*..*.**.**......*.**.*....*......*..****.....*...*
(3 rows)

test=# explain verbose select * from x where y ~>= sig_in('{1,2,3,4,5}'::int4[]);
                                   QUERY PLAN                                   
--------------------------------------------------------------------------------
    { SEQSCAN 
    :startup_cost 0.00 
    :total_cost 797.00 
    :rows 40 
    :width 8 
    :qptargetlist (
       { TARGETENTRY 
       :resdom 
          { RESDOM 
          :resno 1 
          :restype 1936051 
          :restypmod -1 
          :resname y 
          :reskey 0 
          :reskeyop 0 
          :ressortgroupref 0 
          :resjunk false 
          }
        
       :expr 
          { VAR 
          :varno 1 
          :varattno 1 
          :vartype 1936051 
          :vartypmod -1  
          :varlevelsup 0 
          :varnoold 1 
          :varoattno 1
          }
       }
    )
     
    :qpqual (
       { EXPR 
       :typeOid 16  
       :opType op 
       :oper 
          { OPER 
          :opno 1936065 
          :opid 1936063 
          :opresulttype 16 
          :opretset false 
          }
        
       :args (
          { VAR 
          :varno 1 
          :varattno 1 
          :vartype 1936051 
          :vartypmod -1  
          :varlevelsup 0 
          :varnoold 1 
          :varoattno 1
          }
        
          { EXPR 
          :typeOid 1936051  
          :opType func 
          :oper 
             { FUNC 
             :funcid 1936054 
             :funcresulttype 1936051 
             :funcretset false 
             :funcformat 0 
             }
           
          :args (
             { CONST 
             :consttype 1007 
             :constlen -1 
             :constbyval false 
             :constisnull false 
             :constvalue  44 [ 44 0 0 0 1 0 0 0 0 0 0 0 23 0 0 0 5 0 0 0 1 0 0 
             0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 0 0 0 ] 
             }
          )
          }
       )
       }
    )
     
    :lefttree <> 
    :righttree <> 
    :extprm ()
     
    :locprm ()
     
    :initplan <> 
    :nprm 0  
    :scanrelid 1 
    }
 
 Seq Scan on x  (cost=0.00..797.00 rows=40 width=8)
   Filter: (y ~>= sig_in('{1,2,3,4,5}'::integer[]))
(94 rows)

test=# 

--=-=-=


-- 
Itai Zukerman  <http://www.math-hat.com/~zukerman/>

--=-=-=--