SQLite Forum

Index organized tables
Login

Index organized tables

(1) By Ilya (walrus) on 2021-03-01 10:26:27 [link] [source]

Oracle database supports so called index organized tables (IOT) where all data is stored in index B*-tree effectively eliminating duplication of data. It also improves performance of queries which use primary key.

I wonder whether SQLite supports something similar?

(2) By Larry Brasfield (larrybr) on 2021-03-01 11:08:02 in reply to 1 [link] [source]

It's called WITHOUT ROWID.

(3) By mlin (dnamlin) on 2021-03-01 22:25:54 in reply to 2 [link] [source]

Any roadmap for index dedup? (Another nice space-saver for certain common cases!)

(4) By Ryan Smith (cuz) on 2021-03-02 09:15:53 in reply to 1 [link] [source]

That (IOT) is the default mode for SQLite - in fact SQLite doesn't have any alternative way to organize a table.

Technically, in SQLite every table is itself a BTREE Index with data, much like a "Covering Index".
The Index key along which the typical table is structured, is called the RowID, and a good way to refer to such an SQLite table is: "rowid-table".

All access to a table is via lookups of this RowID Key - even if the table has no declared key of any sort in its CREATE TABLE schema. This allows some funky things in SQLite that you do not see in other DBs, for instance:

  • a declared primary Key in SQLite CAN contain NULLs (because it is not typically used as the real Table lookup Key - that is still done via the rowid),
  • a Table without any defined Keys/Indexes can still have very fast lookups via the rowid.

There is an optimization, as Larry mentioned, whereby you can use another primary Key as this table lookup key, by specifying it as the explicit PRIMARY KEY and then declaring the table as "WITHOUT ROWID". (We can refer to that as a non-rowid-table). The advantages here are:

  • The table BTREE Key is organized along the given primary key order,
  • The space that the rowid portion of the table would have taken up is freed, and
  • Lookups via the Primary Key locates the row directly.
    Disadvantage: A straight integer lookup in a Rowid BTREE is marginally faster than a text key. Oh, and it's a right pain for DB management applications which were used to manage everything via the row-id! :)

A normal rowid-table most closely resembles an Oracle IOT based on an integer primary key, and the non-rowid-table optimization above most closely resembles an Oracle IOT table based on any other type of Key.

As an aside: The table lookup BTREE key in SQLite (the key used for table lookups - i.e. the rowid in rowid-tables, or the PK in non-rowid-tables) has some interesting special rules:

  • It cannot contain NULLs - unlike other "normal" PRIMARY KEYs in SQLite.
  • You can refer to the RowID of any rowid-table by the named field "oid", "rowid" or "rowid", without it being declared in the schema.
  • You can explicitly declare a field that is a reference/alias to the rowid of a rowid-table by declaring the column using this exact phrase: "{column} INTEGER PRIMARY KEY, "
  • A rowid table without any explicit column that references/aliases its rowid, can actually rearrange the row-ids if need be, during a vacuum for instance - so if you intend to depend on the rowid for future lookups using your own stored values, best to properly reference/alias it as shown above.

So then, Oracle probably got the IOT idea from SQLite. :)
Actually the IOT optimization is commonly understood by DB designers since long ago, SQLite probably chose it at the start for that reason (or perhaps it was just easier to do - I'm just guessing now).

(5.1) By Ilya (walrus) on 2021-03-11 07:17:19 edited from 5.0 in reply to 1 [source]

Ryan, Larry, thank you much for your valuable comments. I really appreciate it. I've read about WITHOUT ROWID tables before but seems I missed the main point. Thanks again!