granicus.if.org Git - postgresql/blob - src/backend/access/gin/ginbulk.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * ginbulk.c
   4  *        routines for fast build of inverted index
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * IDENTIFICATION
  11  *                      $PostgreSQL: pgsql/src/backend/access/gin/ginbulk.c,v 1.11 2008/01/01 19:45:46 momjian Exp $
  12  *-------------------------------------------------------------------------
  13  */
  14
  15 #include "postgres.h"
  16
  17 #include "access/gin.h"
  18 #include "utils/datum.h"
  19 #include "utils/memutils.h"
  20
  21
  22 #define DEF_NENTRY      2048
  23 #define DEF_NPTR        4
  24
  25 void
  26 ginInitBA(BuildAccumulator *accum)
  27 {
  28         accum->maxdepth = 1;
  29         accum->stackpos = 0;
  30         accum->entries = NULL;
  31         accum->stack = NULL;
  32         accum->allocatedMemory = 0;
  33         accum->entryallocator = NULL;
  34 }
  35
  36 static EntryAccumulator *
  37 EAAllocate(BuildAccumulator *accum)
  38 {
  39         if (accum->entryallocator == NULL || accum->length >= DEF_NENTRY)
  40         {
  41                 accum->entryallocator = palloc(sizeof(EntryAccumulator) * DEF_NENTRY);
  42                 accum->allocatedMemory += GetMemoryChunkSpace(accum->entryallocator);
  43                 accum->length = 0;
  44         }
  45
  46         accum->length++;
  47         return accum->entryallocator + accum->length - 1;
  48 }
  49
  50 /*
  51  * Stores heap item pointer. For robust, it checks that
  52  * item pointer are ordered
  53  */
  54 static void
  55 ginInsertData(BuildAccumulator *accum, EntryAccumulator *entry, ItemPointer heapptr)
  56 {
  57         if (entry->number >= entry->length)
  58         {
  59                 accum->allocatedMemory -= GetMemoryChunkSpace(entry->list);
  60                 entry->length *= 2;
  61                 entry->list = (ItemPointerData *) repalloc(entry->list,
  62                                                                         sizeof(ItemPointerData) * entry->length);
  63                 accum->allocatedMemory += GetMemoryChunkSpace(entry->list);
  64         }
  65
  66         if (entry->shouldSort == FALSE)
  67         {
  68                 int                     res = compareItemPointers(entry->list + entry->number - 1, heapptr);
  69
  70                 Assert(res != 0);
  71
  72                 if (res > 0)
  73                         entry->shouldSort = TRUE;
  74         }
  75
  76         entry->list[entry->number] = *heapptr;
  77         entry->number++;
  78 }
  79
  80 /*
  81  * This is basically the same as datumCopy(), but we duplicate some code
  82  * to avoid computing the datum size twice.
  83  */
  84 static Datum
  85 getDatumCopy(BuildAccumulator *accum, Datum value)
  86 {
  87         Form_pg_attribute *att = accum->ginstate->tupdesc->attrs;
  88         Datum           res;
  89
  90         if (att[0]->attbyval)
  91                 res = value;
  92         else
  93         {
  94                 Size            realSize;
  95                 char       *s;
  96
  97                 realSize = datumGetSize(value, false, att[0]->attlen);
  98
  99                 s = (char *) palloc(realSize);
 100                 accum->allocatedMemory += GetMemoryChunkSpace(s);
 101
 102                 memcpy(s, DatumGetPointer(value), realSize);
 103                 res = PointerGetDatum(s);
 104         }
 105         return res;
 106 }
 107
 108 /*
 109  * Find/store one entry from indexed value.
 110  */
 111 static void
 112 ginInsertEntry(BuildAccumulator *accum, ItemPointer heapptr, Datum entry)
 113 {
 114         EntryAccumulator *ea = accum->entries,
 115                            *pea = NULL;
 116         int                     res = 0;
 117         uint32          depth = 1;
 118
 119         while (ea)
 120         {
 121                 res = compareEntries(accum->ginstate, entry, ea->value);
 122                 if (res == 0)
 123                         break;                          /* found */
 124                 else
 125                 {
 126                         pea = ea;
 127                         if (res < 0)
 128                                 ea = ea->left;
 129                         else
 130                                 ea = ea->right;
 131                 }
 132                 depth++;
 133         }
 134
 135         if (depth > accum->maxdepth)
 136                 accum->maxdepth = depth;
 137
 138         if (ea == NULL)
 139         {
 140                 ea = EAAllocate(accum);
 141
 142                 ea->left = ea->right = NULL;
 143                 ea->value = getDatumCopy(accum, entry);
 144                 ea->length = DEF_NPTR;
 145                 ea->number = 1;
 146                 ea->shouldSort = FALSE;
 147                 ea->list = (ItemPointerData *) palloc(sizeof(ItemPointerData) * DEF_NPTR);
 148                 accum->allocatedMemory += GetMemoryChunkSpace(ea->list);
 149                 ea->list[0] = *heapptr;
 150
 151                 if (pea == NULL)
 152                         accum->entries = ea;
 153                 else
 154                 {
 155                         Assert(res != 0);
 156                         if (res < 0)
 157                                 pea->left = ea;
 158                         else
 159                                 pea->right = ea;
 160                 }
 161         }
 162         else
 163                 ginInsertData(accum, ea, heapptr);
 164 }
 165
 166 /*
 167  * insert middle of left part the middle of right one,
 168  * then calls itself for each parts
 169  */
 170 static void
 171 ginChooseElem(BuildAccumulator *accum, ItemPointer heapptr, Datum *entries, uint32 nentry,
 172                           uint32 low, uint32 high, uint32 offset)
 173 {
 174         uint32          pos;
 175         uint32          middle = (low + high) >> 1;
 176
 177         pos = (low + middle) >> 1;
 178         if (low != middle && pos >= offset && pos - offset < nentry)
 179                 ginInsertEntry(accum, heapptr, entries[pos - offset]);
 180         pos = (high + middle + 1) >> 1;
 181         if (middle + 1 != high && pos >= offset && pos - offset < nentry)
 182                 ginInsertEntry(accum, heapptr, entries[pos - offset]);
 183
 184         if (low != middle)
 185                 ginChooseElem(accum, heapptr, entries, nentry, low, middle, offset);
 186         if (high != middle + 1)
 187                 ginChooseElem(accum, heapptr, entries, nentry, middle + 1, high, offset);
 188 }
 189
 190 /*
 191  * Insert one heap pointer. Suppose entries is sorted.
 192  * Insertion order tries to get binary tree balanced: first insert middle value,
 193  * next middle on left part and middle of right part.
 194  */
 195 void
 196 ginInsertRecordBA(BuildAccumulator *accum, ItemPointer heapptr, Datum *entries, int32 nentry)
 197 {
 198         uint32          i,
 199                                 nbit = 0,
 200                                 offset;
 201
 202         if (nentry <= 0)
 203                 return;
 204
 205         i = nentry - 1;
 206         for (; i > 0; i >>= 1)
 207                 nbit++;
 208
 209         nbit = 1 << nbit;
 210         offset = (nbit - nentry) / 2;
 211
 212         ginInsertEntry(accum, heapptr, entries[(nbit >> 1) - offset]);
 213         ginChooseElem(accum, heapptr, entries, nentry, 0, nbit, offset);
 214 }
 215
 216 static int
 217 qsortCompareItemPointers(const void *a, const void *b)
 218 {
 219         int                     res = compareItemPointers((ItemPointer) a, (ItemPointer) b);
 220
 221         Assert(res != 0);
 222         return res;
 223 }
 224
 225 /*
 226  * walk on binary tree and returns ordered nodes
 227  */
 228 static EntryAccumulator *
 229 walkTree(BuildAccumulator *accum)
 230 {
 231         EntryAccumulator *entry = accum->stack[accum->stackpos];
 232
 233         if (entry->list != NULL)
 234         {
 235                 /* return entry itself: we already was at left sublink */
 236                 return entry;
 237         }
 238         else if (entry->right && entry->right != accum->stack[accum->stackpos + 1])
 239         {
 240                 /* go on right sublink */
 241                 accum->stackpos++;
 242                 entry = entry->right;
 243
 244                 /* find most-left value */
 245                 for (;;)
 246                 {
 247                         accum->stack[accum->stackpos] = entry;
 248                         if (entry->left)
 249                         {
 250                                 accum->stackpos++;
 251                                 entry = entry->left;
 252                         }
 253                         else
 254                                 break;
 255                 }
 256         }
 257         else
 258         {
 259                 /* we already return all left subtree, itself and  right subtree */
 260                 if (accum->stackpos == 0)
 261                         return 0;
 262                 accum->stackpos--;
 263                 return walkTree(accum);
 264         }
 265
 266         return entry;
 267 }
 268
 269 ItemPointerData *
 270 ginGetEntry(BuildAccumulator *accum, Datum *value, uint32 *n)
 271 {
 272         EntryAccumulator *entry;
 273         ItemPointerData *list;
 274
 275         if (accum->stack == NULL)
 276         {
 277                 /* first call */
 278                 accum->stack = palloc0(sizeof(EntryAccumulator *) * (accum->maxdepth + 1));
 279                 accum->allocatedMemory += GetMemoryChunkSpace(accum->stack);
 280                 entry = accum->entries;
 281
 282                 if (entry == NULL)
 283                         return NULL;
 284
 285                 /* find most-left value */
 286                 for (;;)
 287                 {
 288                         accum->stack[accum->stackpos] = entry;
 289                         if (entry->left)
 290                         {
 291                                 accum->stackpos++;
 292                                 entry = entry->left;
 293                         }
 294                         else
 295                                 break;
 296                 }
 297         }
 298         else
 299         {
 300                 accum->allocatedMemory -= GetMemoryChunkSpace(accum->stack[accum->stackpos]->list);
 301                 pfree(accum->stack[accum->stackpos]->list);
 302                 accum->stack[accum->stackpos]->list = NULL;
 303                 entry = walkTree(accum);
 304         }
 305
 306         if (entry == NULL)
 307                 return NULL;
 308
 309         *n = entry->number;
 310         *value = entry->value;
 311         list = entry->list;
 312
 313         Assert(list != NULL);
 314
 315         if (entry->shouldSort && entry->number > 1)
 316                 qsort(list, *n, sizeof(ItemPointerData), qsortCompareItemPointers);
 317
 318         return list;
 319 }