[SOLVED] CS cache data structure scheme Tuple Representation

Tuple Representation

>>
Tuple Representation

Tuples

Records vs Tuples

Converting Records to Tuples

Operations on Records

Operations on Tuples

Fixed-length Records

Variable-length Records

Data Types

Field Descriptors

COMP9315 21T1 Tuple Representation [0/13]

>>
Tuples

Each page contains a collection of tuples

What do tuples contain? How are they structured internally?

COMP9315 21T1 Tuple Representation [1/13]

<< >>
Records vs Tuples

A table is defined by a schema, e.g.

create table Employee (
id integer primary key,
name varchar(20) not null,
jobvarchar(10),
dept smallint references Dept(id)
);

where a schema is a collection of attributes (name,type,constraints)

Reminder: schema information (meta-data) is also stored, in the DB catalog

COMP9315 21T1 Tuple Representation [2/13]

<< >>
Records vs Tuples (cont)

Tuple = collection of attribute values based on a schema, e.g.

Record = sequence of bytes, containing data for one tuple, e.g.

Bytes need to be interpreted relative to schema to get tuple

COMP9315 21T1 Tuple Representation [3/13]

<< >>
Converting Records to Tuples

A Record is an array of bytes (byte[])

representing the data values from a typed Tuple

stored on disk (persistent) or in a memory buffer

A Tuple is a collection of named,typed values (cf. C struct)
to manipulate the values, need an interpretable structure

stored in working memory, and temporary

COMP9315 21T1 Tuple Representation [4/13]

<< >>
Converting Records to Tuples (cont)

Information on how to interpret bytes in a record

may be contained in schema data in DBMS catalog

may be stored in the page directory

may be stored in the record (in a record header)

may be stored partly in the record and partly in the schema

For variable-length records, some formatting info
must be stored in the record or in the page directory

at the least, need to know how many bytes in each varlen value

COMP9315 21T1 Tuple Representation [5/13]

<< >>
Operations on Records

Common operation on records access record via RecordId:

Record get_record(Relation rel, RecordId rid) {
(pid,tid) = rid;
Page buf = get_page(rel, pid);
return get_bytes(rel, buf, tid);
}

Cannot use a Record directly; need a Tuple:

Relation rel = // relation schema
Record rec = get_record(rel, rid)
Tuple t = mkTuple(rel, rec)

Once we have a Tuple, we can access individual attributes/fields

COMP9315 21T1 Tuple Representation [6/13]

<< >>
Operations on Tuples

Once we have a record, we need to interpret it as a tuple

Tuple t = mkTuple(rel, rec)

convert record to tuple data structure for relation rel

Once we have a tuple, we want to examines its contents

Typ getTypField(Tuple t, int i)

extract the ith field from a Tuple as a value of type Typ

E.g. int x = getIntField(t,1), char *s = getStrField(t,2)

COMP9315 21T1 Tuple Representation [7/13]

<< >>
Fixed-length Records

A possible encoding scheme for fixed-length records:

record format (length + offsets) stored in catalog

data values stored in fixed-size slots in data pages

Since record format is frequently used at query time, cache in memory.

COMP9315 21T1 Tuple Representation [8/13]

<< >>
Variable-length Records

Possible encoding schemes for variable-length records:

Prefix each field by length

Terminate fields by delimiter

Array of offsets

COMP9315 21T1 Tuple Representation [9/13]

<< >>
Data Types

DBMSs typically define a fixed set of base types, e.g.

DATE, FLOAT, INTEGER, NUMBER(n), VARCHAR(n),

This determines implementation-level data types for field values:

DATEtime_t
FLOATfloat,double
INTEGERint,long
NUMBER(n)int[] (?)
VARCHAR(n)char[]

PostgreSQL allows new base types to be added

COMP9315 21T1 Tuple Representation [10/13]

<< >>
Field Descriptors

A Tuple could be implemented as

a list of field descriptors for a record instance

(where a FieldDesc gives (offset,length,type) information)

along with a reference to the Record data

typedef struct {
ushortnfields; // number of fields/attrs
ushortdata_off;// offset in struct for data
FieldDesc fields[];// field descriptions
Recorddata;// pointer to record in buffer
} Tuple;

Fields are derived from relation descriptor + record instance data.

COMP9315 21T1 Tuple Representation [11/13]

<< >>
Field Descriptors (cont)

Tuple data could be

a pointer to bytes stored elsewhere in memory

COMP9315 21T1 Tuple Representation [12/13]

<< Field Descriptors (cont)Or, tuple data could be … appended to Tuple struct (used widely in PostgreSQL)COMP9315 21T1 Tuple Representation [13/13]Produced: 27 Feb 2021