Re: [HACKERS] Reverse key index

Pretty neat. It may be a possible alternative to the use of
the hash index in some applications.

Cheers,
Ken

On Sun, Feb 03, 2008 at 07:13:23PM -0800, Gurjeet Singh wrote:
> Hi All,
>
> I have wanted to create a reverse key index for some time now, and it
> seems that an evening of reading and half a day of efforts finally paid off.
> This is just a proof of concept, and sure, the bit-reversing technique can
> use a native language's power for better results.
>
> I started with the following posts:
>
> http://archives.postgresql.org/pgsql-hackers/2002-01/msg01201.php
> http://archives.postgresql.org/pgsql-hackers/2002-01/msg01225.php
>
> The operator class that is created at the end uses one function to
> populate the index in almost a random manner (reverse binary
> representation). And this op-class provides just one operator to compare the
> values, as opposed to Tom's suggestion ("all the other members would be
> byte-reversed-comparison operators"); this is because if we allow the index
> to use any of these other operators (custom or the built-in ones) for range
> scans, the range's starting value will be found for sure, but because the
> btree index follows the leaf nodes from there on, the results will be
> totally what we never asked for!
>
> The result at the end, INDEX del_i, is an index that helps disperse
> heavy sequential INSERTs from different sessions over to different index
> blocks, reducing index block contention hence improving performance. Also,
> this index can be used of equality operator (but no other operator).
>
> Hackers, of course, comments please. Let me know if I have missed
> something, and if this is not exactly what a user would want!
>
> For fun: If you wish to see how a BTree index performs the comparisons
> and populates the index, just uncomment the 'raise notice' statement in
> rev_int_cmp(). And to compare the bit-reversed mode to the normal mode of
> index population, just replace the contents of declare section with 'rev_a
> int = a; rev_b int = b;' in the declare section. :) have fun.
>
> I have uploaded my original, unedited file from the efforts here. It
> goes to lengths to create functions and operators and what not; may be
> helpful for other noobs chasing operators.
> http://www.geocities.com/gurjeet79/reverse_key_index.sql.txt
>
> Best regards,
>
> PS: I think my signature should be:
> 'Do I LOVE Postgres or what!!'
> OR 'I am in LOVE with Postgres'
> OR 'Postgres is _is_ *is* BEAutiful!'
> OR <you suggest>
>
> --------------- CODE ---------------
>
> --- Support
>
> create or replace function public.reverse_string( str varchar )
> returns varchar
> strict
> immutable
> language plpgsql
> as $$
> declare reversed varchar = '';
> begin
> for i in reverse char_length( str ) .. 1 loop
> reversed = reversed || substring( str from i for 1 );
> end loop;
> return reversed;
> end;
> $$;
>
> create or replace function public.rev_int_cmp( a int, b int )
> returns int
> strict
> immutable
> language plpgsql
> as $$
> declare
> rev_a int = reverse_string( a::bit(32)::varchar )::bit(32)::int;
> rev_b int = reverse_string( b::bit(32)::varchar )::bit(32)::int;
> begin
> -- raise notice 'rev_int_cmp( %, % ) called', a, b;
> if( rev_a < rev_b ) then
> return -1;
> elsif( rev_a > rev_b ) then
> return +1;
> else
> return 0;
> end if;
> end;
> $$;
>
> --- Operator class
>
> drop operator class if exists public.rev_int_ops using btree cascade;
> create operator class public.rev_int_ops for type int using btree as
> operator 3 pg_catalog.=,
> function 1 public.rev_int_cmp( int, int );
>
> --- example
>
> drop table if exists del;
> create table del( a int, b char(128) );
> create index del_i on del( a rev_int_ops );
> insert into del select s, s+1 from generate_series( 1, 1000 ) as s; -- rev
> vacuum full analyze del;
>
> explain
> select * from del;
> explain
> select * from del order by a;
> explain
> select * from del where a = 2; -- should use the reverse index
> explain
> select * from del where a < 200; -- should NOT use the reverse index
>
> truncate del;
>
>
> --
> gurjeet[(dot)singh](at)EnterpriseDB(dot)com
> singh(dot)gurjeet(at){ gmail | hotmail | indiatimes | yahoo }.com
>
> EnterpriseDB http://www.enterprisedb.com
>
> 17? 29' 34.37"N, 78? 30' 59.76"E - Hyderabad
> 18? 32' 57.25"N, 73? 56' 25.42"E - Pune
> 37? 47' 19.72"N, 122? 24' 1.69" W - San Francisco *
>
> http://gurjeet.frihost.net
>
> Mail sent from my BlackLaptop device