Add sort support routine for the inet data type.

Add sort support for inet, including support for abbreviated keys.
Testing has shown that this reduces the time taken to sort medium to
large inet/cidr inputs by ~50-60% in realistic cases.

Author: Brandur Leach
Reviewed-By: Peter Geoghegan, Edmund Horner
Discussion: https://postgr.es/m/CABR_9B-PQ8o2MZNJ88wo6r-NxW2EFG70M96Wmcgf99G6HUQ3sw@mail.gmail.com

2 files changed, 284 insertions, 0 deletions

diff --git a/src/test/regress/expected/inet.out b/src/test/regress/expected/inet.out
index 24202376f19..12df25fe9d5 100644
--- a/src/test/regress/expected/inet.out
+++ b/src/test/regress/expected/inet.out
@@ -845,3 +845,192 @@ SELECT inet_merge(c, i) FROM INET_TBL WHERE inet_same_family(c, i);
  ::/24
 (17 rows)
 
+-- Test inet sortsupport with a variety of boundary inputs:
+SELECT a FROM (VALUES
+  ('0.0.0.0/0'::inet),
+  ('0.0.0.0/1'::inet),
+  ('0.0.0.0/32'::inet),
+  ('0.0.0.1/0'::inet),
+  ('0.0.0.1/1'::inet),
+  ('127.126.127.127/0'::inet),
+  ('127.127.127.127/0'::inet),
+  ('127.128.127.127/0'::inet),
+  ('192.168.1.0/24'::inet),
+  ('192.168.1.0/25'::inet),
+  ('192.168.1.1/23'::inet),
+  ('192.168.1.1/5'::inet),
+  ('192.168.1.1/6'::inet),
+  ('192.168.1.1/25'::inet),
+  ('192.168.1.2/25'::inet),
+  ('192.168.1.1/26'::inet),
+  ('192.168.1.2/26'::inet),
+  ('192.168.1.2/23'::inet),
+  ('192.168.1.255/5'::inet),
+  ('192.168.1.255/6'::inet),
+  ('192.168.1.3/1'::inet),
+  ('192.168.1.3/23'::inet),
+  ('192.168.1.4/0'::inet),
+  ('192.168.1.5/0'::inet),
+  ('255.0.0.0/0'::inet),
+  ('255.1.0.0/0'::inet),
+  ('255.2.0.0/0'::inet),
+  ('255.255.000.000/0'::inet),
+  ('255.255.000.000/0'::inet),
+  ('255.255.000.000/15'::inet),
+  ('255.255.000.000/16'::inet),
+  ('255.255.255.254/32'::inet),
+  ('255.255.255.000/32'::inet),
+  ('255.255.255.001/31'::inet),
+  ('255.255.255.002/31'::inet),
+  ('255.255.255.003/31'::inet),
+  ('255.255.255.003/32'::inet),
+  ('255.255.255.001/32'::inet),
+  ('255.255.255.255/0'::inet),
+  ('255.255.255.255/0'::inet),
+  ('255.255.255.255/0'::inet),
+  ('255.255.255.255/1'::inet),
+  ('255.255.255.255/16'::inet),
+  ('255.255.255.255/16'::inet),
+  ('255.255.255.255/31'::inet),
+  ('255.255.255.255/32'::inet),
+  ('255.255.255.253/32'::inet),
+  ('255.255.255.252/32'::inet),
+  ('255.3.0.0/0'::inet),
+  ('0000:0000:0000:0000:0000:0000:0000:0000/0'::inet),
+  ('0000:0000:0000:0000:0000:0000:0000:0000/128'::inet),
+  ('0000:0000:0000:0000:0000:0000:0000:0001/128'::inet),
+  ('10:23::f1/64'::inet),
+  ('10:23::f1/65'::inet),
+  ('10:23::ffff'::inet),
+  ('127::1'::inet),
+  ('127::2'::inet),
+  ('8000:0000:0000:0000:0000:0000:0000:0000/1'::inet),
+  ('::1:ffff:ffff:ffff:ffff/128'::inet),
+  ('::2:ffff:ffff:ffff:ffff/128'::inet),
+  ('::4:3:2:0/24'::inet),
+  ('::4:3:2:1/24'::inet),
+  ('::4:3:2:2/24'::inet),
+  ('ffff:83e7:f118:57dc:6093:6d92:689d:58cf/70'::inet),
+  ('ffff:84b0:4775:536e:c3ed:7116:a6d6:34f0/44'::inet),
+  ('ffff:8566:f84:5867:47f1:7867:d2ba:8a1a/69'::inet),
+  ('ffff:8883:f028:7d2:4d68:d510:7d6b:ac43/73'::inet),
+  ('ffff:8ae8:7c14:65b3:196:8e4a:89ae:fb30/89'::inet),
+  ('ffff:8dd0:646:694c:7c16:7e35:6a26:171/104'::inet),
+  ('ffff:8eef:cbf:700:eda3:ae32:f4b4:318b/121'::inet),
+  ('ffff:90e7:e744:664:a93:8efe:1f25:7663/122'::inet),
+  ('ffff:9597:c69c:8b24:57a:8639:ec78:6026/111'::inet),
+  ('ffff:9e86:79ea:f16e:df31:8e4d:7783:532e/88'::inet),
+  ('ffff:a0c7:82d3:24de:f762:6e1f:316d:3fb2/23'::inet),
+  ('ffff:fffa:ffff:ffff:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:fffb:ffff:ffff:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:fffc:ffff:ffff:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:fffd:ffff:ffff:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:fffe:ffff:ffff:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:fffa:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:fffb:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:fffc:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:fffd::/128'::inet),
+  ('ffff:ffff:ffff:fffd:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:fffe::/128'::inet),
+  ('ffff:ffff:ffff:fffe:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:ffff:4:3:2:0/24'::inet),
+  ('ffff:ffff:ffff:ffff:4:3:2:1/24'::inet),
+  ('ffff:ffff:ffff:ffff:4:3:2:2/24'::inet),
+  ('ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff/128'::inet)
+) AS i(a) ORDER BY a;
+                     a                      
+--------------------------------------------
+ 0.0.0.0/0
+ 0.0.0.1/0
+ 127.126.127.127/0
+ 127.127.127.127/0
+ 127.128.127.127/0
+ 192.168.1.4/0
+ 192.168.1.5/0
+ 255.0.0.0/0
+ 255.1.0.0/0
+ 255.2.0.0/0
+ 255.3.0.0/0
+ 255.255.0.0/0
+ 255.255.0.0/0
+ 255.255.255.255/0
+ 255.255.255.255/0
+ 255.255.255.255/0
+ 0.0.0.0/1
+ 0.0.0.1/1
+ 0.0.0.0
+ 192.168.1.3/1
+ 255.255.255.255/1
+ 192.168.1.1/5
+ 192.168.1.255/5
+ 192.168.1.1/6
+ 192.168.1.255/6
+ 192.168.1.1/23
+ 192.168.1.2/23
+ 192.168.1.3/23
+ 192.168.1.0/24
+ 192.168.1.0/25
+ 192.168.1.1/25
+ 192.168.1.2/25
+ 192.168.1.1/26
+ 192.168.1.2/26
+ 255.255.0.0/15
+ 255.255.0.0/16
+ 255.255.255.255/16
+ 255.255.255.255/16
+ 255.255.255.1/31
+ 255.255.255.0
+ 255.255.255.1
+ 255.255.255.2/31
+ 255.255.255.3/31
+ 255.255.255.3
+ 255.255.255.252
+ 255.255.255.253
+ 255.255.255.255/31
+ 255.255.255.254
+ 255.255.255.255
+ ::/0
+ ffff:fffa:ffff:ffff:ffff:ffff:ffff:ffff/0
+ ffff:fffb:ffff:ffff:ffff:ffff:ffff:ffff/0
+ ffff:fffc:ffff:ffff:ffff:ffff:ffff:ffff/0
+ ffff:fffd:ffff:ffff:ffff:ffff:ffff:ffff/0
+ ffff:fffe:ffff:ffff:ffff:ffff:ffff:ffff/0
+ ffff:ffff:ffff:fffa:ffff:ffff:ffff:ffff/0
+ ffff:ffff:ffff:fffb:ffff:ffff:ffff:ffff/0
+ ffff:ffff:ffff:fffc:ffff:ffff:ffff:ffff/0
+ ffff:ffff:ffff:fffd:ffff:ffff:ffff:ffff/0
+ ffff:ffff:ffff:fffe:ffff:ffff:ffff:ffff/0
+ ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff/0
+ ::4:3:2:0/24
+ ::4:3:2:1/24
+ ::4:3:2:2/24
+ ::
+ ::1
+ ::1:ffff:ffff:ffff:ffff
+ ::2:ffff:ffff:ffff:ffff
+ 10:23::f1/64
+ 10:23::f1/65
+ 10:23::ffff
+ 127::1
+ 127::2
+ 8000::/1
+ ffff:83e7:f118:57dc:6093:6d92:689d:58cf/70
+ ffff:84b0:4775:536e:c3ed:7116:a6d6:34f0/44
+ ffff:8566:f84:5867:47f1:7867:d2ba:8a1a/69
+ ffff:8883:f028:7d2:4d68:d510:7d6b:ac43/73
+ ffff:8ae8:7c14:65b3:196:8e4a:89ae:fb30/89
+ ffff:8dd0:646:694c:7c16:7e35:6a26:171/104
+ ffff:8eef:cbf:700:eda3:ae32:f4b4:318b/121
+ ffff:90e7:e744:664:a93:8efe:1f25:7663/122
+ ffff:9597:c69c:8b24:57a:8639:ec78:6026/111
+ ffff:9e86:79ea:f16e:df31:8e4d:7783:532e/88
+ ffff:a0c7:82d3:24de:f762:6e1f:316d:3fb2/23
+ ffff:ffff:ffff:ffff:4:3:2:0/24
+ ffff:ffff:ffff:ffff:4:3:2:1/24
+ ffff:ffff:ffff:ffff:4:3:2:2/24
+ ffff:ffff:ffff:fffd::
+ ffff:ffff:ffff:fffe::
+ ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff
+(91 rows)
+
diff --git a/src/test/regress/sql/inet.sql b/src/test/regress/sql/inet.sql
index bbfa9d37dfc..c8ef4db7f2b 100644
--- a/src/test/regress/sql/inet.sql
+++ b/src/test/regress/sql/inet.sql
@@ -156,3 +156,98 @@ INSERT INTO INET_TBL (c, i) VALUES ('10', '10::/8');
 SELECT inet_merge(c, i) FROM INET_TBL;
 -- fix it by inet_same_family() condition
 SELECT inet_merge(c, i) FROM INET_TBL WHERE inet_same_family(c, i);
