KdbplusForMortals/splayed tables

From Kx Wiki
Jump to: navigation, search

Contents

1.2 Splayed Tables

1.2.0 Overview

Recall that a table is a named collection of column lists constructed as a flipped column dictionary. For moderately-sized tables—meaning all column lists fit into available memory simultaneously—operations on tables are performed column-wise in memory. Operations on a q table are vector operations on entire column lists, in contrast to SQL where operations apply to individual fields within rows.

When a table will not fit into memory as a single entity, it is possible to store each column in a separate file and have kdb+ map the column files into memory. We call a table stored in such a fashion splayed since it is split apart on disk.

When you point q at a splayed table directory, it maps the columns. Mapped columns are loaded only on demand and are reference counted for table operations (actual memory management is done by the OS). Tables with many columns are particularly suitable for splaying, as most queries refer to a limited set of columns and only those columns need to be loaded.

1.2.0.1 Splayed table Layout

A splayed table directory usually resides immediately beneath the root of the kdb+ database. The splayed table directory name is the table name when the table is mapped. The constituents of the column dictionary are represented in the directory as follows. Each column list is an eponymous q data file—i.e., the file name is the column name. The column dictionary domain (i.e., the symbol list containing column names) is in the hidden file .d; this allows q to maintain column order.

/root
 /tablename			<- splayed table directory
   .d				<- file with column names
   column1name			<- column data file
   column2name			<- column data file
   …

Big Picture (1): We think of a splayed table as a one-dimensional persisted form since it is cut vertically by splitting along columns.

column1 column2 column3
table

Here each ▪ represents a column list as an opaque entity.

1.2.0.2 Limitations of Splaying

(1) For a table to be splayed, every column must be either a simple list or a list of simple lists of uniform type. We shall call the latter a compound list. The function meta displays the type of a simple column as a lower case type char and that of a compound column as an upper case type char.

    meta ([] csimp:1 2 3)
c    | t f a
-----| -----
csimp| i

    meta ([] ccomp:(1 2 3;10 20;100))
c    | t f a
-----| -----
ccomp| I

(2) A table with symbol columns can be splayed only if the symbols are enumerated.

(3) Keyed tables can not be splayed. To achieve the functionality of foreign keys in splayed tables, see §1.2.8.

1.2.1 Splaying a Table

We use set to splay a simple example (no symbol columns) into a fresh directory /db.

    `:/db/t/ set ([] ti:09:30:00 09:31:00; p:101.5 33.5)
`:/db/t/

Observe the trailing / in the file handle, which tells set to splay the table rather than to serialize it. Listing /db shows directory t. Listing t displays the column files p and ti, as well as the hidden file .d.

    /db
      /t
        .d
        ti
        p

Reading the constituent serialized data files back into q using get demonstrates that they are simply the persisted q lists comprising the original column dictionary.

    get `:/db/t/.d
`ti`p
    get `:/db/t/ti
09:30:00 09:31:00
    get `:/db/t/p
101.5 33.5

Observe that a table can also be splayed manually by writing out its constituents to disk in the proper form. This is what set does when it sees a trailing / in the file handle.

    `:/db/tm/.d set `ti`p
`:/db/t/.d
    `:/db/tm/ti set 09:30:00 09:31:00
`:/db/t/ti
    `:/db/tm/p set 101.5 33.5
`:/db/t/p

Indeed, q recognizes our homegrown splayed table.

    get `:/db/tm/
ti       p
--------------
09:30:00 101.5
09:31:00 33.5

1.2.2 Working with Splayed Tables

However a splayed table was created, you can map it into the workspace using \l, which associates a variable with the column dictionary residing in the specified directory.

Note: The process of mapping a splayed (or partitioned) table into memory is commonly called “loading” the table, even though the columnar data is not loaded into the workspace at the time of the command.

We begin by mapping the simple splayed table of the previous section. Observe that a variable t apparently containing the table data has been created.

    \l /db
    t
ti       p
--------------
09:30:00 101.5
09:31:00 33.5

Important: Exercise caution when performing any operation on t that would require loading the entire table into memory. For example, the following query that selects all rows and columns from the table and assigns the result will result in the entire table being loaded into memory. (Without the where phrase the table will simply be reference counted.)

    tmem:select from t where 1b

