|
1 | | -$PostgreSQL: pgsql/src/backend/access/nbtree/README,v 1.16 2007/01/09 02:14:10 tgl Exp $ |
| 1 | +$PostgreSQL: pgsql/src/backend/access/nbtree/README,v 1.17 2007/01/12 17:04:54 tgl Exp $ |
2 | 2 |
|
3 | 3 | This directory contains a correct implementation of Lehman and Yao's |
4 | 4 | high-concurrency B-tree management algorithm (P. Lehman and S. Yao, |
@@ -485,4 +485,47 @@ datatypes to supply us with a comparison procedure via pg_amproc. |
485 | 485 | This procedure must take two nonnull values A and B and return an int32 < 0, |
486 | 486 | 0, or > 0 if A < B, A = B, or A > B, respectively. The procedure must |
487 | 487 | not return INT_MIN for "A < B", since the value may be negated before |
488 | | -being tested for sign. See nbtcompare.c for examples. |
| 488 | +being tested for sign. A null result is disallowed, too. See nbtcompare.c |
| 489 | +for examples. |
| 490 | + |
| 491 | +There are some basic assumptions that a btree operator family must satisfy: |
| 492 | + |
| 493 | +An = operator must be an equivalence relation; that is, for all non-null |
| 494 | +values A,B,C of the datatype: |
| 495 | + |
| 496 | +A = A is truereflexive law |
| 497 | +if A = B, then B = Asymmetric law |
| 498 | +if A = B and B = C, then A = Ctransitive law |
| 499 | + |
| 500 | +A < operator must be a strong ordering relation; that is, for all non-null |
| 501 | +values A,B,C: |
| 502 | + |
| 503 | +A < A is falseirreflexive law |
| 504 | +if A < B and B < C, then A < Ctransitive law |
| 505 | + |
| 506 | +Furthermore, the ordering is total; that is, for all non-null values A,B: |
| 507 | + |
| 508 | +exactly one of A < B, A = B, and B < A is truetrichotomy law |
| 509 | + |
| 510 | +(The trichotomy law justifies the definition of the comparison support |
| 511 | +procedure, of course.) |
| 512 | + |
| 513 | +The other three operators are defined in terms of these two in the obvious way, |
| 514 | +and must act consistently with them. |
| 515 | + |
| 516 | +For an operator family supporting multiple datatypes, the above laws must hold |
| 517 | +when A,B,C are taken from any datatypes in the family. The transitive laws |
| 518 | +are the trickiest to ensure, as in cross-type situations they represent |
| 519 | +statements that the behaviors of two or three different operators are |
| 520 | +consistent. As an example, it would not work to put float8 and numeric into |
| 521 | +an opfamily, at least not with the current semantics that numerics are |
| 522 | +converted to float8 for comparison to a float8. Because of the limited |
| 523 | +accuracy of float8, this means there are distinct numeric values that will |
| 524 | +compare equal to the same float8 value, and thus the transitive law fails. |
| 525 | + |
| 526 | +It should be fairly clear why a btree index requires these laws to hold within |
| 527 | +a single datatype: without them there is no ordering to arrange the keys with. |
| 528 | +Also, index searches using a key of a different datatype require comparisons |
| 529 | +to behave sanely across two datatypes. The extensions to three or more |
| 530 | +datatypes within a family are not strictly required by the btree index |
| 531 | +mechanism itself, but the planner relies on them for optimization purposes. |