SQL tests

CREATE or replace FUNCTION strbit_to_vbit( b text, p_len int DEFAULT null) RETURNS varbit AS $f$
   SELECT lpad(b, l, '0')::varbit
   FROM (select CASE WHEN p_len>0 THEN p_len ELSE length(b) END) t(l)
$f$  LANGUAGE SQL IMMUTABLE;


CREATE or replace FUNCTION sizednat.prefix_length(p varbit) RETURNS int AS $f$
  SELECT COALESCE(  length(substring(p::text from '^0+')),  0  )
$f$ LANGUAGE SQL IMMUTABLE;

CREATE or replace FUNCTION sizednat.sufix_nonzero_toint(p varbit) RETURNS bigint AS $f$
  SELECT varbit_to_bigint(strbit_to_vbit(x))
  FROM ( SELECT COALESCE(  substring(p::text from '[^0][01]*$'),  '0'  )) t(x)
$f$ LANGUAGE SQL IMMUTABLE;

CREATE VIEW sizednat.sample1 AS
  SELECT set_id, sizednat.vbit_to_hbig(vbit) as hidbit_nat, vbit 
  FROM (
    select 1 as set_id, x::bit(3)::varbit AS vbit from generate_series(1, 7) t(x) 
    UNION select 2, x::bit(4)::varbit AS vbit from generate_series(16, 31) t(x) 
    UNION select 3, x::bit(9)::varbit AS vbit from generate_series(1024, 1026) t(x) 
    UNION select 4, x::bit(12)::varbit AS vbit from generate_series(1023, 1025) t(x)
    UNION select 5, strbit_to_vbit(x) from (
        SELECT unnest(array['0', '00', '000', '0000', '00000', '000000', '0000000', 
           '00000000', '00000001', '0000001', '00000010', '00000011', 
	   '000001', '0000010', '00000100', '00000101'
	])) t(x)
  ) t2
; -- select * from sizednat.sample1; -- 44 uniques rows + 1 duplicated row

-- atributos:
select vbit, pref, len, len-pref as sobra, suf from (SELECT hidbit_nat, vbit, sizednat.prefix_length(vbit) as pref, length(vbit::text) as len, sizednat.sufix_nonzero_toint(vbit) as suf
FROM sizednat.sample1
where set_id=5
) t order by 1
;

SELECT x, vbit, varbit_to_bigint(vbit) as x_hint,
   sizednat.vbit_to_baseh(vbit) as natcode_base4h,
   sizednat.vbit_to_baseh(vbit,16) as natcode_base16h
FROM sizednat.sample1;

Ordem esperada:

    (1,0)	    0                        ?
    (2,0)	    00                       0
    (3,0)	    000                      ?
    (4,0)	    0000                     00
    (5,0)	    00000                    ?
    (6,0)	    000000                   000
    (7,0)	    0000000                  ?
    (8,0)	    00000000                 0000
    (8,1)	    00000001                 0001
    (7,1)	    0000001                  ?
    (8,2)	    00000010                 0002
    (8,3)	    00000011                 0003
    (6,1)	    000001                   001
    (7,2)	    0000010                  ?
    (8,4)	    00000100                 0010
    (8,5)	    00000101                 0011

Atributos para conferir a ordem:

vbit	pref	len	sobra	suf
0	1	1	0	0
00	2	2	0	0
000	3	3	0	0
0000	4	4	0	0
00000	5	5	0	0
000000	6	6	0	0
0000000	7	7	0	0
00000000	8	8	0	0
00000001	7	8	1	1
0000001	6	7	1	1
00000010	6	8	2	2
00000011	6	8	2	3
000001	5	6	1	1
0000010	5	7	2	2
00000100	5	8	3	4
00000101	5	8	3	5

Algoritmo: CASE WHEN sobra1=sobra2 THEN (val1>val2) ELSE pref1<pref2 END

WITH samp AS (
  select vbit, pref, len, len-pref as sobra, suf
  from (
    SELECT hidbit_nat, vbit, sizednat.prefix_length(vbit) as pref, length(vbit::text) as len,
          sizednat.sufix_nonzero_toint(vbit) as suf
    FROM sizednat.sample1
    where set_id=5
  ) t order by 1
)
SELECT vbit1, vbit2, s1_isbigger, s1_isbigger=cmp_parts cmp_isworking
FROM (
  SELECT s1.vbit as vbit1, s2.vbit as vbit2, s1.vbit>s2.vbit as s1_isbigger,
    CASE -- cmp algorithm:
       WHEN s1.sobra=0 THEN
            CASE WHEN s2.sobra=0 THEN s1.pref > s2.pref ELSE false END
       WHEN s2.sobra=0 THEN true
       WHEN s1.pref=s2.pref THEN
            CASE WHEN s1.len=s2.len THEN s1.suf > s2.suf ELSE s1.len > s2.len END
       ELSE s1.pref < s2.pref
    END cmp_parts
  FROM samp s1, samp s2
  WHERE s1.vbit!=s2.vbit
) tt
WHERE s1_isbigger!=cmp_parts; -- check no error

---

Benchmark to show slow comparison on bit strings

create table testvbit AS
  select x::bit(16)::varbit as x_bitstr, x as x_int from generate_series(0,65500) t(x)
  UNION
  select x::bit(30)::varbit as x_bitstr, x as x_int from generate_series(60000, 1000000) t(x)
  UNION
  select x::bit(32)::varbit as x_bitstr, x as x_int from generate_series(900000, 5000000) t(x)
  UNION
  select x::bit(40)::varbit as x_bitstr, x as x_int from generate_series(4900000, 9000000) t(x)
;

explain analyse select * FROM testvbit ORDER BY x_bitstr desc limit 1;  -- Execution Time: ~1660 ms
explain analyse select * FROM testvbit ORDER BY x_int    desc limit 1;  -- Execution Time: ~1250 ms
explain analyse select * FROM testvbit ORDER BY x_bitstr desc limit 5;  -- Execution Time: ~3500 ms
explain analyse select * FROM testvbit ORDER BY x_int    desc limit 5;  -- Execution Time: ~1500 ms
explain analyse select * FROM testvbit ORDER BY x_bitstr desc limit 9000;  -- Execution Time: ~12617 ms
explain analyse select * FROM testvbit ORDER BY x_int    desc limit 9000;  -- Execution Time: ~2182 ms

explain analyse select * FROM testvbit ORDER BY x_bitstr limit 1;    -- 1643 ms
explain analyse select * FROM testvbit ORDER BY x_int limit 1;       -- 1266 ms
explain analyse select * FROM testvbit ORDER BY x_bitstr limit 9000; -- 2396 ms
explain analyse select * FROM testvbit ORDER BY x_int    limit 9000; -- 1540 ms

-- numerical comparison is ~3x faster (33% of the lexicographical time)

-- no print time, 

explain analyse select count(*) from ( select * FROM testvbit ORDER BY x_bitstr desc limit 9000 ) t; -- 12803
explain analyse select count(*) from ( select * FROM testvbit ORDER BY x_bitstr      limit 9000 ) t; -- 2109
explain analyse select count(*) from ( select * FROM testvbit ORDER BY x_int desc limit 1) t; -- 1562
explain analyse select count(*) from ( select * FROM testvbit ORDER BY x_int      limit 1) t; -- 1602