The illusion that the variable t contains the entire table’s data is convincing. We can retrieve information about, and data from, the mapped t as if it were a table in the workspace.

    count t
2
    cols t
`ti`p
    meta t
c | t f a
--| -----
ti| v
p | f

    select p from t where ti=09:30:00
p
-----
101.5

    `time xcol t
time     p
-------------
09:30:00 101.5
09:31:00 33.5

You can perform many fundamental table operations on splayed tables. For example, you can extract rows using indexing; you can use an int or a long. As of this writing (Jul 2010) the number of rows in a splayed table cannot exceed 2 billion (decimal).

    t[0]
ti| 09:30:00
p | 101.5

    t[1j]
ti| 09:31:00
p | 33.5

Observe that you can not extract columns with . notation but you can extract a column’s list with generalized indexing.

    t.ti
'ti
    t[;`ti]
09:30:00 09:31:00
    t`ti
09:30:00 09:31:00

1.2.3 Modifying a Mapped Table in Memory

When working with a mapped splayed table, bear in mind that the memory mapping is one directional. Operations performed on mapped data are not reflected in the persisted image. Some operations that attempt to modify a splayed table by name simply fail. Other operations appear to succeed, but the change is local to the workspace. This is probably not what you want and can lead to confusion or errors.

Continuing with our simple example, insert does not work against the mapped table.

    `t insert (10:00:00;42.0)
'splay

On the other hand, upsert apparently succeeds.

    `t upsert (10:00:00; 42.0)
`t
    t
ti       p
--------------
09:30:00 101.5
09:31:00 33.5
10:00:00 42

In fact, the change is not reflected in the persisted table.

    \l /db
    t
ti       p
--------------
09:30:00 101.5
09:31:00 33.5

Similarly, update with a reference by name also apparently succeeds, but again the change is not persisted.

    update p:100.0 from `t where ti=09:30:00
`t
    \l /db
    t
ti       p
--------------
09:30:00 101.5
09:31:00 33.5

1.2.4 Built-in Operations on the Persisted Splayed Table

In order to modify the persisted image of a splayed table, you can use its file handle.

Important: As of this writing (Jul 2010), the table operations available against the file handle of a splayed table are: upsert, xasc, `▪# (apply an attribute) and re-enumerate a symbol column.

1.2.4.1 Appending Records

To append a record (or records) to the persisted image of a splayed table, use its file handle with upsert or the equivalent functional form of ., as you prefer. Behind the scenes, q appends the “field” values to the corresponding column files.

We begin by recreating our previous simple example. We perform a single-record upsert and then a two-record insertion—recall q bulk inserts column lists rather than row lists. Observe that it is not necessary to reload the table in order to reflect the changes made on disk once the table has been mapped into memory.

    `:/db/t/ set ([] ti:09:30:00 09:31:00; p:101.5 33.5)
`:/db/t/
    \l /db
    t
ti       p
--------------
09:30:00 101.5
09:31:00 33.5

    `:/db/t/ upsert (10:00:00;42.0)
`:/data/db/t/
    .[`:/db/t/;();,;(10:00:01 19:00:02;43.0 40.0)]
`:/db/t/
    t
ti       p
--------------
09:30:00 101.5
09:31:00 33.5
10:00:00 42
10:00:01 43
10:00:02 40

1.2.4.2 Sorting and Applying Attributes

Next, we sort the table on disk and apply the parted attribute. This is commonly done for tick data.

    `p xasc `:/db/t
`:/db/t
    t
