On Fri, Jan 25, 2013 at 4:21 PM, Jeff <jeffpl...@yahoo.com> wrote: > > > (Using FB 1.5) >
OK, that's scary right there. Firebird 1.5 is ten years old. Newer versions use approximately the same index structures but have lots of bugs fixed, including several important ones in the index code. > > Do inserts in FB benefit from ordered or sequential PK? > Yes. Unlike the databases that the article considers, Firebird stores data and indexes separately - even primary key indexes, so its talk about "shuffling" data is irrelevant. But still there are advantages to inserting keys into an index in ascending (for ascending indexes) or descending (for descending indexes) order. The most efficient way to generate primary keys is with a generator - also called a "sequence" in newer versions. > Please allow me to clarify. I intend to use High/Low for table PKs. With > this approach, it is very possible that PKs will not be in sequential order > as they are inserted into the db. Will this be an issue in FB? > I don't know what High/Low is, so that's hard to answer. Firebird is designed to handle random inserts into indexes with reasonable efficiency, but building indexes sequentially creates a dense index at low insert cost. When creating a new index on an existing table, Firebird reads the table, sorting by they index key and builds the index from the sorted output. Why is that fast? Two reasons, neither of which as to do with the (relatively) low cost of moving index entries in memory. The first is that random index entries tend to land on random pages in the index. Unless you can hold the entire index (and everything else you need) in memory, that means that pages will be written and read multiple times. <rant>One of the key misunderstandings in databases is that an index is a good alternative to a sort because the cost of an index look up is K*n, while the cost of a sort is L*nlog(n). It's rarely noticed that the value of K (the cost of a page read) is huge compared with log(n).</rant> Filling an index page with ordered values and going on to the next page is more efficient that putting one entry on one page, the next on another, and so on, even if all the pages are in memory. The second reason to store rows in the order of their index (i.e. not just sorted, but sorted ascending for ascending, descending for descending) is prefix compression. Firebird drop the first bytes of a key if they match the previous key value. So if you store AAAAAA, AAAAAAB, AAAAAAC, AAAAABA, what goes into the index is AAAAAA, 6B, 6C, 4BA. Prefix compression makes the indexes dense, meaning that you read fewer index pages to get to the data you want. Clearly if you store those rows in reverse order, the first key in is AAAAABA. When you store AAAAAAC, the index contains AAAAAAC and the second key value becomes 5BA. Each subsequent entry requires a change to the next older entry. I based this question on this article: > > http://www.codeproject.com/Articles/388157/GUIDs-as-fast-primary-keys-under-multiple-database > ort/ <http://groups.yahoo.com/group/firebird-support/> > > I've only scanned the article, but if it offers you a reliable way to turn GUIDs into strings (or byte arrays) in ascending order, the algorithm will reduce the size of indexes and make inserts faster. Cheers, Ann [Non-text portions of this message have been removed]