+
+-- Test inet sortsupport with a variety of boundary inputs:
+SELECT a FROM (VALUES
+  ('0.0.0.0/0'::inet),
+  ('0.0.0.0/1'::inet),
+  ('0.0.0.0/32'::inet),
+  ('0.0.0.1/0'::inet),
+  ('0.0.0.1/1'::inet),
+  ('127.126.127.127/0'::inet),
+  ('127.127.127.127/0'::inet),
+  ('127.128.127.127/0'::inet),
+  ('192.168.1.0/24'::inet),
+  ('192.168.1.0/25'::inet),
+  ('192.168.1.1/23'::inet),
+  ('192.168.1.1/5'::inet),
+  ('192.168.1.1/6'::inet),
+  ('192.168.1.1/25'::inet),
+  ('192.168.1.2/25'::inet),
+  ('192.168.1.1/26'::inet),
+  ('192.168.1.2/26'::inet),
+  ('192.168.1.2/23'::inet),
+  ('192.168.1.255/5'::inet),
+  ('192.168.1.255/6'::inet),
+  ('192.168.1.3/1'::inet),
+  ('192.168.1.3/23'::inet),
+  ('192.168.1.4/0'::inet),
+  ('192.168.1.5/0'::inet),
+  ('255.0.0.0/0'::inet),
+  ('255.1.0.0/0'::inet),
+  ('255.2.0.0/0'::inet),
+  ('255.255.000.000/0'::inet),
+  ('255.255.000.000/0'::inet),
+  ('255.255.000.000/15'::inet),
+  ('255.255.000.000/16'::inet),
+  ('255.255.255.254/32'::inet),
+  ('255.255.255.000/32'::inet),
+  ('255.255.255.001/31'::inet),
+  ('255.255.255.002/31'::inet),
+  ('255.255.255.003/31'::inet),
+  ('255.255.255.003/32'::inet),
+  ('255.255.255.001/32'::inet),
+  ('255.255.255.255/0'::inet),
+  ('255.255.255.255/0'::inet),
+  ('255.255.255.255/0'::inet),
+  ('255.255.255.255/1'::inet),
+  ('255.255.255.255/16'::inet),
+  ('255.255.255.255/16'::inet),
+  ('255.255.255.255/31'::inet),
+  ('255.255.255.255/32'::inet),
+  ('255.255.255.253/32'::inet),
+  ('255.255.255.252/32'::inet),
+  ('255.3.0.0/0'::inet),
+  ('0000:0000:0000:0000:0000:0000:0000:0000/0'::inet),
+  ('0000:0000:0000:0000:0000:0000:0000:0000/128'::inet),
+  ('0000:0000:0000:0000:0000:0000:0000:0001/128'::inet),
+  ('10:23::f1/64'::inet),
+  ('10:23::f1/65'::inet),
+  ('10:23::ffff'::inet),
+  ('127::1'::inet),
+  ('127::2'::inet),
+  ('8000:0000:0000:0000:0000:0000:0000:0000/1'::inet),
+  ('::1:ffff:ffff:ffff:ffff/128'::inet),
+  ('::2:ffff:ffff:ffff:ffff/128'::inet),
+  ('::4:3:2:0/24'::inet),
+  ('::4:3:2:1/24'::inet),
+  ('::4:3:2:2/24'::inet),
+  ('ffff:83e7:f118:57dc:6093:6d92:689d:58cf/70'::inet),
+  ('ffff:84b0:4775:536e:c3ed:7116:a6d6:34f0/44'::inet),
+  ('ffff:8566:f84:5867:47f1:7867:d2ba:8a1a/69'::inet),
+  ('ffff:8883:f028:7d2:4d68:d510:7d6b:ac43/73'::inet),
+  ('ffff:8ae8:7c14:65b3:196:8e4a:89ae:fb30/89'::inet),
+  ('ffff:8dd0:646:694c:7c16:7e35:6a26:171/104'::inet),
+  ('ffff:8eef:cbf:700:eda3:ae32:f4b4:318b/121'::inet),
+  ('ffff:90e7:e744:664:a93:8efe:1f25:7663/122'::inet),
+  ('ffff:9597:c69c:8b24:57a:8639:ec78:6026/111'::inet),
+  ('ffff:9e86:79ea:f16e:df31:8e4d:7783:532e/88'::inet),
+  ('ffff:a0c7:82d3:24de:f762:6e1f:316d:3fb2/23'::inet),
+  ('ffff:fffa:ffff:ffff:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:fffb:ffff:ffff:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:fffc:ffff:ffff:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:fffd:ffff:ffff:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:fffe:ffff:ffff:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:fffa:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:fffb:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:fffc:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:fffd::/128'::inet),
+  ('ffff:ffff:ffff:fffd:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:fffe::/128'::inet),
+  ('ffff:ffff:ffff:fffe:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:ffff:4:3:2:0/24'::inet),
+  ('ffff:ffff:ffff:ffff:4:3:2:1/24'::inet),
+  ('ffff:ffff:ffff:ffff:4:3:2:2/24'::inet),
+  ('ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff/0'::inet),
+  ('ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff/128'::inet)
+) AS i(a) ORDER BY a;