ti       p
--------------
09:31:00 33.5
10:00:00 42
10:00:02 43
09:30:00 101.5

    @[`:/db/t;`p;`p#]
's
    meta t
c | t f a
--| -----
ti| v
p | f   p

1.2.5 Manual Operations on Splayed Table Files

You can perform operations on the persisted image of a splayed table by directly manipulating its constituent files. In this and the following examples that manipulate the file system components, it is usually necessary to reload t to see the changes. The exception is when you make only internal changes to the data files.

1.2.5.1 Column Update

We can perform column manipulations via the file handle using functional @. For example, we change one field in column p.

    `:/db/t/ set ([] ti:09:30:00 09:30:01 09:30:02; p:33 33.5 33.2)
`:/db/t/

    `:/db/t/p set @[get `:/db/t/p;1;:;42.]
`:/db/t/p

    \l /db
    t
ti       p
-------------
09:30:00 33
09:30:01 42
09:30:02 33.2

1.2.5.2 Reordering Columns on Disk

Recreating the previous example, we simulate xcols by reordering the names in the .d file, effectively reordering the columns in the table. It is necessary to reload to see the change.

    `:/db/t/ set ([] ti:09:30:00 09:30:01 09:30:02; p:33 33.5 33.2)
`:/db/t/

    `:/db/t/.d set `p`ti
`:/db/t/.d

    \l /db/t
`t

    t
p    ti
-------------
33   09:30:00
33.5 09:30:01
33.2 09:30:02

1.2.5.3 Sorting by a Column on Disk

A manual descending sort by the column ti is slightly more interesting. It is necessary to reload t to see this change.

    `:/db/t/ set ([] ti:09:30:00 09:30:01 09:30:02; p:33 33.5 33.2)
`:/db/t/

    \l /db/t
`t

    I:idesc t[`ti]
    {@[`:/db/t;x;:;t[I;x]]} each cols t
`:/db/t`:/db/t

    \l /db/t
`t
    t
ti       p
-------------
09:30:02 33.2
09:30:01 33.5
09:30:00 33

Note: The above operation is not atomic. Should the q session die before it completes, the table will be scrambled. Also, other sessions that attempt to map this table during the operation will see unpredictable results.

1.2.5.4 Adding a Column on Disk

We manually add a column v to the splayed table by writing the column value list and updating the .d file to include its name. It is necessary to reload to see this change.

    `:/db/t/ set ([] ti:09:30:00 09:30:01 09:30:02; p:33 33.5 33.2)
`:/db/t/

    n:count get `:/db/t/ti
    @[`:/db/t;`v;:;n#0]
`:/db/t
    @[`:/db/t;`.d;,;`v]
`:/db/t
    \l /db/t
`t
    t
ti       p    v
---------------
09:30:00 33   0
09:30:01 33.5 0
09:30:02 33.2 0

Note: When adding a column, you must ensure that it has the correct length. You cannot provide an atom and expect kdb+ to extend it, as is permissable in table definition syntax. You can get the correct length by counting the records in the table if it is mapped or by counting the items in any existing column on disk using count get `:/db/t/ti.

1.2.5.5 Deleting a Column on Disk

We can effectively delete the column we just added by removing its name from the .d file.

    `:/db/t/.d set `ti`p
`:/data/db/t/.d

    \l /db
    t
ti       p
--------------
09:30:00 33
09:30:01 33.5
09:30:02 33.2

While the column list is no longer associated with the splayed table and is ignored by kdb+, good practice dictates removal of the orphaned file. This can be done with hdel.

    hdel `:/db/t/v
`:/db/t/v

1.2.6 Splayed Tables with Symbols

You must enumerate all symbols in order to splay a table having symbol column(s). Kdb+ insists on this to avoid scanning variable length symbol list items, which would be prohibitively slow for large columns.

Note: By convention, all symbols are enumerated over a single domain named sym, although kdb+ does not require this. The .Q utilities follow this convention.

1.2.6.1 Splaying Enumerated Symbol Columns

Recall that the projected conditional enumeration operation `sym? returns an enumerated value after conditionally appending the symbol to the enumeration domain sym (i.e., if it is not already in the domain). In the following example, observe that we specify the enumeration domain as a file on disk, which causes the file to be created as an empty symbol list if it does not already exist. We assume a fresh /db.

    `:/db/t1/ set ([]s:`:/db/sym?`a`b`a; p:101 102 103f)
`:/db/t1/

    \\
$ q
KDB+ …

    \l /db
    t1
s p
-----
a 101
b 102
a 103

Note: If you do not ensure that the sym file is written out (either manually or by using a .Q utility), the enumeration domain will not exist in the workspace when the table is subsequently mapped. Because q cannot resolve the enumeration, symbol column(s) in the original table(s) will become int columns in the mapped table. This int represents the unresolvable index into the enumeration domain.

To demonstrate this, we repeat the previous example, but instead of enumerating over a sym file on disk, we use an enumeration domain in the workspace. We “forget” to write out sym.

    sym:`()
    `:/temp/t/ set ([]s:`sym?`a`b`a; p:101 102 103f)
`:/temp/t/
    \\
$ q
    \l /temp/t
`t
    t
s p
-----
0 101
1 102
0 103

1.2.6.2 Merging Saved sym Domains

Here we demonstrate how to use functional @ to re-enumerate a symbol column s over a revised symbol domain file. We perform the operation without mapping the table into memory.

Note: If you are doing this on real data, make sure that you backup the existing sym files for safekeeping. Accidents happen!

    `:/db/sym set sym:`d`a`b`c
`:/db/u1
    @[`:/db/t1;`s;`sym$]
`:/db/t1

    \l /db
    sym
`d`a`b`c
    t1[`s]
`u1$`a`b`a

Now suppose we have two splayed tables in /db with separate enumeration domains.

    `:/db/t1/ set ([] s:`:/db/sym?`a`b`c; v:1 2 3)
`:/db/t1/
    `:/db/t2/ set ([] s2:`:/db/sym2?`c`x`y; v2:3.3 4.4 5.5)
`:/db/t2/

How do we make the tables share a common symbol domain? First, we conditionally append sym2 to sym by using the side effect of sym?.

    `:/db/sym?value `:/db/sym2
`sym$`c`x`y
    get `:/db/sym/           / verify that it worked
`a`b`c`x`y

Now we re-enumerate the symbol columns of t2, using a general expression that works for any table. Finally, we use -3! to reveal the underlying form of the table data and demonstrate that t2 indeed uses the merged sym domain.

    \l /db
    scols:exec c from meta t2 where t="s"
    @[`:/db/t2;scols;`:/db/sym?]
`:/db/t2

    -3!select from t2
"+`s2`v2!(`sym$`c`x`y;3.3 4.4 5.5)”

Note that it is not necessary to modify t1 since the conditional append to sym does not invalidate any existing enumerations over sym.

1.2.7 Splayed Tables with Compound Columns

You can splay a table with compound column(s), but there is a tradeoff. Since scanning a large general list would significantly degrade performance, kdb+ creates an index file for each compound column. The index turns accessing an arbitrary item in the compound list into two direct accesses. Thus, you trade space (having two files in place of one) for speed (one-level indirect access instead of scanning).

1.2.7.1 Compound Column Example

We splay a table having a compound int column.

    / note required enlist for singleton row
    `:/temp/t/ set ([] c:(1 2;3 4 5;enlist 6))
`:/temp/t/

Inspect the contents of the /t subdirectory of /db:

    /t
      .d
      c
      c#

Observe that there are two files associated with the compound column — c and c#.

Advanced: The file c# holds the flattened values of the c column. The file c holds (long) values representing the count of each (simple) list in the c column list. You can see these by applying read1 to the files and inspecting the resulting byte lists (remember to read the hexadecimal left-to-right).

    read1 hsym `$"/temp/t/c#"
0x010000000200000003000000040000000500000006000000

    read1 `:/temp/t/c
0xff2000000000000053000000030000000200000000000000050000000000000006000000000..

A moment’s thought shows that reconstructing the compound column from the information in the two files could be done with something like the following q snippet:

    L:(1 2;3 4 5;enlist 6)
    cs:raze L
    c:count each L

    L~(sums -1_0,c) cut cs
1b

1.2.7.2 String Columns

A common compound column type is a column of strings—i.e., a list of list of char. We splay a table with such a column.

    `:/db/tstr/ set ([] n:("abc";enlist "c";"def"))
`:/db/tstr/
    \l /db/tstr
`tstr
    select from tstr
n
-----
"abc"
,"c"
"def"

Be mindful (especially those of you coming directly from SQL) when using string columns that strings are not first class entities in q. For example, you cannot use = to match a string due to its atomic nature.

    select from tstr where n="abc"
'type
=
("abc";,"c";"def")
"abc"

Nor will simple ~ work. While it does not generate an error, it compares the given string to the entire column and hence returns no rows. An adverb does the trick.

    select from tstr where n~"abc"
n
-
    select from tstr where n~\:"abc"
n
-----
"abc"

Teenagers the world over would agree that it is easier (and faster) to use like.

    select from tstr where n like "abc"
n
-----
"abc"

1.2.7.3 Symbols vs. Strings

Many novice kdb+ users are perplexed about whether to use symbols or strings for text data. The answer is not clear-cut. On the plus side for symbols, enumerated symbols are faster and can be matched with =. The downside is that making all text data into symbols will eventually pollute the (memory-resident) sym file, especially if you have text fields that are infrequently referenced or that change often. Reorganizing the sym file of a large production kdb+ database is not for the faint of heart.

A good rule is: fields that are invariant (e.g., keys), are drawn from a controlled domain, or will primarily need equality testing are excellent candidates for symbols. Examples are: exchange symbols, RICs, etc. Fields that need selection on content or are rarely referenced are good candidates for string fields—e.g., comments, audit notes.

There is a grey area encompassing fields such as an alphanumeric order ID. Such fields are unique and invariant but the domain is not limited, as there will be a significant number of new variants each day. Further, the values may be recycled over time. The best advice is to consider your use cases carefully, paying attention to the likely long-term disposition of the ID values.

If in doubt, be conservative initially and use strings. It is relatively easy to convert a string column to symbols later but considerably more difficult to remove symbols from the sym list.

1.2.8 Links between Splayed Tables

We show how to create a link column between mapped splayed tables. To make the example interesting, we create the link between columns of enumerated symbols. First, we create and map the tables:

    `:/db/t1/ set ([] c1:`:/db/sym?`c`b`a; c2: 10 20 30)
`:/db/t1/
    `:/db/t2/ set ([] c3:`:/db/sym?`a`b`a`c; c4: 1. 2. 3. 4.)
`:/db/t2/
    \l /db

After creating the link column, updating the .d file and reloading, the link is functional.

    `:/db/t2/t1link set `t1!t1[`c1]?t2[`c3]
`:/db/t2/t1link
    .[`:/db/t2/.d;();,;`t1link]
`:/db/t2/.d
    \l /db
    select c3,c4,t1link.c2 from t2
c3 c4 c2
--------
a  1  30
b  2  20
a  3  30
c  4  10

In order to create a link column between splayed tables that are not mapped (i.e., on disk), read the appropriate column files and proceed as before. In a fresh /db:

    `:/db/t1/ set ([] c1:`:/db/sym?`c`b`a; c2: 10 20 30)
`:/db/t1/
    `:/db/t2/ set ([] c3:`:/db/sym?`a`b`a`c; c4: 1. 2. 3. 4.)
`:/data/db/t2/

    `:/db/t2/t1link set `t1!(get `:/db/t1/c1)?get `:/db/t2/c3
    .[`:/db/t2/.d;();,;`t1link]
`:/db/t2/.d

1.2.9 Query Execution on Splayed Tables (Advanced)

We have already noted that when kdb+ executes a query against a splayed table, it loads into memory only the columns that the query references. Moreover, kdb+ only accesses the items of the target columns it actually needs.

Recall that in q, functional @ can apply a function along a sub-domain of a list. For example, 42 is added to every tenth item of L:

    L:til 1000000
    @[L;10*til 100000;+;42]
42 1 2 3 4 5 6 7 8 9 52 11 12 13 14 15 16 17 18 19 62 21 22 23 24...

The where function allows us to use a boolean vector having the same length as L as a mask for applying the function. Continuing our previous example, the following adds 42 to every eleventh or seventeenth item.

    B:(or/)0=(til count L)mod/:11 17
    @[L;where B;+;42]
42 1 2 3 4 5 6 7 8 9 10 53 12 13 14 15 16 59 18 19 20 21 64 23 24...

The where phrase in a query is a constraint that determines which rows are selected. More specifically, it is a compound predicate whose result is a boolean vector indicating whether each row passes or fails. Kdb+ uses this predicate vector to target a sub-domain of column items for its query operations, in complete analogy to the above example with the where function. When the mask picks out a small sub-list, this is a large win versus performing the operation on the entire list.

We can see this explicitly by substituting a boolean vector in the where phrase.

    t:([] c1:`a`b`c; c2:1 2 3)
    select from t where 101b
c1 c2
-----
a  1
c  3

Important: In a partitioned or segmented table, ensure that the first sub-phrase of the where reads only the partitions that are necessary.


Prev: 1.1 Loading Tables from Stored Data Next: 1.3 Partitioned Tables

Table of Contents

Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox