PostgreSQL Source Code  git master
network_spgist.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * network_spgist.c
4  * SP-GiST support for network types.
5  *
6  * We split inet index entries first by address family (IPv4 or IPv6).
7  * If the entries below a given inner tuple are all of the same family,
8  * we identify their common prefix and split by the next bit of the address,
9  * and by whether their masklens exceed the length of the common prefix.
10  *
11  * An inner tuple that has both IPv4 and IPv6 children has a null prefix
12  * and exactly two nodes, the first being for IPv4 and the second for IPv6.
13  *
14  * Otherwise, the prefix is a CIDR value representing the common prefix,
15  * and there are exactly four nodes. Node numbers 0 and 1 are for addresses
16  * with the same masklen as the prefix, while node numbers 2 and 3 are for
17  * addresses with larger masklen. (We do not allow a tuple to contain
18  * entries with masklen smaller than its prefix's.) Node numbers 0 and 1
19  * are distinguished by the next bit of the address after the common prefix,
20  * and likewise for node numbers 2 and 3. If there are no more bits in
21  * the address family, everything goes into node 0 (which will probably
22  * lead to creating an allTheSame tuple).
23  *
24  * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
25  * Portions Copyright (c) 1994, Regents of the University of California
26  *
27  * IDENTIFICATION
28  * src/backend/utils/adt/network_spgist.c
29  *
30  *-------------------------------------------------------------------------
31  */
32 #include "postgres.h"
33 
34 #include <sys/socket.h>
35 
36 #include "access/spgist.h"
37 #include "catalog/pg_type.h"
38 #include "utils/builtins.h"
39 #include "utils/inet.h"
40 #include "varatt.h"
41 
42 
43 static int inet_spg_node_number(const inet *val, int commonbits);
44 static int inet_spg_consistent_bitmap(const inet *prefix, int nkeys,
45  ScanKey scankeys, bool leaf);
46 
47 /*
48  * The SP-GiST configuration function
49  */
50 Datum
52 {
53  /* spgConfigIn *cfgin = (spgConfigIn *) PG_GETARG_POINTER(0); */
55 
56  cfg->prefixType = CIDROID;
57  cfg->labelType = VOIDOID;
58  cfg->canReturnData = true;
59  cfg->longValuesOK = false;
60 
62 }
63 
64 /*
65  * The SP-GiST choose function
66  */
67 Datum
69 {
72  inet *val = DatumGetInetPP(in->datum),
73  *prefix;
74  int commonbits;
75 
76  /*
77  * If we're looking at a tuple that splits by address family, choose the
78  * appropriate subnode.
79  */
80  if (!in->hasPrefix)
81  {
82  /* allTheSame isn't possible for such a tuple */
83  Assert(!in->allTheSame);
84  Assert(in->nNodes == 2);
85 
86  out->resultType = spgMatchNode;
87  out->result.matchNode.nodeN = (ip_family(val) == PGSQL_AF_INET) ? 0 : 1;
88  out->result.matchNode.restDatum = InetPGetDatum(val);
89 
91  }
92 
93  /* Else it must split by prefix */
94  Assert(in->nNodes == 4 || in->allTheSame);
95 
96  prefix = DatumGetInetPP(in->prefixDatum);
97  commonbits = ip_bits(prefix);
98 
99  /*
100  * We cannot put addresses from different families under the same inner
101  * node, so we have to split if the new value's family is different.
102  */
103  if (ip_family(val) != ip_family(prefix))
104  {
105  /* Set up 2-node tuple */
106  out->resultType = spgSplitTuple;
107  out->result.splitTuple.prefixHasPrefix = false;
108  out->result.splitTuple.prefixNNodes = 2;
109  out->result.splitTuple.prefixNodeLabels = NULL;
110 
111  /* Identify which node the existing data goes into */
112  out->result.splitTuple.childNodeN =
113  (ip_family(prefix) == PGSQL_AF_INET) ? 0 : 1;
114 
115  out->result.splitTuple.postfixHasPrefix = true;
116  out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix);
117 
118  PG_RETURN_VOID();
119  }
120 
121  /*
122  * If the new value does not match the existing prefix, we have to split.
123  */
124  if (ip_bits(val) < commonbits ||
125  bitncmp(ip_addr(prefix), ip_addr(val), commonbits) != 0)
126  {
127  /* Determine new prefix length for the split tuple */
128  commonbits = bitncommon(ip_addr(prefix), ip_addr(val),
129  Min(ip_bits(val), commonbits));
130 
131  /* Set up 4-node tuple */
132  out->resultType = spgSplitTuple;
133  out->result.splitTuple.prefixHasPrefix = true;
134  out->result.splitTuple.prefixPrefixDatum =
136  out->result.splitTuple.prefixNNodes = 4;
137  out->result.splitTuple.prefixNodeLabels = NULL;
138 
139  /* Identify which node the existing data goes into */
140  out->result.splitTuple.childNodeN =
141  inet_spg_node_number(prefix, commonbits);
142 
143  out->result.splitTuple.postfixHasPrefix = true;
144  out->result.splitTuple.postfixPrefixDatum = InetPGetDatum(prefix);
145 
146  PG_RETURN_VOID();
147  }
148 
149  /*
150  * All OK, choose the node to descend into. (If this tuple is marked
151  * allTheSame, the core code will ignore our choice of nodeN; but we need
152  * not account for that case explicitly here.)
153  */
154  out->resultType = spgMatchNode;
155  out->result.matchNode.nodeN = inet_spg_node_number(val, commonbits);
156  out->result.matchNode.restDatum = InetPGetDatum(val);
157 
158  PG_RETURN_VOID();
159 }
160 
161 /*
162  * The GiST PickSplit method
163  */
164 Datum
166 {
169  inet *prefix,
170  *tmp;
171  int i,
172  commonbits;
173  bool differentFamilies = false;
174 
175  /* Initialize the prefix with the first item */
176  prefix = DatumGetInetPP(in->datums[0]);
177  commonbits = ip_bits(prefix);
178 
179  /* Examine remaining items to discover minimum common prefix length */
180  for (i = 1; i < in->nTuples; i++)
181  {
182  tmp = DatumGetInetPP(in->datums[i]);
183 
184  if (ip_family(tmp) != ip_family(prefix))
185  {
186  differentFamilies = true;
187  break;
188  }
189 
190  if (ip_bits(tmp) < commonbits)
191  commonbits = ip_bits(tmp);
192  commonbits = bitncommon(ip_addr(prefix), ip_addr(tmp), commonbits);
193  if (commonbits == 0)
194  break;
195  }
196 
197  /* Don't need labels; allocate output arrays */
198  out->nodeLabels = NULL;
199  out->mapTuplesToNodes = (int *) palloc(sizeof(int) * in->nTuples);
200  out->leafTupleDatums = (Datum *) palloc(sizeof(Datum) * in->nTuples);
201 
202  if (differentFamilies)
203  {
204  /* Set up 2-node tuple */
205  out->hasPrefix = false;
206  out->nNodes = 2;
207 
208  for (i = 0; i < in->nTuples; i++)
209  {
210  tmp = DatumGetInetPP(in->datums[i]);
211  out->mapTuplesToNodes[i] =
212  (ip_family(tmp) == PGSQL_AF_INET) ? 0 : 1;
213  out->leafTupleDatums[i] = InetPGetDatum(tmp);
214  }
215  }
216  else
217  {
218  /* Set up 4-node tuple */
219  out->hasPrefix = true;
220  out->prefixDatum =
221  InetPGetDatum(cidr_set_masklen_internal(prefix, commonbits));
222  out->nNodes = 4;
223 
224  for (i = 0; i < in->nTuples; i++)
225  {
226  tmp = DatumGetInetPP(in->datums[i]);
227  out->mapTuplesToNodes[i] = inet_spg_node_number(tmp, commonbits);
228  out->leafTupleDatums[i] = InetPGetDatum(tmp);
229  }
230  }
231 
232  PG_RETURN_VOID();
233 }
234 
235 /*
236  * The SP-GiST query consistency check for inner tuples
237  */
238 Datum
240 {
243  int i;
244  int which;
245 
246  if (!in->hasPrefix)
247  {
248  Assert(!in->allTheSame);
249  Assert(in->nNodes == 2);
250 
251  /* Identify which child nodes need to be visited */
252  which = 1 | (1 << 1);
253 
254  for (i = 0; i < in->nkeys; i++)
255  {
256  StrategyNumber strategy = in->scankeys[i].sk_strategy;
257  inet *argument = DatumGetInetPP(in->scankeys[i].sk_argument);
258 
259  switch (strategy)
260  {
263  if (ip_family(argument) == PGSQL_AF_INET)
264  which &= 1;
265  break;
266 
269  if (ip_family(argument) == PGSQL_AF_INET6)
270  which &= (1 << 1);
271  break;
272 
274  break;
275 
276  default:
277  /* all other ops can only match addrs of same family */
278  if (ip_family(argument) == PGSQL_AF_INET)
279  which &= 1;
280  else
281  which &= (1 << 1);
282  break;
283  }
284  }
285  }
286  else if (!in->allTheSame)
287  {
288  Assert(in->nNodes == 4);
289 
290  /* Identify which child nodes need to be visited */
292  in->nkeys, in->scankeys, false);
293  }
294  else
295  {
296  /* Must visit all nodes; we assume there are less than 32 of 'em */
297  which = ~0;
298  }
299 
300  out->nNodes = 0;
301 
302  if (which)
303  {
304  out->nodeNumbers = (int *) palloc(sizeof(int) * in->nNodes);
305 
306  for (i = 0; i < in->nNodes; i++)
307  {
308  if (which & (1 << i))
309  {
310  out->nodeNumbers[out->nNodes] = i;
311  out->nNodes++;
312  }
313  }
314  }
315 
316  PG_RETURN_VOID();
317 }
318 
319 /*
320  * The SP-GiST query consistency check for leaf tuples
321  */
322 Datum
324 {
327  inet *leaf = DatumGetInetPP(in->leafDatum);
328 
329  /* All tests are exact. */
330  out->recheck = false;
331 
332  /* Leaf is what it is... */
333  out->leafValue = InetPGetDatum(leaf);
334 
335  /* Use common code to apply the tests. */
337  true));
338 }
339 
340 /*
341  * Calculate node number (within a 4-node, single-family inner index tuple)
342  *
343  * The value must have the same family as the node's prefix, and
344  * commonbits is the mask length of the prefix. We use even or odd
345  * nodes according to the next address bit after the commonbits,
346  * and low or high nodes according to whether the value's mask length
347  * is larger than commonbits.
348  */
349 static int
350 inet_spg_node_number(const inet *val, int commonbits)
351 {
352  int nodeN = 0;
353 
354  if (commonbits < ip_maxbits(val) &&
355  ip_addr(val)[commonbits / 8] & (1 << (7 - commonbits % 8)))
356  nodeN |= 1;
357  if (commonbits < ip_bits(val))
358  nodeN |= 2;
359 
360  return nodeN;
361 }
362 
363 /*
364  * Calculate bitmap of node numbers that are consistent with the query
365  *
366  * This can be used either at a 4-way inner tuple, or at a leaf tuple.
367  * In the latter case, we should return a boolean result (0 or 1)
368  * not a bitmap.
369  *
370  * This definition is pretty odd, but the inner and leaf consistency checks
371  * are mostly common and it seems best to keep them in one function.
372  */
373 static int
374 inet_spg_consistent_bitmap(const inet *prefix, int nkeys, ScanKey scankeys,
375  bool leaf)
376 {
377  int bitmap;
378  int commonbits,
379  i;
380 
381  /* Initialize result to allow visiting all children */
382  if (leaf)
383  bitmap = 1;
384  else
385  bitmap = 1 | (1 << 1) | (1 << 2) | (1 << 3);
386 
387  commonbits = ip_bits(prefix);
388 
389  for (i = 0; i < nkeys; i++)
390  {
391  inet *argument = DatumGetInetPP(scankeys[i].sk_argument);
392  StrategyNumber strategy = scankeys[i].sk_strategy;
393  int order;
394 
395  /*
396  * Check 0: different families
397  *
398  * Matching families do not help any of the strategies.
399  */
400  if (ip_family(argument) != ip_family(prefix))
401  {
402  switch (strategy)
403  {
406  if (ip_family(argument) < ip_family(prefix))
407  bitmap = 0;
408  break;
409 
412  if (ip_family(argument) > ip_family(prefix))
413  bitmap = 0;
414  break;
415 
417  break;
418 
419  default:
420  /* For all other cases, we can be sure there is no match */
421  bitmap = 0;
422  break;
423  }
424 
425  if (!bitmap)
426  break;
427 
428  /* Other checks make no sense with different families. */
429  continue;
430  }
431 
432  /*
433  * Check 1: network bit count
434  *
435  * Network bit count (ip_bits) helps to check leaves for sub network
436  * and sup network operators. At non-leaf nodes, we know every child
437  * value has greater ip_bits, so we can avoid descending in some cases
438  * too.
439  *
440  * This check is less expensive than checking the address bits, so we
441  * are doing this before, but it has to be done after for the basic
442  * comparison strategies, because ip_bits only affect their results
443  * when the common network bits are the same.
444  */
445  switch (strategy)
446  {
447  case RTSubStrategyNumber:
448  if (commonbits <= ip_bits(argument))
449  bitmap &= (1 << 2) | (1 << 3);
450  break;
451 
453  if (commonbits < ip_bits(argument))
454  bitmap &= (1 << 2) | (1 << 3);
455  break;
456 
458  if (commonbits == ip_bits(argument) - 1)
459  bitmap &= 1 | (1 << 1);
460  else if (commonbits >= ip_bits(argument))
461  bitmap = 0;
462  break;
463 
465  if (commonbits == ip_bits(argument))
466  bitmap &= 1 | (1 << 1);
467  else if (commonbits > ip_bits(argument))
468  bitmap = 0;
469  break;
470 
472  if (commonbits < ip_bits(argument))
473  bitmap &= (1 << 2) | (1 << 3);
474  else if (commonbits == ip_bits(argument))
475  bitmap &= 1 | (1 << 1);
476  else
477  bitmap = 0;
478  break;
479  }
480 
481  if (!bitmap)
482  break;
483 
484  /*
485  * Check 2: common network bits
486  *
487  * Compare available common prefix bits to the query, but not beyond
488  * either the query's netmask or the minimum netmask among the
489  * represented values. If these bits don't match the query, we can
490  * eliminate some cases.
491  */
492  order = bitncmp(ip_addr(prefix), ip_addr(argument),
493  Min(commonbits, ip_bits(argument)));
494 
495  if (order != 0)
496  {
497  switch (strategy)
498  {
501  if (order > 0)
502  bitmap = 0;
503  break;
504 
507  if (order < 0)
508  bitmap = 0;
509  break;
510 
512  break;
513 
514  default:
515  /* For all other cases, we can be sure there is no match */
516  bitmap = 0;
517  break;
518  }
519 
520  if (!bitmap)
521  break;
522 
523  /*
524  * Remaining checks make no sense when common bits don't match.
525  */
526  continue;
527  }
528 
529  /*
530  * Check 3: next network bit
531  *
532  * We can filter out branch 2 or 3 using the next network bit of the
533  * argument, if it is available.
534  *
535  * This check matters for the performance of the search. The results
536  * would be correct without it.
537  */
538  if (bitmap & ((1 << 2) | (1 << 3)) &&
539  commonbits < ip_bits(argument))
540  {
541  int nextbit;
542 
543  nextbit = ip_addr(argument)[commonbits / 8] &
544  (1 << (7 - commonbits % 8));
545 
546  switch (strategy)
547  {
550  if (!nextbit)
551  bitmap &= 1 | (1 << 1) | (1 << 2);
552  break;
553 
556  if (nextbit)
557  bitmap &= 1 | (1 << 1) | (1 << 3);
558  break;
559 
561  break;
562 
563  default:
564  if (!nextbit)
565  bitmap &= 1 | (1 << 1) | (1 << 2);
566  else
567  bitmap &= 1 | (1 << 1) | (1 << 3);
568  break;
569  }
570 
571  if (!bitmap)
572  break;
573  }
574 
575  /*
576  * Remaining checks are only for the basic comparison strategies. This
577  * test relies on the strategy number ordering defined in stratnum.h.
578  */
579  if (strategy < RTEqualStrategyNumber ||
580  strategy > RTGreaterEqualStrategyNumber)
581  continue;
582 
583  /*
584  * Check 4: network bit count
585  *
586  * At this point, we know that the common network bits of the prefix
587  * and the argument are the same, so we can go forward and check the
588  * ip_bits.
589  */
590  switch (strategy)
591  {
594  if (commonbits == ip_bits(argument))
595  bitmap &= 1 | (1 << 1);
596  else if (commonbits > ip_bits(argument))
597  bitmap = 0;
598  break;
599 
602  if (commonbits < ip_bits(argument))
603  bitmap &= (1 << 2) | (1 << 3);
604  break;
605  }
606 
607  if (!bitmap)
608  break;
609 
610  /* Remaining checks don't make sense with different ip_bits. */
611  if (commonbits != ip_bits(argument))
612  continue;
613 
614  /*
615  * Check 5: next host bit
616  *
617  * We can filter out branch 0 or 1 using the next host bit of the
618  * argument, if it is available.
619  *
620  * This check matters for the performance of the search. The results
621  * would be correct without it. There is no point in running it for
622  * leafs as we have to check the whole address on the next step.
623  */
624  if (!leaf && bitmap & (1 | (1 << 1)) &&
625  commonbits < ip_maxbits(argument))
626  {
627  int nextbit;
628 
629  nextbit = ip_addr(argument)[commonbits / 8] &
630  (1 << (7 - commonbits % 8));
631 
632  switch (strategy)
633  {
636  if (!nextbit)
637  bitmap &= 1 | (1 << 2) | (1 << 3);
638  break;
639 
642  if (nextbit)
643  bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
644  break;
645 
647  break;
648 
649  default:
650  if (!nextbit)
651  bitmap &= 1 | (1 << 2) | (1 << 3);
652  else
653  bitmap &= (1 << 1) | (1 << 2) | (1 << 3);
654  break;
655  }
656 
657  if (!bitmap)
658  break;
659  }
660 
661  /*
662  * Check 6: whole address
663  *
664  * This is the last check for correctness of the basic comparison
665  * strategies. It's only appropriate at leaf entries.
666  */
667  if (leaf)
668  {
669  /* Redo ordering comparison using all address bits */
670  order = bitncmp(ip_addr(prefix), ip_addr(argument),
671  ip_maxbits(prefix));
672 
673  switch (strategy)
674  {
676  if (order >= 0)
677  bitmap = 0;
678  break;
679 
681  if (order > 0)
682  bitmap = 0;
683  break;
684 
686  if (order != 0)
687  bitmap = 0;
688  break;
689 
691  if (order < 0)
692  bitmap = 0;
693  break;
694 
696  if (order <= 0)
697  bitmap = 0;
698  break;
699 
701  if (order == 0)
702  bitmap = 0;
703  break;
704  }
705 
706  if (!bitmap)
707  break;
708  }
709  }
710 
711  return bitmap;
712 }
#define Min(x, y)
Definition: c.h:988
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
long val
Definition: informix.c:664
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
void * palloc(Size size)
Definition: mcxt.c:1210
int bitncommon(const unsigned char *l, const unsigned char *r, int n)
Definition: network.c:1603
int bitncmp(const unsigned char *l, const unsigned char *r, int n)
Definition: network.c:1569
inet * cidr_set_masklen_internal(const inet *src, int bits)
Definition: network.c:368
Datum inet_spg_config(PG_FUNCTION_ARGS)
Datum inet_spg_choose(PG_FUNCTION_ARGS)
Datum inet_spg_leaf_consistent(PG_FUNCTION_ARGS)
Datum inet_spg_inner_consistent(PG_FUNCTION_ARGS)
static int inet_spg_node_number(const inet *val, int commonbits)
static int inet_spg_consistent_bitmap(const inet *prefix, int nkeys, ScanKey scankeys, bool leaf)
Datum inet_spg_picksplit(PG_FUNCTION_ARGS)
uintptr_t Datum
Definition: postgres.h:64
@ spgMatchNode
Definition: spgist.h:69
@ spgSplitTuple
Definition: spgist.h:71
#define RTNotEqualStrategyNumber
Definition: stratnum.h:69
#define RTSubStrategyNumber
Definition: stratnum.h:74
uint16 StrategyNumber
Definition: stratnum.h:22
#define RTSubEqualStrategyNumber
Definition: stratnum.h:75
#define RTSuperEqualStrategyNumber
Definition: stratnum.h:77
#define RTEqualStrategyNumber
Definition: stratnum.h:68
#define RTLessEqualStrategyNumber
Definition: stratnum.h:71
#define RTGreaterEqualStrategyNumber
Definition: stratnum.h:73
#define RTGreaterStrategyNumber
Definition: stratnum.h:72
#define RTSuperStrategyNumber
Definition: stratnum.h:76
#define RTLessStrategyNumber
Definition: stratnum.h:70
Datum sk_argument
Definition: skey.h:72
StrategyNumber sk_strategy
Definition: skey.h:68
Definition: inet.h:53
bool hasPrefix
Definition: spgist.h:61
Datum prefixDatum
Definition: spgist.h:62
int nNodes
Definition: spgist.h:63
Datum datum
Definition: spgist.h:55
bool allTheSame
Definition: spgist.h:60
spgChooseResultType resultType
Definition: spgist.h:76
struct spgChooseOut::@46::@49 splitTuple
union spgChooseOut::@46 result
struct spgChooseOut::@46::@47 matchNode
bool longValuesOK
Definition: spgist.h:47
bool canReturnData
Definition: spgist.h:46
Oid labelType
Definition: spgist.h:44
Oid prefixType
Definition: spgist.h:43
ScanKey scankeys
Definition: spgist.h:134
ScanKey scankeys
Definition: spgist.h:169
Datum * datums
Definition: spgist.h:113
bool hasPrefix
Definition: spgist.h:119
int * mapTuplesToNodes
Definition: spgist.h:125
Datum * nodeLabels
Definition: spgist.h:123
Datum * leafTupleDatums
Definition: spgist.h:126
Datum prefixDatum
Definition: spgist.h:120
static Datum InetPGetDatum(const inet *X)
Definition: inet.h:129
#define ip_addr(inetptr)
Definition: inet.h:77
#define ip_family(inetptr)
Definition: inet.h:71
#define PGSQL_AF_INET
Definition: inet.h:39
#define PGSQL_AF_INET6
Definition: inet.h:40
static inet * DatumGetInetPP(Datum X)
Definition: inet.h:123
#define ip_maxbits(inetptr)
Definition: inet.h:83
#define ip_bits(inetptr)
Definition: inet.h:74