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-2009, 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.15 2009/03/24 20:17:10 tgl 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 modified to count
  82  * palloc'd space in accum.
  83  */
  84 static Datum
  85 getDatumCopy(BuildAccumulator *accum, OffsetNumber attnum, Datum value)
  86 {
  87         Form_pg_attribute att = accum->ginstate->origTupdesc->attrs[ attnum - 1 ];
  88         Datum           res;
  89
  90         if (att->attbyval)
  91                 res = value;
  92         else
  93         {
  94                 res = datumCopy(value, false, att->attlen);
  95                 accum->allocatedMemory += GetMemoryChunkSpace(DatumGetPointer(res));
  96         }
  97         return res;
  98 }
  99
 100 /*
 101  * Find/store one entry from indexed value.
 102  */
 103 static void
 104 ginInsertEntry(BuildAccumulator *accum, ItemPointer heapptr, OffsetNumber attnum, Datum entry)
 105 {
 106         EntryAccumulator *ea = accum->entries,
 107                            *pea = NULL;
 108         int                     res = 0;
 109         uint32          depth = 1;
 110
 111         while (ea)
 112         {
 113                 res = compareAttEntries(accum->ginstate, attnum, entry, ea->attnum, ea->value);
 114                 if (res == 0)
 115                         break;                          /* found */
 116                 else
 117                 {
 118                         pea = ea;
 119                         if (res < 0)
 120                                 ea = ea->left;
 121                         else
 122                                 ea = ea->right;
 123                 }
 124                 depth++;
 125         }
 126
 127         if (depth > accum->maxdepth)
 128                 accum->maxdepth = depth;
 129
 130         if (ea == NULL)
 131         {
 132                 ea = EAAllocate(accum);
 133
 134                 ea->left = ea->right = NULL;
 135                 ea->attnum = attnum;
 136                 ea->value = getDatumCopy(accum, attnum, entry);
 137                 ea->length = DEF_NPTR;
 138                 ea->number = 1;
 139                 ea->shouldSort = FALSE;
 140                 ea->list = (ItemPointerData *) palloc(sizeof(ItemPointerData) * DEF_NPTR);
 141                 accum->allocatedMemory += GetMemoryChunkSpace(ea->list);
 142                 ea->list[0] = *heapptr;
 143
 144                 if (pea == NULL)
 145                         accum->entries = ea;
 146                 else
 147                 {
 148                         Assert(res != 0);
 149                         if (res < 0)
 150                                 pea->left = ea;
 151                         else
 152                                 pea->right = ea;
 153                 }
 154         }
 155         else
 156                 ginInsertData(accum, ea, heapptr);
 157 }
 158
 159 /*
 160  * insert middle of left part the middle of right one,
 161  * then calls itself for each parts
 162  */
 163 static void
 164 ginChooseElem(BuildAccumulator *accum, ItemPointer heapptr, OffsetNumber attnum,
 165                                                                                 Datum *entries, uint32 nentry,
 166                           uint32 low, uint32 high, uint32 offset)
 167 {
 168         uint32          pos;
 169         uint32          middle = (low + high) >> 1;
 170
 171         pos = (low + middle) >> 1;
 172         if (low != middle && pos >= offset && pos - offset < nentry)
 173                 ginInsertEntry(accum, heapptr, attnum, entries[pos - offset]);
 174         pos = (high + middle + 1) >> 1;
 175         if (middle + 1 != high && pos >= offset && pos - offset < nentry)
 176                 ginInsertEntry(accum, heapptr, attnum, entries[pos - offset]);
 177
 178         if (low != middle)
 179                 ginChooseElem(accum, heapptr, attnum, entries, nentry, low, middle, offset);
 180         if (high != middle + 1)
 181                 ginChooseElem(accum, heapptr, attnum, entries, nentry, middle + 1, high, offset);
 182 }
 183
 184 /*
 185  * Insert one heap pointer. Suppose entries is sorted.
 186  * Insertion order tries to get binary tree balanced: first insert middle value,
 187  * next middle on left part and middle of right part.
 188  */
 189 void
 190 ginInsertRecordBA(BuildAccumulator *accum, ItemPointer heapptr, OffsetNumber attnum,
 191                                                 Datum *entries, int32 nentry)
 192 {
 193         uint32          i,
 194                                 nbit = 0,
 195                                 offset;
 196
 197         if (nentry <= 0)
 198                 return;
 199
 200         Assert(ItemPointerIsValid(heapptr) && attnum >= FirstOffsetNumber);
 201
 202         i = nentry - 1;
 203         for (; i > 0; i >>= 1)
 204                 nbit++;
 205
 206         nbit = 1 << nbit;
 207         offset = (nbit - nentry) / 2;
 208
 209         ginInsertEntry(accum, heapptr, attnum, entries[(nbit >> 1) - offset]);
 210         ginChooseElem(accum, heapptr, attnum, entries, nentry, 0, nbit, offset);
 211 }
 212
 213 static int
 214 qsortCompareItemPointers(const void *a, const void *b)
 215 {
 216         int                     res = compareItemPointers((ItemPointer) a, (ItemPointer) b);
 217
 218         Assert(res != 0);
 219         return res;
 220 }
 221
 222 /*
 223  * walk on binary tree and returns ordered nodes
 224  */
 225 static EntryAccumulator *
 226 walkTree(BuildAccumulator *accum)
 227 {
 228         EntryAccumulator *entry = accum->stack[accum->stackpos];
 229
 230         if (entry->list != NULL)
 231         {
 232                 /* return entry itself: we already was at left sublink */
 233                 return entry;
 234         }
 235         else if (entry->right && entry->right != accum->stack[accum->stackpos + 1])
 236         {
 237                 /* go on right sublink */
 238                 accum->stackpos++;
 239                 entry = entry->right;
 240
 241                 /* find most-left value */
 242                 for (;;)
 243                 {
 244                         accum->stack[accum->stackpos] = entry;
 245                         if (entry->left)
 246                         {
 247                                 accum->stackpos++;
 248                                 entry = entry->left;
 249                         }
 250                         else
 251                                 break;
 252                 }
 253         }
 254         else
 255         {
 256                 /* we already return all left subtree, itself and  right subtree */
 257                 if (accum->stackpos == 0)
 258                         return 0;
 259                 accum->stackpos--;
 260                 return walkTree(accum);
 261         }
 262
 263         return entry;
 264 }
 265
 266 ItemPointerData *
 267 ginGetEntry(BuildAccumulator *accum, OffsetNumber *attnum, Datum *value, uint32 *n)
 268 {
 269         EntryAccumulator *entry;
 270         ItemPointerData *list;
 271
 272         if (accum->stack == NULL)
 273         {
 274                 /* first call */
 275                 accum->stack = palloc0(sizeof(EntryAccumulator *) * (accum->maxdepth + 1));
 276                 accum->allocatedMemory += GetMemoryChunkSpace(accum->stack);
 277                 entry = accum->entries;
 278
 279                 if (entry == NULL)
 280                         return NULL;
 281
 282                 /* find most-left value */
 283                 for (;;)
 284                 {
 285                         accum->stack[accum->stackpos] = entry;
 286                         if (entry->left)
 287                         {
 288                                 accum->stackpos++;
 289                                 entry = entry->left;
 290                         }
 291                         else
 292                                 break;
 293                 }
 294         }
 295         else
 296         {
 297                 accum->allocatedMemory -= GetMemoryChunkSpace(accum->stack[accum->stackpos]->list);
 298                 pfree(accum->stack[accum->stackpos]->list);
 299                 accum->stack[accum->stackpos]->list = NULL;
 300                 entry = walkTree(accum);
 301         }
 302
 303         if (entry == NULL)
 304                 return NULL;
 305
 306         *n = entry->number;
 307         *attnum = entry->attnum;
 308         *value = entry->value;
 309         list = entry->list;
 310
 311         Assert(list != NULL);
 312
 313         if (entry->shouldSort && entry->number > 1)
 314                 qsort(list, *n, sizeof(ItemPointerData), qsortCompareItemPointers);
 315
 316         return list;
 317 }